| dc.description.abstract | This thesis investigates some combinatorial problems arising in quantum physics and model counting. In particular, we develop new graph-theoretic techniques to resolve some open questions from quantum photonics. We also establish limitations on distributed quantum advantage using some existential graph-theoretic constructions. Finally, we address an open problem in weighted model counting through a set-theoretic approach. We elaborate on each of these results.
Quantum Photonic Experiments: Greenberger–Horne–Zeilinger (GHZ) states are quantum states involving at least three entangled particles. They are foundational in quantum information theory, with practical applications in quantum communication and cryptography. Krenn, Gu, and Zeilinger discovered a correspondence between a class of quantum optical experiments that produce GHZ states and edge-weighted, edge-coloured multigraphs called GHZ graphs. A graph parameter called dimension can be defined on such a graph, which is the same as the dimension of the GHZ state generated by the corresponding experiment. Constructing a GHZ graph with a large number of vertices and a high dimension would be a major breakthrough while proving the non-existence of such graphs has implications for quantum resource theory.
Characterizing GHZ Graphs Without Destructive Interference: The absence of destructive interference in these experiments corresponds to the special case of the problem restricted to unweighted graphs. In this case, Bogdanov showed that every matching-covered GHZ graph with more than 4 vertices has a dimension of either 1 or 2. We extend this result by providing a complete structural characterization of GHZ graphs (without destructive interference) of a given dimension (which would be 1 or 2).
Dimension of GHZ Graphs and the CKA Conjecture: Cervera-Lierta, Krenn, and Aspuru-Guzik conjectured that the maximum dimension of an n-vertex GHZ graph is less than n/2. They verified this using SAT solvers for graphs with up to 8 vertices, but nothing was known for larger graphs. We introduce a technique called \emph{local sparsification} of GHZ graphs, using which we give the first analytical upper bound of $n/\sqrt{2}$ on the dimension for simple GHZ graphs.
Structure of GHZ Graphs and the KG Conjecture: Krenn and Gu made a much stronger conjecture: that the dimension of any GHZ graph with more than four vertices is at most two (analogous to Bogdanov's result in the absence of destructive interference). We study the existence of GHZ graphs from the perspective of the KG conjecture and show that the conjecture holds for graphs with vertex connectivity at most two and cubic graphs. We also prove that any minimal counterexample to the conjecture must be 4-vertex-connected. These insights are helpful for automated GHZ graph searches using tools like PyTheus.
Distributed Quantum Advantage: Locally checkable problems are graph problems in which the task is to find a feasible solution subject to local constraints—graph colouring being a well-known example. Recent work on the classical LOCAL model has focused extensively on such problems, leading to a solid understanding of their distributed computational complexity. However, the impact of the quantum variant (quantum-LOCAL) on this landscape remains wide open.
A major open problem is whether any locally checkable graph problem can be solved asymptotically faster in the quantum-LOCAL model compared to the classical randomized LOCAL model. It has been conjectured that no such problem exists. In this work, we provide new evidence supporting this conjecture: we show that c-colouring trees do not admit significant quantum advantage. Specifically, Linial showed that c-colouring trees require time $\Omega(\log_c n)$ in the classical model. We prove that the same lower bound holds in the NS-LOCAL (non-signalling) model by combining our lower bound technique with the graph-theoretic argument of Linial for the classical model.
Weighted Model Counting: (Unweighted) model counting is the classical problem of determining the number of satisfying assignments of a Boolean formula. Weighted model counting generalizes this to computing the weighted sum over satisfying assignments. It has applications in probabilistic reasoning, network reliability, statistical physics, program synthesis, and system verification. A popular approach to solving weighted model counting reduces it to unweighted model counting. This motivates the following natural question: Can one construct a DNF or CNF formula having exactly k solutions using as few terms (or clauses) as possible?
In this work, we prove that one can always construct such a formula using at most $O(\sqrt{\log k} \log \log k)$ terms. Moreover, our constructions are monotone DNFs—i.e., they consist only of variables in positive form. We also show that there exist infinitely many natural numbers n such that any DNF or CNF with exactly k satisfying assignments requires at least $\Omega(\log \log k)$ terms (or clauses). | en_US |
