Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes

Alex Meiburg; Daniel Nagaj; Ricardo Rivera Cardoso

REVIEW 4 major objections 4 minor 54 references

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes

T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper constructs quantum SAT problems with finite sets of projectors that are complete for BQP_1, coRP, QCMA, and six intersection/union classes, so any complete classification of quantum constraint satisfaction problems must contain…

desk verdict A serious QSAT classification paper whose qudit results look solid and whose qubit results hinge on a single reduction I could not verify from the visible text. read the letter →

arxiv 2506.07244 v1 pith:O6HZXDAK submitted 2025-06-08 quant-ph cs.CC

Ricardo Rivera Cardoso , Alex Meiburg , Daniel Nagaj This is my paper

classification quant-phcs.CC MSC 68Q1268Q1781P68

keywords quantumsatisfiabilityfrustration-freeHamiltonianQMA_1BQP_1coRPQCMAPIandSoPUclassescircuit-to-Hamiltonian

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Quantum satisfiability asks whether a set of local projectors has a common zero eigenstate, equivalently whether a local Hamiltonian is frustration-free. Until this work, every finite-set variant was known to be either in P or complete for NP, MA, or QMA_1. The paper constructs finite sets of qudit and qubit projectors for which the same decision problem is complete for BQP_1, coRP, QCMA, and six further classes built from pairwise intersections and unions of complexity classes. It does this by reworking the circuit-to-Hamiltonian projectors so that satisfiable instances have a rigid 'history state' structure, and then proves a reduction from qudit instances to qubit instances of equal difficulty. If the claims hold, a future Schaefer-type classification of quantum constraint satisfaction cannot stop at the four previously known classes.

What carries the argument

The load-bearing object is a redefinition of the standard circuit-to-Hamiltonian projectors H_init, H_prop, H_out into 'ternary clock' projectors: each logical qudit carries an extra undefined state |?>, while clock qudits carry the states |r>, |a>, |d> that index a computation step. The projectors are engineered so that any instance is either trivially satisfiable, trivially unsatisfiable, or encodes the evaluation of a quantum circuit; monogamy of entanglement (the fact that one qubit cannot be maximally entangled with two others) is used in LCT-QSAT to reject instances whose clock graph is not a single directed chain. The same structural lemmas are re-proved in SLCT-QSAT using only clock-consistency constraints, removing the need for auxiliary Bell-pair subspaces and lowering the qudit dimension from 17 to 6. The QCMA and coRP variants modify the initialization projector to couple logical qudits to witness or auxiliary qudits, forcing the witness to be classical without losing perfect completeness.

What would settle it

A concrete check would be to enumerate all small qubit QCSP instances and apply the paper's reduction in reverse: find one qubit instance that is not equivalent to any qudit instance under the claimed surjective mapping, or whose satisfiability differs from its parent qudit instance, which would refute Theorem 5. For the coRP claim specifically, implementing the Section 6 decision algorithm on exhaustively enumerated small instances and comparing its output with exact diagonalization would show a no-instance accepted with probability above 1/3, directly contradicting the claimed soundness.

Watch

Extended reading notes

Core claim

The central claim is that finite sets of O(1)-local projectors yield QSAT problems complete for BQP_1, coRP, and QCMA, plus six complete problems for PI and SoPU classes. The first QSAT problem, LCT-QSAT, is BQP_1-complete with 4-local clauses on 17-dimensional qudits and uses monogamy of entanglement to force the clock structure to be a one-dimensional chain. A refined version, SLCT-QSAT, achieves the same completeness on 6-dimensional qudits, and Corollary 1.1 removes the dependence on the particular Clifford-cyclotomic gate set. Small modifications produce Witnessed SLCT-QSAT, which is QCMA-complete on 8-dimensional qudits, and Classical SLCT-QSAT, which is coRP-complete on 8-dimensional qudits. Theorem 5 then shows every qudit QCSP reduces to a qubit QCSP of the same difficulty, giving qubit versions with locality 48 (for BQP_1 and QCMA) and 60 (for coRP). Direct products and sums of these problems with 3-SAT and Stoquastic 6-SAT yield complete problems for PI(coRP,NP), SoPU(coRP,NP), PI(BQP_1,NP), SoPU(BQP_1,NP), PI(BQP_1,MA), and SoPU(BQP_1,MA). Corollary 1.3 concludes that any classification of strong quantum CSPs with O(1)-local qubit clauses must either include all thirteen classes or show that some of them coincide.

Load-bearing premise

The load-bearing premise is that every qudit constraint problem can be re-encoded as a qubit constraint problem of exactly the same difficulty; if the reduction misses some qubit instances or changes their satisfiability, the qubit versions of the BQP_1, coRP, and QCMA completeness claims collapse.

Editorial extensions

If this is right

