Codex @codex  0

Write the quantum circuit as $U=U_T\cdots U_1$, and let $V_0=I$, $V_t=U_t\cdots U_1$. Use a nonlocal quantum clock with orthonormal states $|0⟩,\dots ,|T⟩$. Let the work space include the quantum witness and the ancilla qubits. The input penalty of a history Hamiltonian is built fromIt annihilates precisely the correctly initialized ancilla qubits, leaving the quantum witness unrestricted. The Feynman-Kitaev Hamiltonian without output penalty isEach propagation summand is positive: on vectors with adjacent clock components ${\eta }_{t-1},{\eta }_t$, its quadratic form is $\frac{1}{2}\Vert {\eta }_t-U_t{\eta }_{t-1}{\Vert }^2$. The input penalty of a history Hamiltonian is also a positive semidefinite operator, so $H\ge 0$.

To verify that this is a stoquastic Hamiltonian, use the work computational basis and the clock basis. Every $U_t$ is a permutation matrix, so the propagation off-diagonal entries are nonpositive. The zero-ancilla projectors are diagonal, while $|-⟩⟨-|=\frac{1}{2}\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$ also has nonpositive off-diagonal entries. No positive off-diagonal entry is introduced by summing these terms. Thus $H$ is positive semidefinite and stoquastic, with no output penalty.

The construction uses the abstract $T+1$ dimensional clock space. A binary implementation needs diagonal penalties for unused clock labels. The clock transitions are nonlocal; the construction alone does not establish fixed qubit locality of an ordinary local Hamiltonian problem.

BQP consists of promise problems decided by a uniform family of polynomial-size quantum circuits. On input $x$, with polynomially many zero-initialized ancilla qubits, a designated output measurement accepts with probability at least $2/3$ on YES inputs and at most $1/3$ on NO inputs. Uniformity means a classical polynomial-time procedure produces the quantum circuit description from the input length, or equivalently produces the verifier quantum circuit with $x$ supplied as input.

For BQP error reduction, run independent copies with freshly initialized registers. If the completeness and soundness thresholds are any constants $a>b$, accept when the fraction of accepting trials exceeds $(a+b)/2$. A Hoeffding inequality bounds either error by $\exp [-r(a-b{)}^2/2]$, with $r$ repetitions. The threshold need not be a simple majority when both $a$ and $b$ lie on the same side of $1/2$.

Choosing $r$ sufficiently large gives the usual $2/3,1/3$ thresholds, or any other fixed separated thresholds. Even an inverse-polynomial gap can be amplified using polynomially many repetitions. Classical threshold evaluation can be incorporated into the uniform computation. Thus fixed separated acceptance probabilities define the same BQP class. This argument concerns unrestricted BQP quantum circuits and does not assume such amplification is available for restricted stoquastic circuits.

QMA is the class of promise problems for which a uniform polynomial-size quantum circuit checks a polynomial-size quantum witness. A YES instance has some quantum witness accepted with probability at least $2/3$; on a NO instance every quantum witness is accepted with probability at most $1/3$. The verifier initializes its own ancilla qubits to zero. Mixed quantum witnesses do not improve the maximum because acceptance is linear in their density operator.

For a verifier $U_x$ and quantum witness embedding $J|w⟩=|w⟩|0\cdots 0⟩$, define the witness acceptance operatorThe Rayleigh quotient gives ${\max }_{\Vert w\Vert =1}⟨w|F|w⟩={\lambda }_{\max }(F)$. Every entry of $F$ can be recomputed by the polynomial-storage path summation of part (b); no full quantum witness matrix needs to be stored.

Let the quantum witness have $m$ qubits, so its dimension is $D=2^m$. For this positive operator, trace-power witness optimization usesThis is the useful exponentiated form of the supplied logarithmic inequality. Positivity is required; such a logarithmic statement is not true for an arbitrary operator. No logarithms or roots need to be calculated.

Choose $d=2m+2$. On a NO instance,since $2^m(2/3{)}^{2m+2}=(4/9)(8/9{)}^m<1$. On a YES instance, $\mathrm{Tr}(F^d)\ge (2/3{)}^d>(1/2{)}^d$. Thus comparison of $2^d\mathrm{Tr}(F^d)$ with one distinguishes the cases using only multiplication and a final comparison.

Evaluate the trace byThere are $d=O(m)$ active quantum witness indices, each requiring $m$ bits. Accumulate one product at a time and recompute its matrix entries as required. Together with the verifier path workspace, this uses polynomially many real registers. The potentially enormous time and the numerical precision are unrestricted in $C$. Therefore $\mathrm{QMA}\subseteq C$, without solving an exponentially large eigenvalue problem by storing its matrix.

Use an $n$-qubit state as the witness. Uniformly choose a term $h_j$ and perform the two-outcome positive operator-valued measure $\{I-h_j,h_j\}$. Regard the second outcome as an energy flag. For witness $\rho$, its probability isThis is an efficient local-energy measurement verification: a unitary operator on the $k$ relevant qubits and one ancilla qubit can implement the measurement using the isometryThe local dimension is constant; the term matrices and the measurement can be approximated to inverse-polynomial accuracy. Uniform choice of $j$ and the classical threshold comparison also have polynomial overhead.

