Pith. sign in

REVIEW 3 major objections 4 minor 66 references

Dismantling the Stoquastic Dichotomy

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

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

Pith's one-line read The local Hamiltonian problem stays StoqMA-complete under a vanishing-geometric-phase promise, so diagonal unitary transformations cannot enlarge StoqMA.

desk verdict VGP replaces stoquasticity as the real boundary for StoqMA — plausible, significant, but the main containment depends on Lemma 3, which needs a closer look. read the letter →

arxiv 2607.18596 v1 pith:2BRRVXZ3 submitted 2026-07-21 quant-ph cs.CCphysics.comp-ph

Armen Karakashian , Itay Hen This is my paper · ORCID
classification quant-phcs.CCphysics.comp-ph
keywords vanishinggeometricphasestoquasticHamiltonianssignproblemStoqMAlocalHamiltonianadiabaticquantumcomputationMonteCarloPSPACE-completeness
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

This paper argues that the real boundary for sign-problem-free quantum systems and for quantum complexity is not the stoquastic/non-stoquastic dichotomy, but a basis-independent geometric condition: vanishing geometric phase (VGP), the requirement that every closed walk in a Hamiltonian's transition graph accumulates phase 1. The central result is that the local Hamiltonian ground-state energy problem remains StoqMA-complete under the promise that the input has VGP, so the class VGPMA collapses to StoqMA. The paper also constructs VGP Hamiltonians that are provably hard to stoquastize yet admit efficient recognition of VGP, shows that recognizing VGP is PSPACE-complete for general local Hamiltonians and coNP-hard already for 2-local ones, and argues that non-VGP, not merely non-stoquastic, instantaneous Hamiltonians are necessary for the standard route to universal adiabatic quantum advantage. If right, the 'stoquastic vs non-stoquastic' framing should be replaced by 'VGP vs non-VGP' in discussions of the sign problem, Hamiltonian complexity, and quantum annealing.

What carries the argument

The central object is the holonomy of a closed walk in the Hamiltonian's transition graph G_H: the product of normalized off-diagonal entries along the walk, multiplied by (-1) to the walk length. VGP is the condition that every such holonomy equals 1, equivalently that a stoquastizing diagonal unitary exists. The stoquastic proxy map S(H) carries the argument: it is cospectral to any VGP Hamiltonian and provides a stoquastic representative without exhibiting the diagonal. The paper's key technical step is a measurement lemma that lets a StoqMA verifier measure nonlocal nonnegative diagonal terms given only a polynomial-size reversible circuit that approximates their entries, which is what e

What would settle it

Construct a VGP local Hamiltonian whose stoquastic proxy S(H) has entries that no polynomial-size reversible circuit can approximate, or exhibit a nonnegative diagonal operator F for which an entry-oracle measurement fails to produce acceptance probability affine in ⟨ψ|X⊗F|ψ⟩ at inverse-polynomial precision; either would invalidate the measurement lemma and break the paper's central containment.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes that VGP is the diagonal-unitary-invariant notion of sign-problem-freeness that inherits StoqMA's computational boundary. A Hamiltonian has VGP exactly when a diagonal unitary D makes it cospectral to a stoquastic Hamiltonian, namely the stoquastic proxy S(H) that replaces each off-diagonal entry by its negative absolute value. The proof that VGP-LH is in StoqMA never constructs D and never verifies VGP; it uses the VGP promise only to guarantee that S(H) is cospectral to H, then feeds efficiently queryable entries of S(H) into a StoqMA verifier through a generalized measurement lemma that tolerates nonlocal diagonal terms. The resulting collapse VGPMA

Load-bearing premise

The load-bearing premise is that a small reversible circuit that approximates entries of the (possibly nonlocal) stoquastic proxy is sufficient to implement the StoqMA verifier's measurement with the required accuracy; if this generalized measurement premise fails, the proof that VGP-LH is in StoqMA fails, and with it the collapse VGPMA = StoqMA.

Editorial extensions

