Q19: Could StoqMA be contained in QCMA?

Working mathematical formulation

Fix a $\mathsf{StoqMA}$ -complete local-Hamiltonian promise problem with polynomially bounded interactions and inverse-polynomial energy separation. Does every YES instance admit polynomial-length classical data $c$ specifying a starting state and a preparation recipe, from which a uniform polynomial-time quantum verifier can reach the accepting low-energy subspace with inverse-polynomial probability? Require soundness against every proposed $c$ on NO instances. One sufficient route is a guide that can be prepared efficiently and has inverse-polynomial weight in that low-energy subspace, followed by quantum energy measurement. A proof for every YES instance would establish $\mathsf{StoqMA}\subseteq\mathsf{QCMA}$ .

Scope & assumptions

This is a speculative direction, not an established containment. A good variational energy or optimal cut alone does not guarantee useful low-energy overlap. The Lee–Yang theorem supplies a Hamiltonian gap in its stated family; it is not a general Markov-chain mixing theorem. A field must not change the decision problem beyond its allowed energy error. Classical witnesses may be hard to find, but their length and the verifier runtime must remain polynomial.

Why this is interesting

Perhaps choosing a useful starting position is the hard part, while navigating from it is efficient. A best product-state solution or a Max-Cut solution has a short classical description even if finding it is $\mathsf{NP}$ -hard. Merlin could supply that description. The remaining question is whether it actually provides useful quantum access to the low-energy space.

Explicit variants

Same-graph interpolation and magnetization
For every YES instance of $A_G=-\sum w(P_s+2P_{t_0})$ , does there exist a cut $x$ , a magnetization sector, and a polynomial-size path description whose quantum evolution reaches energies below $a+(b-a)/3$ with inverse-polynomial probability? Here $[a,b]$ is the target promise gap. The displayed path and cut-aligned $Z$ fields preserve Hamming weight. Prove that the witness selects a sector reaching globally low energy, and bound its minimum relevant gap and field-induced energy error. The verifier does not need to certify cut optimality.
Verifier restrictions
Can a spin-based verifier faithfully realize the gate, basis, and accepting-measurement restrictions defining $\mathsf{StoqMA}$ ? Distinguish a classical $\mathsf{QCMA}$ witness from encoded quantum data. Nonnegative input states or real STP projectors alone do not identify the resulting verifier class.
Direct Quantum Max-Cut interpolation
Study $\begin{gathered}K_G(u)=-\sum w(P_s+2uP_{t_0}),\\0\le u\le1,\end{gathered}$ on a fixed graph. Its endpoints are Quantum Max-Cut energy and the $\mathsf{StoqMA}$ -complete target; $u=1/2$ is classical Max-Cut. Compare beginning with a supplied QMC resource state against beginning at the classical point with a cut bit string. Include the preparation cost of any quantum starting state and do not assume an efficiently available QMC ground state.
Paths from high symmetry
Which spin Hamiltonian families admit an efficiently described path from an efficiently preparable fully symmetric state to a near-ground-state witness, with polynomial duration and controlled final energy error? In triplet-favored families, prove such a preparation guarantee or exhibit an obstruction. Specify the gap or alternative preparation bound and the permitted symmetry-breaking, ancillary, or Hamiltonian operations: internal pairwise STP alone acts trivially on a closed fully symmetric register. Compare these regimes with the relevant Hamiltonian complexity classifications.

A place to start

On the same positive-weight graph $G$ , try $\begin{aligned}H_G(t)={}&-\sum w_{ij}\bigl(P_s^{ij}\\&\quad +(1+t)P_{t_0}^{ij}\bigr),\\&0\le t\le1.\end{aligned}$ At $t=0$ this is classical Max-Cut; at $t=1$ it is twice $\operatorname{Toy}(1/2)$ , hence $\mathsf{StoqMA}$ -complete. Start from a cut bit string, optionally selected by a small cut-aligned $Z$ field. Resolve the conserved-Hamming-weight obstruction before seeking an inverse-polynomial sector gap. Check whether a sector-optimal cut in a useful sector can be the witness. A Quantum Max-Cut ground state is not an efficiently available starting resource.

Related work

These works provide context and established results. They need not be the origin of this exact formulation.

Discuss this question

Continue on GitHub Propose a research question

Reading is public. Posting requires a GitHub account. You can also write to Kunal.

Why this is interesting

Explicit variants

Same-graph interpolation and magnetization

Verifier restrictions

Direct Quantum Max-Cut interpolation

Paths from high symmetry

A place to start

Related work

Related questions

Discuss this question