Quantum Interactive Proofs (QIP)

A quantum interactive proof system is a cross-examination. On one side sits the verifier — a quantum machine restricted to time polynomial in the input length $n$ , honest but under-resourced. On the other sits the prover — computationally omnipotent but untrusted, wanting to convince the verifier that a common input $x$ belongs to a language $L$ . They exchange quantum registers back and forth; each party applies a quantum channel to the registers it controls, and after polynomially many messages the verifier measures one designated qubit and accepts or rejects. The language is in $\mathsf{QIP}$ when some verifier accepts valid inputs with probability at least $c$ and is fooled on invalid inputs with probability at most $s$ , the gap $c-s\geq 1/\mathrm{poly}(n)$ amplifiable to $c=1$ , $s=2^{-\mathrm{poly}(n)}$ . What makes this more than a single-shot certificate — more than its one-message cousin $\mathsf{QMA}$ — is adaptivity. The verifier can issue a random challenge, force a response, and check consistency; the prover's later messages may be entangled with the verifier's private workspace and with everything it has sent before. That entanglement-mediated commitment is both the source of the model's strength and the obstacle to naive analysis: a cheating prover holds a purification of every message, so one cannot assume messages are classical or fresh. The correct accounting frames the maximum acceptance probability as a semidefinite program over the prover's channels — an optimization whose value, remarkably, is computable in polynomial space. Two theorems then close the story: interaction of any length collapses to three messages, $\mathsf{QIP}=\mathsf{QIP}(3)$ (Kitaev–Watrous), and the class equals $\mathsf{PSPACE}$ exactly (Jain–Ji–Upadhyay–Watrous) — so single-prover quantum interaction buys nothing over classical, a sharp foil to two entangled provers, where the power explodes to the undecidable.

Key takeaways

$\mathsf{QIP}$ is the class of languages a quantum polynomial-time verifier can decide by exchanging polynomially many rounds of quantum messages with an all-powerful, untrusted prover, with a completeness–soundness gap bounded away from $1/2$ .
The headline theorem is $\mathsf{QIP}=\mathsf{PSPACE}$ (Jain–Ji–Upadhyay–Watrous, 2009): many rounds of quantum interaction with one prover buy exactly what classical interaction buys, since $\mathsf{IP}=\mathsf{PSPACE}$ (Shamir).
A second structural theorem is round reduction: $\mathsf{QIP}=\mathsf{QIP}(3)$ — every quantum interactive proof compresses to three messages with only polynomial loss in the gap, with no classical analogue.
The engine of the upper bound is that the optimal prover strategy is the solution of a semidefinite program over quantum channels, approximable in $\mathsf{PSPACE}$ by parallel matrix multiplicative weights.
$\mathsf{QIP}$ admits perfect completeness ( $c=1$ ), exponentially small soundness error, and is closed under complement; it contains $\mathsf{QMA}=\mathsf{QIP}(1)$ and all of $\mathsf{PH}$ .
Key idea: with a single prover, polynomial-round quantum interaction equals $\mathsf{PSPACE}$ and astonishingly collapses to three messages, $\mathsf{QIP}=\mathsf{QIP}(3)=\mathsf{PSPACE}$ — the verifier's maximal acceptance probability is the value of a semidefinite program solvable in polynomial space.

The core insight

With a single prover, polynomial-round quantum interaction equals $\mathsf{PSPACE}$ and collapses to just three messages: $\mathsf{QIP}=\mathsf{QIP}(3)=\mathsf{PSPACE}$ . The verifier's maximum acceptance probability over all prover strategies is the value of a semidefinite program, which can be solved in polynomial space.

Where this lives today