If this is right

  • VGP-LH is StoqMA-complete, so hiding stoquasticity behind any diagonal unitary adds no verification power; equivalently VGPMA = StoqMA.
  • The frustration-free local Hamiltonian problem for PMR-local VGP Hamiltonians is in MA, matching the stoquastic case.
  • Recognizing VGP is PSPACE-complete for local, geometrically local, and PMR-local Hamiltonians, and coNP-hard for 2-local Hamiltonians, so exploiting the VGP promise is much easier than checking it.
  • For standard adiabatic schedules with sign-preserving drivers, VGP is independent of schedule and instance; non-VGP drivers are necessary for the usual universality route, while non-stoquastic but VGP drivers confer no sign-problem-based advantage.
  • Under a VGP promise, the partition function, thermodynamic quantities, and diagonal observables agree exactly with the stoquastic proxy; differences appear only for state-level tasks that require phase data.

Reading between the lines

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

  • If the collapse VGPMA = StoqMA is correct, any future separation between StoqMA and QMA must be witnessed by Hamiltonians that are provably non-VGP rather than merely non-stoquastic.
  • A testable extension is to benchmark quantum annealing devices with VGP-but-not-stoquastic drivers, such as bipartite exchange or XY drivers, against their explicitly stoquastic twins; the paper predicts no sign-problem-derived performance difference.
  • The PSPACE-completeness of VGP recognition suggests a practical screening discipline: use the paper's efficient sufficient conditions for VGP before attempting expensive stoquastization or non-VGP certification.
  • The generalized measurement lemma, if it survives scrutiny, opens the door to other nonlocal 'sign-curing' maps beyond the absolute-value proxy that admit efficient entry oracles and preserve StoqMA containment.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper argues that vanishing geometric phase (VGP), rather than stoquasticity, is the correct diagonal-unitary-invariant boundary for sign-problem-free Monte Carlo simulation and for the complexity of ground-state energy problems. It defines the class VGPMA as problems reducible to the local Hamiltonian problem under a VGP promise, and claims that VGP-LH is StoqMA-complete (Theorem 4), yielding VGPMA = StoqMA (Corollary 6). The proof extends the StoqMA containment of Ioannou et al. to the nonlocal stoquastic proxy S(H) via a generalized measurement lemma (Lemma 3). The paper also constructs VGP Hamiltonians that are hard to stoquastize (Theorem 2), proves PSPACE-completeness of VGP recognition for local and geometrically local Hamiltonians (Theorem 8), and identifies tractable cases for recovering stoquastizing diagonals (Theorem 9, Corollary 9).

Significance. If the proof of Lemma 3 can be made fully rigorous, the collapse VGPMA = StoqMA is a significant result: it shows that the StoqMA-completeness of the local Hamiltonian problem is preserved under diagonal unitary transformations, so stoquasticity is not the operative feature. The separation examples (Example 4, Theorem 2) and the efficient stoquastization of PMR-local VGP Hamiltonians are valuable contributions. The PSPACE-completeness of VGP recognition is a striking contrast to the tractability of using the VGP promise. However, the current manuscript leaves a load-bearing lemma insufficiently proved and contains an internal contradiction about its role, so the headline claims are not yet established to the standard required for publication.

major comments (3)
  1. [Section V.A / Lemma 3 / Appendix B] Lemma 3 is load-bearing for Theorem 4 and hence for Corollary 6, but its proof is not self-contained. Appendix B invokes an unstated 'measurement primitive of Ref. [7]' and asserts that locality is irrelevant without proving the affine acceptance formula for nonlocal projectors. The binary-expansion step ('sample ℓ ... using fresh ancillas exactly as Ref. [7]') must be specified as a coherent circuit over {X,CNOT,Toffoli} with no intermediate measurements, and the constants α, β must be shown to preserve the 1/poly gap. Moreover, the sentence after Lemma 3 says it is 'not necessary' for Theorem 4, while the proof of Theorem 4 explicitly invokes it; if a weaker lemma suffices, it should be stated and proved.
  2. [Section V.A / Lemma 2] The claim that the Ioannou et al. decomposition can be constructed for S(H) using only the operators eH_{S,x} is asserted in property (c), not proved. Since S(H) can have exponential Pauli rank (Example 4), this is nontrivial. The proof must either provide the actual construction or state precisely which properties of the Ref. [7] construction are used, and why they survive when the diagonal terms are nonlocal but efficiently evaluable.
  3. [Section VI.B / Appendix D (Theorem 8)] The PSPACE-hardness reduction is presented at a high level and contains at least one questionable step: the footnote allowing an Or vertex with self-loops is not a legal NCL gadget, and the parity argument depends on it. The equivalence between the existence of an odd-length cycle and FreeNCLRev acceptance needs a rigorous proof, especially the claim that illegal configurations cannot contribute non-VGP cycles. This is a headline result and needs a complete, checkable proof.
