PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Arthur-Merlin Games

Chris Marriott, John Watrous

arXiv:cs/0506068v1cs.CCquant-ph

TL;DR

The paper studies quantum Arthur-Merlin games, where Arthur sends only uniformly random classical bits while Merlin may send quantum information. It develops a message-length-preserving method for exponentially reducing QMA errors and applies it to complexity-class consequences, while also proving results for QAM and QMAM. In particular, QMAM equals QIP, and logarithmic-length QMA certificates provide no more power than BQP.

  • Problem

    Existing QMA error reduction achieved exponentially small errors only by increasing Merlin’s message length polynomially.

    Source: §1 · p. 2

  • Method

    The paper studies quantum Arthur-Merlin games with Arthur restricted to uniformly generated random-bit messages and develops a new error-reduction method for their one-message form.

    Source: §1 · pp. 2–3

  • Results

    Exponential QMA error reduction requires no increase in Merlin’s message length, while QMAM equals QIP and logarithmic-length quantum certificates add no power over BQP.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The results connect restricted quantum interactive-proof models to QMA, BQP, PP, QAM, and QIP through message-efficient error reduction and message-round equivalences.

    Source: §1 · p. 3

    The constructions assume quantum circuits use a fixed universal gate set and a reasonable polynomially bounded binary encoding.

    Source: Quantum computation · p. 4

Abstract

from arXiv · show

This paper studies quantum Arthur-Merlin games, which are Arthur-Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur-Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin's message. Previous constructions for reducing error required a polynomial increase in the length of Merlin's message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that QMA is contained in PP. Other facts that are proved include the equivalence of three (or more) message quantum Arthur-Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur-Merlin games.

1 Introduction

The paper defines quantum Arthur-Merlin games as quantum interactive proofs where Arthur sends only public random bits, then studies their one-, two-, and three-message forms. Its main results establish strong error reduction for QMA and characterize several relationships among QMA, QAM, QMAM, BQP, PP, and QIP.

1 Introduction

  • Quantum Arthur-Merlin games restrict Arthur’s messages to uniformly generated public random bits, while allowing quantum computation and quantum messages from Merlin.The paper studies one-, two-, and three-or-more-message variants arising from this restriction.Source: §1 · p. 2
  • QMA is the one-message class in which Merlin sends Arthur a quantum certificate that Arthur verifies in polynomial time.Prior parallel repetition reduced QMA errors exponentially but required multiple copies and therefore increased Merlin’s message length polynomially.Source: §1 · p. 2
  • Exponential completeness and soundness error reduction is possible for one-message quantum Arthur-Merlin games without increasing Merlin’s message length.This improves on prior error-reduction constructions that required a polynomial increase in message length.Source: §1 · pp. 2–3
  • The paper applies the new error-reduction method to show that logarithmic-length quantum certificates add no power over BQP and to give a simplified proof that QMA is contained in PP.The PP containment was previously known through GapP and matrix-analysis arguments, including a stronger containment in A0PP.Source: §1 · p. 3
  • For two-message games, QAM supports classical-style parallel repetition for error reduction and is contained in BP · PP.Arthur sends random bits and Merlin responds with a quantum state.Source: §1 · p. 3
  • For three-message games, QMAM equals QIP, and this equivalence can use only a single Arthur coin-flip while preserving perfect completeness and exponentially near-1/2 soundness.The paper attributes the quantum advantage over the analogous classical strategy to the possible entanglement between Merlin’s messages, invoking monogamy of entanglement.Source: §1 · p. 3

Organization of the paper

  • The paper is organized around background material, separate QMA, QAM, and QMAM sections, and a concluding discussion of open problems.These sections correspond respectively to one-message, two-message, and three-or-more-message games.Source: Organization of the paper · pp. 3–4

2 Background Information

This background section establishes the paper’s notation, quantum-circuit conventions, counting-complexity tools, and characterization of three-message quantum interactive proofs.

2 Background Information

  • The paper fixes binary-string conventions, polynomial-time tuple encodings, and polynomial-time generated circuit families for its complexity-theoretic definitions.These conventions allow circuit families to depend directly on the input string while remaining efficiently generated.Source: §2 · p. 4, Quantum computation · p. 4