The interactive-proof viewpoint is now the backbone of how we think about trusting quantum computers. The full $\mathsf{QIP}=\mathsf{PSPACE}$ result uses an unbounded prover, but its machinery seeded the question that dominates the field: can a limited verifier check a powerful, untrusted quantum device? Urmila Mahadev's 2018 protocol answered a landmark version — a purely classical polynomial-time verifier can verify any $\mathsf{BQP}$ computation interactively, assuming learning-with-errors is hard —, and device-independent schemes in the Reichardt–Unger–Vazirani line let a near-classical verifier command entangled provers. The same soundness-against-purifications discipline underwrites quantum statistical zero-knowledge $\mathsf{QSZK}$ , and the parallel SDP solver built to prove $\mathsf{QIP}\subseteq\mathsf{PSPACE}$ fed back into classical optimization. Above all, the theorem is the sharpest signpost in the area: single-prover interaction stops at $\mathsf{PSPACE}$ — no quantum advantage from interaction alone — while the 2020 proof that $\mathsf{MIP}^{*}=\mathsf{RE}$ shows a second entangled prover launches the power to the undecidable, resolving Tsirelson's problem and the Connes embedding conjecture along the way.

The physical picture

Picture the protocol as a conversation on a wire. The verifier and prover each hold private quantum memory, and between them passes a shared message register that shuttles back and forth. On its turn each party applies a channel — efficient for the verifier, an arbitrary CPTP map for the prover — and hands the register across. The honest prover has a strategy that lights up the accept qubit with certainty when $x\in L$ ; a cheating prover, however clever, cannot push it past the soundness threshold $s$ when $x\notin L$ . The first figure freezes this dialogue at its most economical form — the three messages Kitaev and Watrous showed already suffice.

Figure

Three-message quantum interactive proof: the prover sends a message, the verifier issues a challenge, the prover responds, and the verifier measures one output qubit — this QIP(3) form already captures all of QIP, accepting with probability at least c = 1 when x is in L and at most s = 2⁻ᵖᵒˡʸ when x is not in L, so the gap c − s stays at least 1/poly

The reason interaction is powerful, and the reason it is hard to analyze, is the same: the prover never lets go of its purification. Every message it sends is entangled with a private register it keeps, so a dishonest prover is not choosing classical strings but quantum channels, and it can correlate its late answers with its early ones. Soundness therefore cannot be argued against any fixed mixed state; it must be argued against the best channel the prover could ever apply. The saving grace is that the verifier's acceptance probability is linear in the prover's channel, subject only to that channel being trace-preserving and completely positive — which turns "find the best cheating prover" into a semidefinite program, and the whole class into a question about where such programs sit. The second figure places the answer.

Figure

Where QIP lives: with one prover, quantum interaction collapses to PSPACE, so QIP = QIP(3) = IP = PSPACE, and QMA = QIP(1) is the one-message floor inside PP; only two entangled provers escape, all the way to the undecidable MIP∗ = RE

The core equations

The definition fixes the model: a language is in $\mathsf{QIP}$ when a single quantum verifier separates yes-inputs from no-inputs by the acceptance probability it can be driven to, maximized over all provers. The maximization on both branches is essential — the honest prover witnesses membership, and the best possible cheating prover must still fail on non-membership.

L\in\mathsf{QIP} \iff \exists\,V:\; x\in L\Rightarrow \max_{P}\Pr[V\leftrightarrow P\text{ accepts}]\geq c,\quad x\notin L\Rightarrow \max_{P}\Pr[V\leftrightarrow P\text{ accepts}]\leq s \qquad (1)

where: $V$ — a polynomial-time quantum ( $\mathsf{BQP}$ ) verifier; $P$ — a computationally unbounded quantum prover; $V\leftrightarrow P$ — the interaction, alternating channels on a shared message register; $c,s$ — completeness and soundness thresholds with gap $c-s\geq 1/\mathrm{poly}(n)$ . Read it as: yes-inputs are provable, no-inputs unprovable, with a margin no adversary can erase. The central theorem is a triple equality — the model is insensitive both to the number of rounds (any poly collapses to three) and to being quantum at all (three quantum messages equal the classical ceiling).

\mathsf{QIP}=\mathsf{QIP}(3)=\mathsf{PSPACE} \qquad (2)

