A long-standing open problem in quantum complexity theory is whether QMA, the quantum analogue of NP, is equal to QMA₁, its one-sided error variant. We show that QMA= QMA^= QMA₁^, where QMA₁^ is like QMA₁, 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 QMA= QMA^ means such an infinite register does not increase the power of QMA, but does imply perfect completeness. By truncating our construction to finite dimensions, we get a QMA-amplifier that only amplifies completeness, not soundness, but does so in significantly less time than previous 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 (q) other gates, proving that QMA has completeness doubly exponentially close to 1, i. e. QMA= QMA (1-2^-2ʳ, 2^-r) for any polynomial r.
Jeffery et al. (Wed,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: