Efficient algorithm for a quantum analogue of 2-SAT

Sergey Bravyi

REVIEW

Efficient algorithm for a quantum analogue of 2-SAT

Sergey Bravyi

Quantum Physics · Submitted 14 Feb 2006 · 9 references

Pith's verdict: Both claims hold up: the 2-SAT algorithm is correct, and the real technical contribution is the four-dimensional clock that pushes QMA_1-hardness down to k=4.

T0 · AI review

How this review was made: An AI referee (selfhosted/deepseek-v4.1-flash) read the paper on November 11, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 7 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv IDquant-ph/0602108 (version 1)

Pith IDIGKHLIC2, Pith's permanent record of this paper and its review

CitationSergey Bravyi. "Efficient algorithm for a quantum analogue of 2-SAT." arXiv:quant-ph/0602108 (2006). https://pith.science/paper/IGKHLIC2

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Two results here, and both survive scrutiny. Quantum 2-SAT is in P, and quantum k-SAT is QMA_1-complete for every k ≥ 4. The second is the sharper technical achievement; the first is the one people cite. Neither is overstated in the abstract, which is refreshing given how often this genre oversells. The stress-test's degeneracy worry about Lemma 2 does not land, and I'll say why below. The genuine soft spot is smaller than that and doesn't touch the structural claims. What's actually new: Lemma 1, the local rule ω = φ ε θ, is the engine. It lets you derive a constraint on (a,c) from constraints on (a,b) and (b,c), and it's proved cleanly from antisymmetry of ε. The rank trichotomy — rank 3 drops two qubits, rank 2 merges into one logical qubit, rank ≤ 1 goes homogeneous — is what makes the induction work, and it's the part I'd hand a student. Lemma 2's constructive completeness argument (a complete homogeneous instance always has a product solution, found in linear time) is the load-bearing piece and is written out in full. On the hardness side, the real content is the clock: four-dimensional clock particles with unborn/active-1/active-2/dead phases let the history state be pinned by 4-local projectors, improving Kitaev's k = 5. That's the contribution and the paper says so. On the stress-test: choosing an arbitrary ψ(1) is safe. For any edge (1,a), φ(1,a) is nonzero, so ε φ(1,a)^T is invertible; ψ(a) = 0 iff ψ(1) = 0. Any nonzero seed gives nonzero neighbors, and the recursion on V_far inherits the same property. No silent zero-vector failure. The real soft spot is the arithmetic model: the O(n^4) claim lives over exact algebraic numbers, and the bit-complexity of the rank and proportionality tests is cited to [5,6] rather than bounded. That's a genuine gap, but a standard one for 2006 and not load-bearing. The O(n^3)-probe termination is sketched rather than proved, though the argument is easy (each probe adds an edge or ends the loop; at most n^2 edges). The paper is also honest about what it leaves open — quantum 3-SAT — and Remark 2 correctly flags that dropping the gap promise gives C=P-hardness. Who it's for: anyone in Hamiltonian complexity; it's a standard reference and deserves a serious referee.

Referee report

Significance

If correct, the results are a clean and useful contribution. The 2-SAT algorithm shows that the natural quantum generalization of 2-SAT is no harder than its classical counterpart, which is a genuinely surprising and clarifying statement given that the 2-local Hamiltonian problem is QMA-complete. The k >= 4 QMA_1-completeness result, reducing the locality from the standard 5 to 4, is a meaningful technical improvement and the clock construction is explicit enough to be checked line by line. The paper is also careful about the precision promise needed to make the k-SAT definition meaningful, and it explicitly flags the exact-arithmetic model in the Introduction remark, which is the right way to state a result of this kind. The work is self-contained: Lemma 1 is proved from antisymmetry of epsilon, Lemma 2 is a full constructive proof, and the spectral-gap bound in Lemma 4 is correctly attributed to the published Kitaev-Shen-Vyalyi book [1].

Major objections (3)

[Section II C, proof of Lemma 2, Eq. (8) and the recursion on V_far] The proof of Lemma 2 begins by choosing an arbitrary psi(1) and then sets psi(a) = epsilon (phi(1,a))^T psi(1) for all neighbours a of vertex 1. The verification that the incident constraints are satisfied is correct for any psi(1), but the resulting product assignment is nonzero only if the constructed one-qubit states are nonzero. If the chosen psi(1) happens to lie in the kernel of (phi(1,a))^T for every neighbour a, then every psi(a) vanishes and the recursion on V_far produces the zero vector, which satisfies all constraints trivially and is not a valid satisfying assignment. The manuscript does not argue that a nonzero seed can always be chosen, nor that the arbitrary choices made at each recursive step can be made non-degenerately. This is load-bearing for the correctness of the algorithm, since the algorithm's Output 2 is a product state and the zero vector is not a state. A short argument that the bad seeds form a proper algebraic subset (or an explicit tie-breaking rule) would close the gap.
[Section II, running-time claim and Introduction remark on exact arithmetic] The abstract and Section II claim a polynomial running time, with O(n^4) quoted in the Introduction and O(n^3) per reduction step in Section II. The algorithm's case analysis in Section II C requires exact rank computations, exact proportionality tests on 2x2 matrices, and exact zero tests on products phi * epsilon * theta. The Introduction remark asserts that linear algebra over algebraic numbers of bounded degree can be solved efficiently, citing books [5,6], but the bit-complexity of the specific tests used here, in particular the growth of the degree of the algebraic numbers under repeated multiplication in Eq. (7), is not bounded in the paper. Since the polynomial-time claim is the paper's headline result, a sentence quantifying the bit-model cost, or an explicit restriction of the claim to the arithmetic model, would make the claim precise. As written, the reader must reconstruct which model the O(n^4) bound refers to.
[Section II, Subsections A and B (rank-3 and rank-2 reductions)] The reductions for rank-3 and rank-2 projectors are stated correctly in outline, but the manuscript does not verify that the new instance produced by these reductions remains an instance of the same problem class with the stated rank bounds, nor that repeated application terminates with a well-defined measure. In Subsection A the new constraints Q_d on the remaining qubits are self-adjoint but their ranks are not analysed; in Subsection B the merged-qubit operators Q_{c,g} = V^dagger Pi_{a,g} V are self-adjoint but again their ranks are not bounded. Since the algorithm's inductive structure depends on eventually reaching a homogeneous instance, a short argument that the number of qubits strictly decreases at each non-homogeneous step (which is plausible but not spelled out) would make the termination claim self-contained.

Minor objections (7)

[Abstract] The abstract says quantum k-SAT is 'complete in the complexity class QMA with one-sided error' for k >= 4, while the body (Lemma 4 and the Introduction) states QMA_1-completeness. The two phrasings should be made consistent, and QMA_1 should be defined in the abstract or referenced forward.
[Introduction, definition of quantum k-SAT] The promise is stated as 'either there exists a state with Pi_S |Psi> = 0 for all S, or sum_S <Psi|Pi_S|Psi> >= epsilon for all |Psi>'. The second condition should be written with the quantifier explicit, e.g. 'for all |Psi>' as a lower bound on the sum, and the relation between epsilon and the polynomial gap in Definition 3 should be stated once.
[Section III, Eq. (16) and the legal clock states] The example with L = 4 lists eight legal clock states, but the general definition below it allows 2L states; the text should say explicitly that the L = 4 list is illustrative and that the general case has 2L states, to avoid the impression that the construction is restricted to four gates.
[Section III, Eq. (25) and the decomposition of H] The decomposition H = H_legal ⊗ H_comp ⊕ H_legal^perp ⊗ H_comp is stated as invariant under H, but the individual terms H_init, H_prop, H_out are only shown to have the stated restrictions after projection by Pi. A sentence noting that each term commutes with the projector onto H_legal ⊗ H_comp, or that the restriction argument is valid because the terms are block-diagonal in this decomposition, would help the reader.
[Appendix A, Lemma 5] The proof invokes the standard decomposition into two-level unitaries and the AND-computation trick, but the size bound poly(k) * 2^{2k} should be derived explicitly, since the exponent appears in the statement and is used in Lemma 3 to argue that U_S has a polynomial-size circuit for constant k.
[Appendix B, Lemma 6] The proof of the converse direction uses the topological ordering of the SCC graph and the involution S -> not S; the sentence 'for any vertex S of G there exists a unique vertex not S' should note that this uniqueness relies on the symmetry of the implication graph under negation, which is stated but could be made more explicit.
[References] Reference [7] is a private communication and is cited in Remark 1 for a 3-local clock construction; since it is unpublished, either a published alternative should be cited or the remark should be softened to a conjecture.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Quantum 2-SAT is no harder than its classical counterpart: a polynomial-time classical algorithm decides whether an n-qubit state can simultaneously avoid a list of forbidden two-qubit subspaces, while the k-qubit version becomes hard only,

