PaperlayerView exact revision on arXiv

Source-linked AI summary

Separating QMA from QCIP with a Classical Oracle, or, the Power of Quantum Proofs over Classical Interaction for Quantum Verifiers

Alper Cakan

arXiv:2610.03648v1cs.CC

TL;DR

Earlier classical-oracle separations between QMA and QCMA still allowed classical-verifier interactive proofs, leaving open whether any problem truly requires quantum proofs. This paper uses a classical oracle to separate QMA from QCIP, ruling out classical-message interactive replacements for some languages.

  • Problem

    Earlier classical-oracle QMA–QCMA separations and [BHV26] used languages in AM, leaving open whether any language truly requires quantum proofs.

    Source: §1 · p. 4

  • Method

    The paper extends incompressibility techniques to approximate interactions between an efficient quantum verifier and an unbounded prover by simulating only the verifier with classical oracle queries.

    Source: §1.1 · p. 5

  • Results

    A classical oracle O and unary language L satisfy L ∈ QMA^O \ QCIP^O, with QCMA^O separation following as a special case.

    Source: §1.1 · pp. 4–5

  • Takeaways & Limitations

    Some languages require quantum proofs even against arbitrary polynomial-round classical-message interaction with a quantum verifier.

    Source: §1.1 · p. 4

    The simulation relies on classical messages: the incompressibility property applies to classical strings, and repeated verifier runs are unavailable with quantum messages.

    Source: §2.5.1 · p. 12

Abstract

from arXiv · show

Whether some problems require quantum proofs has been a central question in quantum complexity (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC 2007). Recently, breakthrough work of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC 2026), followed by a simpler separation due to Bostanci, Huang, and Vaikuntanathan (FOCS 2026), established a classical oracle separation between $\mathsf{QMA}$ and $\mathsf{QCMA}$. However, while they are not in $\mathsf{QCMA}$, the problems used in both separations still lie in $\mathsf{AM}$: they admit a two-message public-coin proof system with a classical verifier. In this work, we ask whether some problems truly require quantum proofs. More formally, we consider the complexity class $\mathsf{QCIP}$, introduced by Buhrman, Le Gall, and Weggemans (2024), where an efficient quantum verifier interacts with an unbounded prover over a classical channel for an arbitrary polynomial number of rounds. We construct a classical oracle $\mathcal{O}$ such that $\mathsf{QMA}^{\mathcal{O}}\not\subseteq\mathsf{QCIP}^{\mathcal{O}}$, thus showing that some languages indeed require quantum proofs, with no classical replacements. Since $\mathsf{QCMA}=\mathsf{QCIP}[1]$, this strengthens the earlier $\mathsf{QMA}$--$\mathsf{QCMA}$ separations, which now follow as a special case of our result. As a technical contribution, we extend to the complexity theory setting the techniques developed by Cakan, Goyal, and Shmueli (CRYPTO 2026) in the context of cryptography for analyzing classically interacting quantum machines. We believe this may be of independent interest.

1 Introduction

The paper asks whether any language truly requires quantum proofs, beyond merely lacking a classical witness. It answers yes with a classical-oracle separation between QMA and QCIP, and develops techniques for analyzing classical interactions between quantum machines.

1 Introduction

  • Earlier classical-oracle QMA–QCMA separations and [BHV26] still had languages in AM, so they did not establish that quantum proofs were necessary.The paper notes that the [BHV26] language has a two-message public-coin protocol with a classical verifier.Source: §1 · p. 4
  • The paper formalizes the question using QCIP: a quantum verifier and unbounded prover exchange classical messages for polynomially many rounds, with private quantum memory.QCMA is the one-message case, QCIP[1] [BLW24].Source: §1 · p. 4

1.1 Our Results

  • A classical oracle O and unary language L satisfy L ∈ QMA^O \ QCIP^O, so QCMA separation follows because QCMA^O = QCIP[1]^O.The result establishes a language with no classical-message interactive proof system using a quantum verifier, not just no classical witness.Source: §1.1 · pp. 4–5
  • The paper extends incompressibility techniques to interactions between an efficient quantum verifier and an unbounded prover, simulating the verifier with classical oracle queries.Earlier techniques analyzed two efficient machines and modified both; this approach approximates the protocol by simulating only the verifier.Source: §1.1 · p. 5

