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:2607.23847

A Slice-Rank Drift Bound for Random Quantum kkk-SAT

Jean Bernoulli Ravelomanana

quant-phmath-phmath.COmath.PRSubmitted Jul 26, 2026• Announced Jul 28, 2026• 0 citations
arXivHTMLPDF

Abstract

Random quantum satisfiability is a natural quantum analogue of random constraint satisfaction and a basic model for frustration-free local Hamiltonians. Despite extensive work on its satisfiable and unsatisfiable regimes, the quantitative location of the random quantum \(k\)-SAT threshold has remained poorly understood, with the best general upper bounds leaving a large gap to the known lower bounds. In this paper we prove a new upper bound on the satisfiability threshold of random quantum \(k\)-SAT. Our result improves the previously known asymptotic upper bound by a factor of order \(k\), giving a bound of order \(2^k/k\). The improvement is also significant at small values of \(k\); in particular, for random quantum \(3\)-SAT we obtain a substantially smaller explicit upper bound than the one previously available. The proof combines the geometric formulation of generic quantum satisfiability with a dimension-decay analysis of the full satisfying subspace. The key input is a multiplicative Shearer-type inequality for tensor-product subspaces, which quantifies how global dimension forces nontrivial local dimension on typical sets of qubits.

Related papers

Bounds on the quantum satisfiability threshold

Sergey B. Bravyi, Cristopher Moore, Alexander C. Russell

Quantum k-SAT is the problem of deciding whether there is a n-qubit state which is perpendicular to a set of vectors, each of which lies in the Hilbert space of k qubits. Equivalently, the problem is to decide whether a particular type of local Hamiltonian has a ground state with zero energy. We consider random quantum k-SAT formulas with n variables and m = αn clauses, and ask at what value of αthese formulas cease to be satisfiable. We show that the threshold for random quantum 3-SAT is at most 3.594. For comparison, convincing arguments from statistical physics suggest that the classical 3-SAT threshold is α\approx 4.267. For larger k, we show that the quantum threshold is a constant factor smaller than the classical one. Our bounds work by determining the generic rank of the satisfying subspace for certain gadgets, and then using the technique of differential equations to analyze various algorithms that partition the hypergraph into a collection of these gadgets. Our use of differential equation to establish upper bounds on a satisfiability threshold appears to be novel, and our techniques may apply to various classical problems as well.

arXiv:0907.1297•Jul 7, 2009•32 citations

Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT

Atsuya Hasegawa, Jonas Kamminga, François Le Gall +1 more

The local Hamiltonian problem is the canonical $\mathsf{QMA}$-complete problem, and $O(2^n)$ time classical algorithms and $O(2^{n/2})$ time quantum algorithms are known to solve the problem in the worst case. It is not clear how to improve these brute force strategies for a broad class of the problem because ground states are highly entangled in general, and we cannot directly apply known strategies for classical CSPs. In this work, we present exponentially faster classical and quantum algorithms under two mild assumptions: (1) the Hamiltonian is frustration-free on YES instances, and (2) it is approximately regular, meaning that every qubit is acted upon by approximately the same number of constraints. We complement these upper bounds by showing that, assuming (Q)SETH, quantum 5-SAT admits no non-trivial worst-case speedup. Our lower bound further demonstrates that the dependence of our algorithms on regularity is in some sense nearly optimal. Specifically, quantum 5-SAT remains (Q)SETH-hard even for Hamiltonians in which all but $O(\sqrt{n})$ qubits participate in only constantly many constraints, while the remaining $O(\sqrt{n})$ qubits each participate in $O(\sqrt{n})$ constraints. By contrast, if either the size of this high-degree subset or the degrees of its qubits is reduced by a factor of $n^δ$, for any $δ>0$, our algorithm solves the problem in time $O(2^{(1- \varepsilon)n})$ for some $\varepsilon>0$. Together, our upper and lower bounds establish a fine-grained complexity dichotomy for quantum satisfiability.

quant-pharXiv:2609.36464•Sep 30, 2026•0 citations

Testing Quantum Satisfiability

Ashley Montanaro, Changpeng Shao, Dominic Verdon

Abstract Quantum k-SAT (the problem of determining whether a k-local Hamiltonian is frustration-free) is known to be QMA $$_1$$ 1 -complete for $$k\ge 3$$ k ≥ 3 , and hence likely hard for quantum computers to solve. Building on a classical result of Alon and Shapira, we show that quantum k-SAT can be solved in randomised polynomial time given the ‘property testing’ promise that the instance is either satisfiable (by any state) or far from satisfiable by a product state; by ‘far from satisfiable by a product state’ we mean that $$\epsilon n^k$$ ϵ n k constraints must be removed before a product state solution exists, for some fixed $$\epsilon >0$$ ϵ > 0 . The proof has two steps: we first show that for a satisfiable instance of quantum k-SAT, most subproblems on a constant number of qubits are satisfiable by a product state. We then show that for an instance of quantum k-SAT which is far from satisfiable by a product state, most subproblems are unsatisfiable by a product state. Given the promise, quantum k-SAT may therefore be solved by checking satisfiability by a product state on randomly chosen subsystems of constant size.

arXiv:2301.10699•Communications in Mathematical Physics•Sep 1, 2025•2 citations

The PRODSAT phase of random quantum satisfiability

Joon Lee, Nicolas Macris, Jean Bernoulli Ravelomanana +1 more