The reading

The paper asks what happens to the classical 2-SAT problem when bits become qubits. In the quantum version, each clause on a pair of bits is replaced by a two-qubit projector, and a satisfying assignment is an $n$-qubit pure state $|Psiangle$ whose every two-qubit reduced density matrix is orthogonal to the corresponding forbidden subspace, i.e. $Pi_{a,b}|Psiangle = 0$ for all pairs. The author gives a classical algorithm that decides this in time $O(n^4)$, generalizing the standard linear-time classical 2-SAT algorithm, and then shows that the $k$-qubit version with a polynomial precision promise is complete for QMA with one-sided error for every constant $k geq 4$. The pair of results draws a sharp line: exact satisfiability of two-qubit quantum constraints is tractable, but four-qubit constraints already encode the full power of quantum verification.

What carries the argument

The load-bearing device is Lemma 1: if a rank-three tensor $psi$ obeys $varphi^{alpha,beta}psi_{alpha,beta,gamma} = 0$ and $theta^{beta,gamma}psi_{alpha,beta,gamma} = 0$, then it also obeys $omega^{alpha,gamma}psi_{alpha,beta,gamma} = 0$ with $omega = varphi, epsilon, theta$, where $epsilon$ is the antisymmetric two-index tensor. In words, two constraints sharing a qubit imply a third constraint on the outer pair, obtained by contracting through $epsilon$. This is the quantum shadow of the classical resolution step that makes 2-SAT easy, and it is what lets the algorithm generate the missing edges of the constraint graph without ever writing down an exponentially large state. The completion of the argument is Lemma 2, which shows that once no new constraint can be generated, a product satisfying assignment can be built by assigning one vertex, propagating to its neighbours via $psi^{(a)} = epsilon (varphi^{(1,a)})^{T} psi^{(1)}$, and recursing on the far set.

Extended reading notes

Core claim

The central claim is that quantum 2-SAT is decidable in classical polynomial time. The algorithm reduces an $n$-qubit instance to an equivalent $(n-1)$- or $(n-2)$-qubit instance in $O(n^3)$ time, then iterates. It does this by inspecting the rank $r_{a,b}$ of each projector: rank 4 means no satisfying assignment exists; rank 3 pins qubits $a,b$ to a fixed product state and removes them; rank 2 lets qubits $a$ and $b$ be merged into one logical qubit via an isometry $V$; and when all ranks are at most 1 the instance is called homogeneous and the algorithm instead generates new constraints using a local composition rule. The process either shrinks the qubit count or reaches a complete set of constraints, and the author proves (Lemma 2) that every homogeneous instance with a complete set of constraints is satisfiable, with a satisfying assignment that is a product of one-qubit states. The second claim is that quantum $k$-SAT with the stated promise gap is QMA$_1$-complete for $k geq 4$, proved by building a 4-qubit-projector Hamiltonian whose zero-energy subspace is spanned by computational history states of an arbitrary verifying circuit.

Load-bearing premise