minor comments (4)
  1. [Section V.A] The statement that Lemma 3 is 'not necessary' for Theorem 4 directly contradicts its use in the proof of Theorem 4. Please reconcile this or remove the disclaimer.
  2. [Section IV.A / Proposition 3] The proof asserts that each PMR term D_iP_i may be decomposed as a sum of whole local terms h_β. In general a PMR term is a sum of parts of local terms. The conclusion for geometrically local Hamiltonians is still correct when the interaction graph has bounded degree, but the proof should be rewritten.
  3. [Definition 26] The StoqMA verifier definition should clarify whether intermediate measurements are allowed. If not, the 'sampling' in Lemma 3 must be implemented coherently; this is related to Major Comment 1 and should be explicit.
  4. [Abstract / Table I] Several missing spaces (e.g., 'isStoqMA-complete') and the dense formatting of Table I make the paper hard to read. Please fix typographical issues.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the VGP-LH StoqMA-completeness proof is a reduction using an independent structural theorem, not a restatement of its own conclusion.

full rationale

The central derivation chain is not circular. VGP-LH ∈ StoqMA is proved by taking a VGP-promised local H, forming the stoquastic proxy S(H) (defined directly from matrix entries by S(H)_ii=H_ii and S(H)_ij=-|H_ij|), and relying on the external theorem from Ref. [4] that VGP implies S(H)=DHD† and hence cospectrality. That theorem is parameter-free, has stated assumptions that do not include the target result, and is independently published and falsifiable; although Ref. [4] shares an author, it is not used as an unverified uniqueness assertion to force the conclusion. The StoqMA-hardness direction is simply stoquastic-LH hardness plus the fact that stoquastic implies VGP, which follows directly from the definitions. The collapse VGPMA=StoqMA is obtained by proved inclusions in both directions, not by definition: VGPMA is defined as reducibility to VGP-LH, and the equality is a corollary of VGP-LH ∈ StoqMA together with StoqMA ⊆ VGPMA. No parameter is fitted to data, no closely related quantity is predicted from a fitted subset, and the paper explicitly avoids constructing a stoquastizing unitary. The main genuine risk is correctness, not circularity: Lemma 3 extends the StoqMA measurement primitive of Ref. [7] to nonlocal diagonal operators, and Appendix B justifies this by asserting that locality is used only to guarantee a reversible circuit; if that assertion fails, Theorem 4 would not follow. But that is an unverified or under-proved step, not a reduction of the result to its own inputs. Self-citations to Refs. [4,5,6,8,30] are present, but they are prior technical results with independent content and are not used to smuggle in the conclusion.

Assumptions & free parameters 0 free parameters · 5 assumptions · 2 invented entities

The paper introduces no free parameters fitted to data; all parameters are part of the input specification or internal constructions. The axioms are standard complexity-theoretic facts and theorems from cited prior work. The invented entities are mathematical tools (PMR locality and the stoquastic proxy map) used to obtain the complexity results.

assumptions (5)
  • domain assumption Stoq-LH ∈ StoqMA (Theorem 5 of Ioannou et al., Ref [7])
    Used as the foundation for the proof that VGP-LH ∈ StoqMA.
  • domain assumption VGP ⇔ existence of a stoquastizing diagonal (Proposition 1, building on Ref [4])
    Connects VGP to diagonal unitary transformation; ensures S(H) is cospectral to H.
  • domain assumption Nondeterministic Constraint Logic (NCL) and FreeNCLRev are PSPACE-complete [33,35]
    Used as the source problem for PSPACE-hardness of VGP recognition.
  • standard math Perron-Frobenius theorem [13]
    Used in Theorem 3 to derive ground-state amplitude structure.
  • domain assumption Ising formulations of NP problems (Lucas, Ref [10])
    Used for coNP-hardness of stoquasticity recognition in the separation example.
invented entities (2)
  • PMR locality (Definition 12)
    purpose: A new locality notion that sits between geometric locality and k-locality; enables efficient stoquastization and several complexity-theoretic results.
    A mathematical definition motivated by the PMR decomposition; not an independently observable physical entity.
  • Stoquastic proxy map S(·) (Definition 11)
    purpose: Maps any Hamiltonian to a stoquastic matrix via off-diagonal absolute values; provides a cospectral stoquastic representative for VGP Hamiltonians.
    A mathematical tool used to transfer StoqMA verifiers without explicitly constructing a diagonal unitary.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Dismantling the Stoquastic Dichotomy." pith.science (2026). https://pith.science/paper/2BRRVXZ3

@misc{pith2026260718596,
  author       = {Pith},
  title        = {Pith review of: Dismantling the Stoquastic Dichotomy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2BRRVXZ3}},
  note         = {Machine review of arXiv:2607.18596}
}
abstract

We challenge the notion that a stoquastic binary governs fundamental computational boundaries in quantum computing and classical simulation of quantum systems. We argue that vanishing geometric phase (VGP), a geometric condition on the Hamiltonian's transition graph, more adequately captures these boundaries. To distinguish VGP from stoquasticity, we construct VGP 3-local Hamiltonians that are formally hard to stoquastize, yet belong to a family admitting polynomial-time recognition of the VGP property. Without constructing a stoquastizing unitary, we prove that the local Hamiltonian problem is $\mathsf{StoqMA}$-complete under the promise that the input Hamiltonian has VGP, and that a frustration-free variant is in $\mathsf{MA}$ under the same promise. We use this result to argue that non-VGP is necessary for any claimed adiabatic advantage justified by escaping the $\mathsf{StoqMA}$ regime. Further, we identify natural settings where the VGP property can be recognized in polynomial time. In contrast, we show that recognition of VGP is $\mathsf{PSPACE}$-complete in general for geometrically local Hamiltonians. Our results show that the computational boundaries $\mathsf{MA} \subseteq \mathsf{StoqMA} \subseteq \mathsf{QMA}$ traditionally attributed to stoquasticity are better understood as boundaries between vanishing and non-vanishing geometric phase structure.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

66 extracted references · 6 linked inside Pith

  1. [7]

    Partition function and thermodynamics The partition functionZ= Tr(e −βH ) is a spectral quantity: under the VGP promise,Z(H) =Z(S(H)), and all equilibrium thermodynamic observables derived from it (free energy, entropy, specific heat) are identical forHand its stoquastic proxy. Moreover, the closed- walk weights in the PMR expansion ofZdepend only on the ...

  2. [1]

    This proves that thediameter, or the longest shortest-path distance between any two vertices, ofCis polynomial in size

    For any|x⟩and|y⟩in the same connected compo- nentCofG H , there is a walk from|x⟩to|y⟩of sizeO(poly(n)). This proves that thediameter, or the longest shortest-path distance between any two vertices, ofCis polynomial in size

  3. [2]

    The size of an isometric cycle ofCis at most linear in the diameter ofC

    We can always choose acycle basisof an undirected graphGthat only consists ofisometric cycles 7. The size of an isometric cycle ofCis at most linear in the diameter ofC. 7 Meaning the distance betweenuandvin the cycle is the same as the shortest distance in the ambient graph 3.Hdoes not have VGP if and only if for every choice of cycle basisCforG H , ther...

  4. [3]

    Recall that deciding if a HamiltonianHwith efficiently computable matrix entries is stoquastic is in 17 coNP[7]

    We argue Σ p 2 membership as follows. Recall that deciding if a HamiltonianHwith efficiently computable matrix entries is stoquastic is in 17 coNP[7]. Hence ifD∈ Dis provided as a (polynomial- sized) witness, one may efficiently computeDHD † and query acoNPoracle to determine ifDHD † is stoquastic. ThusLOCAL-D-STOQ∈NP coNP = Σp 2. If we allowedDto be the ...

  5. [4]

    Then we may writeP i = Xp

    Assume|supp(P i)|={p}. Then we may writeP i = Xp. We know thatH xy =⟨x|D iPi |y⟩can only be non-zero whenxandydiffer on qubitp. Fix the two statess, t∈ {0,1}|Bα|, the restrictions ofxand yto the blockB α containingp(i.e.,p∈B α); since xandydiffer only at qubitp,tequalsswith bitp flipped. Letzbe the restriction ofx(ory) to the qubits outside ofB α. SinceHi...

  6. [5]

    Stoquastization ofD iPi under someD∈ Drequires⟨x|D iPi |y⟩=H xy 7→ −|Hxy|

    Assume supp(P i) ={p, q}. Stoquastization ofD iPi under someD∈ Drequires⟨x|D iPi |y⟩=H xy 7→ −|Hxy|. (SinceHis 2-local,D i is supported on {p, q}as well, so these entries do not depend on spectator qubits; the linear constraints for this case are derived jointly with the PMR-local case below.) The above cases are the two possibilities for a PMR term ofHwh...

  7. [6]

    Ground-state energy This is the content of Theorem 4

  8. [8]

    Every diagonal equilibrium expec- tation value is therefore identical forHand its stoquastic proxy, and is accessible to any method that samples from a2 z

    Diagonal observables For any observableOthat is diagonal in the compu- tational basis,⟨ψ 0|O|ψ0⟩= P z a2 z Ozz depends only on the magnitudesa z =| ⟨z|ψ0⟩ |, which by Theorem 3 co- incide with the ground-state amplitudes ofS(H) on the relevant component. Every diagonal equilibrium expec- tation value is therefore identical forHand its stoquastic proxy, an...