where: $\mathsf{QIP}(m)$ — languages with quantum interactive proofs of exactly $m$ messages; $\mathsf{PSPACE}$ — languages decidable in polynomial space. The equality bundles a lower bound $\mathsf{PSPACE}\subseteq\mathsf{QIP}$ (from $\mathsf{IP}=\mathsf{PSPACE}$ ), a round collapse $\mathsf{QIP}=\mathsf{QIP}(3)$ , and an upper bound $\mathsf{QIP}(3)\subseteq\mathsf{PSPACE}$ . Formally the interaction is a composition of channels on a fixed set of registers initialized to all-zeros. The verifier's and prover's maps alternate; only the verifier's are constrained to be efficient.

\rho_{\text{out}} = \big(\mathcal{V}_k\circ\mathcal{P}_k\circ\cdots\circ\mathcal{P}_1\circ\mathcal{V}_0\big)\big(\lvert 0\cdots 0\rangle\langle 0\cdots 0\rvert\big) \qquad (3)

where: $\mathcal{V}_i$ — the verifier's channel at round $i$ (efficient, without loss of generality a unitary on ancillas); $\mathcal{P}_j$ — the prover's channel at round $j$ (an arbitrary CPTP map on the message register and its private memory); $\rho_{\text{out}}$ — the final joint state, from which the verifier reads one designated output qubit. Acceptance is a projective measurement of that qubit: the probability is the trace of the accept projector against the final state — linear in $\rho_{\text{out}}$ , hence in each channel.

\Pr[\text{accept}] = \mathrm{Tr}\!\left[\Pi_{\text{acc}}\,\rho_{\text{out}}\right],\qquad \Pi_{\text{acc}}=\lvert 1\rangle\langle 1\rvert_{\text{out}}\otimes I \qquad (4)

where: $\Pi_{\text{acc}}$ — the projector onto the "accept" value of the output qubit, tensored with identity; $\mathrm{Tr}$ — the trace over all registers. Because this is linear in the prover's maps, optimizing over provers is convex — the key to the upper bound. Define the optimal value of the protocol as the best acceptance probability over all provers. This value is exactly the optimum of a semidefinite program.

\omega(V)=\max_{P}\ \mathrm{Tr}\!\left[\Pi_{\text{acc}}\,\rho_{\text{out}}(P)\right]=\text{value of an SDP} \qquad (5)

where: $\omega(V)$ — the maximum acceptance probability over all provers; $P$ — a prover strategy encoded by Choi operators obeying positivity and trace-preservation. Deciding $L$ reduces to estimating $\omega(V)$ and comparing it to the midpoint $(c+s)/2$ . Finally, the gap is not fragile: any inverse-polynomial gap amplifies to perfect completeness and exponentially small soundness error, and the class is closed under complement.

c=1,\qquad s\leq 2^{-q(n)}\ \text{for any polynomial }q,\qquad \mathsf{QIP}=\mathsf{co\text{-}QIP} \qquad (6)

where: $c=1$ — an honest prover makes the verifier accept a yes-input with certainty; $s\leq 2^{-q(n)}$ — soundness error driven exponentially small by repetition; $\mathsf{co\text{-}QIP}$ — complements of $\mathsf{QIP}$ languages, equal to $\mathsf{QIP}$ since $\mathsf{PSPACE}=\mathsf{co\text{-}PSPACE}$ .

Derivation AQuantum interaction sits in PSPACE via the SDP value

The goal is to explain why $\mathsf{QIP}\subseteq\mathsf{PSPACE}$ without ever simulating the exponential-dimensional interaction directly. The strategy has three moves: first collapse any protocol to three messages so that the prover applies a single channel; then encode that channel as a Choi operator, turning "best cheating prover" into the maximization of a linear functional over positive semidefinite matrices with an affine trace-preservation constraint — a semidefinite program; and finally observe that this particular SDP, though of exponential dimension, has enough parallel structure that a matrix multiplicative-weights algorithm approximates its value in polynomially many parallel iterations, each of which a polynomial-space machine can carry out. The membership decision is then a comparison of the approximate value to the acceptance threshold.

