Das Quanten-Erfüllbarkeitsproblem - Algorithmen und komplexitätstheoretische Schwierigkeit
Zusammenfassung der Projektergebnisse
Background. Constraint satisfaction problems are a foundation stone of theoretical computer science, arising in applications from manufacturing to machine learning to computational logic. The k-SATISFIABILITY (k-SAT) problem, in particular, is the canonical intractable (i.e. NP-complete) problem. Its quantum generalization, the Quantum Satisfiability problem (k-QSAT) is similarly the canonical “quantum NP-hard” problem, asking: Given a set of “local quantum constraints” {Πi } acting on k qubits each, does there exist an n-qubit quantum state |ψ⟩ which simultaneously “satisfies” all constraints? Despite being strongly physically motivated, however, there remain serious gaps in our understanding of the complexity of k-QSAT, which this project aimed to resolve. Most important scientific advances made. We made significant progress in three directions regarding the complexity of QSAT: (1) How hard is QSAT on systems of dimension larger than 2? (2) Are there QSAT instances which are guaranteed to have a “nice” solution |ψ⟩, and yet finding |ψ⟩ is provably intractable? (3) Is there an efficient parameterized algorithm for QSAT, whose bottleneck is a graph-theoretic parameter in the hypergraph defining the instance? Our results are as follows. 1. High dimensional QSAT) While 3-QSAT is intractable, 2-QSAT on qubits is efficiently solvable. What happens, however, when 2-QSAT acts on systems of dimension higher than 2? We show for the first time that 2-QSAT on qubits can become be intractable. Formally, we show that 2-QSAT with constraints acting on pairs of qubits and 5-dimensional systems is “quantum NP”-complete. In fact, we show this hardness is preserved even when all constraints are severely restricted by being on a 1D line — then, systems of alternating dimension just 3 and a larger constant d ≫ 3 suffice for intractability. This significantly improves on the best previous 1D results, which required all systems to have dimension at least 11. 2. Intractability of finding solutions) The complexity class “Total Function NP (TFNP)” is used to show that, even if a problem is guaranteed to have a solution, finding said solution is sometimes intractable. This project makes a surprising discovery — the first problem in quantum complexity theory with this “TFNP”-like property. Specifically, it was known that k-QSAT with a “System of Distinct Representatives (SDR)” on qubits always has a “nice” solution. We first used new tools from algebraic geometry to define a novel framework based on Weighted SDRs (WSDRs), via which we showed that even high-dimesional QSAT with SDR always has a solution. Then, we defined the first “quantum-inspired” subclass of TFNP, denoted “Multihomogeneous Systems (MHS)”, and proved that QSAT with SDR is MHS-complete, yielding the first formal evidence of its intractiblity. This is exciting for three reasons: (1) TFNP subclasses are few and far between. (2) MHS is the first TFNP subclass based on algebraic geometry. (3) Our MHS-complete problem, QSAT with SDR, is strikingly hard only in the quantum setting (i.e. classical SAT with SDR is easy!). Thus, we obtain an intriguing separation between classical and quantum satisfiability. 3. Prospects for parameterized algorithms) In previous work, we gave the first candidate parameterized algorithm for QSAT, albeit with limitations. This project successfully lifts some of these restrictions, and characterizes the complexity of computing the required inputs to the algorithm. First, we extend the algorithm to “non-generic” instances of QSAT, meaning the type of constraints allowed is no longer restricted. Second, the algorithm requires as input the specification of a set of qubits which form the “hard foundation” of the instance. We show both NP-hardness of approximation and approximation algorithms for computing such “minimum size foundations”. We also give an efficient exact algorithm in a key setting, resolving an open question.
Projektbezogene Publikationen (Auswahl)
-
Guest Column: The 7 faces of quantum NP. ACM SIGACT News, 54(4), 54-91.
Gharibian, Sevag
-
Quantum 2-SAT on low dimensional systems is QMA1-complete: Direct embeddings and black-box simulation
Dorian Rudolph, Sevag Gharibian & Daniel Nagaj
