Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2209.04655

Satisfiability Phase Transtion for Random Quantum 3XOR Games

Adam Bene Watts, J. William Helton, Zehong Zhao

Published Sep 10, 2022• 2 citations
arXivHTMLPDF

Abstract

Recent results showed it was possible to determine if a modest size 3XOR game has a perfect quantum strategy. We build on these and give an explicit polynomial time algorithm which constructs such a perfect strategy or refutes its existence. This new tool lets us numerically study the behavior of randomly generated 3XOR games with large numbers of questions. A key issue is: how common are pseudotelephathy games (games with perfect quantum strategies but no perfect classical strategies)? Our experiments strongly indicate that the probability of a randomly generated game being pseudotelpathic stays far from 1, indeed it is bounded below 0.15. We also find strong evidence that randomly generated 3XOR games undergo both a quantum and classical "phase transition", transitioning from almost certainly perfect to almost certainly imperfect as the ratio of number of clauses ($m$) to number of questions ($n$) increases. The locations of these two phase transitions appear to coincide at $m/n \approx 2.74$.

DOI
10.48550/arxiv.2209.04655

Related papers

Algorithms, Bounds, and Strategies for Entangled XOR Games

Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar +1 more

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.

arXiv:1801.00821•Leibniz international proceedings in informatics•Jan 2, 2018•12 citations

Product, generic, and random generic quantum satisfiability

Chris R. Laumann, Andreas Martin Läuchli, Roderich Moessner +2 more

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 $\mathit{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.

arXiv:0910.2058•Physical Review A•Jun 28, 2010•43 citations

Quantum Adiabatic Evolution Algorithm and Quantum Phase Transition in 3-Satisfiability Problem

Sergey Knysh, Vadim Smelyanskiy

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)\approx$ 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.

arXiv:cond-mat/0602257•Feb 10, 2006•5 citations

3XOR Games with Perfect Commuting Operator Strategies Have Perfect Tensor Product Strategies and are Decidable in Polynomial Time

Adam Bene Watts, J. William Helton

Abstract We consider 3XOR games with perfect commuting operator strategies. Given any 3XOR game, we show existence of a perfect commuting operator strategy for the game can be decided in polynomial time. Previously this problem was not known to be decidable. Our proof leads to a construction, showing a 3XOR game has a perfect commuting operator strategy iff it has a perfect tensor product strategy using a 3 qubit (8 dimensional) GHZ state. This shows that for perfect 3XOR games the advantage of a quantum strategy over a classical strategy (defined by the quantum-classical bias ratio) is bounded. This is in contrast to the general 3XOR case where the optimal quantum strategies can require high dimensional states and there is no bound on the quantum advantage. To prove these results, we first show equivalence between deciding the value of an XOR game and solving an instance of the subgroup membership problem on a class of right angled Coxeter groups. We then show, in a proof that consumes most of this paper, that the instances of this problem corresponding to 3XOR games can be solved in polynomial time.

arXiv:2010.16290•Communications in Mathematical Physics•Feb 10, 2023•4 citations

Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses

Mingyou Wu

The random k-SAT instances undergo a "phase transition" from being generally satisfiable to unsatisfiable as the clause number m passes a critical threshold, $r_k n$. 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 \ge 3$, any small $ε>0$ and sufficiently large n: $\cdot$ k-local quantum search achieves general efficiency on random instances of max-k-SSAT with $m=Ω(n^{2+δ+ε})$ using $\mathcal{O}(n)$ iterations, and $\cdot$ k-local adiabatic quantum search enhances the bound to $m=Ω(n^{1+δ+ε})$ within an evolution time of $\mathcal{O}(n^2)$. In both cases, the circuit complexity of each iteration is $\mathcal{O}(n^k)$, and the efficiency is assured with overwhelming probability $1 - \mathcal{O}(\mathrm{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=Ω(n^{2+ε})$ based on the average-case complexity theory.

arXiv:2403.03237•Mar 5, 2024•3 citations

Efficiency of structured adiabatic quantum computation

Juan José García‐Ripoll, Mari Carmen Bañuls

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.

arXiv:0812.1760•Dec 9, 2008•2 citations
Recent results showed it was possible to determine if a modest size 3XOR game has a perfect quantum strategy. We build on these and give an explicit polynomial time algorithm which constructs such a perfect strategy or refutes its existence. This new tool lets us numerically study the behavior of randomly generated 3XOR games with large numbers of questions. A key issue is: how common are pseudotelephathy games (games with perfect quantum strategies but no perfect classical strategies)? Our experiments strongly indicate that the probability of a randomly generated game being pseudotelpathic stays far from 1, indeed it is bounded below 0.15. We also find strong evidence that randomly generated 3XOR games undergo both a quantum and classical "phase transition", transitioning from almost certainly perfect to almost certainly imperfect as the ratio of number of clauses (mmm) to number of questions (nnn) increases. The locations of these two phase transitions appear to coincide at m/n≈2.74m/n \approx 2.74m/n≈2.74.
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 kkk-QSAT, the problem of quantum satisfiability for kkk-qubit projectors which generalizes classical satisfiability with kkk-bit clauses to the quantum setting. First we define the NP\mathit{NP}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=3k=3k=3 and k=4k=4k=4 and mild evidence for the existence of a phase which is satisfiable by entangled states alone.
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Γ=0Γ=0 the value of γ(0)≈γ(0)\approxγ(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.
Abstract We consider 3XOR games with perfect commuting operator strategies. Given any 3XOR game, we show existence of a perfect commuting operator strategy for the game can be decided in polynomial time. Previously this problem was not known to be decidable. Our proof leads to a construction, showing a 3XOR game has a perfect commuting operator strategy iff it has a perfect tensor product strategy using a 3 qubit (8 dimensional) GHZ state. This shows that for perfect 3XOR games the advantage of a quantum strategy over a classical strategy (defined by the quantum-classical bias ratio) is bounded. This is in contrast to the general 3XOR case where the optimal quantum strategies can require high dimensional states and there is no bound on the quantum advantage. To prove these results, we first show equivalence between deciding the value of an XOR game and solving an instance of the subgroup membership problem on a class of right angled Coxeter groups. We then show, in a proof that consumes most of this paper, that the instances of this problem corresponding to 3XOR games can be solved in polynomial time.
Local Quantum Search Algorithm for Random kkk-SAT with Ω(n1+ε)Ω(n^{1+ε})Ω(n1+ε) Clauses
The random k-SAT instances undergo a "phase transition" from being generally satisfiable to unsatisfiable as the clause number m passes a critical threshold, rknr_k nrk​n. 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≥3k \ge 3k≥3, any small ε>0ε>0ε>0 and sufficiently large n: ⋅\cdot⋅ k-local quantum search achieves general efficiency on random instances of max-k-SSAT with m=Ω(n2+δ+ε)m=Ω(n^{2+δ+ε})m=Ω(n2+δ+ε) using O(n)\mathcal{O}(n)O(n) iterations, and ⋅\cdot⋅ k-local adiabatic quantum search enhances the bound to m=Ω(n1+δ+ε)m=Ω(n^{1+δ+ε})m=Ω(n1+δ+ε) within an evolution time of O(n2)\mathcal{O}(n^2)O(n2). In both cases, the circuit complexity of each iteration is O(nk)\mathcal{O}(n^k)O(nk), and the efficiency is assured with overwhelming probability 1−O(erfc(nδ/2))1 - \mathcal{O}(\mathrm{erfc}(n^{δ/2}))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+ε)m=Ω(n^{2+ε})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.