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 -qubit target, we prove that achieving constant average fidelity with the target requires , where is the number of verifier queries and 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 from a single classical proof to an arbitrary classical interaction. As a result, we obtain a quantum-oracle separation of UniqueQMA from QCIP with polynomially many classical messages. In particular, we give a unitary oracle such that there exists a language but . 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 , Grover’s algorithm uses queries, and this dependence is optimal [10, 24]. A prover who knows the marked item can remove this query requirement by sending its -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 -qubit state by applying the reflection
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 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 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 be a Haar-random -qubit state. If the verifier makes oracle queries to the oracle and the prover sends at most classical bits in total, then producing an output with constant average fidelity with requires
Fidelity means for the verifier’s output , averaged over the hidden state and the protocol’s randomness. For polynomial prover-to-verifier communication, the theorem gives an exponential query requirement. For , 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 such that
The class QCIP was introduced by Buhrman, Le Gall, and Weggemans [16] and was further studied by Grewal and Kretschmer [23]. Notice that . 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 and a language with yes- and no-instances efficiently samplable relative to . Nevertheless, the classical yes- and no-instance distributions remain computationally indistinguishable to quantum polynomial-time algorithms with access to and classical access to a 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 trade-off 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 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.
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 -qubit pure state through the reflection
The promise is that the oracle is either , for some hidden state , or the identity. A UniqueQMA prover can send itself, after which one controlled oracle query distinguishes the two cases perfectly. Aaronson and Kuperberg proved that any verifier that distinguishes from with bounded error on average for a Haar random -qubit state , even when given an -bit classical witness chosen as an arbitrary function of , must make 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 , 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 , 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 , and let be the Haar probability measure on pure states in . For each , let be the deterministic prover fixed above. A public transcript is the ordered list of classical messages exchanged so far. Let be the set of hidden states whose provers send all the replies recorded in , when given the verifier messages recorded there. For a positive-probability transcript , define
The quantity is the probability that a Haar-random state belongs to . 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 through the messages in the transcript . In other words, the probability of generating the verifier messages in is the same for every state in . Thus, conditioned on , the hidden state has Haar measure restricted to , and the verifier’s conditional private state depends only on . Thus measures how much the transcript has narrowed the possible hidden states relative to the verifier. Initially,
A verifier message does not change this quantity. Indeed, conditioned on the earlier transcript , the verifier’s state is independent of the particular hidden state in . Therefore, if the verifier next sends , then
Now suppose that the prover sends a reply . Since is deterministic, this reply restricts the compatible set to
The sets , as ranges over the possible replies, partition . Define
Note that is exactly the conditional probability that the prover sends , given the earlier transcript .
If reply is observed, the increase in is
Therefore, averaging over the possible replies, the expected increase is
Here the expectation is over the distribution of . The right-hand side is the entropy of the prover’s reply, measured using natural logarithms. If the reply contains bits, it has at most possible values, and hence
Thus, a -bit prover message can increase the expected value of by at most , while verifier messages do not increase it at all.
Finally, let be the total number of prover bits sent before query and let denote the public transcript immediately before that query. Summing the preceding bound over all prover messages before that query gives
This expectation correctly weights each transcript by its probability: transcripts with very small compatible sets may have large , but they are correspondingly unlikely to occur.
From information to query complexity. The bound on 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 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. . We now replace all 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
This is where enters: each query contributes to the total change. Constant distinguishing advantage consequently requires .
The QMA–QCIP[2] gap problem. For the gap problem we follow the random-subset construction of Barhoush, Morimae, Nishimaki, and Yamakawa [8]. At length , choose a random sparse set of yes-labels. Each yes-label controls a reflection about an independent Haar-random state; every no-label controls the identity. Two further oracles swap the blank state with a uniform superposition of all yes-labels together with any requested number of witness copies, or a uniform superposition over all no-labels.
Suppose an adversary receives an instance . 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 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.
Next, we generalize our arguments of the indistinguishability of the reflection oracle to the case where the adversary has access to a QCIP[2] oracle rather than being just a QCIP[2] verifier.
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 are natural logarithms. For density operators and , let
denote trace distance. Trace distance is contractive under quantum channels and bounds the difference between the probabilities of every measurement outcome.
Let be Haar measure on the pure states in , or equivalently on . We write 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 , define
The two cases of the promise problem are
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 the order is
while for it is
Here is sent by the verifier and by the prover. Thus QCIP[1] = QCMA, QCIP[2] is verifier-first, and QCIP[3] has order . 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 classical messages, over all fixed integers . 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 , where is the transcript. No efficiency or uniformity condition is imposed on . When the oracle is , let be the verifier’s acceptance probability when interacting with , and define
where the maximum is over deterministic classical provers.
Lemma 1 (Deterministic classical provers suffice). Fix an oracle 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. ■
When , we allow the deterministic prover to depend arbitrarily on . 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 , let 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 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 , where is a unitary on a specified polynomial number of qubits. We use the length-respecting convention of Aaronson and Kuperberg: on input , a machine queries only . 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 on is -uniform, for , if for every measurable set . Equivalently, we write as an inequality of measures.
Lemma 2 (Haar overlap under conditioning (Lemma 3.2 in [3]). Let be -uniform and let be a density operator on , where . Then
What a Classical Transcript Reveals
We first describe the experiment used throughout this section. Fix a verifier with padded query slots, fix , and fix a measurable choice , for , of deterministic classical provers. The measurable choice needed for the lower bound is constructed explicitly in Theorem 4. Sample , let the prover be , and replace every verifier oracle call before slot by the identity. The prover is already represented by the fixed prover , so it makes no oracle calls inside this experiment. We call this the identity-prefix execution. Let be its public classical transcript immediately before query . The randomness in 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 , define its compatible set
Thus contains exactly the hidden states consistent with the prover’s part of $h. Verifier messages still appear in , because they determine which reply the prover sends. Their own probabilities impose no further restriction on once the preceding transcript is fixed. Measurability of the choice makes every set Haar measurable.
Warm-up: three messages. Consider a transcript
where are prover messages and is the verifier’s challenge. Capital letters denote random messages, and lower-case letters denote their realized values. After observing , the compatible states form . Once is fixed, the identity-prefix verifier’s private state is fixed as well. Hence the distribution of is the same for every , and observing does not shrink the set:
The final prover message can shrink it:
Thus and can reveal information about , but cannot reveal new information once is known. If query occurs before , then only the bits in are charged.
Lemma 3 (Query overlap after a classical transcript). In the identity-prefix execution, let be the state of the oracle-input register before query , conditioned on transcript . If at most padded prover bits precede this query, then
Proof. We first show that, conditioned on any possible transcript , the hidden state is Haar distributed over , and the verifier’s private state depends only on , not on the particular .
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 . 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 . Since is deterministic, the new compatible set is exactly
where denotes extended by . Conditioning on this reply restricts the hidden state to . 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 -bit prover message partitions into the sets . Let
Therefore, the expected logarithmic mass of the compatible set is:
The inequality holds because a -bit message has at most possible values, so its conditional entropy is at most . Average over the preceding transcript and repeat for every prover message before query . Their padded lengths total at most , giving
For each possible transcript , the query state is fixed, whereas the hidden state has Haar measure conditioned on . Lemma 2 therefore gives
Averaging over 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 , which we suppress from the notation.
Theorem 4 (Classical-interaction query bound). Let exchange only classical messages, make at most queries to the distinguished -dimensional oracle, and receive at most padded prover bits. Then
where the maximum is over deterministic classical provers. The same bound holds for .
Proof. For every , choose a deterministic classical prover 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 , 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 . Order the verifier’s oracle calls chronologically. For , let be the final state of the verifier and public transcript when the first calls use and the remaining calls use . To bound the effect of one replacement, purify the state before the query to , and let be the overlap of its oracle-input register with . The two post-query purifications have inner product , so their trace distance is
Discarding the purifying register and applying later operations cannot increase trace distance. For a controlled query, is replaced by the weight on , which is at most , so the same bound holds.
Conditioned on transcript before query , let be the reduced density operator of the oracle-input register, obtained by tracing out all other registers; the overlap defined above is therefore . Convexity of trace distance, concavity of the square root, and Lemma 3 give
We can telescope over the queries to obtain Eq. (4) for the chosen maximizing provers.
We now compare the optimal acceptance probabilities. Suppose first that , and choose a deterministic prover that achieves . 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 is the maximum acceptance probability over all prover strategies, it satisfies
Together with , this gives
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,
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
One Oracle Separating Every Message Count
For each , choose a bit and a Haar random -qubit state . Define the -qubit unitary
where is the identity on qubits. Thus when , while when . The quantum oracle is the family . The construction below specifies the bits and states .
For each length , define
The associated unary language is
Thus deciding whether means determining whether is the identity or a reflection.
Theorem 5 (Simultaneous separation). There exists a quantum oracle such that
In particular, the same oracle satisfies for every fixed integer .
Proof. First, we show that for every oracle of this form. Reject non-unary inputs. On input , the verifier receives an -qubit witness , prepares a control qubit in , applies controlled-, applies a Hadamard gate to the control, and accepts exactly when the outcome is . If , the witness is accepted with probability one. If , every witness is rejected.
Enumerate all polynomial-time uniform quantum verifiers with classical communication as , using a fixed finite universal gate set. Let and be polynomial bounds on the oracle queries and total prover-to-verifier communication of . This enumeration includes every verifier with polynomially many messages.
At stage , choose a fresh input length , larger than every length used earlier, such that the right-hand side of Eq. (4), with , , and , is less than . This is possible because and are polynomials whereas is exponential.
Consider on input , and let when the length- component is the identity. There are two cases.
If , set . Then , but violates soundness.
If , Theorem 4 gives
where is Haar distributed on qubits. Hence some satisfies . Set . Then , but violates completeness.
Set all unused components to the identity. The length-respecting restriction on verifier oracle access ensures that later stages do not change ’s behavior on . The value 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 .
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 . On input , the first verifier circuit produces a classical challenge and a private quantum state that it passes to the second verifier. The prover returns a classical answer depending on , and the second verifier circuit decides whether to accept. Let be the largest acceptance probability over all deterministic classical provers when both verifier circuits have access to the quantum oracle .
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 consists of all total Boolean functions satisfying
When the value lies strictly between and , 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 , let be its verifier, and let and be distributions supported on and , respectively. The pair is a gap problem if:
for every polynomial , a QPT oracle algorithm on input samples , where has distribution and is accepted by with probability at least ;
a possibly inefficient oracle algorithm samples ; and
for every polynomial and every QPT , there is a completion such that
The distinguisher has quantum query access to and classical access to .
The random-subset oracle
Fix , let , and put
Choose uniformly among all -element subsets of . Independently choose an -qubit Haar-random state for every .
The oracle has one testing component and two sampling components. The testing component has a control qubit, an -bit label register, and an -qubit state register. On computational-basis control and label registers, it acts as
Thus a controlled query at applies the reflection about , while a query at applies the identity.
For a unit vector orthogonal to , write
This unitary swaps and and fixes their common orthogonal complement. For every integer , define
The oracle contains the blocks
The integer 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 denote the collection of these independently sampled components over all input lengths, and define
Membership at the finitely many smaller lengths is defined arbitrarily.
Lemma 4 (Verification and sampling). For every realization of , the language belongs to with perfect completeness and perfect soundness. Moreover, the uniform distributions on and on its complement satisfy the first two conditions of Definition 3.
Proof. On input , the QMA verifier performs the Hadamard test for the controlled testing block . If , the witness is a eigenvector and is accepted with probability one. If , the addressed block is the identity for every witness, so the verifier rejects with probability one.
On input , the yes sampler applies to , measures the label register, and returns the remaining witness registers. Its output is a uniform together with . Applying to 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 for some constant and all sufficiently large . 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 , where the ’s are orthonormal, and let
Then
The same estimate holds when one orthogonal term is added to an -term superposition.
Proof. The two target states have inner product , and hence
Expanding the definition of in Eq. (6) and using 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 , puncturing the same label changes every tagged block by the same amount. The norm of the tagged direct-sum difference is the maximum of the block norms, so the estimate is uniform in . ■
We now choose the answers on ambiguous QCIP[2] queries. For every binary string , independently sample
once and keep it fixed. Write for this threshold table. Given a base oracle , define
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 are always accepted and values at most are always rejected. If two base oracles give values and to the same description, then, using the same threshold in both worlds,
Indeed, an answer differs only when the uniform threshold falls between and , and the interval has length .
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 of the construction above, the uniform distributions on and its complement form a QMA–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 , and let 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 , a uniform , and a uniform . Independently sample the threshold table 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 and outputs its result.
. Use the original oracle and give the input .
. Remove the term indexed by from every .
. Replace the reflection at address by the identity.
. Add to .
. Keep this modified oracle, but replace the input by .
. Remove from the no sampler.
. Restore the reflection at address .
. Restore the term indexed by in every yes sampler.
Each hybrid changes only the operation specified, leaving everything else as in the preceding hybrid. Thus 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 and . 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 , the threshold is independent of the preceding history, and Eq. (9) bounds the disagreement probability by . A repeated query cannot cause the first disagreement. Hence a union bound over the at most queries bounds this change by
where the maximum is over the descriptions allowed by the resource bound. This maximum also covers adaptively chosen descriptions.
Sampler changes. The transitions to , to , to , and to 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 . The preceding completion bound preserves exponential smallness.
Reflection changes. For to and to , the yes samplers no longer contain . Fix the labels and all oracle data other than . The remaining background is independent of . Apply Theorem 4 to a verifier that first receives a protocol description 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 and the later replies as a function of . For each , 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
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 , so Theorem 4 with no prover messages also bounds the direct change by .
The middle switch. Put . Conditioned on , the ordered pair is uniform over distinct elements of . In and , the testing and yes-sampling components use exactly the labels in , and the no sampler is uniform over . The modified oracle and its completion therefore do not depend on which element of the pair was originally in . Exchanging and leaves their joint distribution unchanged, so and have identical output distributions. The triangle inequality now gives
These probabilities include the choice of the base oracle and threshold table. To obtain a fixed realization, write and for ’s yes- and no-input acceptance probabilities for fixed . Apply Eq. (10) to an algorithm that runs 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 and by . Subtracting gives
Markov’s inequality and the Borel–Cantelli lemma imply that is negligible with probability one over . 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]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]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]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
- [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
- [7]Barhoush, M., Morimae, T., Movassagh, R.: Separating quantum indistinguishability obfuscation from falsifiable assumptions. arXiv:2608.25195 (2026). https://arxiv.org/abs/2608.25195
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [19]Casper, O., Nehoran, B., Sattath, O.: Conversable quantum fire in the standard model. arXiv:2609.36335 (2026). https://arxiv.org/abs/2609.36335
- [20]Farhi, E., Gosset, D., Hassidim, A., Lautumirski, 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
- [23]Grewal, S., Kretschmer, W.: Entanglement and post-measurement branching in quantum interactive proofs. arXiv:2509.15319 (2025). https://arxiv.org/abs/2509.15319
- [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
- [27]Jain, R., Kerendis, 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
- [30]Kundu, S., Lalonde, O.: Near-optimal entanglement-communication tradeoffs for remote state preparation. arXiv:2602.09428 (2026). https://arxiv.org/abs/2602.09428
- [33]Mahadev, U.: Classical verification of quantum computations. SIAM Journal on Computing 51(4), 1172–1229 (2022). https://doi.org/10.1137/20M1371828
- [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