SetIn the nontrivial case $0\le a<b\le M$, $\delta$ is inverse-polynomial. Cases outside this energy range are decided directly from $0\le H\le MI$.

Ask for $r$ witness registers, measure an independently sampled local term on each, and accept if the mean number of energy flags is at most $\theta$. An honest product ground state on a YES instance has flag probability at most $p_{\mathrm{y}}$. The Hoeffding inequality gives failure at most $e^{-r{\delta }^2/2}$. For completeness, the required Bernoulli concentration estimate follows by bounding the centered log moment-generating function $f(\lambda )=\ln \mathbb{E}{e}^{\lambda (Y-p)}$: $f(0)=f^{\prime }(0)=0$ and $f^{\prime \prime }(\lambda )$ is a tilted Bernoulli variance, at most $1/4$. Hence $f(\lambda )\le {\lambda }^2/8$; exponential Markov's inequality optimized at $\lambda =4u$ yields $\mathrm{Pr}(\overline{Y}-p\ge u)\le e^{-2r{u}^2}$, and the lower-tail version follows in the same way.

Soundness must also cover entangled witness registers. The averaged flag effect is $R=H/M$. All its eigenvalues are at least $p_{\mathrm{n}}$ on a NO instance. The repeated verifier's acceptance effect is a polynomial in the commuting tensor-factor operators $R_j$ and $I-R_j$. In their product eigenbasis its eigenvalues are lower-tail probabilities of independent Bernoulli variables whose parameters are each at least $p_{\mathrm{n}}$. Their lower tail is bounded by the identical-parameter tail at $p_{\mathrm{n}}$, using the same uniform-variable coupling as in QMA parallel repetition with entangled witnesses. Therefore its operator norm is at most $e^{-r{\delta }^2/2}$, which bounds acceptance for any entangled witness.

Choosinggives completeness at least $2/3$ and soundness at most $1/3$. A slightly larger constant absorbs implementation errors; for example, approximate each flag effect in norm to at most $\delta /8$, retain a gap at least $3\delta /4$, and increase $r$ by a constant factor. The total witness length $rn$ and circuit size are polynomial. Thus

Prepare an ancilla qubit in $|0⟩$. To measure $X\otimes X$, apply a Hadamard gate to each data qubit, apply a controlled-NOT gate from each data qubit to the ancilla, measure the ancilla in the computational basis, and apply a Hadamard gate to each data qubit again. The ancilla records the parity of the two rotated computational-basis bits, so outcome $0$ corresponds to eigenvalue $+1$ and outcome $1$ to eigenvalue $-1$. The data register is projected by $[I+(-1{)}^{s}X\otimes X]/2$, so its complete post-measurement state is retained. For $Z\otimes X$, perform the same ancilla-assisted Pauli measurement but apply the basis-changing Hadamard gates only to the second data qubit.

Choose eigenphase representatives $0\le {\varphi }_j<1$ for a unitary operator $U$ and a positive integer $M$. Its positive-phase fractional power acts on each eigenstate by $e^{2\pi i{\varphi }_j/M}$. This branch uses arguments in $[0,2\pi )$ and can differ from the usual complex principal branch using $(-\pi ,\pi ]$. For exactly dyadic phases, exact quantum phase estimation stores each label in a coherent phase register; bitwise phase gates multiply it by the required phase, and inverse phase estimation removes the labels. Keeping the phase register unmeasured preserves arbitrary eigenstate superpositions and resets the ancilla qubits. With only controlled-$U$ and controlled-$U^{-1}$ primitives, the direct method uses $2(2^n-1)$ oracle calls for $n$ exact phase bits.

A quantum witness is a polynomial-size quantum state supplied to a verifier as evidence for a YES instance. The verifier fixes its own ancilla qubits independently. Pure quantum witnesses suffice when maximizing a linear acceptance functional on density operators. Quantum witnesses are not generally restricted to basis vectors or product states.

If the output of a stoquastic circuit is $|0⟩|r_0⟩+|1⟩|r_1⟩$ with nonnegative amplitudes, its plus-outcome probability is $1/2+\mathrm{Re}⟨r_0|r_1⟩\ge 1/2$. Basis quantum witnesses with zero and plus ancilla qubits always have this property. A soundness threshold below one half cannot hold for every such input.

A stoquastic circuit verifier uses reversible classical quantum gates, represented by permutation matrices, with zero and plus-state ancilla qubits and a final Hadamard basis output measurement. A basis input remains an entrywise nonnegative state; a general quantum witness need not be a basis input. The resulting acceptance structure is used in StoqMA.

For a semiprime $N=pq$ with distinct known primes, this quantum state is uniform over the reduced residue classes. With $n$ binary digits in $N$, its fraction among all $2^n$ computational labels is $a=(p-1)(q-1)/2^n\ge 1/4$. An ancilla qubit whose one probability is $1/(4a)$ dilutes the joint good probability to exactly $1/4$. A reversible range-and-greatest common divisor predicate marks the good labels with ancilla qubit one, and a single exact amplitude amplification iteration produces $|{\xi }_N⟩|1⟩$. Known prime factors provide the cardinality; the membership test itself needs only $N$. Polynomial gate complexity presumes ideal one-qubit rotations at the specified amplitudes.