Quantum computation

  • Quantum circuits use Toffoli, Hadamard, and i-shift gates, a universal set, with polynomially bounded binary encodings.The paper assumes familiarity with quantum information and the quantum circuit model.Source: Quantum computation · p. 4
  • BQP is defined through polynomial-time generated circuits acting on a polynomial number of qubits, followed by measurement of the first output qubit with bounded error.The circuit starts on the all-zero state, and outcome 1 denotes acceptance.Source: Quantum computation · pp. 4–5

Counting classes

  • The counting-complexity background defines #P, FP, GapP, PP, A0PP, and BP·PP, emphasizing GapP closure properties used in quantum-classical containments.For BQP⊆PP, a GapP function is constructed so that its sign identifies membership, using the circuit’s gate matrices and Hadamard count.Source: Counting classes · pp. 5–6

Quantum interactive proofs

  • Three-message quantum interactive proofs use verifier register V, message register M, and prover workspace P, with alternating unitaries V1, U, and V2 before measurement.The prover sends M, the verifier applies V1 and returns M, the prover applies U and returns M, and the verifier applies V2 before accepting on outcome 1.Source: Quantum interactive proofs · pp. 6–7
  • The verifier’s maximum acceptance probability is characterized through state sets supported on a projection and their reduced states, with purification allowing the prover workspace to be limited to m+k qubits.The sets S(Λ) and SV(Λ) describe joint states and verifier-register reductions, while the acceptance expression is related to Uhlmann’s theorem and fidelity.Source: Quantum interactive proofs · p. 7

3 QMA

The paper formalizes QMA verification and presents strong error reduction that preserves Merlin’s message length. The construction yields exponentially small completeness and soundness errors and supports applications including QMA ⊆ PP.

3 QMA

  • QMA uses an m-qubit quantum certificate that a polynomial-time quantum verifier accepts with completeness at least a and soundness at most b.The standard convention is a = 2/3 and b = 1/3 when no bounds are specified.Source: §3 · p. 8

Strong Error Reduction

  • Earlier parallel-repetition error reduction requires multiple certificate copies and therefore increases Merlin’s message length, whereas the new construction avoids that increase.The earlier method must handle certificates that may be arbitrarily entangled across copies.Source: Strong Error Reduction · pp. 8–9
  • QMA(a, b) ⊆ QMA(1 − 2^-r, 2^-r) for every polynomial r, without increasing the m-qubit certificate length.The analysis extends from eigenstate certificates to arbitrary certificates using an orthonormal eigenbasis of the acceptance operator.Source: Strong Error Reduction · pp. 9, 12, 13
  • The verification procedure B repeatedly applies A and A†, measuring acceptance and restoration of Arthur’s workspace, then decides from the resulting outcome pattern.The projections distinguish Arthur’s acceptance or rejection from whether the workspace returns to its all-zero state.Source: Strong Error Reduction · p. 9
  • For an eigenstate with acceptance probability p, each transition preserves the previous outcome with probability p, so the observed sequences follow a binomial form.This transition structure enables Chernoff-type bounds for the final decision.Source: Strong Error Reduction · pp. 10–11

Applications of strong error reduction

L ∈QMAm

The paper shows that logarithmic-length quantum certificates add no power over BQP and derives a PP upper bound for QMA using acceptance operators and trace estimates.

L ∈QMAm

  • For a QMA verifier, the acceptance operator Q_x is positive semidefinite, and its trace is at least 3/4 on yes-instances but at most 1/4 on no-instances.The trace bounds follow from summing the nonnegative eigenvalues of Q_x under the verifier’s completeness and soundness guarantees.Source: L ∈QMAm · p. 13
  • QMA is contained in PP by representing scaled traces through GapP functions and testing the sign of a resulting GapP expression.The construction yields a GapP function positive on yes-instances and negative on no-instances; a related modification gives QMA ⊆ A0PP.Source: L ∈QMAm · pp. 13–14
  • The constants defining QMAlog are arbitrary because the paper’s error-reduction result changes completeness and soundness parameters without changing the certificate-length regime.The paper explicitly defines QMAlog using 2/3 and 1/3 and notes that this choice is arbitrary.Source: L ∈QMAm · p. 14
  • QMA with logarithmic-length certificates equals BQP.The proof replaces Merlin’s message with a totally mixed state; logarithmic certificate length leaves an inverse-polynomial acceptance gap that standard amplification can resolve.Source: L ∈QMAm · p. 14
  • A polynomial-time simulation uses the totally mixed m-qubit state, whose acceptance probability is proportional to tr(Q_x).This state can be implemented by uniformly selecting a standard-basis state, using Hadamard transforms and reversible computation.Source: L ∈QMAm · p. 14