The polynomial-time claim is made in an exact-arithmetic model: the algorithm must compute ranks of two-qubit projectors and test whether $2 times 2$ matrices are proportional, and the paper asserts without bounding that this linear algebra over algebraic numbers of bounded degree is efficient, so the $O(n^4)$ step count is only a polynomial-time bound if that arithmetic overhead is polynomial too.

Editorial extensions

If this is right

Exact satisfiability of a family of two-qubit quantum constraints can be decided on a classical machine in polynomial time, so no quantum computer is needed for this fragment of the local Hamiltonian problem.
Any satisfiable homogeneous quantum 2-SAT instance admits a satisfying assignment that is a product of one-qubit states, so entanglement is never required to satisfy rank-one two-qubit constraints exactly.
Quantum $k$-SAT with a polynomial promise gap is QMA$_1$-complete for all constant $k geq 4$, so four-qubit projectors already suffice to encode any one-sided-error quantum verification procedure.
The reduction from $k=5$ to $k=4$ is achieved with a clock register of four-dimensional particles paired into qubits, giving an explicit 4-local projector decomposition of the history-state Hamiltonian.

Reading between the lines

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

The tractability boundary sits exactly where classical SAT's does, between 2 and 3, but the paper leaves quantum 3-SAT open; a reader can test whether the rank-merging technique of Section II can be pushed to rank-two three-qubit projectors, or whether a 3-local history-state construction exists.
If quantum 2-SAT is in P while 2-local Hamiltonian is QMA-complete, the hardness of the local Hamiltonian problem must live in the ground-state-energy promise rather than in exact satisfiability, which suggests checking whether the QMA-hardness construction survives restriction to frustration-free instances with exactly zero ground energy.
The product-state conclusion for complete instances is a structural statement that could be probed numerically: for small $n$, search for a satisfiable homogeneous instance whose every satisfying state is entangled.
The QMA$_1$ completeness result depends on a promise gap $epsilon = 1/n^{alpha}$; without that gap the paper's own Remark 2 notes the problem becomes hard for the polynomial hierarchy, so the gap is doing real work rather than bookkeeping.

Original abstract

Complexity of a quantum analogue of the satisfiability problem is studied. Quantum k-SAT is a problem of verifying whether there exists n-qubit pure state such that its k-qubit reduced density matrices have support on prescribed subspaces. We present a classical algorithm solving quantum 2-SAT in a polynomial time. It generalizes the well-known algorithm for the classical 2-SAT. Besides, we show that for any k>=4 quantum k-SAT is complete in the complexity class QMA with one-sided error.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 4,138 input tokens.

What the abstract itself states, as probabilities: claims first 0.08 · states limitation 0.25 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.02 · states quantitative result 0.70 · compares with prior results 0.81 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

Complexity of a quantum analogue of the satisfiability problem is studied. Quantum k-SAT is a problem of verifying whether there exists n-qubit pure state such that its k-qubit reduced density matrices have support on prescribed subspaces. We present a classical algorithm solving quantum 2-SAT in a polynomial time. It generalizes the well-known algorithm for the classical 2-SAT. Besides, we show that for any k>=4 quantum k-SAT is complete in the complexity class QMA with one-sided error.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Complexity of a quantum analogue of the satisfiability problem is studied.	background 0.76	0.48	0.05	asserted 0.72
s1	Quantum k-SAT is a problem of verifying whether there exists n-qubit pure state such that its k-qubit reduced density matrices have support on prescribed subspaces.	background 1.00	0.10	0.04	asserted 1.00
s2	We present a classical algorithm solving quantum 2-SAT in a polynomial time.	contribution 0.82	0.96	0.81	asserted 1.00
s3	It generalizes the well-known algorithm for the classical 2-SAT.	interpretation 0.72	0.69	0.08	asserted 1.00
s4	Besides, we show that for any k>=4 quantum k-SAT is complete in the complexity class QMA with one-sided error.	result 0.92	0.92	0.23	asserted 1.00

What kind of paper the classifier reports this is: method or tool 0.67 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Works cited (9)

[1]

