Entangled games are a quantum analog of constraint satisfaction problems and have had important applications to quantum complexity theory, quantum cryptography, and the foundations of quantum mechanics. Given a game, the basic computational problem is to compute its entangled value: the supremum success probability attainable by a quantum strategy. We study the complexity of computing the (commuting-operator) entangled value omega^* of entangled XOR games with any number of players. Based on a duality theory for systems of operator equations, we introduce necessary and sufficient criteria for an XOR game to have omega^* = 1, and use these criteria to derive the following results: 1) An algorithm for symmetric games that decides in polynomial time whether omega^* = 1 or omega^* < 1, a task that was not previously known to be decidable, together with a simple tensor-product strategy that achieves value 1 in the former case. The only previous candidate algorithm for this problem was the Navascués-Pironio-Acín (also known as noncommutative Sum of Squares or ncSoS) hierarchy, but no convergence bounds were known. 2) A family of games with three players and with omega^* < 1, where it takes doubly exponential time for the ncSoS algorithm to witness this. By contrast, our algorithm runs in polynomial time. 3) Existence of an unsatisfiable phase for random (non-symmetric) XOR games. We show that there exists a constant C_k^{unsat} depending only on the number k of players, such that a random k-XOR game over an alphabet of size n has omega^* < 1 with high probability when the number of clauses is above C_k^{unsat} n. 4) A lower bound of Omega(n log(n)/log log(n)) on the number of levels in the ncSoS hierarchy required to detect unsatisfiability for most random 3-XOR games. This is in contrast with the classical case where the (3n)^{th} level of the sum-of-squares hierarchy is equivalent to brute-force enumeration of all possible solutions.
We report a cluster of results on
k-QSAT, the problem of quantum satisfiability for
k-qubit projectors which generalizes classical satisfiability with
k-bit clauses to the quantum setting. First we define the
NP-complete problem of product satisfiability and give a geometrical criterion for deciding when a QSAT interaction graph is product satisfiable with positive probability. We show that the same criterion suffices to establish quantum satisfiability for all projectors. Second, we apply these results to the random graph ensemble with generic projectors and obtain improved lower bounds on the location of the SAT-unSAT transition. Third, we present numerical results on random, generic satisfiability which provide estimates for the location of the transition for
k=3 and
k=4 and mild evidence for the existence of a phase which is satisfiable by entangled states alone.
We study the complexity of computing the commuting-operator value
ω∗ of entangled XOR games with any number of players. We introduce necessary and sufficient criteria for an XOR game to have
ω∗=1, and use these criteria to derive the following results: 1. An algorithm for symmetric games that decides in polynomial time whether
ω∗=1 or
ω∗<1, a task that was not previously known to be decidable, together with a simple tensor-product strategy that achieves value 1 in the former case. The only previous candidate algorithm for this problem was the Navascués-Pironio-Acín (also known as noncommutative Sum of Squares or ncSoS) hierarchy, but no convergence bounds were known. 2. A family of games with three players and with
ω∗<1, where it takes doubly exponential time for the ncSoS algorithm to witness this (in contrast with our algorithm which runs in polynomial time). 3. A family of games achieving a bias difference
2(ω∗−ω) arbitrarily close to the maximum possible value of
1 (and as a consequence, achieving an unbounded bias ratio), answering an open question of Briët and Vidick. 4. Existence of an unsatisfiable phase for random (non-symmetric) XOR games: that is, we show that there exists a constant
Ckunsat depending only on the number
k of players, such that a random
k-XOR game over an alphabet of size
n has
ω∗<1 with high probability when the number of clauses is above
Ckunsatn. 5. A lower bound of
Ω(nlog(n)/loglog(n)) on the number of levels in the ncSoS hierarchy required to detect unsatisfiability for most random 3-XOR games. This is in contrast with the classical case where the
n-th level of the sum-of-squares hierarchy is equivalent to brute-force enumeration of all possible solutions.
In this paper we show that the performance of the quantum adiabatic algorithm is determined by phase transitions in underlying problem in the presence of transverse magnetic field
Γ. We show that the quantum version of random Satisfiability problem with 3 bits in a clause (3-SAT) has a first-order quantum phase transition. We analyze the phase diagram
γ=γ(Γ) where
γ is an average number of clauses per binary variable in 3-SAT. The results are obtained in a closed form assuming replica symmetry and neglecting time correlations at small values of the transverse field
Γ. In the limit of
Γ=0 the value of
γ(0)≈ 5.18 corresponds to that given by the replica symmetric treatment of a classical random 3-SAT problem. We demonstrate the qualitative similarity between classical and quantum versions of this problem.
The random k-SAT instances undergo a "phase transition" from being generally satisfiable to unsatisfiable as the clause number m passes a critical threshold,
rkn. This causes a drastic reduction in the number of satisfying assignments, shifting the problem from being generally solvable on classical computers to typically insolvable. Beyond this threshold, it is challenging to comprehend the computational complexity of random k-SAT. In quantum computing, Grover's search still yields exponential time requirements due to the neglect of structural information. Leveraging the structure inherent in search problems, we propose the k-local quantum search algorithm, which extends quantum search to structured scenarios. Grover's search, by contrast, addresses the unstructured case where k=n. Given that the search algorithm necessitates the presence of a target, we specifically focus on the problem of searching the interpretation of satisfiable instances of k-SAT, denoted as max-k-SSAT. If this problem is solvable in polynomial time, then k-SAT can also be solved within the same complexity. We demonstrate that, for small
k≥3, any small
ε>0 and sufficiently large n:
⋅ k-local quantum search achieves general efficiency on random instances of max-k-SSAT with
m=Ω(n2+δ+ε) using
O(n) iterations, and
⋅ k-local adiabatic quantum search enhances the bound to
m=Ω(n1+δ+ε) within an evolution time of
O(n2). In both cases, the circuit complexity of each iteration is
O(nk), and the efficiency is assured with overwhelming probability
1−O(erfc(nδ/2)). By modifying this algorithm capable of solving all instances of max-k-SSAT, we further prove that max-k-SSAT is polynomial on average when
m=Ω(n2+ε) based on the average-case complexity theory.
We show enough evidence that a structured version of Adiabatic Quantum Computation (AQC) is efficient for most satisfiability problems. More precisely, when the success probability is fixed beforehand, the computational resources grow subexponentially in the number of qubits. Our study focuses on random satisfiability and exact cover problems, developing a multi-step algorithm that solves clauses one by one. Relating the computational cost to classical properties of the problem, we collect significant statistics with up to N=140 qubits, around the phase transitions, which is where the hardest problems appear.