Step 1. Apply the Kitaev–Watrous parallelization to reduce to $\mathsf{QIP}(3)$ : a single verifier message, a single prover reply, and a final verifier measurement, with the completeness–soundness gap preserved up to a $1/\mathrm{poly}(n)$ factor. Why: with exactly one prover channel to optimize over, the strategy space becomes a single convex set of operators rather than a tree of adaptive maps, which is what makes an SDP formulation possible at all.

Step 2. Encode the prover's channel $\mathcal{P}:A\to B$ by its Choi operator $J(\mathcal{P})$ , so that complete positivity becomes $J(\mathcal{P})\succeq 0$ and trace preservation becomes the linear constraint $\mathrm{Tr}_{B}\,J(\mathcal{P})=I_{A}$ . Why: the Choi isomorphism converts an abstract channel into a matrix living in a fixed cone, replacing "quantify over channels" with "quantify over PSD matrices satisfying one affine equation".

Step 3. Write the acceptance probability as $\omega(V)=\max_{J}\ \langle Q_V,\,J\rangle$ , where $Q_V\succeq 0$ is a fixed operator assembled from the verifier's two channels and the accept projector, and the maximum is over $J\succeq 0$ with $\mathrm{Tr}_{B}J=I_A$ . Why: because acceptance is linear in the prover's map, the objective is a linear functional of $J$ — this is precisely a semidefinite program, with $Q_V$ as its cost matrix.

Step 4. Solve the SDP by the parallel matrix multiplicative-weights method: iterate $X^{(t+1)}\propto \exp\!\big(\eta\sum_{\tau\leq t}M^{(\tau)}\big)$ , updating a matrix weight against the constraint violations, for $O(\log(\dim)/\varepsilon^2)$ rounds to reach additive error $\varepsilon$ . Why: multiplicative weights needs only matrix exponentials and inner products, each computable in polynomial space even for an operator of dimension $2^{\mathrm{poly}(n)}$ , and the iteration count is only polynomial — so the whole optimization fits in $\mathsf{PSPACE}$ .

Step 5. Compare the approximate value to the midpoint $(c+s)/2$ to decide membership; choosing $\varepsilon$ smaller than half the gap makes the comparison correct. Why: an inverse-polynomial gap survives the round reduction, so a polynomially small $\varepsilon$ suffices, and every ingredient — reduction, encoding, iteration, comparison — has been shown to run in polynomial space.

\mathsf{QIP}\subseteq\mathsf{PSPACE}\qquad\text{(upper bound)}

Verified against Jain–Ji–Upadhyay–Watrous, J. ACM 58(6) (2011): a verifier should reproduce the Choi-operator SDP, its trace-preservation constraint, and the $O(\log/\varepsilon^2)$ multiplicative-weights iteration count.

Go deeper · Derivation B · 2 minPSPACE sits inside QIP from Shamir's theorem

Derivation BPSPACE sits inside QIP from Shamir's theorem

The goal is to show the matching lower bound $\mathsf{PSPACE}\subseteq\mathsf{QIP}$ costs nothing to obtain, because it is inherited wholesale from the classical theorem $\mathsf{IP}=\mathsf{PSPACE}$ . The plan is to recall Shamir's result — that the $\mathsf{PSPACE}$ -complete problem of true quantified Boolean formulas has a classical interactive proof via arithmetization and sum-check — and then to argue that a classical interactive proof is literally a special case of a quantum one, obtained by restricting the verifier to computational-basis operations and classical randomness. Because the embedding preserves acceptance probabilities exactly, completeness and soundness carry over unchanged, and every $\mathsf{PSPACE}$ language lands in $\mathsf{QIP}$ .

Step 1. Invoke Shamir's theorem: $\mathsf{TQBF}$ , the language of true fully quantified Boolean formulas and a $\mathsf{PSPACE}$ -complete problem, has an interactive proof, so $\mathsf{IP}=\mathsf{PSPACE}$ . Why: TQBF being $\mathsf{PSPACE}$ -complete means a protocol for it, plus polynomial-time reductions, yields a protocol for every $\mathsf{PSPACE}$ language — the lower bound need only be established once.

