Source-linked AI summary
Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT
Atsuya Hasegawa, Jonas Kamminga, François Le Gall, Suguru Tamaki
TL;DR
The paper asks whether frustration-free quantum satisfiability admits faster-than-brute-force algorithms, and develops algorithms using degree-balance conditions. It proves quantum 5-SAT hardness under (Q)SETH, including for instances with a small set of high-degree qubits.
Problem
The paper asks whether quantum satisfiability's frustration-free YES instances allow faster-than-brute-force algorithms.
Source: §1.1 · p. 3, §1.2 · p. 4Method
The paper uses frustration-freeness and degree-distribution conditions to obtain faster algorithms for suitable Hamiltonians.
Source: §1.2 · pp. 4–5Results
Assuming SETH, quantum 5-SAT has no O*(2^((1−ε)n)) classical algorithm, and its hardness persists with O(√n) exceptional qubits of degree O(√n).
Source: §1.2 · pp. 5–6Takeaways & Limitations
The results show that degree balance distinguishes instances with algorithmic speedups from some degree-concentrated instances that retain (Q)SETH-hardness.
Source: §1.2 · pp. 4, 6, §1.4 · p. 8The paper leaves open whether degree balance combined with an appropriate optimum–average separation yields faster algorithms for general, frustrated local Hamiltonians.
Source: §1.4 · p. 8
Abstract
from arXiv · showhide
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^\delta$, for any $\delta>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.
1 Introduction
The introduction asks whether frustration-freeness can make quantum satisfiability easier than worst-case local-Hamiltonian search, and answers that degree balance determines when it can. It presents faster algorithms for balanced frustration-free instances, (Q)SETH-hardness for quantum 5-SAT under concentrated degree profiles, and open questions beyond these bounds.
1.1 Background
- Quantum satisfiability asks whether all local constraints can be satisfied simultaneously, and the introduction asks whether frustration-freeness enables a constant-exponent improvement over brute force.The comparison is motivated by faster algorithms for fixed-width classical SAT and the contrast with exact MAX-SAT optimization.Source: §1.1 · pp. 3–4
1.2 Our results
- For fixed locality, frustration-free Hamiltonians admit a randomized classical constant-exponent speedup when maximum degree or a degree moment is bounded by a constant multiple of average degree.The Dmax condition includes regular and geometrically local instances; the Dp condition allows greater degree imbalance.Source: §1.2 · pp. 4–5
- Quantum 5-SAT is (Q)SETH-hard, even when all but O(√n) qubits have constant degree and the remaining O(√n) have degree O(√n).The algorithm covers exceptional-set profiles with exponents a + b < 1, while the boundary a = b = 1/2 is stated to support hardness.Source: §1.2 · pp. 5–6
1.3 Our techniques
- The upper-bound method selects pairwise disjoint constraints, restricts their subsystems to local kernels, and compresses the Hamiltonian while preserving the YES-instance zero energy and NO-instance promise gap.Degree balance or discarding constraints incident to very high-degree qubits enables finding a sufficiently large disjoint family.Source: §1.3 · p. 6
1.4 Related work
- The lower bound adapts a compressed-clock SAT reduction, redesigning the clocks to meet QSAT's legal-term requirements at the cost of increasing locality to 5.The paper also connects its independent-set approach to a classical 3-SAT algorithm and leaves faster algorithms for frustrated, geometrically local Hamiltonians as an open question.Source: §1.3 · pp. 6–7, §1.4 · p. 7, §1.5 · p. 8
1.5 Open questions
- Open questions include whether geometrically local non-frustration-free Hamiltonians admit faster algorithms, whether quantum 5-SAT hardness extends to locality 4 or 3, and whether other boundary degree profiles are hard.The paper notes that splitting the clock state across more registers might trade lower exceptional-set size for higher degree and locality.Source: §1.5 · p. 8
2 Preliminaries
The preliminaries define local Hamiltonians and quantum k-SAT, then state the classical and quantum SAT hypotheses used in the paper. They also present a linear-size quantum circuit for verifying sparse k-SAT instances.
2.1 Local Hamiltonian problem
- A k-local Hamiltonian is a sum of positive-semidefinite terms, each acting nontrivially on at most k qubits; the decision problem compares its ground-state energy with thresholds.The standard promise uses energy thresholds separated by at least 1/poly(n).Source: §2.1 · p. 9
- Quantum k-SAT asks whether a sum of local projectors is frustration-free, making it a special case of the frustration-free local Hamiltonian problem.For positive-semidefinite terms, frustration-freeness is equivalent to zero ground-state energy.Source: §2.1 · p. 10
2.2 SAT, SETH and QSETH
- SETH rules out O(2^(1−ε)n)-time classical k-SAT algorithms for some k, while QSETH rules out O(2^((1−ε)n/2))-time quantum algorithms; both use O(n)-clause instances.The sparsification lemma permits assuming O(n) clauses in these conjectures.Source: §2.2 · p. 11
- For any fixed k, a k-CNF instance with n variables and O(n) clauses has a polynomial-time constructible quantum verifier using O(n) elementary gates and O(log n) ancillas.The circuit outputs Φ(x) on its output register for every input assignment x.Source: §2.2 · p. 11
- The verifier acts on each input qubit O(d_i) times, where d_i counts clauses containing its variable, while ancilla qubits are acted on ˜O(n) times.This ties input-qubit gate use to variable occurrence counts.Source: §2.2 · p. 11
3 Faster exponential-time algorithms
The section speeds up frustration-free local Hamiltonian algorithms by compressing the Hilbert space using disjoint local terms, then finding a high-weight disjoint family. Its results give algorithms under degree-balance conditions and identify parameter regimes where they apply.
3.1 Compression theorem
- A polynomial-time compression maps selected disjoint local terms to their kernels, producing an effective Hamiltonian whose local-term description can be computed efficiently.The isometry preserves the relevant ground-energy claims, and selected terms vanish after projection.Source: §3.1 · pp. 12–14
3.2 Constructing a weighted disjoint family
- A sufficiently heavy disjoint family is enough; the section constructs one using either a maximum-degree bound or Lp-based truncation.The maximum-degree construction uses a greedy coloring argument; truncation removes constraints touching high-degree qubits before applying that construction.Source: §3.2 · pp. 16–17
3.3 Main result
- When ρmax or ρp exceeds a constant threshold, the theorem supplies randomized classical and quantum algorithms, and an inverse-polynomial estimate of the effective ground energy solves the instance.The effective Hamiltonian has constant-dimensional tensor factors and projected terms acting on only constantly many factors.Source: §3.3 · pp. 18–20
3.4 Interesting parameter regimes
- Almost-regular quantum k-SAT, including instances with constant maximum degree, admits a randomized classical algorithm with the stated speedup.The result also applies when qubits can be partitioned into subsets whose size times maximum degree is O(n^(1-ε)), or whose degrees are constant.Source: §3.4 · p. 20
- More generally, the stated classical speedup applies when each degree-bounded subset has size and degree exponents whose sum is less than one.The result is stated for a partition into a constant number of subsets.Source: §3.4 · pp. 20–21
4 (Q)SETH hardness of quantum 5-SAT
This section adapts size-preserving circuit-to-Hamiltonian methods to establish SETH and QSETH hardness for quantum 5-SAT, including sparse instances with only O(√N) high-degree qubits and constant-degree remaining qubits.
4 (Q)SETH hardness of quantum 5-SAT
- The result adapts size-preserving circuit-to-Hamiltonian methods to valid QSAT instances, with a locality increase from 3-local Hamiltonians to quantum 5-SAT.The underlying approach by Chia, Hasegawa, Le Gall and Shen [CHLGS26] embeds verification circuits using n + o(n) qubits rather than O(n + T).Source: §4 · p. 22
4.1 The K clock
- The K clock couples a pulse register to a unary register, enabling a one-local time readout while enforcing legal clock states with 3-local projectors.The unary coupling addresses the difficulty of enforcing a nonempty pulse clock using local projectors.Source: §4.1 · pp. 22–24
4.2 The L clock
- The L clock uses Bravyi’s clock [Bra06] to support 2-local incrementing with projectors.The resulting shift and gate projectors have locality 4 when the computational operation is 2-local.Source: §4.2 · pp. 24–25
4.3 Compressed clock construction
- Combining clocks yields a Hamiltonian that is a sum of 5-local projectors for a verification circuit of T = SKSL successive 2-local gates; if every state is accepted with probability at most 1 − ε, then λ(H) ≥ Ω(ε).The schedule alternately increments and decrements the L clock because resetting it is difficult.Source: §4.3 · pp. 26, 28
4.4 (Q)SETH hardness of quantum 5-SAT
- A classical 2^(1−ε)n-time quantum 5-SAT algorithm would contradict SETH, and a quantum 2^(1−ε)n/2-time algorithm would contradict QSETH.The reductions yield faster algorithms for k-SAT for any k.Source: §4.4 · p. 29
4.5 (Q)SETH hardness with somewhat balanced degree
- The degree-focused redesign targets the O(log n) verification-circuit ancillas, bounding their degrees by O(√n) while keeping verification linear-time.The subsection introduces a bounded-degree k-SAT verification circuit for fixed k and ∆.Source: §4.5 · p. 30
- Quantum 5-SAT remains (Q)SETH-hard with O(N) clauses when only O(√N) qubits have degree O(√N) and the rest have constant degree.The result uses a modified verification circuit and essentially matches Corollary 3.6.Source: §4.5 · pp. 33–34
- A faster-than-2^N algorithm for this degree-bounded quantum 5-SAT case would yield a faster-than-2^n algorithm for k-SAT, contradicting SETH; the QSETH argument is similar.The sparsification parameter is chosen below the assumed speedup exponent to retain a positive improvement for k-SAT.Source: §4.5 · p. 34
- The reduction uses a verification circuit on n input qubits and O(√n) ancillas, with O(n) gates; sparsification keeps each input qubit’s constraint degree constant.The clock and ancilla qubits form the O(√n)-sized high-degree subset, while input qubits have constant degree.Source: §4.5 · p. 34
AI disclosure
The authors report that all original ideas were theirs and that ChatGPT 5.5 and 5.6 assisted with the write-up.
AI disclosure
- The authors derived all original ideas and used ChatGPT 5.5 and 5.6 to aid in writing the manuscript.The authors take full responsibility for the manuscript's content.Source: AI disclosure · p. 34
A Proof of Lemma 2.11
The proof builds a reversible circuit that verifies a k-SAT formula by updating a counter for satisfied clauses and testing whether it reaches the total clause count. The counter updates are sized to the bits changed at each increment, yielding linear gate count and logarithmic ancilla use when k is constant and m = O(n).
A Proof of Lemma 2.11
- The counter update for step i touches t_i bits, the number changed when binary i − 1 is incremented to i.A controlled suffix update has O(t) gate and clean-work-qubit costs.Source: A Proof of Lemma 2.11 · p. 38
- The verifier processes each clause, applies a clause-controlled counter update, then compares the final counter with m to write whether the formula is satisfied.The clause register is uncomputed after each update.Source: A Proof of Lemma 2.11 · p. 39
- The counter reaches m when every clause is satisfied, while any unsatisfied clause creates a deficit that never decreases, so the final equality test detects satisfaction.Completeness gives z_m = m; soundness follows because each unsatisfied clause increases the deficit.Source: A Proof of Lemma 2.11 · p. 39
- For constant k and m = O(n), the complete verifier uses O(n) gates and O(log n) ancilla qubits.Work qubits are reused, and the counter uses logarithmic space in m.Source: A Proof of Lemma 2.11 · p. 40