4 QAM

The paper defines two-message quantum Arthur-Merlin games, proves parallel repetition for QAM, and places QAM within BP·PP.

4 QAM

  • QAM consists of protocols where Arthur sends uniformly random bits and Merlin responds with a quantum state depending on those bits.Arthur’s polynomial-time quantum circuit acts on Merlin’s message, Arthur’s workspace, and the random string.Source: §4 · p. 15

Error reduction for QAM

  • Parallel repetition reduces QAM completeness and soundness errors to 1−2^-r and 2^-r for every polynomially bounded r.The repeated protocol accepts when sufficiently many repetitions accept, and the theorem applies for all sufficiently large repetition counts.Source: Error reduction for QAM · p. 15
  • Merlin’s optimal strategy in the repeated QAM game is independent across repetitions, even though the protocol does not require independent play.The proof compares the unrestricted strategy with independent optimal strategies and then applies a Chernoff-type bound.Source: Error reduction for QAM · pp. 15–17

An upper bound on QAM

  • For a uniformly random Arthur message, the protocol’s maximum acceptance probability is bounded using the random variable μ(A_x,y), the best acceptance probability over Merlin’s message.The upper-bound argument uses the verifier’s completeness and soundness guarantees together with Markov’s inequality.Source: An upper bound on QAM · p. 17
  • QAM is contained in BP·PP.After error reduction, a PP language captures the relevant verifier behavior for most random strings, yielding the stated probabilistic-polynomial upper bound.Source: An upper bound on QAM · p. 17

5 QMAM

The paper formalizes three-message quantum Arthur-Merlin games, proves that they equal quantum interactive proofs, and extends error reduction and equivalence to longer protocols.

5 QMAM

  • QMAM protocols let Merlin send quantum messages before and after Arthur’s random coin flip, with Merlin’s second message generated by a unitary strategy.The formal definition accounts for Merlin retaining private qubits between messages and applying a coin-dependent unitary.Source: §5 · p. 18

Equivalence of QMAM and QIP

  • QMAM equals QIP.The inclusion from QMAM to QIP is immediate, while the reverse inclusion is obtained by simulating a three-message quantum interactive proof with a single random coin sent by Arthur.Source: Equivalence of QMAM and QIP · pp. 18–19
  • Every QIP language has a three-message QMAM protocol with perfect completeness, soundness error at most 1/2+2^-r, and only one coin-flip from Arthur.The construction uses fidelity-based bounds to control acceptance in the two coin-flip branches.Source: Equivalence of QMAM and QIP · pp. 18–19

Error reduction for QMAM

  • Parallel repetition reduces the soundness error of perfect-completeness QMAM protocols from b to b^N while preserving perfect completeness.This follows from the corresponding repetition property for three-message quantum interactive proofs.Source: Error reduction for QMAM · p. 20
  • For any polynomially bounded function r, QIP equals QMAM(1, 2^-r), with a three-message quantum Arthur–Merlin game having completeness error 0 and soundness error at most 1/2 + 2^-r.Source: Equivalence of QMAM and QIP · p. 19, Error reduction for QMAM · p. 20

More than three messages

  • Quantum Arthur-Merlin games with any polynomial number of messages are equivalent in power to three-message quantum Arthur-Merlin games.Polynomial-message games are quantum interactive proofs, which can be parallelized to three-message proofs and then simulated by three-message QMAM protocols.Source: Equivalence of QMAM and QIP · pp. 18–19, More than three messages · p. 20

6 Open questions

The paper closes by identifying unresolved questions about the relationships among quantum Arthur-Merlin classes, classical Arthur-Merlin classes, and the polynomial hierarchy.

6 Open questions

  • It remains open whether QMA or QAM contains interesting problems not known to lie in AM, and whether QMAM has problems not known to lie in PSPACE.These questions are presented as open examples concerning the relative power of quantum and classical verification models.Source: §6 · p. 20
  • It is unknown whether an oracle can separate BQP from AM, QMA or QAM from AM, or QMA or QAM from the polynomial hierarchy.The paper notes that even the existence of an oracle placing BQP outside AM is not known.Source: §6 · p. 20
  • The paper asks whether the classical identity almost-NP = AM has a quantum analogue, almost-QMA = QAM.This is posed as a separate open question about approximate class definitions.Source: §6 · p. 20
Loading cs/0506068v1…