2 Technical Overview

The overview frames the separation as a distributional oracle-input problem and states acceptance guarantees for quantum witnesses versus interactive classical-message proofs. It recalls the proof-system and oracle-input models used to express those guarantees.

2.1 Model and Our Main Theorem

  • In QCIP, a quantum verifier and prover exchange polynomially many classical bits over polynomially many rounds, while retaining private quantum memory.The one-classical-message case is QCMA = QCIP[1].Source: §2.1 · p. 6
  • In QMA, the prover sends one polynomial-size quantum witness, after which the verifier decides without further interaction.A proof system requires completeness and soundness for YES and NO inputs, respectively.Source: §2.1 · p. 6
  • The oracle-input model gives algorithms quantum query access to a finite Boolean table, with resources measured by the sequence parameter rather than table length.The theorem uses this model to formulate a distributional problem that can be converted into an oracle separation.Source: §2.1 · pp. 6–7
  • The main theorem considers YES and NO distributions over oracle inputs with overlapping supports and states acceptance guarantees for QMA and QCIP.The overview identifies a polynomial-time quantum verifier with polynomial-size witnesses for the QMA upper bound.Source: §2.1 · p. 7

2. QCIP lower bound.

The section establishes a classical-oracle lower bound for QCIP using YES and NO oracle distributions built around code-preimage search. It analyzes classical interactive proofs through a classical simulation and cheating prover, combining incompressibility and quantum decoding with bounds on the prover’s reply search and final verification under the NO distribution.

2. QCIP lower bound.

  • A classical oracle O and unary language L^O exist with L^O in QMA^O but not QCIP^O; QCIP protocols complete on most YES oracles also admit cheating provers on a substantial fraction of NO oracles.In particular, completeness on a 1−ε fraction of YES oracles implies that on at least a 1/3−ε fraction of NO oracles some prover makes the verifier accept with probability greater than 1/3.Source: §2 · p. 7, §2.5 · p. 10

2.2 Oracle Intuition

  • The oracle intuition combines classical incompressibility—classical strings cannot encode many solutions—with quantum equivocation, while extending Cakan, Goyal, and Shmueli techniques to classical interaction.The YES oracle contains instances of a search problem, whereas the NO oracle independently marks points; incompressibility limits how many solutions classical messages can convey.Source: §2.2 · p. 8

2.3 The Oracles

  • YES oracles encode biased code-preimage pairs, while NO oracles independently mark points; the construction uses p = λ−4, δ = 2−⌈λ/12⌉, and a univariate multiplicity code.A quantum algorithm can find code preimages for fixed targets, and the verifier accesses only O, not the hash functions H.Source: §2.3 · p. 9

2.4 The QMA Proof System

  • Under YESλ, the verifier accepts with probability at least 1−2^-λ on at least a 1−2^-λ fraction of oracles, sampling u uniformly and checking O(y,v).Source: §2.4 · p. 10

Acceptance under the NO distribution

  • Under NO, the verifier samples its target after receiving the witness, limiting the witness’s information about that target’s oracle slice and bounding acceptance for arbitrary witnesses.The argument compares execution with an independent copy of the slice, whose acceptance is at most δ, then applies Pinsker’s and Markov’s inequalities.Source: Acceptance under the NO distribution · p. 10

2.5 QCIP Lower Bound

  • The QCIP lower bound first simulates the quantum verifier classically, then applies public-coin and perfect-completeness transformations, and finally constructs a cheating prover using incompressibility.The simulation preserves acceptance up to additive error 1/100 for every prover on all but a negligible fraction of oracles; the final argument transfers cheating to the original verifier.Source: §2.5 · pp. 10–11

2.5.1 Classical Simulation

  • The classical simulator learns verifier queries into oracle-estimation databases; unlike Cakan, Goyal, and Shmueli, it works for arbitrary provers simultaneously and uses polynomially many queries.Classical messages permit repeated executions and incompressibility arguments; a cutoff bounds queries while preserving acceptance up to 1/100 except on a negligible fraction of oracles.Source: §2.5.1 · pp. 11–13
  • Outside an exceptional fraction of oracles, the classical simulation’s cutoff adds at most 1/200 to its error for every prover.The cutoff probability is bounded by the probability that some s-bit message decodes to t pairs marked by the oracle.Source: §2.5.1 · p. 14