Step 2. Note that the LFKN–Shamir protocol proves TQBF by arithmetizing the formula over a finite field and running the sum-check protocol, whose per-round soundness error is at most $d/\lvert\mathbb{F}\rvert$ for a polynomial of degree $d$ . Why: keeping the soundness error inverse-exponential across polynomially many rounds is what gives a genuine gap $c-s\geq 1/\mathrm{poly}$ , the object the quantum embedding must preserve.

Step 3. Observe that a probabilistic polynomial-time classical verifier is a restricted quantum verifier: one that measures only in the computational basis and draws randomness from ancilla qubits prepared in uniform superposition and immediately measured. Why: this exhibits the classical verifier as a legal $\mathsf{BQP}$ verifier, so the classical protocol is a bona fide quantum interactive proof, not merely an analogue of one.

Step 4. Send classical messages as computational-basis states; the honest and optimal cheating strategies available classically remain available to a quantum prover, and the acceptance probabilities match: $\Pr_{\text{quantum}}[\text{accept}]=\Pr_{\text{classical}}[\text{accept}]$ . Why: identical acceptance probabilities mean completeness and soundness transfer verbatim, so $L\in\mathsf{IP}\Rightarrow L\in\mathsf{QIP}$ .

Step 5. Conclude $\mathsf{PSPACE}=\mathsf{IP}\subseteq\mathsf{QIP}$ ; combined with the upper bound of the previous derivation, $\mathsf{QIP}=\mathsf{PSPACE}$ . Why: two inclusions in opposite directions pin the class exactly, and the round collapse then reads $\mathsf{QIP}(3)=\mathsf{PSPACE}$ as well.

\mathsf{PSPACE}=\mathsf{IP}\subseteq\mathsf{QIP}\qquad\text{(lower bound)}

Verified as standard: a verifier should check the sum-check soundness $\leq d/\lvert\mathbb{F}\rvert$ per round in LFKN/Shamir and the trivial classical-to-quantum embedding of verifier and messages.

Limiting cases

How the power of the model depends on the number of messages, the type of message, and the number of provers:

Case	Result	Meaning
One message	$\mathsf{QIP}(1)=\mathsf{QMA}$	A single quantum certificate from prover to verifier; believed strictly inside $\mathsf{PSPACE}$ , and provably inside $\mathsf{PP}$ .
Three messages	$\mathsf{QIP}(3)=\mathsf{QIP}=\mathsf{PSPACE}$	Round collapse: three messages already realize the full power of polynomial-round quantum interaction.
Polynomially many rounds	$\mathsf{QIP}=\mathsf{QIP}(\mathrm{poly})=\mathsf{PSPACE}$	Extra rounds beyond three buy nothing; the ceiling matches classical $\mathsf{IP}=\mathsf{PSPACE}$ .
Classical interaction	$\mathsf{IP}=\mathsf{PSPACE}\subseteq\mathsf{QIP}$	Every classical interactive proof is a degenerate quantum one, giving the lower bound for free.
Two entangled provers	$\mathsf{MIP}^{*}=\mathsf{RE}$	Two non-communicating provers sharing entanglement make verification as hard as the halting problem — far beyond $\mathsf{PSPACE}$ .

Common trapA cheating prover just sends some fixed classical or fresh quantum message

It does not, and assuming so is the fastest way to a wrong soundness proof. The prover holds a global purification of the whole interaction, so every message it sends is entangled with a private register it retains and with all of its earlier messages. A dishonest prover is choosing a channel, adaptively correlated across rounds, not a state — and it can steer late answers using information smuggled in early ones. Soundness must therefore be argued against the semidefinite-program optimum $\omega(V)$ over all such channels, never against a single fixed mixed state. A second trap in the same family: the collapse $\mathsf{QIP}=\mathsf{QIP}(3)$ is strictly a single-prover phenomenon. It says nothing about the multi-prover entangled setting, where no analogous round reduction holds and the power climbs all the way to the undecidable $\mathsf{MIP}^{*}=\mathsf{RE}$ .

