Quantum-Merlin-Arthur problems have perfect completeness with an infinite counter

A longstanding open problem in quantum complexity theory is whether Quantum Merlin-Arthur ($\mathrm{QMA}$), the quantum analog of nondeterministic polynomial time, is equal to $\mathrm{QMA}_1$, its one-sided error variant. We show that $\mathrm{QMA}=\mathrm{QMA}^∞=\mathrm{QMA}_1^∞$, where $\mathrm{QMA}_1^∞$ is like $\mathrm{QMA}_1$, but the verifier has an infinite register, as part of their witness system, in which they can efficiently perform a shift (increment) operation. We call this register an "infinite counter", and compare it to a program counter in a Las Vegas algorithm. The result, $\mathrm{QMA}=\mathrm{QMA}^∞$ means such an infinite register does not increase the power of $\mathrm{QMA}$, but does imply perfect completeness. By truncating our construction to finite dimensions, we get a $\mathrm{QMA}$-amplifier that only amplifies completeness, not soundness, but does so in significantly less time than previous $\mathrm{QMA}$ amplifiers. Our new construction achieves completeness $1-2^{-q}$ using $O(1)$ calls to each of the original verifier and its inverse, and $O(log q)$ other gates, proving that $\mathrm{QMA}$ has completeness doubly exponentially close to 1, i.e., $\mathrm{QMA}=\mathrm{QMA}(1-2^{-2^r},2^{-r}$) for any polynomial $r$.

• View at Publisher