2.5.2 A Cheating Prover

  • The prover tracks the transcript and consistent candidate YES oracles, retaining candidates that mark tested pairs in the actual NO oracle.After a failed test it removes candidates and retries the same reply; choosing a largest test set ensures universally marked pairs are within that set.Source: §2.5.2 · pp. 14–16
  • The cheating prover finds a reply in every round except with probability at most δ over the NO oracle and public coins.The analysis uses independent pair markings and a union bound over possible states and public coins.Source: §2.5.2 · p. 16
  • When every search succeeds, the verifier’s final computation rejects with probability at most N2δ.A candidate oracle agrees with the computation’s answers on universally marked pairs; comparing those answers with the actual NO oracle gives the bound.Source: §2.5.2 · p. 16

3 Preliminaries

The preliminaries fix notation and oracle-access conventions, then define proof systems relative to a fixed oracle and to finite oracle-table inputs.

3.1 Notation and Conventions

  • The conventions define sampling, distributions, information measures, quantum states, and interactive transcripts; parties may retain private memory between rounds.Promise problems require completeness and soundness only on their designated YES and NO inputs.Source: §3.1 · pp. 17–18, §3.3 · p. 19

3.2 Oracle Access

  • Quantum algorithms access a Boolean oracle in superposition, while classical queries specify an address and receive its bit.Each quantum oracle-gate application counts as one query; polynomial running time implies a polynomial query bound.Source: §3.2 · p. 18

3.3 Proof Systems Relative to a Fixed Oracle

  • For a fixed oracle, QMA uses a quantum witness and QCMA uses a classical witness, with a quantum verifier in both classes.Pure quantum witnesses suffice, and the witness may depend on the input and oracle.Source: §3.3 · pp. 18–19
  • A QCIP protocol uses a polynomial-time quantum verifier, an unbounded classical prover, polynomially many classical messages and rounds, and may retain verifier quantum memory between messages.With one exchanged message, QCIP equals QCMA.Source: §3.3 · p. 19

3.4 Oracle Inputs

  • Oracle-input problems give algorithms query access to a finite Boolean table, with resource bounds measured in the parameter λ rather than table length.QCIP oracle-input protocols use a quantum verifier and classical prover; the prover may read the entire table.Source: §3.4 · p. 20

4 Codes and Incompressibility

This section uses code-preimage search and two incompressibility results to formalize why short classical messages cannot generally encode many marked solutions.

4.1 Codes and Code-Preimage Problem

  • A quantum decoder uses a code-preimage witness to find a codeword for each target, succeeding for every target with probability at least 1 − 2^-λ over the sampled hashes.The code family has an efficient injective linear encoding, and the construction prepares the public code state before applying the decoder.Source: §4.1 · p. 21

4.2 Incompressibility

  • For code-preimage pairs, the analogous incompressibility theorem bounds the probability that any encoder decodes t distinct valid pairs from its short message.The oracle hashes codewords with independently sampled Bernoulli(λ^-4) entries.Source: §4.2 · p. 22
  • For independent marking, except with bounded probability over the oracle, every encoder has success probability at most ε over its shared random tape when decoding t marked elements.The oracle marks each element independently with probability δ; the encoder outputs an s-bit message and the decoder has no oracle access.Source: §4.2 · p. 23

5 Public Coins and Perfect Completeness

The section combines public-coin and perfect-completeness transformations for classical-query protocols, preserving a stated soundness guarantee.

5 Public Coins and Perfect Completeness

  • A classical-query protocol can be transformed into a public-coin protocol with a deterministic prover, whose verifier makes all oracle queries after the final prover reply.The transformed verifier depends only on the original verifier and the polynomial resource bounds.Source: §5 · p. 24
  • If the designated prover's original acceptance probability is at least 2/3 − 1/100, the transformed protocol has perfect completeness.This guarantee holds for every oracle input.Source: §5 · p. 24
  • If every original prover's acceptance probability is at most 1/3 + 1/100, every prover's transformed acceptance probability is at most 1/3.This soundness guarantee also holds for every oracle input.Source: §5 · p. 24