A. Kitaev, A. Shen, and M. Vyalyi “Classical and quantum computation” , Graduate Studies in Mathematics, Vol. 47, American Mathematical Society (2002)

View on Pith 2002
[2]

J. Kempe, A. Kitaev, and O. Regev “The complexity of the local Hamiltonian problem” , quant-ph/0406180

View on Pith Pith review arXiv
[3]

B. Aspvall, M. Plass, and R. Tarjan “A linear-time algorithm for testing the truth of certain qu antiﬁed boolean formulas” , Info. Proc. Letters, Vol. 8, Iss. 3, p. 121-123 (1979)

View on Pith 1979
[4]

D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev “Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation” , Proceedings of 45th FOCS (2004), quant-ph/0405098

View on Pith Pith review arXiv 2004
[5]

A. Aho, J. Hopcroft, and J. Ullman “The Design and Analysis of Computer Algorithms” , Addison-Wesley Reading, Mas- sachusetts (1974)

View on Pith 1974
[6]

D. Bini and V.Y. Pan “Polynomial and matrix computation ” , Vol. 1, Birkh¨ auser, Boston, Cambridge, MA (1994)

View on Pith 1994
[7]

David DiVincenzo, private communication

View on Pith
[8]

A. Barenco, C. H. Bennett, R. Cleve, D. DiVincenzo, N. Mar golus, P. Shor, T. Sleator, J. Smolin, H. Weinfurter “Elementary gates for quantum computation” , Phys. Rev. A52, p. 3457 (1995)

View on Pith 1995
[9]

S. Fenner, F. Green, S. Homer, R. Pruim “Determining Acceptance Possibility for a Quantum Computa tion is Hard for the Polynomial Hierarchy”, quant-ph/9812056. 12 APPENDIX A: QUANTUM CIRCUITS OVER A FIXED FIELD Lemma 5 Let V be a unitary operator acting on k qubits. Suppose that matrix elements of V in the standard basis belong to a ﬁeld F ⊂ C. Then V can...

View on Pith Pith review arXiv

Forward citations

Cited by 8 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Zero-Energy Problems for Supersymmetric Hamiltonians on a Chain Are $\mathrm{QMA}_1$-Complete
quant-ph 2026-08 accept novelty 8.0 of 10

Exact zero-energy problems for supersymmetric Hamiltonians on a one-dimensional chain are QMA1-complete for both Hermitian and nilpotent supercharge formulations.
${\sf QMA}={\sf QMA}_1$ with an infinite counter
quant-ph 2025-06 conditional novelty 8.0 of 10

With an infinite counter register as part of the witness, QMA and its perfect-completeness variant QMA_1 become the same complexity class, and a finite truncation gives doubly-exponential completeness amplification.
Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
quant-ph 2025-06 conditional novelty 8.0 of 10

New QSAT variants on qubits and qudits are complete for BQP_1, coRP, QCMA and six PI/SoPU classes, implying any classification of strong quantum CSPs must contain at least 13 classes unless some collapse.
The Fermionic Cohomology Problem on the Full Fock Space Is $\mathrm{QMA}_1$-Complete
quant-ph 2026-09 conditional novelty 7.0 of 10

The total fermionic cohomology problem on the full Fock space is QMA1-complete.
A Slice-Rank Drift Bound for Random Quantum $k$-SAT
quant-ph 2026-07 accept novelty 7.0 of 10

Random quantum k-SAT is unsatisfiable above density α⋆(k)∼2^k/k, improving the prior O(2^k) upper bound by a factor of order k, with α⋆(3)≈1.947.

Show 3 more citing papers

State Engineering of Unsteerable Hamiltonians
quant-ph 2025-05 conditional novelty 7.0 of 10

Frustrated local Hamiltonians can sometimes be steered into their ground-state manifold via discrete local measurement steps, and when they cannot, local steering is bounded by a 'glass floor' set by the smallest eige...
Heisenberg limited quantum algorithm for estimating the fidelity susceptibility
quant-ph 2025-09 conditional novelty 6.0 of 10

