betaFeedback

WorksPhysics and Astronomy

Quantum State Search with Classical Interactive Advice

Abstract

We study whether a quantum verifier can find a hidden quantum state by exchanging classical messages with an unbounded prover who knows the state. The verifier has access to a reflection oracle about the target. For a Haar-random nn-qubit target, we prove that achieving constant average fidelity with the target requires (q+1)2(B+1)=Ω(2n)(q+1)^2(B+1)=Ω(2^n), where qq is the number of verifier queries and BB is the total prover-to-verifier communication. The bound allows arbitrary classical interaction and unrestricted computation between queries. Our proof extends the lower bound of Aaronson and Kuperberg (ToC'07) from a single classical proof to an arbitrary classical interaction. As a result, we obtain a quantum-oracle separation of QMA from QCIP. In particular, we give a unitary oracle U\mathcal{U} such that there exists a language L∈QMAUL\in\mathrm{QMA}^{\mathcal{U}} but L∉QCIPUL\notin\mathrm{QCIP}^{\mathcal{U}}. Our separation holds even for UniqueQMA, the restriction of QMA to verification with a unique quantum witness, which is known to be strictly weaker than QMA in the quantum black-box setting. We further give an oracle construction for a notion known as QMA–QCIP[2] gap problem. This gives average case hardness for a QMA language under classical access to a QCIP[2] decision oracle and is used in establishing negative results on witness encryption and quantum indistinguishability obfuscation.

Introduction

Unstructured search is one of the basic problems in computer science. For a search space of size 2n2^n, Grover’s algorithm uses O(2n/2)O(2^{n/2}) queries, and this dependence is optimal [10, 24]. A prover who knows the marked item can remove this query requirement by sending its nn-bit address to the verifier. Does classical interaction provide a similar advantage when the hidden object is a quantum state?

Aaronson and Kuperberg [3] studied this question for a single classical message. They used an oracle that marks an unknown nn-qubit state ∣ψ⟩|\psi\rangle by applying the reflection

Rψ=I−2∣ψ⟩⟨ψ∣.R_{\psi} = I - 2|\psi\rangle\langle\psi|.

They proved that polynomial classical advice is not sufficient to find the hidden state and distinguish this oracle from the identity, given only polynomial queries. On the other hand, quantum advice easily allows distinguishing this oracle from the identity using ψ\psi as advice.

These findings have important implications for the relationship between the classes QMA and QCMA. Informally, both these classes describe problems whose solutions can be verified by a polynomial-time quantum verifier, using a quantum witness in the case of QMA and a classical witness in the case of QCMA. The relation between these classes captures a fundamental question in quantum complexity theory: can quantum witnesses enable more powerful verification than classical witnesses?

Aaronson and Kuperberg’s result shows that a classical witness cannot do what a quantum witness can do in this oracle model, thus demonstrating the first oracle separation between QMA and QCMA.

We ask whether the same advantage holds against classical interactive advice. In our setting, the verifier interacts with an unbounded prover that knows ψ\psi and tries to help the verifier find the hidden state through classical interaction. The verifier may retain quantum memory and interleave classical messages with oracle queries. Such a protocol cannot simply be replaced by one short classical advice: there is not a necessarily “optimal” transcript of interactive classical messages that can be sent in one-shot to the verifier since the success of a transcript may depend on the internal state of the verifier and quantum computations cannot be derandomized.

Our main result extends the Aaronson–Kuperberg lower bound to arbitrary classical interaction.

Theorem 1 (Hidden-state search with classical interaction, informal). Let ∣ψ⟩|\psi\rangle be a Haar-random nn-qubit state. If the verifier makes qq oracle queries to the oracle RψR_{\psi} and the prover sends at most BB classical bits in total, then producing an output with constant average fidelity with ∣ψ⟩|\psi\rangle requires

(q+1)2(B+1)=Ω(2n).(q+1)^2(B+1) = \Omega(2^n).

Fidelity means ⟨ψ∣ρ∣ψ⟩\langle\psi|\rho|\psi\rangle for the verifier’s output ρ\rho, averaged over the hidden state and the protocol’s randomness. For polynomial prover-to-verifier communication, the theorem gives an exponential query requirement. For 2n≤B=o(2n)2n \le B = o(2^n), it matches the one-message upper bound of Aaronson and Kuperberg [3]. Classical interaction therefore does not aid in performing unstructured search for a hidden Haar random state.

The Aaronson–Kuperberg separation actually separates UniqueQMA from QCMA, since the QMA language built in their oracle model has one unique witness up to global phase. The class UniqueQMA restricts QMA to yes-instances with a one-dimensional accepting witness subspace: a designated witness is accepted with high probability, while every orthogonal witness is accepted with low probability [27].

Our oracle construction generalizes the Aaronson–Kuperberg separation by extending the QCMA to the class QCIP, which is the complexity class with a quantum polynomial-time verifier and a computationally–unbounded prover that can interact with each other through classical messages. In particular, as a direct consequence of Theorem 1 we obtain the following result.

Theorem 2. There is a quantum oracle UU such that

UniqueQMA⁡U⊈QCIP⁡U.\operatorname{UniqueQMA}^{U} \not\subseteq\operatorname{QCIP}^{U}.

The class QCIP was introduced by Buhrman, Le Gall, and Weggemans [16] and was further studied by Grewal and Kretschmer [23]. Notice that QCIP⁡[1]=QCMA⁡1\operatorname{QCIP}[1] = \operatorname{QCMA}^{1}. This separation does not assert an unrelativized separation, since polynomial-round QCIP contains QMA in the plain model [16]. It is also consistent with computationally sound classical verification of quantum computations [33], whose soundness under the learning-with-errors assumption applies only against efficient cheating provers.

In concurrent and independent work, Çakan [17] separates QMA from polynomial-round QCIP using a different approach than our own. Çakan’s separation has the advantage of being relative to a classical oracle which is a more restricted model. In comparison, our approach provides a simpler and perhaps more intuitive separation. Moreover, our result separates UniqueQMA rather than QMA, and thus provides a more fine-tuned separation. Çakan’s separation does not provide a unique witness to the constructed QMA language so it does not separate UniqueQMA from QCIP. Note that uniqueness is a substantive restriction: there exists black-box separations between QMA and UniqueQMA [5].

An average-case gap problem. Next, we use our lower bound to build a primitive called a QMA–QCIP[2] gap problem, introduced by Barhoush, Morimae, and Movassagh [7]. Assuming this gap problem, they present a restricted black-box separation between witness encryption with classical ciphertexts and any falsifiable assumption. This class of assumptions essentially includes any assumption where the challenger can efficiently check whether the adversary has won the game and includes one-way functions and LWE. Their barrier also implies a separation between classically encoded quantum indistinguishability obfuscation and falsifiable assumptions. We provide an oracle construction of this gap problem which supports these separations.

Theorem 3 (Oracle gap problem, informal). There exist a quantum unitary oracle TT and a language G∈QMATG \in\mathrm{QMA}^{T} with yes- and no-instances efficiently samplable relative to TT. Nevertheless, the classical yes- and no-instance distributions remain computationally indistinguishable to quantum polynomial-time algorithms with access to TT and classical access to a QCIP[2]T\mathrm{QCIP}[2]^{T} decision oracle.

Barhoush, Morimae, Nishimaki, and Yamakawa [8] introduce a similar notion of QMA–QCMA gap assumption, which they build relative to a quantum oracle. Assuming such a gap, they obtain a quantum black-box barrier for non-interactive classical verification of quantum computation from falsifiable assumptions. We adapt their oracle construction to permit QCIP[2] decision access.

We will now discuss how our results relate to various areas in quantum cryptography.

State preparation with verification access. The task of transmitting a quantum state using classical interaction is known as remote state preparation. This area has well-established communication–entanglement tradeoffs [12, 13], including lower bounds [30]. These models do not provide the verifier with a reflection oracle for the state to be prepared, which allows the ability to verify a state. Our contribution is to include this additional resource and quantify its tradeoff with classical communication. Note that verification ability can help restore a state when a sufficiently large subsystem is already available [20]. The task of preparing state given the ability to verify is also closely related to publicly verifiable quantum money [2, 1].

Comparison with quantum no-telegraphing and quantum fire. Nehoran and Zhandry [35] establish quantum no-telegraphing even when the sender is computationally unbounded: a receiver with bounded oracle access cannot reconstruct the state from a polynomial-length classical description. Their result concerns one-way communication, whereas our lower bound permits arbitrary classical interaction.

Çakan, Goyal, and Shmueli [18] establish interactive untelegraphability relative to a classical oracle. Their model allows unbounded computation between oracle queries and even unrestricted classical communication, but bounds the oracle queries of both the sender and the receiver. This restriction on the sender is essential when comparing their result with ours: their security guarantee does not cover classical messages obtained through unrestricted oracle computation. In our setting, the prover has complete knowledge of the hidden state ∣ψ⟩|\psi\rangle and may perform arbitrary computation and oracle queries. We bound only the total prover-to-verifier communication and the verifier’s oracle queries. Thus, our lower bound does not rely on the prover’s inability to learn the state or obtain a useful description of it.

Casper, Nehoran, and Sattath [19] construct conversable quantum fire in the standard model under cryptographic assumptions. Their states resist one-way classical transfer by quantum polynomial-time parties but admit transfer through classical interaction.

Acknowledgments

The concepts and proof ideas were mainly generated by the authors. We used ChatGPT 6 Astra to help write the proofs, improve presentation and check for mistakes. The authors take responsibility for any mistakes or issues.

Technical overview

We now give a simplified description of the proof of our separation.

The unitary oracle and UniqueQMA language we construct is the same as the Aaronson–Kuperberg separation. Their oracle hides an unknown Haar random nn-qubit pure state ∣ψ⟩\lvert\psi\rangle through the reflection

Rψ=I−2∣ψ⟩⟨ψ∣.R_{\psi} = I - 2\lvert\psi\rangle\langle\psi\rvert.

The promise is that the oracle is either RψR_{\psi}, for some hidden state ∣ψ⟩\lvert\psi\rangle, or the identity. A UniqueQMA prover can send ∣ψ⟩\lvert\psi\rangle itself, after which one controlled oracle query distinguishes the two cases perfectly. Aaronson and Kuperberg proved that any verifier that distinguishes RψR_{\psi} from II with bounded error on average for a Haar random nn-qubit state ψ\psi, even when given an mm-bit classical witness chosen as an arbitrary function of ψ\psi, must make Ω(2nm+1)\Omega\left(\sqrt{\frac{2^n}{m+1}}\right) queries.

We need to generalize this argument to QCIP provers. We first show that the prover in a QCIP protocol can be made deterministic. In particular, for each hidden state ψ\psi, we fix one optimal prover that may depend arbitrarily on the hidden state. The idea is that given any transcript of messages and the state ψ\psi, there must exist a response by the prover that maximizes the probability of the verifier accepting. We fix such a maximizing response for each transcript to obtain a deterministic prover.

The transcript-information lemma. Set D=2nD = 2^n, and let μD\mu_D be the Haar probability measure on pure states in CD\mathbb{C}^D. For each ψ\psi, let PψP_\psi be the deterministic prover fixed above. A public transcript hh is the ordered list of classical messages exchanged so far. Let C(h)C(h) be the set of hidden states whose provers send all the replies recorded in hh, when given the verifier messages recorded there. For a positive-probability transcript hh, define

L(h):=ln⁡1μD(C(h)).L(h) := \ln\frac{1}{\mu_D(C(h))}.

The quantity μD(C(h))\mu_D(C(h)) is the probability that a Haar-random state belongs to C(h)C(h). We now consider the experiment in which the verifier’s access to the reflection oracle is replaced with access to an identity oracle. In this case, the verifier only has knowledge of the state ψ\psi through the messages in the transcript hh. In other words, the probability of generating the verifier messages in hh is the same for every state in C(h)C(h). Thus, conditioned on hh, the hidden state has Haar measure restricted to C(h)C(h), and the verifier’s conditional private state depends only on hh. Thus L(h)L(h) measures how much the transcript has narrowed the possible hidden states relative to the verifier. Initially,

C(∅)=CPD−1andL(∅)=0.C(\varnothing)=\mathbb{C}\mathbb{P}^{D-1} \qquad\text{and} \qquad L(\varnothing)=0.

A verifier message does not change this quantity. Indeed, conditioned on the earlier transcript hh, the verifier’s state is independent of the particular hidden state in C(h)C(h). Therefore, if the verifier next sends aa, then

C(ha)=C(h)andL(ha)=L(h).C(ha)=C(h) \qquad\text{and} \qquad L(ha)=L(h).

Now suppose that the prover sends a reply zz. Since PψP_\psi is deterministic, this reply restricts the compatible set to

C(hz)={ψ∈C(h):Pψ(h)=z}.C(hz)=\{\psi\in C(h):P_\psi(h)=z\}.

The sets C(hz)C(hz), as zz ranges over the possible replies, partition C(h)C(h). Define

pz≔μD(C(hz))μD(C(h)).p_z\coloneqq\frac{\mu_D(C(hz))}{\mu_D(C(h))}.

Note that pzp_z is exactly the conditional probability that the prover sends zz, given the earlier transcript hh.

If reply zz is observed, the increase in LL is

L(hz)−L(h)=ln⁡1μD(C(hz))−ln⁡1μD(C(h))=ln⁡μD(C(h))μD(C(hz))=ln⁡1pz.\begin{aligned} L(hz)-L(h)&=\ln\frac{1}{\mu_D(C(hz))}-\ln\frac{1}{\mu_D(C(h))}\\ &=\ln\frac{\mu_D(C(h))}{\mu_D(C(hz))}=\ln\frac{1}{p_z}. \end{aligned}

Therefore, averaging over the possible replies, the expected increase is

E[L(hZ)−L(h)∣h]=∑zpzln⁡1pz.\mathbb{E}[L(hZ)-L(h)\mid h]=\sum_z p_z\ln\frac{1}{p_z}.

Here the expectation is over the distribution of ψ\psi. The right-hand side is the entropy of the prover’s reply, measured using natural logarithms. If the reply contains bb bits, it has at most 2b2^b possible values, and hence

∑zpzln⁡1pz≤ln⁡(2b)=bln⁡2.\sum_z p_z\ln\frac{1}{p_z}\leq\ln(2^b)=b\ln2.

Thus, a bb-bit prover message can increase the expected value of LL by at most bln⁡2b\ln2, while verifier messages do not increase it at all. Finally, let BtB_t be the total number of prover bits sent before query tt and let TtT_t denote the public transcript immediately before that query. Summing the preceding bound over all prover messages before that query gives

E[L(Tt)]=E[ln⁡1μD(C(Tt))]≤Btln⁡2.(1)\mathbb{E}[L(T_t)] = \mathbb{E}\left[\ln\frac{1}{\mu_D(C(T_t))}\right] \le B_t\ln2. \tag*{(1)}

This expectation correctly weights each transcript by its probability: transcripts with very small compatible sets may have large L(h)L(h), but they are correspondingly unlikely to occur.

From information to query complexity. The bound on E[L]\mathbb{E}[L] allows us to bound the information the verifier has before each oracle query. In particular, it allows us to show that before any query, the query register has expected overlap at most O((B+1)/D)O((B+1)/D) with the hidden state. Replacing that identity query by a reflection changes the state by at most twice the square root of this overlap in trace distance i.e. O((B+1)/D)O(\sqrt{(B+1)/D}). We now replace all qq queries one at a time until we return to the standard experiment where all queries by the verifier are answered with the reflection oracle. The triangle inequality gives a total expected change of at most

O(qB+1D).O\left(q\sqrt{\frac{B+1}{D}}\right).

This is where qq enters: each query contributes to the total change. Constant distinguishing advantage consequently requires (q+1)2(B+1)=Ω(D)(q+1)^2(B+1)=\Omega(D).

The QMA–QCIP[2] gap problem. For the gap problem, we follow a similar construction to that of Barhoush, Morimae, Nishimaki, and Yamakawa [8]. At length nn, choose a random sparse set LnL_n of yes-labels and an independent Haar-random state ∣ψx⟩|\psi_x\rangle for each label xx. The construction has three oracle components:

  • Testing oracle. Given a label xx and a quantum state, this oracle applies the reflection about ∣ψx⟩|\psi_x\rangle if x∈Lnx\in L_n, and the identity otherwise. Thus, a verifier given ∣ψx⟩|\psi_x\rangle as a quantum witness can test whether xx is a yes-instance using one controlled query.

  • Yes-sampling oracle. Starting from a blank state, this oracle prepares a uniform superposition of yes-labels, each accompanied by a requested number of copies of its corresponding witness. Measuring the label register gives a uniformly random x∈Lnx\in L_n, together with copies of ∣ψx⟩|\psi_x\rangle.

  • No-sampling oracle. Starting from a blank state, this oracle prepares a uniform superposition of labels outside LnL_n. Measuring the label register gives a uniformly random no-instance.

To demonstrate the existence of a QMA–QCIP gap problem relative to these oracles, we need to establish that no QPT adversary can distinguish a randomly sampled yes-instance from a randomly sampled no-instance, even given access to these oracles as well as a QCIP[2] oracle.

Suppose an adversary receives an instance y∈Ly \in L. Since the part of the oracle generating yes instances only generates them in a uniform superposition, it is easy to carry out a hybrid argument where yy is deleted from the yes-sampling oracle and replaced into the no-sampling oracle. These changes only have negligible difference on the output of the oracles given that the state generated are in uniform superposition over exponentially many elements.

However, the adversary still has access to a QCIP oracle, which seems stronger than a QCIP verifier: the adversary can adaptively query the oracle to decide QCIP instances. Nevertheless, a change of perspective makes this situation less daunting. The adversary’s interaction with the oracle resembles that of a QCIP verifier with a prover, since both involve classical interaction. By utilizing this idea, we show that our lower-bound arguments for QCIP verifiers also apply to the adversary, establishing that it cannot find the hidden state associated with yy. This completes the indistinguishability argument for the QMA–QCIP gap problem.

Finally, a short second-moment argument followed by Borel–Cantelli fixes one base oracle that work for all efficient distinguishers. The formal construction and proof appear in § 6.

Model and Preliminaries

All logarithms written as ln are natural logarithms. For density operators ρ\rho and σ\sigma, let

D(ρ,σ)=12∥ρ−σ∥1D(\rho,\sigma) = \frac{1}{2}\lVert\rho-\sigma\rVert_1

denote trace distance. Trace distance is contractive under quantum channels and bounds the difference between the probabilities of every measurement outcome.

Let μD\mu_D be Haar measure on the pure states in CD\mathbb{C}^D, or equivalently on CPD−1\mathbb{CP}^{D-1}. We write Ψ←μD\Psi\leftarrow\mu_D for a Haar-random pure state.

A QPT algorithm means a uniform polynomial-time quantum oracle algorithm.

The marked-state reflection oracle

For every unit vector ∣ψ⟩∈CD|\psi\rangle\in\mathbb{C}^D, define

Rψ=I−2∣ψ⟩⟨ψ∣.R_\psi= I - 2|\psi\rangle\langle\psi|.

The two cases of the promise problem are

marked:Rψ for some ∣ψ⟩,unmarked:I.\text{marked}: R_\psi\text{ for some } |\psi\rangle,\qquad\text{unmarked}: I.

As in Aaronson and Kuperberg [3], controlled oracle calls are allowed. This only strengthens the verifier.

Classical-message quantum interactive proofs

We make the communication model explicit. The verifier and prover start in a fixed product state; in particular, they have no shared classical or quantum setup and no shared entanglement. They exchange only classical strings. Formally, every outgoing message register is measured, or equivalently completely dephased, in the computational basis before it is transmitted. The verifier and prover may retain arbitrary private quantum registers. A public transcript is the round-indexed list of all transmitted classical messages. It does not include either party’s private measurement outcomes.

Messages alternate, and the prover sends the last counted message. More explicitly, for r=2p−1r=2p-1 the order is

Z1⟶A1⟶Z2⟶⋯⟶Ap−1⟶Zp.Z_1 \longrightarrow A_1 \longrightarrow Z_2 \longrightarrow\cdots\longrightarrow A_{p-1} \longrightarrow Z_p.

while for r=2pr=2p it is

A1⟶Z1⟶A2⟶⋯⟶Ap⟶Zp.A_1 \longrightarrow Z_1 \longrightarrow A_2 \longrightarrow\cdots\longrightarrow A_p \longrightarrow Z_p.

Here AiA_i is sent by the verifier and ZiZ_i by the prover. Thus QCIP[1] = QCMA, QCIP[2] is verifier-first, and QCIP[3] has order P→V→PP \to V \to P. Padding by ignored messages makes equivalent conventions harmless. Following Buhrman, Le Gall, and Weggemans, we use QCIP without a bracketed parameter for the union of polynomial-time protocols having at most ndn^d classical messages, over all fixed integers d≥1d \ge1. Their total communication is also polynomial.

On a fixed input, a deterministic classical prover simply specifies one classical reply after every possible public transcript. We write this reply as P(h)P(h), where hh is the transcript. No efficiency or uniformity condition is imposed on PP. When the oracle is WW, let Acc⁡W(V,P)\operatorname{Acc}_W(V,P) be the verifier’s acceptance probability when interacting with PP, and define

val⁡W(V)=max⁡PAcc⁡W(V,P),\operatorname{val}_W(V)=\max_P \operatorname{Acc}_W(V,P),

where the maximum is over deterministic classical provers.

Lemma 1 (Deterministic classical provers suffice). Fix an oracle WW and a protocol with classical communication and no shared initial state. The maximum acceptance probability over all quantum provers is attained by a deterministic classical prover.

Proof. Fix any quantum prover. Conditioned on a public transcript, the parties’ private states are a product state. Indeed, they start with no shared state; local computations preserve this property; and conditioning on a transmitted classical message changes only the sender’s private state. Thus, once the transcript is fixed, the verifier’s conditional state does not depend on the prover’s private quantum memory.

We now fix the prover’s replies, starting with its last message and working backwards. At a transcript where the prover sends its last message, there is a probability distribution over the possible classical replies. Its acceptance probability is therefore an average of the acceptance probabilities obtained by fixing the reply. Some fixed reply is at least as good as this average, so choose such a reply for that transcript. At a transcript of probability zero, choose any reply. Do this for every transcript at the last prover turn. Then repeat the same argument at the preceding prover turn, with all later replies already fixed, and continue backwards. This produces a deterministic reply for every public transcript, and the resulting deterministic classical prover accepts at least as often as the original quantum prover. Finally, the protocol has finitely many turns and finite message registers, so there are only finitely many deterministic classical provers. One of them therefore attains the largest acceptance probability. ■\blacksquare

When W=RψW = R_{\psi}, we allow the deterministic prover PP to depend arbitrarily on ψ\psi. This already grants the prover everything it could learn from unlimited oracle access.

To define oracle-query slots unambiguously, divide the verifier’s computation into phases separated by transmitted messages. Within each phase, pad every adaptive query path to the phase’s maximum number of queries, using oracle calls controlled on a zero flag. Every execution then has the same chronologically ordered list of query slots. For slot tt, let BtB_t be the sum of the padded lengths of the prover messages in earlier communication slots. This is a deterministic bound, independent of the branch taken. Let BB be the total padded prover-to-verifier communication in the protocol. Private measurements may be deferred, while the measurements that create transmitted classical messages are kept explicit.

Relativized model

A quantum oracle is a sequence U=(U1,U2,…)\mathcal{U} = (U_1,U_2,\ldots), where UnU_n is a unitary on a specified polynomial number of qubits. We use the length-respecting convention of Aaronson and Kuperberg: on input 0n0^n, a machine queries only UnU_n. This makes the diagonal construction transparent.

Geometric Lemma

We state an important geometric lemma used in Aaronson–Kuperberg separation [3].

Definition 1. A probability measure ν\nu on CPD−1\mathbb{C}P^{D-1} is pp-uniform, for 0<p≤10 < p \le1, if pν(G)≤μD(G)p\nu(G) \le\mu_D(G) for every measurable set GG. Equivalently, we write pν≤μDp\nu\le\mu_D as an inequality of measures.

Lemma 2 (Haar overlap under conditioning (Lemma 3.2 in [3]). Let ν\nu be pp-uniform and let ρ\rho be a density operator on CD\mathbb{C}^{D}, where D≥2D \ge2. Then

EΨ←ν[⟨Ψ∣ρ∣Ψ⟩]≤1+ln⁡(1/p)D.\mathbb{E}_{\Psi\leftarrow\nu}[\langle\Psi\mid\rho\mid\Psi\rangle] \le\frac{1+\ln(1/p)}{D}.

What a Classical Transcript Reveals

We first describe the experiment used throughout this section. Fix a verifier VV with qq padded query slots, fix t∈[q]t \in[q], and fix a measurable choice ψ↦Pψ\psi\mapsto P_{\psi}, for ψ∈CPD−1\psi\in\mathbb{C}\mathbb{P}^{D-1}, of deterministic classical provers. The measurable choice needed for the lower bound is constructed explicitly in Theorem 4. Sample Ψ←μD\Psi\leftarrow\mu_D, let the prover be PΨP_{\Psi}, and replace every verifier oracle call before slot tt by the identity. The prover is already represented by the fixed prover PΨP_{\Psi}, so it makes no oracle calls inside this experiment. We call this the identity-prefix execution. Let TtT_t be its public classical transcript immediately before query tt. The randomness in TtT_t comes from the Haar state and from the verifier’s measurements and private randomness. When we say that the verifier’s state is fixed by a transcript, we mean that its conditional density operator is fixed; it may be mixed because private outcomes are averaged.

For a possible transcript hh, define its compatible set

C(h)={ψ∈CPD−1:Pψ sends every prover message recorded in h}.C(h) = \{\psi\in\mathbb{C}\mathbb{P}^{D-1} : P_{\psi}\text{ sends every prover message recorded in }h\}.

Thus C(h)C(h) contains exactly the hidden states consistent with the prover’s part of hh. Verifier messages still appear in hh, because they determine which reply the prover sends. Their own probabilities impose no further restriction on ψ\psi once the preceding transcript is fixed. Measurability of the choice ψ↦Pψ\psi\mapsto P_{\psi} makes every set C(h)C(h) Haar measurable.

Warm-up: three messages. Consider a transcript

Y⟶A⟶ZY \longrightarrow A \longrightarrow Z

where Y,ZY, Z are prover messages and AA is the verifier’s challenge. Capital letters denote random messages, and lower-case letters denote their realized values. After observing Y=yY = y, the compatible states form C(y)C(y). Once yy is fixed, the identity-prefix verifier’s private state is fixed as well. Hence the distribution of AA is the same for every ψ∈C(y)\psi\in C(y), and observing A=aA = a does not shrink the set:

C(y,a)=C(y).C(y,a) = C(y).

The final prover message can shrink it:

C(y,a,z)={ψ∈C(y):Pψ(y,a)=z}.C(y,a,z) = \{\psi\in C(y) : P_{\psi}(y,a) = z\}.

Thus YY and ZZ can reveal information about Ψ\Psi, but AA cannot reveal new information once YY is known. If query tt occurs before ZZ, then only the bits in YY are charged.

Lemma 3 (Query overlap after a classical transcript). In the identity-prefix execution, let ρt,h\rho_{t,h} be the state of the oracle-input register before query tt, conditioned on transcript Tt=hT_t = h. If at most BtB_t padded prover bits precede this query, then

EΨ,Tt[⟨Ψ∣ρt,Tt∣Ψ⟩]≤1+Btln⁡2D.(2)\mathbb{E}_{\Psi,T_t}\left[\langle\Psi|\rho_{t,T_t}|\Psi\rangle\right] \le\frac{1+B_t\ln2}{D}. \tag*{(2)}

Proof. We first show that, conditioned on any possible transcript hh, the hidden state is Haar distributed over C(h)C(h), and the verifier’s private state depends only on hh, not on the particular ψ∈C(h)\psi\in C(h).

Both statements hold at the empty transcript. Now suppose first that the verifier sends the next message. Given the preceding transcript, its private state is fixed because all earlier verifier oracle calls are identities. Therefore the distribution of its message, and its residual post-measurement state, do not depend on ψ\psi. The compatible set is unchanged. Similarly, at any point in the protocol, when the verifier sends a message, it does not change the compatible set.

Suppose instead that the prover sends the next message zz. Since PψP_\psi is deterministic, the new compatible set is exactly

C(hz)={ψ∈C(h):Pψ(h)=z},C(hz) = \{\psi\in C(h) : P_\psi(h) = z\},

where hzhz denotes hh extended by zz. Conditioning on this reply restricts the hidden state to C(hz)C(hz). This proves the induction.

We next bound the expected logarithmic inverse mass of the compatible set. At the empty transcript this quantity is zero, and a verifier message leaves it unchanged. A padded bb-bit prover message partitions C(h)C(h) into the sets C(hz)C(hz). Let

p(z∣h)=μD(C(hz))μD(C(h)).p(z \mid h) = \frac{\mu_D(C(hz))}{\mu_D(C(h))}.

Therefore, the expected logarithmic mass of the compatible set is:

∑zp(z∣h)ln⁡1μD(C(hz))=ln⁡1μD(C(h))+∑zp(z∣h)ln⁡1p(z∣h)≤ln⁡1μD(C(h))+bln⁡2.\begin{aligned} \sum_z p(z \mid h) \ln\frac{1}{\mu_D(C(hz))} = \ln\frac{1}{\mu_D(C(h))} + \sum_z p(z \mid h) \ln\frac{1}{p(z \mid h)} \\ &\le\ln\frac{1}{\mu_D(C(h))} + b \ln2. \end{aligned}

The inequality holds because a bb-bit message has at most 2b2^b possible values, so its conditional entropy is at most bln⁡2b \ln2. Average over the preceding transcript and repeat for every prover message before query tt. Their padded lengths total at most BtB_t, giving

E[ln⁡1μD(C(Tt))]≤Btln⁡2.(3)\mathbb{E}\left[\ln\frac{1}{\mu_D(C(T_t))}\right] \le B_t \ln2. \tag*{(3)}

For each possible transcript hh, the query state ρt,h\rho_{t,h} is fixed, whereas the hidden state has Haar measure conditioned on C(h)C(h). Lemma 2 therefore gives

E[⟨Ψ∣ρt,h∣Ψ⟩∣Tt=h]≤1+ln⁡(1/μD(C(h)))D.\mathbb{E}\left[\langle\Psi\mid\rho_{t,h} \mid\Psi\rangle\mid T_t = h\right] \le\frac{1 + \ln(1/\mu_D(C(h)))}{D}.

Averaging over TtT_t and applying Eq. (3) proves the claim. ■

The General Query Lower Bound

We combine Lemma 3 with the standard quantum-query hybrid method [10]. The following theorem also allows access to a fixed background oracle independent of Ψ\Psi, which we suppress from the notation.

Theorem 4 (Classical-interaction query bound). Let VV exchange only classical messages, make at most qq queries to the distinguished DD-dimensional oracle, and receive at most BB padded prover bits. Then

EΨ[max⁡P∣Acc⁡RΨ(V,P)−Acc⁡I(V,P)∣]≤2q1+Bln⁡2D,(4)\mathbb{E}_{\Psi}\left[\max_{P}\left|\operatorname{Acc}_{R_{\Psi}}(V,P)-\operatorname{Acc}_{I}(V,P)\right|\right]\leq2q\sqrt{\frac{1+B\ln2}{D}}, \tag*{(4)}

where the maximum is over deterministic classical provers. The same bound holds for EΨ[∣val⁡RΨ(V)−val⁡I(V)∣]\mathbb{E}_{\Psi}[|\operatorname{val}_{R_{\Psi}}(V)-\operatorname{val}_{I}(V)|].

Proof. For every ψ\psi, choose a deterministic classical prover PψP_{\psi} maximizing the absolute difference in Eq. (4). At each fixed input length, there are finitely many possible deterministic response functions on the protocol’s transcript tree. Order them and choose the first maximizer. Since acceptance probabilities for each fixed prover are continuous in ψ\psi, this choice is Borel measurable.

Use the same prover throughout the hybrid. Only the verifier makes oracle calls as the prover has full knowledge of ψ\psi. Order the verifier’s oracle calls chronologically. For t=0,…,qt=0,\ldots,q, let Ωtψ\Omega_t^{\psi} be the final state of the verifier and public transcript when the first tt calls use II and the remaining calls use RψR_{\psi}.

To bound the effect of one replacement, purify the state before the query to ∣Φ⟩|\Phi\rangle, and let uu be the overlap of its oracle-input register with ∣ψ⟩|\psi\rangle. The two post-query purifications have inner product 1−2u1-2u, so their trace distance is

1−∣1−2u∣2=2u(1−u)≤2u.\sqrt{1-|1-2u|^2}=2\sqrt{u(1-u)}\leq2\sqrt{u}.

Discarding the purifying register and applying later operations cannot increase trace distance. For a controlled query, uu is replaced by the weight on ∣1⟩⊗∣ψ⟩|1\rangle\otimes|\psi\rangle, which is at most uu, so the same bound holds.

Conditioned on transcript hh before query tt, let ρt,h\rho_{t,h} be the reduced density operator of the oracle-input register, obtained by tracing out all other registers; the overlap defined above is therefore u=⟨ψ∣ρt,h∣ψ⟩u=\langle\psi|\rho_{t,h}|\psi\rangle. Convexity of trace distance, concavity of the square root, and Lemma 3 give

EΨ[D(Ωt−1Ψ,ΩtΨ)]≤2EΨ,Tt[⟨Ψ∣ρt,Tt∣Ψ⟩]≤21+Bln⁡2D.\mathbb{E}_{\Psi}\left[D\left(\Omega_{t-1}^{\Psi},\Omega_t^{\Psi}\right)\right]\leq2\mathbb{E}_{\Psi,T_t}\left[\sqrt{\langle\Psi|\rho_{t,T_t}|\Psi\rangle}\right] \leq2\sqrt{\frac{1+B\ln2}{D}}.

We can telescope over the qq queries to obtain Eq. (4) for the chosen maximizing provers.

We now compare the optimal acceptance probabilities. Suppose first that val⁡Rψ(V)≥val⁡I(V)\operatorname{val}_{R_{\psi}}(V)\geq\operatorname{val}_{I}(V), and choose a deterministic prover P⋆P^{\star} that achieves val⁡Rψ(V)\operatorname{val}_{R_{\psi}}(V). This prover specifies a classical reply to every possible transcript. We can use exactly the same reply rules when the verifier instead queries the identity oracle. Since val⁡I(V)\operatorname{val}_{I}(V) is the maximum acceptance probability over all prover strategies, it satisfies

val⁡I(V)≥Acc⁡I(V,P⋆).\operatorname{val}_{I}(V)\geq\operatorname{Acc}_{I}(V,P^{\star}).

Together with val⁡Rψ(V)=Acc⁡Rψ(V,P⋆)\operatorname{val}_{R_{\psi}}(V)=\operatorname{Acc}_{R_{\psi}}(V,P^\star), this gives

val⁡Rψ(V)−val⁡I(V)≤Acc⁡Rψ(V,P⋆)−Acc⁡I(V,P⋆).\operatorname{val}_{R_{\psi}}(V)-\operatorname{val}_{I}(V)\leq\operatorname{Acc}_{R_{\psi}}(V,P^\star)-\operatorname{Acc}_{I}(V,P^\star).

Thus, the difference between the optimal values is at most the difference obtained by keeping this one prover fixed. If the identity-oracle value is larger, choose a prover optimal for the identity oracle and reverse the argument. In either case,

∣val⁡Rψ(V)−val⁡I(V)∣≤max⁡P∣Acc⁡Rψ(V,P)−Acc⁡I(V,P)∣.\left|\operatorname{val}_{R_{\psi}}(V)-\operatorname{val}_{I}(V)\right|\leq\max_{P}\left|\operatorname{Acc}_{R_{\psi}}(V,P)-\operatorname{Acc}_{I}(V,P)\right|.

Averaging over the hidden state and applying Eq. (4) proves the second part of the theorem. In particular, a constant average absolute gap between the two values requires

q=Ω(DB+1).q=\Omega\left(\sqrt{\frac{D}{B+1}}\right).

One Oracle Separating Every Message Count

For each n≥1n\geq1, choose a bit bn∈{0,1}b_n\in\{0,1\} and a Haar random nn-qubit state ∣ψn⟩\lvert\psi_n\rangle. Define the nn-qubit unitary

Un=I2n−2bn∣ψn⟩⟨ψn∣.U_n=I_{2^n}-2b_n\lvert\psi_n\rangle\langle\psi_n\rvert.

where I2nI_{2^n} is the identity on nn qubits. Thus Un=I2nU_n=I_{2^n} when bn=0b_n=0, while Un=RψnU_n=R_{\psi_n} when bn=1b_n=1. The quantum oracle is the family U=(Un)n≥1\mathcal{U}=(U_n)_{n\geq1}. The construction below specifies the bits bnb_n and states ∣ψn⟩\lvert\psi_n\rangle.

For each length nn, define

LnU={{0n},bn=1,∅,bn=0.L_n^{\mathcal{U}}= \begin{cases} \{0^n\}, & b_n=1,\\ \varnothing, & b_n=0. \end{cases}

The associated unary language is

LU=⋃n≥1LnU={0n:bn=1}.L^{\mathcal{U}}=\bigcup_{n\geq1}L_n^{\mathcal{U}}=\{0^n:b_n=1\}.

Thus deciding whether 0n∈LU0^n\in L^{\mathcal{U}} means determining whether UnU_n is the identity or a reflection.

Theorem 5 (Simultaneous separation). There exists a quantum oracle U\mathcal{U} such that

LU∈UniqueQMAUandLU∉QCIPU.L^{\mathcal{U}}\in\mathrm{UniqueQMA}^{\mathcal{U}} \qquad\text{and}\qquad L^{\mathcal{U}}\notin\mathrm{QCIP}^{\mathcal{U}}.

In particular, the same oracle satisfies UniqueQMAU⊈QCIP[r]U\mathrm{UniqueQMA}^{\mathcal{U}}\not\subseteq\mathrm{QCIP}[r]^{\mathcal{U}} for every fixed integer r≥1r\geq1.

Proof. First, we show that LU∈UniqueQMA⁡UL^{\mathcal{U}} \in\operatorname{UniqueQMA}^{\mathcal{U}} for every oracle of this form. Reject non-unary inputs. On input 0n0^n, the verifier receives an nn-qubit witness ∣ϕ⟩|\phi\rangle, prepares a control qubit in ∣+⟩|+\rangle, applies controlled-UnU_n, applies a Hadamard gate to the control, and accepts exactly when the outcome is 1. If Un=RψnU_n = R_{\psi_n}, the witness ∣ψn⟩|\psi_n\rangle is accepted with probability one. If Un=IU_n = \mathbb{I}, every witness is rejected.

Enumerate all polynomial-time uniform quantum verifiers with classical communication as V1,V2,…V_1,V_2,\ldots, using a fixed finite universal gate set. Let qi(n)q_i(n) and Bi(n)B_i(n) be polynomial bounds on the oracle queries and total prover-to-verifier communication of ViV_i. This enumeration includes every verifier with polynomially many messages.

At stage ii, choose a fresh input length nin_i, larger than every length used earlier, such that the right-hand side of Eq. (4), with q=qi(ni)q = q_i(n_i), B=Bi(ni)B = B_i(n_i), and D=2niD = 2^{n_i}, is less than 1/31/3. This is possible because qiq_i and BiB_i are polynomials whereas 2ni2^{n_i} is exponential.

Consider ViV_i on input 0ni0^{n_i}, and let v0=val⁡I(Vi)v_0 = \operatorname{val}_{\mathbb{I}}(V_i) when the length-nin_i component is the identity. There are two cases.

  • If v0>1/3v_0 > 1/3, set Uni=IU_{n_i} = \mathbb{I}. Then 0ni∉LU0^{n_i} \notin L^{\mathcal{U}}, but ViV_i violates soundness.

  • If v0≤1/3v_0 \le1/3, Theorem 4 gives

EΨ[val⁡RΨ(Vi)]≤v0+EΨ[∣val⁡RΨ(Vi)−v0∣]<23.\mathbb{E}_{\Psi}\left[\operatorname{val}_{R_{\Psi}}(V_i)\right] \le v_0 + \mathbb{E}_{\Psi}\left[\left|\operatorname{val}_{R_{\Psi}}(V_i)-v_0\right|\right] < \frac{2}{3}.

where Ψ\Psi is Haar distributed on nin_i qubits. Hence some ∣ψni⟩|\psi_{n_i}\rangle satisfies val⁡Rψni(Vi)<2/3\operatorname{val}_{R_{\psi_{n_i}}}(V_i) < 2/3. Set Uni=RψniU_{n_i} = R_{\psi_{n_i}}. Then 0ni∈LU0^{n_i} \in L^{\mathcal{U}}, but ViV_i violates completeness.

Set all unused components to the identity. The length-respecting restriction on verifier oracle access ensures that later stages do not change ViV_i’s behavior on 0ni0^{n_i}. The value val⁡\operatorname{val} already maximizes over every deterministic prover, so future oracle components cannot give the prover an additional advantage omitted by the bound. Thus every polynomial-round QCIP verifier fails on some input, while the same language lies in UniqueQMA⁡U\operatorname{UniqueQMA}^{\mathcal{U}}. ■

An Average-Case QMA–QCIP[2] Gap Problem

The unary language used in § 5 gives a worst-case separation, but it does not provide efficiently samplable instances and witnesses. We now give a sampler-augmented oracle satisfying the average-case definition of Barhoush, Morimae, and Movassagh [7]. The construction and the seven-hybrid proof follow the QMA–QCMA gap oracle of Barhoush, Morimae, Nishimaki, and Yamakawa [8]. The new ingredient is the threshold-coupling argument inside the proof of Theorem 6, which controls adaptive queries to a QCIP[2] decision oracle.

The relativized gap definition

We use explicit descriptions over a fixed finite universal gate set. A query to a QCIP[2] decision oracle is a string z=(V1,V2,x)z=(V_1,V_2,x). On input xx, the first verifier circuit produces a classical challenge aa and a private quantum state that it passes to the second verifier. The prover returns a classical answer depending on aa, and the second verifier circuit decides whether to accept. Let val⁡T(z)\operatorname{val}_{\mathcal{T}}(z) be the largest acceptance probability over all deterministic classical provers when both verifier circuits have access to the quantum oracle T\mathcal{T}.

We use the convention in [7] to define a QCIP[2] oracle. Note that for a QCIP[2] language some inputs do not belong to yes or no instances, so it is not clear how the oracle should respond to such inputs. We deal with this as in [7] by defining a whole class of oracles where any function can belong to the class as long as it accepts yes instances and rejects no instances. Then, any adversary that uses a QCIP[2] oracle to solve some task should be able to succeed regardless of which function in the class it is given oracle access to. We call a function in this class a completion of the QCIP[2] oracle.

Definition 2 (Relativized two-message decision oracle). The set OQCIP[2]T\mathcal{O}^{\mathcal{T}}_{\mathrm{QCIP}[2]} consists of all total Boolean functions O\mathcal{O} satisfying

O(z)=1if val⁡T(z)≥23,O(z)=0if val⁡T(z)≤13.\mathcal{O}(z)=1\quad\text{if }\operatorname{val}_{\mathcal{T}}(z)\ge\frac{2}{3},\qquad\mathcal{O}(z)=0\quad\text{if }\operatorname{val}_{\mathcal{T}}(z)\le\frac{1}{3}.

When the value lies strictly between 1/31/3 and 2/32/3, the answer is unrestricted. Oracle calls are classical. In this oracle construction, a completion is an arbitrary total Boolean function satisfying these two constraints.

The quantifier over completions prevents an algorithm from relying on specially chosen answers to ambiguous queries.

Definition 3 (Relativized QMA–QCIP[2]). gap problem] Let GT∈QMATG^{\mathcal{T}}\in\mathrm{QMA}^{\mathcal{T}}, let QTQ^{\mathcal{T}} be its verifier, and let Yn\mathcal{Y}_n and Nn\mathcal{N}_n be distributions supported on GT∩{0,1}nG^{\mathcal{T}}\cap\{0,1\}^n and {0,1}n∖GT\{0,1\}^n\setminus G^{\mathcal{T}}, respectively. The pair (Y,N)(\mathcal{Y},\mathcal{N}) is a gap problem if:

  1. for every polynomial tt, a QPT oracle algorithm on input (1n,1t(n))(1^n,1^{t(n)}) samples (x,∣wx⟩⊗t(n))(x,\lvert w_x\rangle^{\otimes t(n)}), where xx has distribution Yn\mathcal{Y}_n and ∣wx⟩\lvert w_x\rangle is accepted by QTQ^{\mathcal{T}} with probability at least 2/32/3;

  2. a possibly inefficient oracle algorithm samples Nn\mathcal{N}_n; and

  3. for every polynomial ss and every QPT AA, there is a completion O∈OQCIP[2]T\mathcal{O}\in\mathcal{O}^{\mathcal{T}}_{\mathrm{QCIP}[2]} such that

∣Pr⁡X1,…,Xs←Yn[AT,O(X1,…,Xs)=1]−Pr⁡X1,…,Xs←Nn[AT,O(X1,…,Xs)=1]∣≤negl⁡(n).\left| \Pr_{X_1,\ldots,X_s\leftarrow\mathcal{Y}_n}\left[A^{\mathcal{T},\mathcal{O}}(X_1,\ldots,X_s)=1\right] - \Pr_{X_1,\ldots,X_s\leftarrow\mathcal{N}_n}\left[A^{\mathcal{T},\mathcal{O}}(X_1,\ldots,X_s)=1\right] \right| \le\operatorname{negl}(n).

The distinguisher has quantum query access to T\mathcal{T} and classical access to O\mathcal{O}.

The random-subset oracle

Fix n≥4n \ge4, let N=2nN = 2^n, and put

K=⌈2n/2⌉.K = \left\lceil2^{n/2} \right\rceil.

Choose LnL_n uniformly among all KK-element subsets of {0,1}n\{0,1\}^n. Independently choose an nn-qubit Haar-random state ∣ψx⟩|\psi_x\rangle for every x∈{0,1}nx \in\{0,1\}^n.

The oracle has one testing component and two sampling components. The testing component WnW_n has a control qubit, an nn-bit label register, and an nn-qubit state register. On computational-basis control and label registers, it acts as

Wn∣c,x⟩∣ϕ⟩=∣c,x⟩Rψxc1[x∈Ln]∣ϕ⟩.(5)W_n|c,x\rangle|\phi\rangle= |c,x\rangle R_{\psi_x}^{c1[x\in L_n]}|\phi\rangle. \tag*{(5)}

Thus a controlled query at x∈Lnx \in L_n applies the reflection about ∣ψx⟩|\psi_x\rangle, while a query at x∉Lnx \notin L_n applies the identity.

For a unit vector ∣a⟩|a\rangle orthogonal to ∣0⟩|0\rangle, write

S(a)=∣a⟩⟨0∣+∣0⟩⟨a∣+I−∣0⟩⟨0∣−∣a⟩⟨a∣.(6)S(a) = |a\rangle\langle0| + |0\rangle\langle a| + I - |0\rangle\langle0| - |a\rangle\langle a|. \tag*{(6)}

This unitary swaps ∣0⟩|0\rangle and ∣a⟩|a\rangle and fixes their common orthogonal complement. For every integer t≥1t \ge1, define

∣Yn,t⟩=1K∑x∈Ln∣x⟩∣ψx⟩⊗t∣1⟩,∣Nn⟩=1N−K∑x∉Ln∣x⟩∣1⟩.(7)|Y_{n,t}\rangle= \frac{1}{\sqrt{K}}\sum_{x\in L_n}|x\rangle|\psi_x\rangle^{\otimes t}|1\rangle,\qquad|N_n\rangle= \frac{1}{\sqrt{N-K}}\sum_{x\notin L_n}|x\rangle|1\rangle. \tag*{(7)}

The oracle contains the blocks

GenYes⁡n,t=S(Yn,t)for every t≥1,GenNo⁡n=S(Nn).\operatorname{GenYes}_{n,t} = S(Y_{n,t}) \quad\text{for every } t \ge1,\qquad\operatorname{GenNo}_n = S(N_n).

The integer tt is a classical tag. Equivalently, all these blocks form one tagged block-diagonal unitary. A polynomial-time machine can address only tags and registers of polynomial length.

Let T\mathcal{T} denote the collection of these independently sampled components over all input lengths, and define

GT=⋃n≥4Ln.G^{\mathcal{T}} = \bigcup_{n\ge4} L_n.

Membership at the finitely many smaller lengths is defined arbitrarily.

Lemma 4 (Verification and sampling). For every realization of T\mathcal{T}, the language GTG^{\mathcal{T}} belongs to QMATQMA^{\mathcal{T}} with perfect completeness and perfect soundness. Moreover, the uniform distributions on LnL_n and on its complement satisfy the first two conditions of Definition 3.

Proof. On input xx, the QMA verifier performs the Hadamard test for the controlled testing block WnW_n. If x∈Lnx \in L_n, the witness ∣ψx⟩|\psi_x\rangle is a −1-1 eigenvector and is accepted with probability one. If x∉Lnx \notin L_n, the addressed block is the identity for every witness, so the verifier rejects with probability one. On input (1n,1t)(1^n,1^t), the yes sampler applies GenYes⁡n,t\operatorname{GenYes}_{n,t} to ∣0⟩\lvert0\rangle, measures the label register, and returns the remaining witness registers. Its output is a uniform x∈Lnx \in L_n together with ∣ψx⟩⊗t\lvert\psi_x\rangle^{\otimes t}. Applying GenNon⁡\operatorname{GenNon} to ∣0⟩\lvert0\rangle and measuring the label gives a uniform element of the complement. Each sampler makes one oracle query.

Stability of the oracle hybrids

The seven-hybrid proof changes one sampler term or one reflection at a time. The sampler transitions use the elementary perturbation estimate below. The reflection transitions will be handled directly inside the seven-hybrid proof by applying Theorem 4 to a suitable meta-verifier. Throughout this subsection, “exponentially small” means at most 2−cn2^{-cn} for some constant c>0c > 0 and all sufficiently large nn. The constant and the starting point may depend on the fixed algorithm and its polynomial resource bounds. We freely absorb polynomial factors into this notation.

Lemma 5 (Puncturing a coherent sampler). Let ∣A⟩=M−1/2∑j=1M∣aj⟩\lvert A\rangle= M^{-1/2}\sum_{j=1}^{M}\lvert a_j\rangle, where the ∣aj⟩\lvert a_j\rangle’s are orthonormal, and let

∣A−i⟩=1M−1∑j≠i∣aj⟩.\lvert A^{-i}\rangle= \frac{1}{\sqrt{M-1}}\sum_{j\ne i}\lvert a_j\rangle.

Then

∥S(A)−S(A−i)∥=O(M−1/2).\left\lVert S(A)-S(A^{-i})\right\rVert= O(M^{-1/2}).

The same estimate holds when one orthogonal term is added to an MM-term superposition.

Proof. The two target states have inner product (M−1)/M\sqrt{(M-1)/M}, and hence

∥∣A⟩−∣A−i⟩∥2=2−21−1M=O(M−1).\left\lVert\lvert A\rangle-\lvert A^{-i}\rangle\right\rVert^2=2-2\sqrt{1-\frac{1}{M}}=O(M^{-1}).

Expanding the definition of SS in Eq. (6) and using ∥∣a⟩⟨a∣−∣b⟩⟨b∣∥≤2∥∣a⟩−∣b⟩∥\left\lVert\lvert a\rangle\langle a\rvert-\lvert b\rangle\langle b\rvert\right\rVert\le2\left\lVert\lvert a\rangle-\lvert b\rangle\right\rVert gives the claimed operator-norm bound. The calculation for adding a term is identical. For every fixed deterministic prover, the ordinary query hybrid changes the acceptance probability by at most twice the number of queries times the operator-norm change. Taking the maximum over deterministic provers preserves this bound.

For the tagged family {GenYes⁡n,t}t\{\operatorname{GenYes}_{n,t}\}_t, puncturing the same label changes every tagged block by the same O(M−1/2)O(M^{-1/2}) amount. The norm of the tagged direct-sum difference is the maximum of the block norms, so the estimate is uniform in tt.

We now choose the answers on ambiguous QCIP[2] queries. For every binary string zz, independently sample

Θz←[2/5,3/5]\Theta_z \leftarrow[2/5,3/5]

once and keep it fixed. Write Θ=(Θz)z\Theta=(\Theta_z)_z for this threshold table. Given a base oracle TT, define

OT,Θ(z)=1[val⁡T(z)≥Θz].(8)\mathcal{O}_{T,\Theta}(z)=\mathbf{1}[\operatorname{val}_T(z)\ge\Theta_z]. \tag*{(8)}

The random table is only a probabilistic-method device. Once it is fixed, the completion is deterministic and every repeated query receives the same answer. Every such function is a valid deterministic completion: values at least 2/32/3 are always accepted and values at most 1/31/3 are always rejected. If two base oracles give values vv and v′v' to the same description, then, using the same threshold in both worlds,

Pr⁡Θ[1[v≥Θz]≠1[v′≥Θz]]≤5∣v−v′∣.(9)\Pr_{\Theta}[\mathbf{1}[v\ge\Theta_z]\ne\mathbf{1}[v'\ge\Theta_z]]\le5|v-v'|. \tag*{(9)}

Indeed, an answer differs only when the uniform threshold falls between vv and v′v', and the interval [2/5,3/5][2/5,3/5] has length 1/51/5.

The gap problem

We follow the seven-hybrid argument of Barhoush, Morimae, Nishimaki, and Yamakawa [8 Theorem 8], using Theorem 4 to handle classical interaction.

Theorem 6 (Oracle gap problem). For some realization TT of the construction above, the uniform distributions on LnL_n and its complement form a QMA–QCIP[2]\mathrm{QMA}\text{--}\mathrm{QCIP}[2] gap problem against uniform QPT distinguishers.

Proof. QMA membership and the sampling requirements follow from Lemma 4. We prove indistinguishability first for one input label. Fix a uniform QPT algorithm AA, and let Q=Q(n)Q=Q(n) be a polynomial bounding its queries and the description lengths and resources of the protocols it can submit to the completion oracle, under the stated encoding conventions.

Sample the base oracle T\mathcal{T}, a uniform y∈Lny\in L_n, and a uniform yˉ∉Ln\bar{y}\notin L_n. Independently sample the threshold table Θ\Theta and use it throughout. Whenever a hybrid changes the base oracle, its completion is changed accordingly, using this same table.

Consider the following hybrids, each of which runs AA and outputs its result.

  • H0H_0. Use the original oracle and give AA the input yy.

  • H1H_1. Remove the term indexed by yy from every GenYesn,t\mathrm{GenYes}_{n,t}.

  • H2H_2. Replace the reflection at address yy by the identity.

  • H3H_3. Add yy to GenNon\mathrm{GenNo}_n.

  • H4H_4. Keep this modified oracle, but replace the input yy by yˉ\bar{y}.

  • H5H_5. Remove yy from the no sampler.

  • H6H_6. Restore the reflection at address yy.

  • H7H_7. Restore the term indexed by yy in every yes sampler.

Each hybrid changes only the operation specified, leaving everything else as in the preceding hybrid. Thus H7H_7 uses the original oracle and a uniform no-instance.

We first explain how to account for the completion oracle when comparing two neighboring base oracles T\mathcal{T} and T′\mathcal{T}'. Change the completion while keeping the base oracle fixed, then change the base oracle while keeping the completion fixed. For the first change, couple the executions until their first different completion answer. On a new query zz, the threshold Θz\Theta_z is independent of the preceding history, and Eq. (9) bounds the disagreement probability by 5∣val⁡T(z)−val⁡T′(z)∣5|\operatorname{val}_{T}(z)-\operatorname{val}_{T'}(z)|. A repeated query cannot cause the first disagreement. Hence a union bound over the at most QQ queries bounds this change by

5Qmax⁡z∣val⁡T(z)−val⁡T′(z)∣5Q \max_{z} |\operatorname{val}_{T}(z)-\operatorname{val}_{T'}(z)|

where the maximum is over the descriptions allowed by the resource bound. This maximum also covers adaptively chosen descriptions.

Sampler changes. The transitions H0H_0 to H1H_1, H2H_2 to H3H_3, H4H_4 to H5H_5, and H6H_6 to H7H_7 each add or remove one sampler term. By Lemma 5, the operator-norm change is exponentially small, uniformly over all tags. The ordinary query hybrid therefore bounds both the change in every protocol value and the direct change seen by AA. The preceding completion bound preserves exponential smallness.

Reflection changes. For H1H_1 to H2H_2 and H5H_5 to H6H_6, the yes samplers no longer contain yy. Fix the labels and all oracle data other than ψy\psi_y. The remaining background is independent of ψy\psi_y. Apply Theorem 4 to a verifier that first receives a protocol description zz from its prover and then executes that protocol. The description and subsequent prover messages have polynomial total length, and the verifier makes polynomially many queries. Its prover may choose both zz and the later replies as a function of ψy\psi_y. For each zz, the difference between optimal values is at most the maximum acceptance-probability difference for the same deterministic prover. The bound on this maximum in Theorem 4 therefore gives

Eψy[max⁡z∣val⁡T(z)−val⁡T′(z)∣]≤2−Ω(n).\mathbb{E}_{\psi_y}\left[\max_z \left|\operatorname{val}_{T}(z)-\operatorname{val}_{T'}(z)\right|\right]\le2^{-\Omega(n)}.

Thus the completion change is exponentially small. For the direct oracle change, reverse the comparison if necessary and keep the completion belonging to the world in which the reflection has been removed. This completion and the punctured samplers are independent of ψy\psi_y, so Theorem 4 with no prover messages also bounds the direct change by 2−Ω(n)2^{-\Omega(n)}.

The middle switch. Put S=Ln∖{y}S=L_n\setminus\{y\}. Conditioned on SS, the ordered pair (y,yˉ)(y,\bar{y}) is uniform over distinct elements of ScS^c. In H3H_3 and H4H_4, the testing and yes-sampling components use exactly the labels in SS, and the no sampler is uniform over ScS^c. The modified oracle and its completion therefore do not depend on which element of the pair was originally in LnL_n. Exchanging yy and yˉ\bar{y} leaves their joint distribution unchanged, so H3H_3 and H4H_4 have identical output distributions.

The triangle inequality now gives

∣Pr⁡[H0=1]−Pr⁡[H7=1]∣≤2−Ω(n).(10)\left|\Pr[H_0=1]-\Pr[H_7=1]\right|\le2^{-\Omega(n)}. \tag*{(10)}

These probabilities include the choice of the base oracle and threshold table. To obtain a fixed realization, write pYp_Y and pNp_N for AA’s yes- and no-input acceptance probabilities for fixed (T,Θ)(T,\Theta). Apply Eq. (10) to an algorithm that runs AA on its challenge and independently on an internally sampled yes-label, accepting only if both runs accept. Repeat with an internally sampled no-label. This bounds the absolute values of E[pY2−pYpN]\mathbb{E}[p_Y^2-p_Yp_N] and E[pYpN−pN2]\mathbb{E}[p_Yp_N-p_N^2] by 2−Ω(n)2^{-\Omega(n)}. Subtracting gives

ET,Θ[(pY−pN)2]≤2−Ω(n).\mathbb{E}_{T,\Theta}[(p_Y-p_N)^2] \le2^{-\Omega(n)}.

Markov’s inequality and the Borel–Cantelli lemma imply that ∣pY−pN∣|p_Y-p_N| is negligible with probability one over (T,Θ)(\mathcal{T},\Theta). There are countably many uniform QPT algorithms, so we can fix a realization for which this holds for every such algorithm.

Finally, polynomially many independent samples follow by the usual hybrid over the input coordinates. A single-challenge distinguisher chooses a uniformly random coordinate for its challenge and samples the preceding coordinates from the yes distribution and the following coordinates from the no distribution, using the public sampling oracles. Its advantage is the original distinguishing advantage divided by the number of samples. Thus a non-negligible advantage on polynomially many samples would contradict the single-sample bound for the fixed realization. This proves the remaining requirement of Definition 3. ■

References

  1. [1]Aaronson, S.: Quantum copy-protection and quantum money. In: 24th Annual IEEE Conference on Computational Complexity (CCC 2009), pp. 229–242. IEEE (2009). https://doi.org/10.1109/CCC.2009.42
  2. [2]Aaronson, S., Christiano, P.: Quantum money from hidden subspaces. Theory of Computing 9, 349–401 (2013). https://doi.org/10.4086/toc.2013.v009a009
  3. [3]Aaronson, S., Kuperberg, G.: Quantum versus classical proofs and advice. Theory of Computing 3, 129–157 (2007). https://doi.org/10.4086/toc.2007.v003a007
  4. [5]Anshu, A., Haferkamp, J., Hwang, Y., Nguyen, Q.T.: On the complexity of unique quantum witnesses and quantum approximate counting. In: 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), LIPIcs, vol. 362, pp. 10:1–10:20. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2026). https://doi.org/10.4230/LIPIcs.ITCS.2026.10
  5. [7]Barhoush, M., Morimae, T., Movassagh, R.: Separating quantum indistinguishability obfuscation from falsifiable assumptions. arXiv:2608.25195 (2026). https://arxiv.org/abs/2608.25195
  6. [8]Barhoush, M., Morimae, T., Nishimaki, R., Yamakawa, T.: Separating non-interactive classical verification of quantum computation from falsifiable assumptions. In: Advances in Cryptology—CRYPTO 2026, LNCS, vol. 16804, pp. 279–310. Springer (2026). https://doi.org/10.1007/978-3-032-35409-9_10
  7. [10]Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM Journal on Computing 26(5), 1510–1523 (1997). https://doi.org/10.1137/S0097539796300933
  8. [12]Bennett, C.H., DiVincenzo, D.P., Shor, P.W., Smolin, J.A., Terhal, B.M., Wootters, W.K.: Remote state preparation. Physical Review Letters 87(7), 077902 (2001). https://doi.org/10.1103/PhysRevLett.87.077902
  9. [13]Bennett, C.H., Hayden, P., Leung, D.W., Shor, P.W., Winter, A.: Remote preparation of quantum states. IEEE Transactions on Information Theory 51(1), 56–74 (2005). https://doi.org/10.1109/TIT.2004.839476
  10. [16]Buhrman, H., Le Gall, F., Weggemans, J.: Classical versus quantum queries in quantum PCPs with classical proofs. arXiv:2411.00946 (2024). https://arxiv.org/abs/2411.00946
  11. [17]Çakan, A.: Separating QMA from QCIP with a classical oracle, or, the power of quantum proofs over classical interaction for quantum verifiers. arXiv:2610.03648 (2026). https://arxiv.org/abs/2610.03648
  12. [18]Çakan, A., Goyal, V., Shmueli, O.: Public-key quantum fire and key-fire from classical oracles. In: Advances in Cryptology—CRYPTO 2026, LNCS, vol. 16804, pp. 341–371. Springer (2026). https://doi.org/10.1007/978-3-032-35409-9_12
  13. [19]Casper, O., Nehoran, B., Sattath, O.: Conversable quantum fire in the standard model. arXiv:2609.36335 (2026). https://arxiv.org/abs/2609.36335
  14. [20]Farhi, E., Gosset, D., Hassidim, A., Lutomirski, A., Nagaj, D., Shor, P.: Quantum state restoration and single-copy tomography for ground states of Hamiltonians. Physical Review Letters 105(19), 190503 (2010). https://doi.org/10.1103/PhysRevLett.105.190503
  15. [23]Grewal, S., Kretschmer, W.: Unentanglement and post-measurement branching in quantum interactive proofs. arXiv:2509.15319 (2025). https://arxiv.org/abs/2509.15319
  16. [24]Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC 1996), pp. 212–219. ACM (1996). https://doi.org/10.1145/237814.237866
  17. [27]Jain, R., Kerenidis, I., Kuperberg, G., Santha, M., Sattath, O., Zhang, S.: On the power of a unique quantum witness. Theory of Computing 8, 375–400 (2012). https://doi.org/10.4086/toc.2012.v008a017
  18. [30]Kundu, S., Lalonde, O.: Near-optimal entanglement-communication tradeoffs for remote state preparation. arXiv:2602.09428 (2026). https://arxiv.org/abs/2602.09428
  19. [33]Mahadev, U.: Classical verification of quantum computations. SIAM Journal on Computing 51(4), 1172–1229 (2022). https://doi.org/10.1137/20M1371828
  20. [35]Nehoran, B., Zhandry, M.: A computational separation between quantum no-cloning and no-telegraphing. In: 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), LIPIcs, vol. 287, pp. 82:1–82:23. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2024). https://doi.org/10.4230/LIPIcs.ITCS.2024.82

Paper details

vlnc:W_vgdmpaj7
Version
v2 · latest
Published
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

ChatGPT 6 Astra

View statement
Looking for related papers…
Contents