6 The Distributional Separation

The section defines two distributions over oracle tables and states a distributional separation, with a QMA upper bound and a QCIP lower bound.

6 The Distributional Separation

  • Both oracle distributions sample hash-function entries independently; one defines oracle values using the hash condition, while the other independently marks each table entry with probability δ.The verifier queries O but has no separate access to H.Source: §6 · p. 25
  • The stated QMA upper bound uses a uniform polynomial-time quantum verifier making at most one classical oracle query, with witnesses of O(λ^6 log λ) qubits.The passage specifies this bound for all sufficiently large λ.Source: §6 · p. 25
  • The section states a QCIP lower bound for every protocol, with the threshold for λ depending on the verifier's rounds, queries, and total communication.The provers receive 1^λ and have unrestricted oracle access.Source: §6 · pp. 25–26

7 The QMA Upper Bound

The QMA verifier uses a code-preimage decoder and one classical oracle query. Its analysis pairs a YES-distribution decoding guarantee with a NO-distribution information bound for a random target.

7.1 The Verifier

  • The verifier samples u, decodes a candidate preimage of u∥0q−λ, rejects invalid codewords, and otherwise accepts exactly when one classical query returns one.The code is public, so the verifier prepares the code state itself.Source: §7.1 · p. 27

7.2 Acceptance under the YES Distribution

  • Under YES, Lemma 4 establishes an acceptance guarantee using witness |ΨH⟩ when the sampled hashes satisfy Lemma 2's guarantee.The proof averages the decoding guarantee over u.Source: §7.2 · p. 27

7.3 Acceptance under the NO Distribution

  • The NO analysis bounds a witness's information about oracle values at a uniformly chosen target, even when the witness depends on values at other targets.The argument is closely related to Nayak’s random access code bound [Nay99].Source: §7.3 · p. 28
  • Under NO, replacing the target's oracle function with an independent copy limits final-query acceptance to δ; only a γNO fraction of oracles have a witness accepted above γNO.The verifier samples the target after receiving the witness, and the NO analysis bounds witness information about values at a uniformly chosen target.Source: §7.3 · pp. 28–29

8 The QCIP Lower Bound

This section develops a QCIP lower bound by analyzing classical simulations of interactive protocols and bounding the success of cheating provers. It uses incompressibility and accuracy bounds, reply searches and final-query verification, and an appendix diagonalization against QCIP verifiers under QMA guarantees.

8 The QCIP Lower Bound

  • The QCIP lower bound follows by transforming the verifier to use classical queries, then public coins and perfect completeness, before applying the public-coin lower bound.The result also holds with unrestricted verifier computation and arbitrary-length classical advice fixed independently of the sampled oracle; for fixed protocol bounds, the required λ threshold is advice-independent.Source: §8 · pp. 30–31

8.1 From QCIP to Classical Queries

  • The section reduces the QCIP lower bound to classical-query simulation, public-coin conversion, and a cheating-prover argument, using the query model when simulation requires superpolynomial local computation.The simulation and cheating-prover lemmas are proved in Sections 8.1 and 8.2, respectively.Source: §8 · p. 30

8.1.1 Simulation with Classical Queries and Incompressibility

  • A classical-query verifier and oracle-free randomized decoder can use a short message encoding the transcript and indices of trials that added addresses to support incompressibility analysis.This approach allows incompressibility to be applied even when the prover has unrestricted oracle access.Source: §8.1.1 · p. 32

8.1.2 The Simulator without a Database Cutoff

  • The simulator estimates each query by measuring its input register, querying unseen addresses classically, and recording added addresses in a database that can be recovered from a short classical string.Without a database cutoff, the simulator finishes with probability one but may make exponentially many queries in ℓ.Source: §8.1.1 · p. 32, §8.1.2 · p. 35

8.1.3 Accuracy without a Database Cutoff

  • The no-cutoff simulator changes the verifier’s acceptance probability by at most ϵ/3, by bounding query weight on unadded addresses and comparing hybrids one query at a time.For each query, the probability that estimation ends with query weight above θ is at most ϵ/(6Ntot).Source: §8.1.3 · pp. 35–36
  • Across rounds, the hybrid replacements change acceptance probability by at most ε/3.Each of the N replacements per round contributes at most ε/(3N_tot); summing over r rounds gives ε/3.Source: §8.1.3 · p. 38

