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.
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.
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≥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 ϵ n k constraints must be removed before a product state solution exists, for some fixed ϵ>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 local Hamiltonian problem is the canonical QMA-complete problem, and O(2n) time classical algorithms and 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) qubits participate in only constantly many constraints, while the remaining O(n) qubits each participate in 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δ, for any δ>0, our algorithm solves the problem in time O(2(1−ε)n) for some ε>0.
Together, our upper and lower bounds establish a fine-grained complexity dichotomy for quantum satisfiability.
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.
Local Quantum Search Algorithm for Random k-SAT with Ω(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, 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 prove that, for an n-qubit system of dimension d=2n, every state satisfying Tr(ρ2)≤1/(d−a∗), with a∗=0.458327⋯, lies inside the stabilizer polytope and is therefore magic-free. Combining this result with general geometric properties of high-dimensional polytopes, we establish quantitative estimates for the Hilbert--Schmidt inradius and volume radius of the stabilizer polytope, and use them to characterize the typicality of magic in random induced states obtained by tracing out a k-dimensional subsystem from a d×k-dimensional Haar-random pure state. We prove a sharp phase transition in the probability of such states having magic, whose transition dimension k⋆ is bounded between Ω(d2/log2d) and O(d2). We further prove that the number of facets of the stabilizer polytope lies between exp[Ω(d2/log2d)] and exp[O(d2log2d)] employing a result of Bourgain and Milman in convex geometry, substantially improving upon the previous quasipolynomial lower bound and implying that doubly-exponentially many linear inequalities in the number of qubits are required for an exact description of the magic-free region. Overall, our results reveal the near-extremal geometry of the stabilizer polytope and provide a quantitative foundation for understanding the typicality, robustness, and detectability of magic.
Random quantum circuits are a central concept in quantum information theory with applications ranging from demonstrations of quantum computational advantage to descriptions of scrambling in strongly interacting systems and black holes. The utility of random quantum circuits in these settings stems from their ability to rapidly generate quantum pseudorandomness. In a seminal paper by Brand\~ao, Harrow, and Horodecki [Commun. Math. Phys. 346, 397 (2016)] it was proven that the tth moment operator of local random quantum circuits on n qudits with local dimension q has a spectral gap of at least $\mathrm{\ensuremath{\Omega}}({n}^{\ensuremath{-}1}{t}^{\ensuremath{-}5\ensuremath{-}3.1/ln(q)})$, which implies that they are efficient constructions of approximate unitary designs. As a first result, we use Knabe bounds for the spectral gaps of frustration-free Hamiltonians to show that one-dimensional random quantum circuits have a spectral gap scaling as $\mathrm{\ensuremath{\Omega}}({n}^{\ensuremath{-}1})$, provided that t is small compared to the local dimension: ${t}^{2}\ensuremath{\le}O(q)$. This implies a (nearly) linear scaling of the circuit depth in the design order t. Our second result is an unconditional spectral gap bounded below by $\mathrm{\ensuremath{\Omega}}[{n}^{\ensuremath{-}1}{ln}^{\ensuremath{-}1}(n){t}^{\ensuremath{-}\ensuremath{\alpha}(q)}]$ for random quantum circuits with all-to-all interactions. This improves both the n and t scaling in design depth for the nonlocal model. We show this by proving a recursion relation for the spectral gaps involving an auxiliary random walk. Lastly, we solve the smallest nontrivial case exactly and combine with numerics and Knabe bounds to improve the constants involved in the spectral gap for small values of t.