A quantum algorithm estimates fidelity susceptibility in O~(1/epsilon) queries using a resolvent reformulation, achieving Heisenberg-limited precision.
Noncontextual Pauli Hamiltonians
quant-ph 2025-06 conditional novelty 5.0 of 10

Noncontextual Pauli Hamiltonians have support up to 2^(n+1), block-diagonal spectra, and eigenstates with stabilizer rank linear in the number of qubits.

How later papers used it

55 later papers cite it

Evidence: substantial. 53 of the citing papers share no author with it, and 11 of those carry a confident label from Pith's citation classifier.

Pith read 28 of the 134 citing sentences, choosing only those whose citation markers point at this paper alone, and wrote the paraphrases from them. The summary, the counts, the evidence level, the links and the quotes come from code; the summary counts the papers listed below. A later paper is listed under a label when Pith's citation classifier gives one of its sentences that label at probability 0.8 or more (0.95 for support), Pith's reading finds that the citing paper itself did it, and a second check confirms the paraphrase against the sentence. This section lists uses only. It does not list criticism or disagreement, so their absence here says nothing about how the paper has been received. Papers that share an author with this one are listed apart, under "By the same authors". A quote is the citing authors' own sentence, shown when their paper's licence is CC BY, CC BY-SA or CC0. JSON

2 later papers by other authors are listed below: 2 used its method or tool.

Uses its method or tool 2 of 4 papers with this label

Employed this paper's homogeneous 2-SAT and completion techniques to finish the proof when all of the (ρ_ij) are of rank 3 or 4.

No-go Theorem for One-way Quantum Computing on Naturally Occurring Two-level Systems (2010) · 1.00 · paraphrased: the licence does not allow quoting
Following Ref. [ref] , given constraints $⟨η_u,v|, ⟨η_v,w|$ for $u w$ which both act on a qubit $v ∈V$, we may infer a further implicit constraint $⟨η̃_u,w|$, such that $⟨η̃_u,w| ρ_u,w = 0$ whenever both $⟨η_u,v| ρ_u,v = 0$ and $⟨η_v,w| ρ_v,w = 0$ hold: [equation] We may renormalise $⟨η̃_u,w|$ so that $η̃_u,wη̃_u,w = 1$, provided that the operator is non-zero.

Difficult instances of the counting problem for 2-quantum-SAT are very atypical (2014) · Constraint induction · 0.92

How the literature uses it

54 arXiv papers cite this in 133 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 71 sentences without a confident label

Contests it 1 paper

The situation is further complicated by the fact that this technical point was treated incorrectly in reference [ref] due to an error in the proof of Lemma 5 [ref] .

Quantum 3-SAT is QMA1-complete · Definitions and Overview · contest 0.93

Uses its method or tool 4 papers

We will now use the clock construction from [ref] to construct a mapping from our modified verification circuit to quantum $(k,s)$-$$.

Clique Homology is QMA1-hard · Quantum $(k,s)$-$$ is $_1$ hard · 1.00
Then relation is given by $ω_α,γ = ϕ_α,β ϵ_β,δ θ_δ,γ,$ where $ϵ= 01-10$ and the summation of repeated indices is implicit [ref] .

No-go Theorem for One-way Quantum Computing on Naturally Occurring Two-level Systems · Introduction · 0.84
Following Ref. [ref] , given constraints $⟨η_u,v|, ⟨η_v,w|$ for $u w$ which both act on a qubit $v ∈V$, we may infer a further implicit constraint $⟨η̃_u,w|$, such that $⟨η̃_u,w| ρ_u,w = 0$ whenever both $⟨η_u,v| ρ_u,v = 0$ and $⟨η_v,w| ρ_v,w = 0$ hold: [equation] We may renormalise $⟨η̃_u,w|$ so that $η̃_u,wη̃_u,w = 1$, provided that the operator is non-zero.

Difficult instances of the counting problem for 2-quantum-SAT are very atypical · Constraint induction · 0.92

Compares with it 4 papers

This is a much simpler form than the recursive construction in Ref. [ref] .

