Related Experiment Video
Updated: May 24, 2026

Generation and Coherent Control of Pulsed Quantum Frequency Combs
Published on: June 8, 2018
Quantum-Merlin-Arthur Problems Have Perfect Completeness with an Infinite Counter
Stacey Jeffery1,2, Freek Witteveen1
1CWI, QuSoft, Amsterdam.
Abstract:
A longstanding open problem in quantum complexity theory is whether Quantum Merlin-Arthur (QMA), the quantum analog of nondeterministic polynomial time, is equal to QMA_{1}, its one-sided error variant. We show that QMA=QMA^{∞}=QMA_{1}^{∞}, where QMA_{1}^{∞} is like 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, 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(logq) other gates, proving that QMA has completeness doubly exponentially close to 1, i.e., QMA=QMA(1-2^{-2^{r}},2^{-r}) for any polynomial r.
Related Concept Videos
Indeterminate Products
Improper Integrals: Infinite Intervals
Limits at Infinity
Limits with Oscillating Discontinuities
Fundamental Theorem of Algebra
Second Uniqueness Theorem
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the surface...