There is a finite-set QSAT problem, SLCT-QSAT and its qubit version, whose yes/no instances can be decided by a quantum circuit with perfect completeness, giving the first nontrivial BQP_1-complete problem.
There is a QSAT problem, Classical SLCT-QSAT, decidable by a randomized classical algorithm with one-sided error, so frustration-freeness with a restricted projector set can be a coRP-complete question.
The QCMA-complete problem Witnessed SLCT-QSAT shows that allowing a classical witness in a QSAT instance places it in a class strictly between the witness-free and quantum-witness settings, unless some of these classes collapse.
Any future classification theorem for strong quantum CSPs, analogous to Schaefer's theorem for classical CSPs, must either incorporate at least thirteen distinct classes or provide a proof that some of the thirteen are equal.
Because the qubit versions have finite projector sets and constant locality, the completeness results transfer to physically natural qubit Hamiltonians rather than remaining confined to high-dimensional qudit constructions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the qudit-to-qubit reduction of Theorem 5 is as strong as claimed, the three qubit QSAT problems provide concrete qubit Hamiltonians whose frustration-free problem sits in BQP_1, coRP, or QCMA; these are natural candidates for attempts to lower the locality constant or to find simpler glassy versions of the same clauses.
The monogamy-of-entanglement gadget used to force linear clock structure could be reused in other constraint problems where a one-dimensional interaction graph simplifies the decision procedure, independent of the quantum circuit encoding.
The thirteen-class conclusion sharpens the stakes of derandomization-style open questions: establishing, for instance, coRP = P would immediately collapse two of the new PI and SoPU classes to NP, while showing BQP_1 and NP are incomparable would force any classification to separate them.
A testable extension would be to search for smaller-dimensional versions of the ternary |? > trick, asking whether the same containment and hardness arguments survive when the logical Hilbert space dimension is reduced below six while keeping the same promise on the spectral gap.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know two things. First, the qudit part of this paper is a real advance: the authors construct QSAT problems complete for BQP_1, coRP, and QCMA using a ternary undefined state and carefully engineered clocks, and they explicitly identify and correct a flaw in Meiburg's earlier attempt. That is genuinely new and, from what I can see, carefully argued. Second, the larger claims—qubit versions of all these problems and the 13-class classification—rest on Theorem 5, a qudit-to-qubit reduction whose proof is in Section 7, which I have not seen. That is the load-bearing wall.

What the paper does well: the constructions are explicit, the algorithms are described in enough detail to be checked, and the hardness reductions are standard circuit-to-Hamiltonian embeddings. The BQP_1 containment argument for LCT-QSAT is intricate but plausible, and the soundness analysis uses Kitaev's geometric lemma in the expected way. The paper is honest about its own risk, flagging that the qubit reduction is 'believed not to be possible classically' and that the standard embedding fails because it is not surjective on instances. The citation pattern looks fine: they build on Gosset–Nagaj and Rudolph, and they correct rather than ignore prior work.

The soft spots are real but localized. Theorem 5 is not just a technical lemma; without it, Corollary 1.2, Theorem 6, and Corollary 1.3 all collapse. The paper's own Section 1.2 explains why the naive reduction fails, and the stress-test note is right: a correct reduction must give a finite qubit projector set whose full instance closure is equivalent to the qudit instance set, preserving the yes/no answer and the 1/poly gap on every instance. That is a strong condition, and it is exactly the kind of thing that can go wrong in a long appendix. There is also a smaller issue: the abstract's claim of the 'first nontrivial BQP_1-complete problem' deserves a clearer literature check, since gate-set-dependent BQP_1 classes are subtle.

If Section 7 delivers the surjective mapping, this is a major result and the 13-class taxonomy will be the new baseline for strong QCSP classification. If it fails, the qudit results still stand as a substantial contribution—new complete problems for BQP_1, coRP, and QCMA, plus a corrected version of Meiburg's program. Either way, this deserves a serious referee. I would send it out, with a specific request to verify Theorem 5 and the appendix proofs, rather than desk reject.

Referee Report

4 major / 4 minor

Summary. The paper defines several finite-projector quantum SAT problems and claims completeness for BQP_1 (with the Clifford-cyclotomic gate set G8), QCMA, coRP, and six PI/SoPU classes. The central technical device is a modified circuit-to-Hamiltonian construction in which the usual H_init, H_prop, and H_out terms are re-engineered with a ternary 'undefined' logical state, high-dimensional clock qudits, and (in the first construction) monogamy-of-entanglement constraints. These ingredients are intended to force every instance to be either trivially satisfiable, trivially unsatisfiable, or equivalent to evaluating a witness-free quantum circuit, a deterministic classical circuit, or a circuit with a classical witness. The paper further claims a general reduction from qudit QCSPs to qubit QCSPs (Theorem 5), and uses direct product/sum constructions to obtain six PI/SoPU-complete qubit QSAT problems, giving Corollary 1.3 that any strong QCSP classification must contain at least 13 classes. The version of the manuscript provided to me contains no Section 7, no Section 8, and no Appendices A-C, although the text repeatedly refers to them; this is the main obstacle to verification.

Significance. If the missing proofs are correct, this is a substantial contribution. The paper would provide the first nontrivial BQP_1-complete problem, new QCMA- and coRP-complete QSAT problems, and the first complete problems for several PI and SoPU classes, together with a concrete lower bound of 13 classes for any future Schaefer-type classification of strong quantum constraint satisfaction. The construction of LCT-QSAT, in particular the use of monogamy of entanglement to force a one-dimensional clock structure, is genuinely novel. The main-text algorithms are written in enough detail to be reproducible, although no machine-checked proofs or code are provided. The significance is conditional: the advertised qubit and PI/SoPU results all depend on the absent Section 7 and Section 8, and the containment proofs depend on absent appendices.

major comments (4)

[§7 (Theorem 5 and Corollary 1.2)] The qudit-to-qubit reduction, Theorem 5, is the load-bearing bridge for every qubit-level claim, but it is not present in the submitted manuscript. Section 1.2 itself concedes that the standard encoding is not surjective on instances and that the resulting qubit problem contains harder instances. A correct proof must supply a finite O(1)-local qubit projector set whose full instance closure under arbitrary collections, in the sense of Definition 2.7, has the same yes/no classification and the same 1/poly promise gap as the original qudit problem. Without this construction, Corollary 1.2, Theorem 6, and Corollary 1.3 are unsupported.
[§3.3, §4.1, and Appendices A/B] The containment proofs for LCT-QSAT and SLCT-QSAT rely on the structural classification lemmas Lemmas 3.1-3.10 and 4.1-4.8, but the text states that their proofs are collected in Appendices A and B, which are not included. In particular, Lemmas 3.2-3.7 are what justify the rejection steps of the classical algorithm; without those proofs, the perfect-completeness claim cannot be checked. The same applies to Propositions 3.1-3.3 and to the claims about simultaneous propagation clauses. The complete appendix material must be provided.
[§3.2, §3.5, and §4.3] There is a gate-set mismatch in the hardness reductions. Definitions 3.1 and 4.1 allow propagation unitaries only from {H, HT, (H⊗H)CNOT}, but the hardness proofs begin with a BQP_1 circuit U_x whose gates are from Clifford+T, G8 = {H, CNOT, T}, and then place those gates directly into Π_prop clauses. No exact polynomial-time decomposition of CNOT or T in terms of the allowed set is given. Since BQP_1 requires perfect completeness, even approximation is not acceptable here; a short exact decomposition lemma is needed.
[§8 (Theorem 6 and Corollary 1.3)] Section 8, which is supposed to define the direct product and direct sum of QCSPs and prove Theorem 6, is absent. The claim in Section 1.2 that satisfying states 'always respect the product (resp. sum) structure' and the 'mild technical conditions' for efficient conversion are exactly the technical content needed for the six PI/SoPU completeness results. Without this section, Theorem 6 and the 13-class Corollary 1.3 remain assertions rather than proven results.

minor comments (4)

[§2.3] In the paragraph after Definition 2.7, the sentence 'there exists a state a state that satisfies all constraints' contains a duplicated phrase and should be corrected.
[§3.2] The remark that certain tensor products are abbreviated as |a⟩⟨a| is under-specified; a table of the decomposition of the 17-dimensional qudit into logical, clock, and endpoint subspaces would make the projector definitions much easier to check.
[§3.4.1, Step (2.5)] The step 'If there are no Π_init and Π_out clauses' is ambiguous; Lemma 3.6 refers to a clock component that does not contain at least one Π_init and at least one Π_out clause, so the step should be phrased as 'does not contain both types of clauses'.
[§3.4.4, Eq. (19)] The soundness bound 'max p_i,j ≥ sum/(total number of projectors)' is stated with 'total number of projectors' without defining whether the count includes only measured projectors or all projectors in the instance; this should be made explicit, since the soundness argument uses the promise on the full instance.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the hardness and membership proofs are independent reductions, and the only self-citation is used to disavow flawed prior work.

full rationale

The derivation chain is self-contained in the nontrivial directions. Theorems 1-4 reduce arbitrary BQP1/QCMA/coRP circuits to instances of explicitly defined Hamiltonian terms (e.g. Eqs. 9-11, 25-27, and Definitions 3.1, 4.1, 5.1, 6.1), and containment is proved by a separate structural analysis followed by a quantum or classical simulation of the circuit expressed by the TACC; neither direction uses the target QSAT problem as its own witness. Theorem 5, the qudit-to-qubit reduction, is explicitly flagged as nontrivial — the paper concedes in Section 1.2 that the standard embedding is not surjective on instances and says the issue is addressed with 'a more careful mapping' — and the available text does not define the qubit problem as identical to the qudit problem by construction. The absence of the Section 7 proof is an evidentiary gap for the qubit corollaries, not a circular step. The only self-citation (Meiburg 2021) is invoked to state that those earlier constructions are flawed, which is the opposite of loading the argument onto self-citation. The PI/SoPU results concern newly introduced classes whose definitions are independent of the QSAT instances; direct-product and direct-sum hardness follows from the class definitions, which is a legitimate completeness statement rather than a fitted input renamed as a prediction. No load-bearing step reduces, by the paper's own equations or by self-citation, to its own inputs.

Assumptions & free parameters 4 free parameters · 6 assumptions · 4 invented entities

The free parameters are the locally chosen Hilbert-space dimensions and the gate-set degree, all hand-picked to satisfy the proof structure. The axioms are standard complexity-theoretic theorems plus the monogamy principle used to constrain instance shapes. The invented entities are mathematical states/subspaces inside the QSAT constructions, not empirical predictions; they carry no independent evidence outside the paper.

free parameters (4)

