Related Experiment Video
Updated: May 24, 2026
06:42
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.
Physical Review Letters
|May 22, 2026
Summary
Quantum Merlin-Arthur (QMA) complexity class equals its one-sided error variant (QMA1) even with an infinite counter. This finding simplifies QMA amplifiers, achieving high completeness efficiently.
Area of Science:
- Quantum Computing
- Computational Complexity Theory
- Theoretical Computer Science
Background:
- Quantum Merlin-Arthur (QMA) is the quantum analogue of nondeterministic polynomial time.
- A key open problem is whether QMA equals QMA1, its one-sided error variant.
Purpose of the Study:
- To resolve the long-standing question of whether QMA equals QMA1.
- To introduce and analyze the power of an "infinite counter" in quantum verification.
Main Methods:
- Introduced QMA1 with an infinite counter (QMA1^∞).
- Demonstrated QMA = QMA^∞ = QMA1^∞.
- Developed a QMA amplifier by truncating the construction to finite dimensions.
Main Results:
- An infinite counter does not increase the computational power of QMA.
- The construction implies perfect completeness for QMA.
- Achieved a QMA amplifier with completeness 1-2^{-q} using significantly fewer resources than prior methods.
Conclusions:
- Established QMA = QMA1, settling a major open problem in quantum complexity.
- The new QMA amplifier offers a more efficient way to boost completeness.
- Proved that QMA has completeness doubly exponentially close to 1.
Related Concept Videos
01:29Indeterminate Products
Indeterminate forms also arise in the evaluation of limits involving products, particularly when one factor approaches zero while the other tends to positive or negative infinity. This situation, commonly described as a zero-times-infinity form, does not have an immediately interpretable outcome. Depending on how the factors behave relative to one another, the limit of such a product may be zero, infinite, or a finite nonzero value.Product Limits and Algebraic RewritingTo analyze limits of this...
01:29Improper Integrals: Infinite Intervals
An integral is classified as improper due to an infinite interval when at least one of its limits of integration extends to positive or negative infinity. In such cases, the region under the curve is unbounded, and standard techniques for evaluating definite integrals are not directly applicable. Instead, the improper integral is defined through a limiting process that allows one to determine whether the accumulated area remains finite despite the infinite domain.Application to Exponential...
01:24Limits at Infinity
The function that decreases as the input becomes very large provides a clear example of how mathematical functions can behave at extreme values. When the input increases continuously, the output becomes smaller and smaller, getting closer to a particular fixed value. Although the output never actually reaches this value, it moves nearer to it without limit. This behavior is a fundamental concept in understanding how functions behave as the input grows indefinitely. The graphical representation...
01:19Limits with Oscillating Discontinuities
An oscillating discontinuity is a type of discontinuity in which a function’s values fluctuate infinitely often as the input approaches a particular point. Unlike jump discontinuities, where the function suddenly shifts between two values, or infinite discontinuities, where the function diverges without bound, an oscillating discontinuity arises from rapid back-and-forth variation. Because the function never stabilizes toward a single value, no finite limit exists at that point.One of the most...
01:30Fundamental Theorem of Algebra
The Fundamental Theorem of Algebra is central to the study of polynomial equations, asserting that every non-constant polynomial with complex coefficients has at least one complex zero. This means that a polynomial of degree n ≥ 1, written as: with an ≠ 0, has at least one solution in the complex number system. Since the set of real numbers is a subset of complex numbers, this theorem applies equally to polynomials with real coefficients.Building on this result, the Complete Factorization...
01:16Second Uniqueness Theorem
Consider a region consisting of several individual conductors with a definite charge density in the region between these conductors. The second uniqueness theorem states that if the total charge on each conductor and the charge density in the in-between region are known, then the electric field can be uniquely determined.
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...
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...