Dismantling the Stoquastic Dichotomy

• URL: http://arxiv.org/abs/2607.18596v1
• Date: Tue, 21 Jul 2026 00:10:19 GMT
• Title: Dismantling the Stoquastic Dichotomy
• Abstract summary: We argue that vanishing geometric phase (VGP) more adequately captures computational boundaries.<n>We show that recognition of VGP is $mathsfPSPACE$-complete in general for geometrically local Hamiltonians.
• Score: 0.05729426778193397
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Exact chiral symmetry with quantum signal processing [39.146761527401424]
  We give a quantum signal processing algorithm for the overlap fermion Hamiltonian.<n>Applying the overlap Hamiltonian costs only a factor logarithmic in $_e$ more than the Wilson-Dirac Hamiltonian.
  arXiv  Detail & Related papers  (2026-07-30T17:00:58Z)
• Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
  For Hamiltonian $H = sum_j h_j$, we proveally tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer.<n>Our hold for arbitrary term norms $|h_j|$, time $t$, and trace-distance error $$.
  arXiv  Detail & Related papers  (2026-07-22T07:41:32Z)
• Rounding Almost Commuting Hamiltonians [40.02212661155582]
  Commuting Hamiltonians lie at the boundary between classical constraint satisfaction and quantum many-body physics.<n>We show how to efficiently approximate any almost commuting $2$-local qubit Hamiltonian by a commuting one.
  arXiv  Detail & Related papers  (2026-05-25T17:53:36Z)
• DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians [20.990700912031773]
  We study the computational complexity of estimating the normalized trace $2-nTr[f(A)]$ for a log-local Hamiltonian $A$ acting on $n$ qubits.<n>This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions $f(x)$.<n>We show that if $f(x)$ is a continuous function with approximate degree $(rm poly(n))$, then estimating $2-nTr[f(A)]$ up to constant additive error is
  arXiv  Detail & Related papers  (2026-04-02T01:15:12Z)
• Hamiltonian Decoded Quantum Interferometry for General Pauli Hamiltonians [6.4675604105664]
  We study the Hamiltonian Decoded Quantum Interferometry (HDQI) for the general Hamiltonians $H=sum_ic_iP_i$ on an $n$-qubit system.<n>We show that, given access to an appropriate decoding oracle, there exist efficient quantum algorithms for preparing the state $_mathcal P(H) = fracmathcal P(H)textTr[$cal P(H)]$, where $mathcal P(H)textTr[$
  arXiv  Detail & Related papers  (2026-01-26T18:44:59Z)
• Hamiltonian Decoded Quantum Interferometry [69.7049555871155]
  We introduce Hamiltonian Decoded Quantum Interferometry (HDQI)<n>HDQI utilizes coherent measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian Bellians.<n>We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians.
  arXiv  Detail & Related papers  (2025-10-09T08:06:15Z)
• Kernpiler: Compiler Optimization for Quantum Hamiltonian Simulation with Partial Trotterization [38.59115551211364]
  Existing compilation techniques for Hamiltonian simulation struggle to provide gate counts feasible on current quantum computers.<n>We propose partial Trotterization, where sets of non-commuting Hamiltonian terms are directly compiled allowing for less error per Trotter step.<n>We demonstrate with numerical simulations across spin and fermionic Hamiltonians that compared to state of the art methods such as Qiskit's Rustiq and Qiskit's Paulievolutiongate, our novel compiler presents up to 10x gate and depth count reductions.
  arXiv  Detail & Related papers  (2025-04-09T18:41:31Z)
• A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition [77.76727425995186]
  Solving variational inequalities (SVIs) is a foundational problem at the heart of optimization.<n>Most research has focused on carving out specific subclasses that elude those intractability barriers.
  arXiv  Detail & Related papers  (2025-04-04T13:24:41Z)
• Quantum singular value transformation without block encodings: Near-optimal complexity with minimal ancilla [18.660349597156266]
  We develop new algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework that encapsulates most known quantum algorithms.<n>Our results establish a new framework for quantum algorithms, significantly reducing hardware overhead while maintaining near-optimal performance.
  arXiv  Detail & Related papers  (2025-04-03T08:24:15Z)
• Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
  We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. We present a quantum algorithm that uses $O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$ queries to the block-encoding for any $Gamma$.
  arXiv  Detail & Related papers  (2024-04-04T17:58:01Z)
• Unbiased constrained sampling with Self-Concordant Barrier Hamiltonian Monte Carlo [18.14591309607824]
  Barrier Hamiltonian Monte Carlo (BHMC) is a version of the HMC algorithm which aims at sampling from a Gibbs distribution $pi$ on a manifold $mathrmM$. We propose a new filter step, called "involution checking step", to address this problem. Our main results establish that these two new algorithms generate reversible Markov chains with respect to $pi$ and do not suffer from any bias in comparison to previous implementations.
  arXiv  Detail & Related papers  (2022-10-21T12:56:07Z)
• The Complexity of Translationally Invariant Problems beyond Ground State Energies [6.445605125467574]
  Three fundamental questions regarding local Hamiltonians are $mathsfQMA$-hard, $mathsfPmathsfQMA[log]$-hard and $mathsfQCMA$-hard. We show that translationally invariant versions of both APX-SIM and GSCON remain intractable.
  arXiv  Detail & Related papers  (2020-12-23T14:44:57Z)
• Termwise versus globally stoquastic local Hamiltonians: questions of complexity and sign-curing [3.762360672951513]
  We show that the stoquastic local Hamiltonian problem is $textbfStoqMA$-complete even for globally stoquastic Hamiltonians. We expand the class of sign-curing transformations by showing how Clifford transformations can sign-cure a class of disordered 1D $XYZ$ Hamiltonians.
  arXiv  Detail & Related papers  (2020-07-23T12:29:46Z)
• Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians [0.0]
  We present a classical algorithm to efficiently sample from the effective subspace of a $k$-local stoquastic Hamiltonian $H$. Our results rule out exponential separations between stoquastic AQC and classical computation that arise from hidden symmetries in $k$-local Hamiltonians.
  arXiv  Detail & Related papers  (2020-04-18T18:25:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.