LCT-QSAT qudit dimension = 17
The 17-dimensional local Hilbert space is chosen by hand to host logical, endpoint, and clock+auxiliary subspace structure; changing it changes the problem.
SLCT-QSAT qudit dimension = 6
After removing endpoint and auxiliary subspaces, dimension 6 remains; selected to keep ternary logic and clock encoding.
Witnessed/Classical SLCT-QSAT qudit dimension = 8
Adds a 2-dimensional witness (or auxiliary) subspace to the 6-dimensional SLCT space.
Clifford-cyclotomic degree for BQP_1 completeness = 8 (Clifford+T)
The paper proves completeness for BQP_1^{G8} and then uses Rudolph's theorem to extend to any G_{2^l}; the choice G8 is ad hoc to the proof.

assumptions (6)

standard math Kitaev's Geometric Lemma
Used to lower-bound the smallest eigenvalue of H_init + H_prop in soundness proofs (Sections 3.5.1, 5.4.1).
standard math QCMA = QCMA_1 with gate set G8 (Jordan et al.)
Used in Theorem 3 to conclude QCMA-completeness from QCMA_1^{G8}-completeness (Section 5, Section 2.2.1).
standard math BQP_1^{G_{2i}} = BQP_1^{G_{2j}} (Rudolph)
Used in Corollary 1.1 to remove the gate-set dependence from Theorems 1 and 2 (Section 2.2).
standard math Giles-Selinger exact synthesis of Clifford+T unitaries
Used to argue that the eigenvalue-measurement circuits V(Π_i) and C can be implemented perfectly with G8 (Sections 2.3.1, 3.4.2).
domain assumption Monogamy of entanglement
Used in LCT-QSAT to force clock qudits to have at most one neighbor and thus one-dimensional chains (Lemmas 3.2-3.4, Section 3.1). It is a mathematical theorem in this setting, but a physical principle the construction depends on.
standard math The promise gap can be amplified for BQP_1/QCMA/coRP
Relied on to turn inverse-polynomial separations into constant gaps (Section 3.4.4, Section 2.2).

invented entities (4)

Undefined logical state |?⟩
purpose: Added to the logical subspace so that uninitialized data qudits can be set to a harmless state, making many instances trivially satisfiable and keeping membership in BQP_1/coRP
This is a basis state in the constructed Hilbert space, not a physical prediction.
Clock auxiliary subspaces C_A and C_B
purpose: Enable Bell-pair constraints that enforce a linear clock structure via monogamy of entanglement in LCT-QSAT
Mathematical device in the definition of the 17-dimensional qudit.
Endpoint subspace E_C
purpose: Anchors the start/end of active clock chains in LCT-QSAT
Mathematical device; removed in SLCT-QSAT.
Witness/Aux subspace
purpose: Hosts a classical witness or entangled auxiliary register to tune the problem from BQP_1 to QCMA or coRP
Constructed dimension expansion in Witnessed and Classical SLCT-QSAT, not a new physical degree of freedom.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes." pith.science (2026). https://pith.science/paper/O6HZXDAK

@misc{pith2026250607244,
  author       = {Pith},
  title        = {Pith review of: Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/O6HZXDAK}},
  note         = {Machine review of arXiv:2506.07244}
}

abstract

Previously, all known variants of the Quantum Satisfiability (QSAT) problem, i.e. deciding whether a $k$-local ($k$-body) Hamiltonian is frustration-free, could be classified as being either in $\mathsf{P}$; or complete for $\mathsf{NP}$, $\mathsf{MA}$, or $\mathsf{QMA_1}$. Here, we demonstrate new qubit variants of this problem that are complete for $\mathsf{BQP_1}$, $\mathsf{coRP}$, $\mathsf{QCMA}$, $\mathsf{PI(coRP,NP)}$, $\mathsf{PI(BQP_1,NP)}$, $\mathsf{PI(BQP_1,MA)}$, $\mathsf{SoPU(coRP,NP)}$, $\mathsf{SoPU(BQP_1,NP)}$, and $\mathsf{SoPU(BQP_1,MA)}$. Our result implies that a complete classification of quantum constraint satisfaction problems (QCSPs), analogous to Schaefer's dichotomy theorem for classical CSPs, must either include these 13 classes, or otherwise show that some are equal. Additionally, our result showcases two new types of QSAT problems that can be decided efficiently, as well as the first nontrivial $\mathsf{BQP_1}$-complete problem. We first prove there are qudit QSAT problems that are complete for $\mathsf{BQP_1}$, $\mathsf{coRP}$, and $\mathsf{QCMA}$ by re-defining elements of the circuit-to-Hamiltonian transformation. We then show that any QCSP can be reduced to a problem in qubits while maintaining the same complexity - something believed not to be possible classically. The remaining six problems are obtained by considering "sums" and "products" of the first seven QSAT problems. Before this work, the QSAT problems generated in this way resulted in complete problems for $\mathsf{PI}$ and $\mathsf{SoPU}$ classes that were trivially equal to other known classes. We thus commence the study of these new and seemingly nontrivial classes. While [Meiburg, 2021] first sought to prove completeness for the first three classes, we note that his constructions are flawed. Here, we rework them and obtain improvements on the required qudit dimensionality.

