= Solution
<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\rangle=|w\rangle|0\cdots0\rangle$, define the <witness acceptance operator>
$$
F=J^\dagger U_x^\dagger\Pi_1U_xJ,\qquad0\leq F\leq I.
$$
The <Rayleigh quotient> gives $\max_{\|w\|=1}\langle w|F|w\rangle=\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> uses
$$
\lambda_{\max}(F)^d\leq\operatorname{Tr}(F^d)\leq D\lambda_{\max}(F)^d.
$$
This 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,
$$
\operatorname{Tr}(F^d)\leq 2^m(1/3)^d<(1/2)^d,
$$
since $2^m(2/3)^{2m+2}=(4/9)(8/9)^m<1$. On a YES instance, $\operatorname{Tr}(F^d)\geq(2/3)^d>(1/2)^d$. Thus comparison of $2^d\operatorname{Tr}(F^d)$ with one distinguishes the cases using only multiplication and a final comparison.
Evaluate the trace by
$$
\operatorname{Tr}(F^d)=\sum_{i_0,\ldots,i_{d-1}}F_{i_0i_1}F_{i_1i_2}\cdots F_{i_{d-1}i_0}.
$$
There 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$. \b[Therefore $\mathrm{QMA}\subseteq C$], without solving an exponentially large <eigenvalue> problem by storing its matrix.
Back to article page