Worked examples

1 · Amplifying a weak gap to exponentially small error (fully worked)

A protocol has completeness $c=2/3$ and soundness $s=1/3$ , so its gap is only a constant. You want a soundness error at most $2^{-100}$ . Running the protocol $N$ times independently and taking a majority vote, how large must $N$ be?

Step 1. Each run outputs an accept/reject bit — probability $\leq s=1/3$ on a no-input, $\geq c=2/3$ on a yes-input. Set the majority threshold at $1/2$ ; an error needs the empirical fraction to cross $1/2$ , a deviation of at least $\delta=\tfrac12-\tfrac13=\tfrac16$ from the mean. The per-run advantage is $\delta = 1/6$ .

Step 2. Hoeffding's inequality bounds the probability that the mean of $N$ independent $[0,1]$ variables deviates from its expectation by $\delta$ : $\Pr[\text{error}]\leq e^{-2N\delta^{2}}=e^{-2N/36}=e^{-N/18}$ . The error decays as $e^{-N/18}$ .

Step 3. Demand $e^{-N/18}\leq 2^{-100}$ . Take logarithms: $N/18\geq 100\ln 2=69.31$ , so $N\geq 18\times 69.31=1247.7$ . Rounding up, $N=1248$ repetitions suffice to push the soundness error below $2^{-100}$ while keeping completeness near $1$ .

Step 4. The lesson: a constant gap amplifies to cryptographic-strength soundness at only a polynomial ( $\sim\!1.2\times10^{3}$ ) cost in runs, which is why $\mathsf{QIP}$ can fix any convenient constant gap. In the quantum setting naive parallel repetition can interact with entanglement, but sequential repetition with a fresh verifier works, and $\mathsf{QIP}$ even admits perfect completeness $c=1$ . Constant gap $\to$ error $2^{-100}$ in $N=1248$ runs.

2 · Why the classical sum-check protocol already lands in QIP

The lower bound $\mathsf{PSPACE}\subseteq\mathsf{QIP}$ runs the classical sum-check protocol for $\mathsf{TQBF}$ . Estimate its soundness for a formula on $n=50$ variables, taking arithmetized degree $d\leq 2$ per round, about $m=2n^{2}=5000$ rounds, and a field of size $\lvert\mathbb{F}\rvert=2^{100}$ .

Step 1. In sum-check the prover sends a low-degree polynomial each round; if it lies, the verifier's random field point catches the lie unless it happens to be a root, which occurs with probability at most $d/\lvert\mathbb{F}\rvert$ . Per-round soundness error $\leq d/\lvert\mathbb{F}\rvert = 2/2^{100}=2^{-99}$ .

Step 2. By a union bound over the $m=5000$ rounds, the total soundness error is at most $m\,d/\lvert\mathbb{F}\rvert = 5000\times 2^{-99}$ . Since $5000<2^{13}$ , this is below $2^{13}\cdot 2^{-99}=2^{-86}$ . Total soundness error $< 2^{-86}$ — exponentially small.

Step 3. Completeness is exact: an honest prover always sends the true polynomials and is always accepted, so $c=1$ . Embed classically: coin flips become measured ancilla qubits, field elements are sent as computational-basis states, and the quantum acceptance probability equals the classical one exactly — a $\mathsf{QIP}$ protocol with $c=1$ , $s<2^{-86}$ . Because $\mathsf{TQBF}$ is $\mathsf{PSPACE}$ -complete, this single embedded protocol certifies $\mathsf{PSPACE}\subseteq\mathsf{QIP}$ , using no superposition beyond simulating classical randomness. Interaction, not quantumness, carries the power — one prover's quantum messages add no ceiling above classical interaction.

Physics of the portrait

The theory of quantum interactive proofs has one clear through-line: a single researcher who defined the class, proved it collapses to three messages, and finally pinned it exactly to $\mathsf{PSPACE}$ .

Origins · 1 minJohn Watrous and how this was discovered