Figures

Figures reproduced from arXiv: 2506.07244 by the authors.

**Figure 2.** Representation of a k-QSAT instance which encodes a QMA1 verification circuit U = UL . . . U1. For simplicity, we let U act on four data qubits: two ancilla qubits and two qubits for the witness state. The ancillas are those present in Pinit clauses, and the witness state qubits those that are un-initialized. The ancilla measured at the end of the computation is labeled ans. The leftmost clock particle has a “start”… view at source ↗

**Figure 3.** (a) Example of a typical instance that encodes the computation of a [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗

Figures from the paper (11 more)

**Figure 4.** Figure 4: (a) A simplified graphical representation of a one-dimensional instance built with projectors Π [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]

**Figure 5.** Figure 5: A clock component containing examples of relevant events that may occur in the clock component. [PITH_FULL_IMAGE:figures/full_fig_p020_5.png]

**Figure 6.** Figure 6: Examples of sub-instances whose satisfiability is determined with a quantum algorithm. Top: [PITH_FULL_IMAGE:figures/full_fig_p021_6.png]

**Figure 7.** Figure 7: Circuit C that evaluates whether propagating |ϕt⟩ with Ut+1,0 is the same as propagating with Ut+1,j . Here, Ut+1,0 and Ut+1,j act nontrivially on at most two qubits of the data register. This circuit is equivalent to measuring the eigenvalue of projector Πprop (with u…

**Figure 8.** Figure 8: Diagram summarizing the steps of the proof showing that the Hamiltonian of Eq. ( [PITH_FULL_IMAGE:figures/full_fig_p034_8.png]

**Figure 9.** Figure 9: A clock component of a SLCT-QSAT sub-instance that may be satisfiable. The long double [PITH_FULL_IMAGE:figures/full_fig_p038_9.png]

**Figure 10.** Figure 10: (a) Examples of the only types of Πprop clauses acting on a clock qudit with a Πinit clause that may be satisfiable. We assume that the clock qudit is not present in a Πout clause. Top: one or many undefined Πprop clauses that point away from the qudit. Bottom: at mos…

**Figure 11.** Figure 11: The clock component of Fig [PITH_FULL_IMAGE:figures/full_fig_p042_11.png]

**Figure 12.** Figure 12: (a) Toy example of an input “quantum” instance with a TACC of length [PITH_FULL_IMAGE:figures/full_fig_p045_12.png]

**Figure 13.** Figure 13: Circuits illustrating the equivalence between [PITH_FULL_IMAGE:figures/full_fig_p060_13.png]

**Figure 14.** Figure 14: Left: A clock qudit in a chain with two successors. Right: A clock qudit in a chain with two [PITH_FULL_IMAGE:figures/full_fig_p079_14.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

54 extracted references · 41 canonical work pages

[1]

Kitaev, Alexander Shen, and Mikhail N

Alexei Y. Kitaev, Alexander Shen, and Mikhail N. Vyalyi.Classical and quantum computation. 47. American Mathematical Soc., 2002

work page 2002
[2]

The Complexity of the Local Hamiltonian Problem

Julia Kempe, Alexei Kitaev, and Oded Regev. “The Complexity of the Local Hamiltonian Problem”. In:FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science. Springer, 2004, pp. 372–383.isbn: 978-3-540-24058-7.doi:10.1007/978-3-540-30538-5_31

work page doi:10.1007/978-3-540-30538-5_31 2004
[3]

Sergey Bravyi.Efficient algorithm for a quantum analogue of 2-SAT. 2006. arXiv:quant-ph/0602108 [quant-ph].url:https://arxiv.org/abs/quant-ph/0602108

arXiv 2006
[4]

Quantum 3-SAT isQMA 1-complete

David Gosset and Daniel Nagaj. “Quantum 3-SAT isQMA 1-complete”. In:SIAM Journal on Com- puting45.3 (2016), pp. 1080–1128

work page 2016
[5]

Exact Synthesis of Multiqubit Clifford-Cyclotomic Circuits

Matthew Amy et al. “Exact Synthesis of Multiqubit Clifford-Cyclotomic Circuits”. In:Reversible Com- putation. Ed. by Torben Ægidius Mogensen and Lukasz Mikulski. Cham: Springer Nature Switzerland, 2024, pp. 238–245

work page 2024
[6]

Bessen, and Barbara M

Sergey Bravyi, Arvid J. Bessen, and Barbara M. Terhal.Merlin-Arthur Games and Stoquastic Complex- ity. 2006. arXiv:quant-ph/0611021 [quant-ph].url:https://arxiv.org/abs/quant-ph/0611021

arXiv 2006
[7]

Commutative version of the local Hamiltonian problem and com- mon Eigenspace problem

Sergey Bravyi and Mikhail Vyalyi. “Commutative version of the local Hamiltonian problem and com- mon Eigenspace problem”. In:Quantum Info. Comp.5 (May 2005), pp. 187–215.doi:10 . 26421 / QIC5.3-2

work page 2005
[8]

Quantum Computational Complexity of the N-Representability Problem: QMA Complete

Yi-Kai Liu, Matthias Christandl, and F. Verstraete. “Quantum Computational Complexity of the N-Representability Problem: QMA Complete”. In:Phys. Rev. Lett.98 (11 2007), p. 110503.doi: 10.1103/PhysRevLett.98.110503.url:https://link.aps.org/doi/10.1103/PhysRevLett.98. 110503

work page doi:10.1103/physrevlett.98.110503.url:https://link.aps.org/doi/10.1103/physrevlett.98 2007

Show all 54 references

[9]

Interacting Boson Problems Can Be QMA Hard

Tzu-Chieh Wei, Michele Mosca, and Ashwin Nayak. “Interacting Boson Problems Can Be QMA Hard”. In:Phys. Rev. Lett.104 (4 2010), p. 040501.doi:10.1103/PhysRevLett.104.040501.url:https: //link.aps.org/doi/10.1103/PhysRevLett.104.040501

2010 doi
[10]

Computational complexity of interacting electrons and funda- mental limitations of density functional theory

Norbert Schuch and Frank Verstraete. “Computational complexity of interacting electrons and funda- mental limitations of density functional theory”. In:Nature physics5.10 (2009), pp. 732–735

2009
[11]

The Bose-Hubbard model is QMA-complete

Andrew M Childs, David Gosset, and Zak Webb. “The Bose-Hubbard model is QMA-complete”. In: Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014. Springer. 2014, pp. 308–319

2014
[12]

The complexity of quantum spin systems on a two-dimensional square lattice

Roberto Oliveira and Barbara M. Terhal. “The complexity of quantum spin systems on a two-dimensional square lattice”. In:Quantum Info. Comput.8.10 (Nov. 2008), pp. 900–924.issn: 1533-7146

2008
[13]

The Local Hamiltonian Problem on a Line with Eight States is QMA-Complete

Sean Hallgren, Daniel Nagaj, and Sandeep Narayanaswami. “The Local Hamiltonian Problem on a Line with Eight States is QMA-Complete”. In:Quantum Info. Comput.13.9–10 (2013), pp. 721–750. issn: 1533-7146

2013
[14]

On the Complexity of Two Dimensional Commuting Local Hamiltonians

Dorit Aharonov, Oded Kenneth, and Itamar Vigdorovich. “On the Complexity of Two Dimensional Commuting Local Hamiltonians”. In:13th Conference on the Theory of Quantum Computation, Com- munication and Cryptography (TQC 2018). Ed. by Stacey Jeffery. Vol. 111. Leibniz Internation...

2018 doi
[15]

Sandy Irani and Jiaqing Jiang.Commuting Local Hamiltonian Problem on 2D beyond qubits. 2023. arXiv:2309.04910 [quant-ph].url:https://arxiv.org/abs/2309.04910

2023 arXiv
[16]

Grilo.Complexity of geometrically local stoquastic Hamiltonians

Asad Raza, Jens Eisert, and Alex B. Grilo.Complexity of geometrically local stoquastic Hamiltonians
[17]

Complexity classification of local Hamiltonian problems

Toby Cubitt and Ashley Montanaro. “Complexity classification of local Hamiltonian problems”. In: SIAM Journal on Computing45.2 (2016), pp. 268–316. 71

2016
[18]

On complexity of the quantum Ising model

Sergey Bravyi and Matthew Hastings. “On complexity of the quantum Ising model”. In:Communica- tions in Mathematical Physics349.1 (2017), pp. 1–45

2017
[19]

The complexity of facets (and some facets of complexity)

C.H. Papadimitriou and M. Yannakakis. “The complexity of facets (and some facets of complexity)”. In:Journal of Computer and System Sciences28.2 (Apr. 1984), pp. 244–259.issn: 0022-0000.doi: 10.1016/0022-0000(84)90068-0.url:http://dx.doi.org/10.1016/0022-0000(84)90068-0

1984 doi
[20]

The Boolean Hierarchy I: Structural Properties

Jin-Yi Cai et al. “The Boolean Hierarchy I: Structural Properties”. In:SIAM Journal on Computing 17.6 (Dec. 1988), pp. 1232–1252.issn: 1095-7111.doi:10.1137/0217078.url:http://dx.doi.org/ 10.1137/0217078

1988 doi
[21]

Alex Meiburg.Quantum Constraint Problems can be complete forBQP,QCMA, and more. 2021. arXiv: 2101.08381 [quant-ph].url:https://arxiv.org/abs/2101.08381

2021 arXiv
[22]

Dorian Rudolph.Towards a universal gateset forQMA 1. 2024. arXiv:2411.02681 [quant-ph].url: https://arxiv.org/abs/2411.02681

2024 arXiv
[23]

Quantum mechanical computers

Richard P Feynman. “Quantum mechanical computers.” In:Found. Phys.16.6 (1986), pp. 507–532

1986
[24]

Explicitly correlated electronic structure calcula- tions with transcorrelated matrix product operators

Alberto Baiardi, Micha l Lesiuk, and Markus Reiher. “Explicitly correlated electronic structure calcula- tions with transcorrelated matrix product operators”. In:Journal of Chemical Theory and Computation 18.7 (2022), pp. 4203–4217

2022
[25]

Quantum simulation of three-body interactions in weakly driven quantum systems

Francesco Petiziol et al. “Quantum simulation of three-body interactions in weakly driven quantum systems”. In:Phys. Rev. Lett.126.25 (2021), p. 250504

2021
[26]

J. H. Busnaina et al.Native Three-Body Interactions in a Superconducting Lattice Gauge Quantum Simulator. 2025. arXiv:2501.13383 [quant-ph].url:https://arxiv.org/abs/2501.13383

2025 arXiv
[27]

Chuang et al.Observation of a Halo Trimer in an Ultracold Bose-Fermi Mixture

Alexander Y. Chuang et al.Observation of a Halo Trimer in an Ultracold Bose-Fermi Mixture. 2024. arXiv:2411.04820 [cond-mat.quant-gas].url:https://arxiv.org/abs/2411.04820

2024
[28]

Probing Few-Body Nuclear Dynamics via 3H and 3He (e, e ′ p)pn Cross-Section Measurements

R. Cruz-Torres et al. “Probing Few-Body Nuclear Dynamics via 3H and 3He (e, e ′ p)pn Cross-Section Measurements”. In:Phys. Rev. Lett.124 (21 2020), p. 212501.doi:10 . 1103 / PhysRevLett . 124 . 212501.url:https://link.aps.org/doi/10.1103/PhysRevLett.124.212501

2020 doi
[29]

Two Combinatorial MA-Complete Problems

Dorit Aharonov and Alex B. Grilo. “Two Combinatorial MA-Complete Problems”. In:12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Ed. by James R. Lee. Vol. 185. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl...

2021 doi
[30]

Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems

Stephen P. Jordan et al. “Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems”. In:Quantum Info. Comput.12(5-6) (2012), pp. 461–471

2012
[31]

The complexity of satisfiability problems

Thomas J. Schaefer. “The complexity of satisfiability problems”. In:Proceedings of the Tenth Annual ACM Symposium on Theory of Computing. STOC ’78. New York, NY, USA: Association for Computing Machinery, 1978, pp. 216–226.isbn: 9781450374378.doi:10 . 1145 / 800133 . 804350.url...

1978
[32]

A proof of the CSP dichotomy conjecture

Dmitriy Zhuk. “A proof of the CSP dichotomy conjecture”. In:Journal of the ACM (JACM)67.5 (2020), pp. 1–78

2020
[33]

Quantum computations: algorithms and error correction

A Yu Kitaev. “Quantum computations: algorithms and error correction”. In:Russian Mathematical Surveys52.6 (1997), p. 1191

1997
[34]

Exact synthesis of multiqubit Clifford+ T circuits

Brett Giles and Peter Selinger. “Exact synthesis of multiqubit Clifford+ T circuits”. In:Physical Review A87.3 (2013), p. 032332

2013
[35]

Dorit Aharonov and Tomer Naveh.Quantum NP - A Survey. 2002. arXiv:quant - ph / 0210077 [quant-ph].url:https://arxiv.org/abs/quant-ph/0210077

2002 arXiv
[36]

On perfect completeness for QMA

Scott Aaronson. “On perfect completeness for QMA”. In:Quantum Info. Comput.9 (2009), pp. 81–89

2009
[37]

The complexity of stoquastic local Hamiltonian problems

Sergey Bravyi et al. “The complexity of stoquastic local Hamiltonian problems”. In:Quantum Info. Comput.8.5 (2008), pp. 361–385.issn: 1533-7146. 72

2008
[38]

Quantum hamiltonian complexity

Sevag Gharibian et al. “Quantum hamiltonian complexity”. In:Foundations and Trends in Theoretical Computer Science10.3 (2015), pp. 159–282

2015
[39]

Ground state connectivity of local Hamiltonians

Sevag Gharibian and Jamie Sikora. “Ground state connectivity of local Hamiltonians”. In:International Colloquium on Automata, Languages, and Programming. Springer. 2015, pp. 617–628

2015
[40]

Two QCMA-complete problems

Pawel Wocjan, Dominik Janzing, and Thomas Beth. “Two QCMA-complete problems”. In:Quantum Info. Comput.3.6 (2003), pp. 635–643.issn: 1533-7146

2003
[41]

QCMA hardness of ground space connectivity for commuting Hamiltonians

David Gosset, Jenish C. Mehta, and Thomas Vidick. “QCMA hardness of ground space connectivity for commuting Hamiltonians”. In:Quantum1 (2017), p. 16

2017
[42]

Ying-hao Chen.2-Local Hamiltonian with Low Complexity is QCMA. 2019. arXiv:1909.03787 [cs.CC]. url:https://arxiv.org/abs/1909.03787

2019 arXiv
[43]

PP is closed under intersection

Richard Beigel, Nick Reingold, and Daniel Spielman. “PP is closed under intersection”. In:Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC ’91. STOC ’91. ACM Press, 1991, pp. 1–9.doi:10.1145/103418.103426.url:http://dx.doi.org/10.1145/103418. 103426

1991
[44]

The complexity of satisfiability problems: Refining Schaefer’s theorem

Eric Allender et al. “The complexity of satisfiability problems: Refining Schaefer’s theorem”. In:Journal of Computer and System Sciences75.4 (June 2009), pp. 245–254.issn: 0022-0000.doi:10.1016/j. jcss.2008.11.001.url:http://dx.doi.org/10.1016/j.jcss.2008.11.001

2009 doi
[45]

Undirected connectivity in log-space

Omer Reingold. “Undirected connectivity in log-space”. In:Journal of the ACM55.4 (Sept. 2008), pp. 1–24.issn: 1557-735X.doi:10.1145/1391289.1391291.url:http://dx.doi.org/10.1145/ 1391289.1391291

2008
[46]

On truth-table reducibility to SAT

Samuel R. Buss and Louise Hay. “On truth-table reducibility to SAT”. In:Information and Compu- tation91.1 (Mar. 1991), pp. 86–102.issn: 0890-5401.doi:10.1016/0890- 5401(91)90075- d.url: http://dx.doi.org/10.1016/0890-5401(91)90075-D

1991 doi
[47]

The strong exponential hierarchy collapses

Lane A. Hemachandra. “The strong exponential hierarchy collapses”. In:Journal of Computer and System Sciences39.3 (Dec. 1989), pp. 299–322.issn: 0022-0000.doi:10.1016/0022-0000(89)90025- 1.url:http://dx.doi.org/10.1016/0022-0000(89)90025-1

1989 doi
[48]

Chris Cade, Marten Folkertsma, and Jordi Weggemans.Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States. 2024. arXiv:2207.10097 [quant-ph]. url:https://arxiv.org/abs/2207.10097. A Proofs of Lemmas: Section 3 Lemma 3.1(Single-t...

2024 arXiv
[50]

If they are well-defined or undefined and includec 0
[51]

If they are well-defined and includec T
[52]

Proof.Case (1) is trivial

If they are undefined, includec T , and point towards it. Proof.Case (1) is trivial. By assumption,c 0 is present in a well-defined clause of the TACC that points away from it. This is the same setting as in Lemma 4.4, which concludes that the instance is unsatisfiable. Consid...
[53]

If they are well-defined or undefined, and point towardsc d
[54]

Proof.The first case was already covered in Lemma 4.3

If they are well-defined and point away fromc d. Proof.The first case was already covered in Lemma 4.3. For the second case, recall thatc d must be|a⟩ at all times. Satisfying the Π prop clause requires the active state to shift towards the other clock qudit, leavingc d to be ...
[2024]

arXiv:2407.15499 [quant-ph].url:https://arxiv.org/abs/2407.15499

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Kitaev, Alexander Shen, and Mikhail N

Alexei Y. Kitaev, Alexander Shen, and Mikhail N. Vyalyi.Classical and quantum computation. 47. American Mathematical Soc., 2002

work page 2002

[2] [2]

The Complexity of the Local Hamiltonian Problem

Julia Kempe, Alexei Kitaev, and Oded Regev. “The Complexity of the Local Hamiltonian Problem”. In:FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science. Springer, 2004, pp. 372–383.isbn: 978-3-540-24058-7.doi:10.1007/978-3-540-30538-5_31

work page doi:10.1007/978-3-540-30538-5_31 2004

[3] [3]

Sergey Bravyi.Efficient algorithm for a quantum analogue of 2-SAT. 2006. arXiv:quant-ph/0602108 [quant-ph].url:https://arxiv.org/abs/quant-ph/0602108

arXiv 2006

[4] [4]

Quantum 3-SAT isQMA 1-complete

David Gosset and Daniel Nagaj. “Quantum 3-SAT isQMA 1-complete”. In:SIAM Journal on Com- puting45.3 (2016), pp. 1080–1128

work page 2016

[5] [5]

Exact Synthesis of Multiqubit Clifford-Cyclotomic Circuits

Matthew Amy et al. “Exact Synthesis of Multiqubit Clifford-Cyclotomic Circuits”. In:Reversible Com- putation. Ed. by Torben Ægidius Mogensen and Lukasz Mikulski. Cham: Springer Nature Switzerland, 2024, pp. 238–245

work page 2024

[6] [6]

Bessen, and Barbara M

Sergey Bravyi, Arvid J. Bessen, and Barbara M. Terhal.Merlin-Arthur Games and Stoquastic Complex- ity. 2006. arXiv:quant-ph/0611021 [quant-ph].url:https://arxiv.org/abs/quant-ph/0611021

arXiv 2006

[7] [7]

Commutative version of the local Hamiltonian problem and com- mon Eigenspace problem

Sergey Bravyi and Mikhail Vyalyi. “Commutative version of the local Hamiltonian problem and com- mon Eigenspace problem”. In:Quantum Info. Comp.5 (May 2005), pp. 187–215.doi:10 . 26421 / QIC5.3-2

work page 2005

[8] [8]

Quantum Computational Complexity of the N-Representability Problem: QMA Complete

Yi-Kai Liu, Matthias Christandl, and F. Verstraete. “Quantum Computational Complexity of the N-Representability Problem: QMA Complete”. In:Phys. Rev. Lett.98 (11 2007), p. 110503.doi: 10.1103/PhysRevLett.98.110503.url:https://link.aps.org/doi/10.1103/PhysRevLett.98. 110503

work page doi:10.1103/physrevlett.98.110503.url:https://link.aps.org/doi/10.1103/physrevlett.98 2007