The $k$-QSAT problem is a quantum analog of the famous $k$-SAT constraint satisfaction problem. We must determine the zero energy ground states of a Hamiltonian of $N$ qubits consisting of a sum of $M$ random $k$-local rank-one projectors. It is known that product states of zero energy exist with high probability if and only if the underlying factor graph has a clause-covering dimer configuration. This means that the threshold of the PRODSAT phase is a purely geometric quantity equal to the dimer covering threshold. We revisit and fully prove this result through a combination of complex analysis and algebraic methods based on Buchberger's algorithm for complex polynomial equations with random coefficients. We also discuss numerical experiments investigating the presence of entanglement in the PRODSAT phase in the sense that product states do not span the whole zero energy ground state space.

arXiv:2404.18447•Apr 29, 2024•2 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

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
Random quantum satisfiability is a natural quantum analogue of random constraint satisfaction and a basic model for frustration-free local Hamiltonians. Despite extensive work on its satisfiable and unsatisfiable regimes, the quantitative location of the random quantum (k)-SAT threshold has remained poorly understood, with the best general upper bounds leaving a large gap to the known lower bounds. In this paper we prove a new upper bound on the satisfiability threshold of random quantum (k)-SAT. Our result improves the previously known asymptotic upper bound by a factor of order (k), giving a bound of order (2^k/k). The improvement is also significant at small values of (k); in particular, for random quantum (3)-SAT we obtain a substantially smaller explicit upper bound than the one previously available. The proof combines the geometric formulation of generic quantum satisfiability with a dimension-decay analysis of the full satisfying subspace. The key input is a multiplicative Shearer-type inequality for tensor-product subspaces, which quantifies how global dimension forces nontrivial local dimension on typical sets of qubits.
Quantum k-SAT is the problem of deciding whether there is a n-qubit state which is perpendicular to a set of vectors, each of which lies in the Hilbert space of k qubits. Equivalently, the problem is to decide whether a particular type of local Hamiltonian has a ground state with zero energy. We consider random quantum k-SAT formulas with n variables and m = αn clauses, and ask at what value of αthese formulas cease to be satisfiable. We show that the threshold for random quantum 3-SAT is at most 3.594. For comparison, convincing arguments from statistical physics suggest that the classical 3-SAT threshold is α\approx 4.267. For larger k, we show that the quantum threshold is a constant factor smaller than the classical one. Our bounds work by determining the generic rank of the satisfying subspace for certain gadgets, and then using the technique of differential equations to analyze various algorithms that partition the hypergraph into a collection of these gadgets. Our use of differential equation to establish upper bounds on a satisfiability threshold appears to be novel, and our techniques may apply to various classical problems as well.
The local Hamiltonian problem is the canonical QMA\mathsf{QMA}QMA-complete problem, and O(2n)O(2^n)O(2n) time classical algorithms and O(2n/2)O(2^{n/2})O(2n/2) time quantum algorithms are known to solve the problem in the worst case. It is not clear how to improve these brute force strategies for a broad class of the problem because ground states are highly entangled in general, and we cannot directly apply known strategies for classical CSPs. In this work, we present exponentially faster classical and quantum algorithms under two mild assumptions: (1) the Hamiltonian is frustration-free on YES instances, and (2) it is approximately regular, meaning that every qubit is acted upon by approximately the same number of constraints. We complement these upper bounds by showing that, assuming (Q)SETH, quantum 5-SAT admits no non-trivial worst-case speedup. Our lower bound further demonstrates that the dependence of our algorithms on regularity is in some sense nearly optimal. Specifically, quantum 5-SAT remains (Q)SETH-hard even for Hamiltonians in which all but O(n)O(\sqrt{n})O(n​) qubits participate in only constantly many constraints, while the remaining O(n)O(\sqrt{n})O(n​) qubits each participate in O(n)O(\sqrt{n})O(n​) constraints. By contrast, if either the size of this high-degree subset or the degrees of its qubits is reduced by a factor of nδn^δnδ, for any δ>0δ>0δ>0, our algorithm solves the problem in time O(2(1−ε)n)O(2^{(1- \varepsilon)n})O(2(1−ε)n) for some ε>0\varepsilon>0ε>0. Together, our upper and lower bounds establish a fine-grained complexity dichotomy for quantum satisfiability.
Abstract Quantum k-SAT (the problem of determining whether a k-local Hamiltonian is frustration-free) is known to be QMA 1_11​ 1 -complete for k≥3k\ge 3k≥3 k ≥ 3 , and hence likely hard for quantum computers to solve. Building on a classical result of Alon and Shapira, we show that quantum k-SAT can be solved in randomised polynomial time given the ‘property testing’ promise that the instance is either satisfiable (by any state) or far from satisfiable by a product state; by ‘far from satisfiable by a product state’ we mean that ϵnk\epsilon n^kϵnk ϵ n k constraints must be removed before a product state solution exists, for some fixed ϵ>0\epsilon >0ϵ>0 ϵ > 0 . The proof has two steps: we first show that for a satisfiable instance of quantum k-SAT, most subproblems on a constant number of qubits are satisfiable by a product state. We then show that for an instance of quantum k-SAT which is far from satisfiable by a product state, most subproblems are unsatisfiable by a product state. Given the promise, quantum k-SAT may therefore be solved by checking satisfiability by a product state on randomly chosen subsystems of constant size.
The kkk-QSAT problem is a quantum analog of the famous kkk-SAT constraint satisfaction problem. We must determine the zero energy ground states of a Hamiltonian of NNN qubits consisting of a sum of MMM random kkk-local rank-one projectors. It is known that product states of zero energy exist with high probability if and only if the underlying factor graph has a clause-covering dimer configuration. This means that the threshold of the PRODSAT phase is a purely geometric quantity equal to the dimer covering threshold. We revisit and fully prove this result through a combination of complex analysis and algebraic methods based on Buchberger's algorithm for complex polynomial equations with random coefficients. We also discuss numerical experiments investigating the presence of entanglement in the PRODSAT phase in the sense that product states do not span the whole zero energy ground state space.
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 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.