No-go Theorem for One-way Quantum Computing on Naturally Occurring Two-level Systems · Introduction · 1.00
This formulation makes it clear that we are dealing with a quantum version of the Boolean satisfiability problem—distinct from the QSAT problem introduced by Bravyi [ref] —which is undecidable as per Theorem [ref].

Quantum logic is undecidable · Introduction · 0.86
Also, in [ref] , one considers a quantum analogue of 2-SAT, where we seek a state $|ψ⟩$ whose local density matrices have support on prescribed subspaces.

The Complexity of the Consistency and N-representability Problems for Quantum States · Introduction · 0.90

Cites it as support 2 papers

Behind our considerations lies the result that when $G$ is SAT, we can always find a satisfying product state [ref] .

Classical-Quantum Mixing in the Random 2-Satisfiability Problem · Introduction · 0.99
It turns out that for $2$-QSAT (but not for $2$-LH!), this latter assumption is wrong — we can efficiently write down the ground state of a frustration-free $2$-local Hamiltonian [ref] .

The 7 faces of quantum NP · Bashful: QMA with perfect completeness ($$) · 0.99

Cites it as background 33 papers

In this section, we review the complexity class $_1$ and quantum $k$-$$, the canonical $_1$-complete problem [ref] .

Clique Homology is QMA1-hard · $_1$ and Quantum $k$-$$ · 0.98
In Ref. [ref] , it was proved that the quantum analog of the $2$-SAT problem, which asks whether a set of projections on two-qubit subsystems has a simultaneous ground state, is also efficiently solvable on a classical computer.

No-go Theorem for One-way Quantum Computing on Naturally Occurring Two-level Systems · Introduction · 0.80
When there is no projection of rank larger than $1$, we are dealing with the homogeneous case [ref] .

Complete Characterization of the Ground Space Structure of Two-Body Frustration-Free Hamiltonians for Qubits · Introduction · 0.92

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

A. Kitaev, A. Shen, and M. Vyalyi “Classical and quantum computation” , Graduate Studies in Mathematics, Vol. 47, American Mathematical Society (2002)

View on Pith 2002

[2] [2]

J. Kempe, A. Kitaev, and O. Regev “The complexity of the local Hamiltonian problem” , quant-ph/0406180

View on Pith Pith review arXiv

[3] [3]

B. Aspvall, M. Plass, and R. Tarjan “A linear-time algorithm for testing the truth of certain qu antiﬁed boolean formulas” , Info. Proc. Letters, Vol. 8, Iss. 3, p. 121-123 (1979)

View on Pith 1979

[4] [4]

D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev “Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation” , Proceedings of 45th FOCS (2004), quant-ph/0405098

View on Pith Pith review arXiv 2004

[5] [5]

A. Aho, J. Hopcroft, and J. Ullman “The Design and Analysis of Computer Algorithms” , Addison-Wesley Reading, Mas- sachusetts (1974)

View on Pith 1974

[6] [6]

D. Bini and V.Y. Pan “Polynomial and matrix computation ” , Vol. 1, Birkh¨ auser, Boston, Cambridge, MA (1994)

View on Pith 1994

[7] [7]

David DiVincenzo, private communication

View on Pith

[8] [8]

A. Barenco, C. H. Bennett, R. Cleve, D. DiVincenzo, N. Mar golus, P. Shor, T. Sleator, J. Smolin, H. Weinfurter “Elementary gates for quantum computation” , Phys. Rev. A52, p. 3457 (1995)

View on Pith 1995

[9] [9]

S. Fenner, F. Green, S. Homer, R. Pruim “Determining Acceptance Possibility for a Quantum Computa tion is Hard for the Polynomial Hierarchy”, quant-ph/9812056. 12 APPENDIX A: QUANTUM CIRCUITS OVER A FIXED FIELD Lemma 5 Let V be a unitary operator acting on k qubits. Suppose that matrix elements of V in the standard basis belong to a ﬁeld F ⊂ C. Then V can...

View on Pith Pith review arXiv