John Watrous

computer scientist, Institute for Quantum Computing, University of Waterloo · defined the class QIP and led the proof that QIP = PSPACE

Quantum interactive proofs are, to a large degree, John Watrous's subject. In his 1999 paper "PSPACE has constant-round quantum interactive proof systems" he introduced $\mathsf{QIP}$ as the quantum analogue of Babai's and Goldwasser–Micali–Rackoff's interactive proofs, showed quantum verifiers could check every $\mathsf{PSPACE}$ language in a constant number of rounds, and bounded the class above by $\mathsf{EXP}$ . The following year, with Alexei Kitaev, he proved the round-reduction theorem $\mathsf{QIP}=\mathsf{QIP}(3)$ (STOC 2000): every quantum interactive proof folds into three messages with only polynomial loss in the gap — a phenomenon with no classical counterpart. The exact power then stood open for nearly a decade, squeezed between $\mathsf{PSPACE}$ and $\mathsf{EXP}$ , until it fell in 2009 when Watrous, with Rahul Jain, Zhengfeng Ji, and Sarvagya Upadhyay, proved $\mathsf{QIP}=\mathsf{PSPACE}$ by recognizing the optimal prover strategy as a semidefinite program and solving it in polynomial space — settling a complexity question and producing a new space-efficient SDP solver at once. His 2018 textbook The Theory of Quantum Information remains the standard reference for the channel-and-SDP machinery the whole story rests on.

History

1985

— Goldwasser, Micali, Rackoff and, independently, Babai introduce interactive proof systems

1992

— Shamir proves IP = PSPACE, building on the LFKN sum-check protocol

1999

— Watrous defines QIP and shows PSPACE has constant-round quantum interactive proofs

2000

— Kitaev and Watrous prove the round-reduction theorem QIP = QIP(3)

2009

— Jain, Ji, Upadhyay and Watrous prove QIP = PSPACE via a semidefinite program

Going further

Texts. Watrous, The Theory of Quantum Information (2018), chapters on quantum channels and interactive proofs · Kitaev, Shen, Vyalyi, Classical and Quantum Computation (2002) · Wilde, Quantum Information Theory, 2nd ed. (2017) · Vidick & Watrous, Quantum Proofs, Foundations and Trends in Theoretical Computer Science (2016) · Arora & Barak, Computational Complexity (2009), chapters on interactive proofs and $\mathsf{IP}=\mathsf{PSPACE}$ .

Provenance. The model and the round collapse $\mathsf{QIP}=\mathsf{QIP}(3)$ follow Kitaev & Watrous, STOC 2000, and Watrous (2018). The equality $\mathsf{QIP}=\mathsf{PSPACE}$ is Jain, Ji, Upadhyay & Watrous, J. ACM 58(6) (2011); the lower bound uses Shamir's $\mathsf{IP}=\mathsf{PSPACE}$ (1992) and the LFKN sum-check protocol (1990). A verifier should recompute: the Choi-operator SDP and its trace-preservation constraint; the $O(\log/\varepsilon^{2})$ multiplicative-weights iteration count; the sum-check soundness $\leq d/\lvert\mathbb{F}\rvert$ per round; the Hoeffding amplification $N=1248$ for error $2^{-100}$ at gap $1/6$ ; and the classical-to-quantum embedding. All class inclusions are standard; no constants are fabricated.

Prerequisites. The Complexity Class BQP · Quantum Merlin–Arthur (QMA) · BQP is Contained in PP and PSPACE · BQP versus P, NP, and PSPACE. Leads to. QIP = PSPACE · MIP∗ = RE · QMA Variants and Related Classes.

Ask the tutor: Ask me to walk through why the prover's optimal strategy is a semidefinite program, or how three messages can possibly capture every quantum interactive proof.

What is the difference between QIP and QMA?