Show all 66 references
  1. [9]

    Classical ground-state description For a stoquastic Hamiltonian, the Perron–Frobenius ground-state has⟨z|ψ 0⟩ ≥0 on each connected compo- nent and is completely characterized by the probability distributionp(z) =| ⟨z|ψ0⟩ |2—a purely classical object. For a VGP Hamiltonian, the...

  2. [10]

    Quantum state preparation The ground state|ϕ 0⟩of a stoquastic Hamiltonian is nonnegative in the computational basis, so it is fixed en- tirely by its amplitude data{a z}; the VGP ground state carries the same amplitude data rotated by the stoquas- tizing diagonal,|ψ 0⟩=D † |ϕ...

  3. [11]

    XY-mixers

    Entanglement and other phase-sensitive properties A stoquastizing diagonal need not factorize across a bipartition, and a non-factorizing diagonal can change Schmidt values: a controlled-Zacross the cut is diago- nal and maps the product state|+⟩ |+⟩to an entangled state. Cons...

  4. [12]

    Two Hamiltonians related by a diagonal unitary share all holonomies and all QMC weights, yet one may be sto- quastic and the other not

    VGP as the PMR-QMC sign-problem-free boundary Within the PMR-QMC framework, stoquasticity is a basis-dependent sufficient condition for sign-problem-free simulation, while VGP is the exact, diagonal-similarity invariant necessary and sufficient condition (Theorem 1). Two Hamil...

  5. [13]

    A computational wall between VGP and stoquasticity There exist VGP local Hamiltonians that belong to a family that admit efficient recognition of the VGP prop- erty, but are formally hard to stoquastize in a complexity- theoretic sense (Theorem 2). Thus VGP and stoquastic- ity...

  6. [14]

    The mechanism is worth isolating

    Diagonal unitary transformations do not enlarge StoqMA The local Hamiltonian problem restricted to VGP Hamiltonians isStoqMA-complete (Theorem 4, Corol- lary 4): the ground-state energy decision problem does not become harder when stoquasticity is hidden be- hind a diagonal un...

  7. [15]

    The equivalence extends to thermodynamics and diagonal observables Beyond energy, the partition function, all equilibrium thermodynamic quantities, and all diagonal equilibrium expectation values areidenticalfor a VGP Hamiltonian Hand its stoquastic proxyS(H) (Section VIII); w...

  8. [16]

    Recognition is harder than exploitation A striking asymmetry runs through our results: one canusethe VGP promise far more easily than one can verify it (in the worst case). Ground-state energy esti- mation under the promise is no harder than in the sto- quastic case, yet decid...

  9. [17]

    Consequences for adiabatic quantum computation The program of engineering non-stoquastic drivers and catalysts rests on the premise that non-stoquasticity is itself the resource that makes a device hard to simu- late. Our results relocate that premise (Section IX): for standar...

  10. [18]

    Scope and limitations Three limitations bound these conclusions. First, our notion of sign-problem-freeness in classical simulation is specific to the PMR-QMC framework; we have not shown that VGP characterizes the sign problems aris- ing in worldline, stochastic series expans...

  11. [19]

    The PMR-QMC sign problem boundary, estab- lished in [4], is thatHis sign-problem-free under PMR- QMC if and only ifHhas VGP

    Conclusion The results of this paper can be summarized as fol- lows. The PMR-QMC sign problem boundary, estab- lished in [4], is thatHis sign-problem-free under PMR- QMC if and only ifHhas VGP. The complexity state- ment, established here, is that the local Hamiltonian problem...

  12. [20]

    Problem 1(coNP-completeness of VGP recognition for 2-local Hamiltonians).We have shown that VGP recog- nition iscoNP-hard for 2-local spin-1/2 Hamiltonians

    Open problems. Problem 1(coNP-completeness of VGP recognition for 2-local Hamiltonians).We have shown that VGP recog- nition iscoNP-hard for 2-local spin-1/2 Hamiltonians. Is this decision problem also incoNP? A natural approach to provingcoNPmembership is bounding the sizes o...

  13. [21]

    Troyer and U.-J

    M. Troyer and U.-J. Wiese, Computational complexity and fundamental limitations to fermionic quantum monte carlo simulations, Physical Review Letters94, 170201 (2005)

    2005

  14. [22]

    E. Y. Loh, J. E. Gubernatis, R. T. Scalettar, S. R. White, D. J. Scalapino, and R. L. Sugar, Sign problem in the numerical simulation of many-electron systems, Physical Review B41, 9301 (1990)

    1990

  15. [23]

    Bravyi, A

    S. Bravyi, A. J. Bessen, and B. M. Terhal, Merlin-arthur games and stoquastic complexity (2006), arXiv:quant- ph/0611021 [quant-ph]

    2006

  16. [24]

    Hen, Determining quantum monte carlo simulabil- ity with geometric phases, Physical Review Research3, 023080 (2021)

    I. Hen, Determining quantum monte carlo simulabil- ity with geometric phases, Physical Review Research3, 023080 (2021)

    2021

  17. [25]

    Babakhani and A

    A. Babakhani and A. Karakashian, Stoquasticity is not enough: towards a sharper diagnostic for quantum monte carlo simulability (2025), arXiv:2508.14382 [quant-ph]

    2025

  18. [26]

    Gupta, T

    L. Gupta, T. Albash, and I. Hen, Permutation matrix representation quantum monte carlo, Journal of Statis- tical Mechanics: Theory and Experiment2020, 073105 (2020)

    2020

  19. [27]

    Ioannou, S

    M. Ioannou, S. Piddock, M. Marvian, J. Klassen, and B. M. Terhal, Termwise versus globally sto- quastic local hamiltonians: questions of complex- ity and sign-curing, arXiv preprint arXiv:2007.11964 10.48550/arXiv.2007.11964 (2020)

    2007 doi arXiv

  20. [28]

    Babakhani, L

    A. Babakhani, L. Barash, and I. Hen, A quantum monte carlo algorithm for arbitrary high-spin hamiltonians, Computer Physics Communications321, 110037 (2026)

    2026

  21. [29]

    Shackleton, Twisted quantum doubles are sign problem-free, Physical Review Letters136, 186503 (2026)

    L. Shackleton, Twisted quantum doubles are sign problem-free, Physical Review Letters136, 186503 (2026)

    2026

  22. [30]

    Lucas, Ising formulations of many np problems, Fron- tiers in Physics2, 5 (2014), arXiv:1302.5843 [cond- mat.stat-mech]

    A. Lucas, Ising formulations of many np problems, Fron- tiers in Physics2, 5 (2014), arXiv:1302.5843 [cond- mat.stat-mech]

    2014 arXiv

  23. [31]

    Marvian, D

    M. Marvian, D. A. Lidar, and I. Hen, On the computa- tional complexity of curing non-stoquastic hamiltonians, Nature Communications10, 1571 (2019)

    2019

  24. [32]

    M. R. Garey and D. S. Johnson,Computers and In- tractability: A Guide to the Theory of NP-Completeness, A Series of Books in the Mathematical Sciences (W. H. Freeman, San Francisco, 1979) p. 338

    1979

  25. [33]

    R. A. Horn and C. R. Johnson,Matrix Analysis, 2nd ed. (Cambridge University Press, Cambridge, 2013)

    2013

  26. [34]

    G. S. Uhrig, J. Hackmann, D. Stanek, J. Stolze, and F. B. Anders, Conservation laws protect dynamic spin corre- lations from decay: Limited role of integrability in the central spin model, Physical Review B90, 10.1103/phys- revb.90.060301 (2014)

    2014 doi

  27. [35]

    Bravyi and B

    S. Bravyi and B. M. Terhal, Complexity of stoquastic frustration-free hamiltonians, SIAM Journal on Comput- ing39, 1462 (2009)

    2009

  28. [36]

    Sattath, S

    O. Sattath, S. C. Morampudi, C. R. Laumann, and R. Moessner, When a local hamiltonian must be frustration-free, Proceedings of the National Academy of Sciences113, 6433–6437 (2016)

    2016

  29. [37]

    Klassen and B

    J. Klassen and B. M. Terhal, Two-local qubit hamiltoni- ans: when are they stoquastic?, Quantum3, 139 (2019)

    2019

  30. [38]

    S. A. Cook, The complexity of theorem-proving proce- dures, inProceedings of the Third Annual ACM Sympo- sium on Theory of Computing, STOC ’71 (ACM, New York, NY, USA, 1971) pp. 151–158

    1971

  31. [39]

    L. A. Levin, Universal search problems, Problemy Peredachi Informatsii9, 115 (1973), english translation in Problems of Information Transmission, 9(3):265–266, 1973

    1973

  32. [40]

    Biere, M

    A. Biere, M. Heule, H. van Maaren, and T. Walsh, eds., Handbook of Satisfiability, 2nd ed., Frontiers in Artificial Intelligence and Applications, Vol. 336 (IOS Press, 2021)

    2021

  33. [41]

    Klassen, M

    J. Klassen, M. Marvian, S. Piddock, M. Ioannou, I. Hen, and B. M. Terhal, Hardness and ease of curing the sign problem for two-local qubit hamiltonians, SIAM Journal on Computing49, 1332 (2020), arXiv:1906.08800 [quant- ph]

    2020 arXiv

  34. [42]

    Arora and B

    S. Arora and B. Barak,Computational Complexity: A Modern Approach(Cambridge University Press, 2009)

    2009

  35. [43]

    Bravyi, Monte carlo simulation of stoquastic hamil- tonians, Quantum Information & Computation15, 1122 (2015), arXiv:1402.2295 [quant-ph]

    S. Bravyi, Monte carlo simulation of stoquastic hamil- tonians, Quantum Information & Computation15, 1122 (2015), arXiv:1402.2295 [quant-ph]

    2015 arXiv

  36. [44]

    Bravyi and M

    S. Bravyi and M. Hastings, On complexity of the quantum ising model, Communications in Mathematical Physics349, 1 (2017)

    2017

  37. [45]

    Aharonov, W

    D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, Adiabatic quantum computation is equivalent to standard quantum computation, SIAM Journal on Computing37, 166 (2007)

    2007

  38. [46]

    J. D. Biamonte and P. J. Love, Realizable hamiltonians for universal adiabatic quantum computers, Physical Re- view A78, 012352 (2008)

    2008

  39. [47]

    Seki and H

    Y. Seki and H. Nishimori, Quantum annealing with anti- ferromagnetic fluctuations, Physical Review E85, 051112 (2012)

    2012

  40. [48]

    Albash and D

    T. Albash and D. A. Lidar, Adiabatic quantum compu- tation, Reviews of Modern Physics90, 015002 (2018)

    2018

  41. [49]

    Marshall, Antiferromagnetism, Proceedings of the Royal Society of London A232, 48 (1955)

    W. Marshall, Antiferromagnetism, Proceedings of the Royal Society of London A232, 48 (1955)

    1955

  42. [50]

    Crosson, T

    E. Crosson, T. Albash, I. Hen, and A. P. Young, De- Signing hamiltonians for quantum adiabatic optimiza- tion, Quantum4, 334 (2020)

    2020

  43. [51]

    M. B. Hastings and M. H. Freedman, Obstructions to classically simulating the quantum adiabatic algorithm, Quantum Information & Computation13, 1038–1076 (2013), arXiv:1302.5733 [quant-ph]. 25

    2013 arXiv

  44. [52]

    W. J. Savitch, Relationships between nondeterministic and deterministic tape complexities, Journal of Com- puter and System Sciences4, 177 (1970)

    1970

  45. [53]

    R. A. Hearn and E. D. Demaine, Pspace-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation (2004), arXiv:cs/0205005 [cs.CC]

    2004 arXiv

  46. [54]

    T. C. van der Zanden, Parameterized complexity of graph constraint logic, in10th International Symposium on Pa- rameterized and Exact Computation (IPEC 2015), Leib- niz International Proceedings in Informatics (LIPIcs), Vol. 43 (Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Infor- ...

    2015

  47. [55]

    De Biasi and T

    M. De Biasi and T. Ophelders, The complexity of snake, in8th International Conference on Fun with Algorithms (FUN 2016), Leibniz International Proceedings in Infor- matics (LIPIcs), Vol. 49, edited by E. D. Demaine and F. Grandoni (Schloss Dagstuhl–Leibniz-Zentrum f¨ ur In- fo...

    2016

  48. [56]

    The measurement primitive of Ref

    Diagonal projectors given by reversible circuits Let Π = P y∈S |y⟩⟨y|be a diagonal projector whose indicatory7→[y∈S] is computed by a reversible circuit CΠ over{X,CNOT,Toffoli}of size poly(n). The measurement primitive of Ref. [7] measures the termX⊗Π as follows: applyC Π to w...

  49. [57]

    Expanding bGin its bits gives bG= bX ℓ=1 2−ℓ Πℓ,Π ℓ := X y:ℓ-th bit of bG(y) = 1 |y⟩⟨y|, 27 a nonnegative combination ofbdiagonal projectors

    General nonnegative diagonals by binary expansion WriteG:=F/M, so that 0≤G(y)≤1 for everyy, and let bG(y) := bF(y)/Mbe the truncation produced byO F , which satisfies| bG(y)−G(y)| ≤2 −b. Expanding bGin its bits gives bG= bX ℓ=1 2−ℓ Πℓ,Π ℓ := X y:ℓ-th bit of bG(y) = 1 |y⟩⟨y|, 2...

  50. [58]

    [33]), is a graph-based model of reconfiguration

    Nondeterministic Constraint Logic (NCL) Nondeterministic Constraint Logic (NCL), introduced by Hearn and Demaine (Ref. [33]), is a graph-based model of reconfiguration. An NCL instance consists of an edge-weighted graph together with an orientation of its edges. A configuratio...

  51. [59]

    For every edgee, introduce a new qubitb(e)

    Encoding the reconfiguration graph of an NCL instance into a 5-local Hamiltonian Suppose Γ = (V, E) is anAnd/OrNCL instance with bounded bandwidth. For every edgee, introduce a new qubitb(e). For every vertexwwith incident edgee, defineσ(e, w) to be •+1 ifb(e) = 0 implieseis p...

  52. [60]

    There are three cases: a

    Assume thateis a blue edge. There are three cases: a. Assumeuandvare bothOrvertices. Then every edge incident touorvis blue. Define he := [1u,1 +1 u,2] [1v,1 +1 v,2] b. Assume thatuandvare bothAndvertices. Define he =1 u,11u,21v,11v,2 c. Without loss of generality, assume that...

  53. [61]

    BothuandvareAndvertices

    Assume thateis a red edge. BothuandvareAndvertices. Without loss of generality, assume thate (u) 1 is blue ande (v) 1 is blue. Define he :=1 u,11v,1. One can verify that the Hamiltonians are 5-local and are entry-wise≥0. Definingh e for everye∈E, the stoquastic 5-local Hamilto...

  54. [62]

    That is the only way foruandvto have their minimum inflow requirement met withoute

    Reversingeis legal if and only if the blue edges incident touandvare providing inflow touandv. That is the only way foruandvto have their minimum inflow requirement met withoute. Therefore, given a legal configurationz∈ {0,1} |E|, a transition|z⟩ →X b(e) |z⟩is allowed inG H if...

  55. [63]

    Starting from|x⟩, apply every PMR term fromH gadget toCexcepth eB XbXp0

  56. [64]

    Next, apply the pathP

  57. [65]

    So, we can applyh eB XbXp0

    Now the bit assignments to qubits{b(e)} e∈E agree with the configurationy. So, we can applyh eB XbXp0

  58. [66]

    Finish the closed walk by applying the pathPin reverse. For the reverse direction, •G H ′ contains an odd-length cycleγ⇐ ⇒ •H ′ contains an odd-length fundamental cycleCthat admitsγintoG H ′ ⇐ ⇒ •Cconsists of PMR terms fromH gadget, each PMR term occurring as a factor an odd n...

Pith tools

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