8.1.4 Bounding the Cutoff Probability

  • The probability that any database reaches size t is at most g(F), while the simulator makes at most M = (N_tot + t) · K0 classical queries.The cutoff bound holds for every prover, including provers whose replies depend on F.Source: §8.1.4 · pp. 38–39

8.1.5 Accuracy with a Database Cutoff

  • The cutoff simulator admits a classical replacement using at most M oracle queries and (M + r) · krand random bits.Rounding each sampled distribution changes it by total variation distance at most L · 2^-krand; replacing samples one at a time bounds the resulting error.Source: §8.1.5 · p. 40

8.1.6 Applying Incompressibility

  • The exceptional event g(FO) > ε has probability at most β/ε under either oracle distribution, yielding ηλ = β/ε ≤ 2^-Ω(λ^2).The exceptional event is the same for all provers.Source: §8.1.6 · p. 41

8.2 Lower Bound for Public-Coin Verifiers

  • For public-coin verifiers, the section states that a cheating prover has average acceptance at least 1 − (N + 1)δ under NOλ.The construction uses perfect acceptance under YESλ and incompressibility to find replies consistent with the prover’s actual oracle.Source: §8.2 · p. 41

8.2.1 The Cheating Prover

  • The cheating prover maintains candidate oracles consistent with its transcript and searches replies by requiring pairs to be marked while retaining sufficient probability on remaining candidates.For each reply, it considers the candidates that would send that reply, then chooses pairs to test simultaneously.Source: §8.2.1 · p. 43
  • After a failed test, a maximum-cardinality eligible set cannot become eligible again, so each reply search terminates after finitely many tests.The candidate collection only shrinks, and the eligibility threshold is positive.Source: §8.2.1 · p. 44

8.2.2 Invariants of the Prover

  • An inclusion-maximal eligible set T has size at most K − 2 and equals the pairs marked by every oracle in F[T].Across successful searches, the prover tracks the common marked set and a residual probability bound; each successful test ensures that set is contained in MARKED.Source: §8.2.2 · pp. 44–45

8.2.3 Finding a Reply

  • The cheating prover aborts with probability at most J · 2^-s, by bounding reachable states and applying a union bound over reply searches.For each reachable state, the reply-search analysis bounds failure; the state count is at most J for a fixed public random tape.Source: §8.2.3 · p. 47

8.2.4 The Final Oracle Queries

  • Conditioned on no abort, final-verification rejection is at most Nδ; the proof averages this bound and adds the abort probability.The verifier’s final computation accepts with the oracle of common marked pairs, and the analysis bounds the chance that replacing it with ONO changes a query answer.Source: §8.2.4 · pp. 48–49

A From Distributions to Oracle Separations

  • The appendix proves oracle-input promise and fixed-oracle decision separations by restricting to oracles satisfying QMA guarantees, then diagonalizing against QCIP verifiers.Source: A From Distributions to Oracle… · p. 53

A.1 Oracle-Input Promise Separation

The oracle-input promise problem admits a QMA protocol but no QCIP protocol. Its promise sets are disjoint, and the QMA verifier uses a polynomial-size quantum witness and at most one classical oracle query.

A.1 Oracle-Input Promise Separation

  • Each distribution assigns probability at least 1 − 2^-Ω(λ) to its corresponding promise set, and the YES and NO promise sets are disjoint.The YES set is empty for lengths below λ0.Source: §A.1 · p. 53
  • The oracle-input promise problem admits a QMA protocol but no QCIP protocol.The theorem states the separation for the promise problem of Definition 7.Source: §A.1 · p. 53
  • The QMA verifier uses an a(λ)-qubit witness and at most one classical oracle query, with completeness at least 3/4 and soundness below 1/3 for λ ≥ λ0.The proof derives these bounds from the promise guarantees.Source: §A.1 · pp. 53–54

A.2 Fixed-Oracle Decision Separation