$\mathsf{QMA}$ is the one-message case, $\mathsf{QIP}(1)$ : the prover sends a single quantum certificate $\lvert\psi\rangle$ and the verifier checks it, with no back-and-forth. $\mathsf{QIP}$ allows the verifier to reply — to issue random challenges and demand consistent answers over polynomially many rounds. That adaptivity is exactly what lifts the class from $\mathsf{QMA}$ (contained in $\mathsf{PP}$ , believed strictly below $\mathsf{PSPACE}$ ) up to all of $\mathsf{PSPACE}$ . The relationship mirrors the classical one between $\mathsf{NP}$ (one message) and $\mathsf{IP}=\mathsf{PSPACE}$ (many messages): interaction is where the power lives.

Why does QIP = QIP(3) not collapse classical IP to constant rounds?

The quantum round-reduction leans on genuinely quantum tricks — folding many messages into a single register and running one consistency test (a swap-test-like check) on what returns — that have no classical counterpart. If classical $\mathsf{IP}$ collapsed to a constant number of rounds, then $\mathsf{PSPACE}$ would sit inside $\mathsf{AM}$ , which would collapse the polynomial hierarchy to its second level. Complexity theorists overwhelmingly believe that does not happen, so the classical and quantum stories differ sharply on round structure even though they share the same ceiling, $\mathsf{PSPACE}$ . The collapse is a statement about quantum message compression, not about interaction in general.

How can a proof about quantum computation be carried out in polynomial space?

Because the object being computed is not the exponential-dimensional quantum state but a single number: the optimal acceptance probability $\omega(V)$ . After reducing to three messages, that number is the value of a semidefinite program, and semidefinite programs can be solved by matrix multiplicative weights using only matrix exponentials and inner products. Each such operation, even on a $2^{\mathrm{poly}(n)}$ -dimensional operator, is expressible as a polynomial-space computation, and only polynomially many iterations are needed. So one never stores the whole state — one iterates an optimization whose every step fits in polynomial space, and reads off the answer.

Does QIP = PSPACE mean quantum computers give no advantage?

No — it is a precise, local statement about interaction with a single prover, not a global verdict on quantum computing. It says that if all the power comes from a dialogue with one untrusted prover, quantum messages do not raise the ceiling above classical interaction ( $\mathsf{IP}=\mathsf{PSPACE}$ ). Quantum advantage lives elsewhere: in $\mathsf{BQP}$ versus classical polynomial time (factoring, simulation), in the still-open gap between $\mathsf{QMA}$ and $\mathsf{NP}$ for single-message proofs, and most dramatically in the multi-prover entangled setting, where $\mathsf{MIP}^{*}=\mathsf{RE}$ dwarfs the classical $\mathsf{MIP}=\mathsf{NEXP}$ . $\mathsf{QIP}=\mathsf{PSPACE}$ sharpens the map by ruling one region flat.

What exactly is the Choi operator and why does it matter here?

The Choi operator $J(\mathcal{P})$ is a matrix that fully encodes a quantum channel $\mathcal{P}$ : you feed half of a maximally entangled pair through the channel and record the resulting joint state. Its value is that the awkward, infinite set of "all physical channels" becomes a clean convex set of matrices — those that are positive semidefinite and satisfy one linear trace-preservation equation. Because the verifier's acceptance probability is linear in the prover's channel, and hence linear in $J(\mathcal{P})$ , optimizing over all cheating provers becomes maximizing a linear function over that convex set: a semidefinite program. Without the Choi picture there is no clean optimization to solve, and no route into $\mathsf{PSPACE}$ .

Why do two entangled provers behave so differently from one?

With a single prover the verifier can purify the entire interaction into one strategy of fixed (if exponential) dimension, and the optimum is a finite-dimensional semidefinite program — computable, and bounded by $\mathsf{PSPACE}$ . With two non-communicating provers sharing entanglement, the optimal success is a supremum over entangled strategies of unbounded dimension, with no Tsirelson-style finite cutoff. That supremum is not merely hard to compute — it is uncomputable, which is the content of $\mathsf{MIP}^{*}=\mathsf{RE}$ . The entanglement between separate provers cannot be "purified away" by the verifier, and it is precisely that irreducibility which defeats the single-prover SDP analysis.