A stage-by-stage diagonalization constructs a unary language in QMA relative to a fixed classical oracle but outside QCIP. The section also shows that sequential repetition amplifies QCIP protocols relative to any fixed oracle.

A.2 Fixed-Oracle Decision Separation

  • The construction diagonalizes against QCIP verifiers one at a time, fixing oracle values within each verifier’s query-length bound while reserving later blocks.An unbounded prover can read later blocks, so the construction first ensures a completeness failure excludes every prover, even with a fixed auxiliary oracle.Source: §A.2 · pp. 54–56
  • There are a classical oracle O and a unary language L in QMA^O \ QCIP^O.The fixed-oracle construction defeats each enumerated QCIP verifier on a selected input length.Source: §A.2 · pp. 55–56
  • The QMA verifier runs V on selected blocks and rejects on unselected blocks, placing the constructed language in QMA^O.The verifier need not identify the selected blocks.Source: §A.2 · p. 56

B Amplification for QCIP

  • When the completeness–soundness gap is at least inverse-polynomial, polynomially many sequential repetitions give completeness at least 1−2^-p(n) and soundness at most 2^-p(n), for any polynomial p.The repeated protocol uses at most the repetition count times the original verifier’s messages and oracle queries.Source: B Amplification for QCIP · p. 57

C Standard Tools for Interactive Proofs

The section establishes standard tools for classical-message interactive proofs: classical provers can reproduce quantum-prover strategies, and public-coin and perfect-completeness transformations preserve polynomial query bounds.

C Standard Tools for Interactive Proofs

C.1 Classical Prover Strategies

  • With classical messages, a classical prover can reproduce a quantum prover’s transcript distribution, and a deterministic reply table can maximize the verifier’s acceptance probability.Conditioned on a transcript, the verifier’s and prover’s private states remain independent.Source: §C.1 · pp. 58–59

C.2 Public Coins and Perfect Completeness

  • For each fixed oracle, the transformations adjust the stated acceptance bounds and produce a deterministic prover for the perfect-completeness protocol.The public-coin step changes bounds 2/3 − 1/100 and 1/3 + 1/100 to 2/3 and 1/3; the next step raises completeness to 1 while preserving soundness 1/3.Source: §C.2 · p. 59

C.2.1 Public Coins

The public-coin transformation postpones oracle queries until after the prover’s final reply while preserving the protocol’s acceptance guarantees and query bounds.

C.2.1 Public Coins

  • Oracle queries can be postponed until after the last reply without changing their number or lengths or the acceptance probability for any fixed oracle and prover.The verifier first collects public challenges and replies, then simulates the original interaction using the saved messages.Source: §C.2.1 · p. 59
  • The public-coin protocol preserves the designated prover’s acceptance guarantee of at least 2/3 and arbitrary provers’ soundness guarantee of at most 1/3.These bounds apply under the respective original hypotheses of 2/3 − 1/100 and 1/3 + 1/100.Source: §C.2.1 · p. 59
  • The transformation’s oracle-dependent consistency test uses no more queries than one execution of the amplified verifier.Its other tests use public hashes or integer comparisons and require no oracle queries.Source: §C.2.1 · p. 60

C.2.2 Perfect Completeness

The perfect-completeness transformation uses shifted public tapes to obtain acceptance on every tape while controlling soundness and query overhead. A separate containment argument bounds the chance that independent random marked sets miss every set in a distribution’s support.

C.2.2 Perfect Completeness

  • The perfect-completeness transformation produces a deterministic prover, raises completeness to 1, and preserves soundness at most 1/3.For a verifier with Q queries before transformation, the transformed verifier makes at most ℓ·Q queries, all after the last reply.Source: §C.2.2 · pp. 60, 62
  • Shifted public tapes are chosen so their translates cover every tape, ensuring that at least one verifier copy accepts for every public tape.The transformation uses multiple copies, each evaluated with a shifted tape.Source: §C.2.2 · p. 61

D Containment in an Independent Random Set

  • The containment section bounds the probability that independent random marked sets contain no set from a distribution’s support.Its argument applies a second-moment bound to one random set and then uses independent repetitions to analyze their union.Source: D Containment in an Independent Random… · p. 63
Loading 2610.03648v1…