Succinct Arguments for QMA from Collapsing Hash Functions
arXiv:2609.35633v1 [quant-ph] 28 Sep 2026
James Bartusek∗
Giulio Malavolta†
Abstract We prove the existence of succinct arguments for QMA, assuming only the existence of collapsing hash functions. This is the first scheme that relies only on unstructured “Minicrypt” assumptions, which are not known to imply public-key encryption. Our main technical contribution is a quantum-succinct claw-state generation protocol that allows us to bootstrap a small number of quantum correlations into an arbitrarily large number of claw-state correlations, using classical communication only. This improves upon the work of [Zhang, STOC 2021], having better round complexity, a proof in the standard model, and being overall much simpler. This yields a quantum-succinct blind delegation of quantum computation protocol from one-way functions, which we plug into the communication-compression compiler of [Bartusek, Liu, and Malavolta, EUROCRYPT 2026] to obtain succinct arguments for QMA.
Contents 1 Introduction 1.1 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Technical Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Concurrent work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 AI usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 2 3 7 7
2 Preliminaries 2.1 Succinct Arguments for QMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Claw States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Pseudorandom Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 8 8 9
3 Claw-State Generation Protocol 10 3.1 Protocol Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4 Sequential Repetition
15
5 Succinct Arguments for QMA 18 5.1 Blind Delegation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.2 Putting Things Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 References
∗ †
24
Columbia University [email protected] Bocconi University [email protected]
1
1
Introduction
Succinct arguments enable the verification of mathematical statements using significantly fewer resources than required to process a complete proof. Pioneered by Kilian [Kil92], succinct arguments have become a pillar of study in both foundational and applied cryptography. In his work, Kilian showed how to compile any probabilistically checkable proof system (PCP) [ALM+ 98, AS98] for NP into a succinct argument for NP using only collision-resistant hash functions. Recent years have witnessed a surge of interest in quantum information-processing, giving rise to a natural follow-up question: Under what cryptographic assumptions do there exist succinct arguments for all of QMA, namely, what type of cryptographic structure enables the extremely efficient verification of statements with quantum proofs? A series of recent works [BTL+ 22, MNZ24, GTNV25, BLM26] has culminated in a construction of succinct arguments for QMA from the following two cryptographic ingredients: • Collapsing hash functions: the post-quantum analogue of collision-resistance. • Oblivious state preparation: a generic “public-key” style assumption that can be instantiated from LWE, LIP, or assumptions on cryptographic group actions [BK25, BMM26]. The state of the art thus highlights a significant gap from the classical setting: While succinct arguments for NP only require unstructured cryptography in the form of collision-resistant hash functions (placing them in “Minicrypt”), succinct arguments for QMA are only known from publickey style assumptions, positioning them in “Cryptomania”. In this work, we establish that succinct arguments for QMA do in fact live in Minicrypt by proving their existence assuming only collapsing hash functions [Unr16]. As collapsing is the postquantum analogue of collision-resistance, this exactly matches the weakest assumption under which Kilian’s succinct arguments for NP are known to be post-quantum secure [CMSZ22].
1.1
Results
Our main result is stated below, where λ denotes the security parameter. Theorem 1.1. There exists a fixed polynomial poly such that, assuming collapsing hash functions, there exists an argument system for QMA with completeness 1 − negl(λ), soundness error negl(λ), total communication bounded by poly(λ), and verifier runtime |x| · poly(λ). The protocol uses quantum communication (and thus a quantum verifier) and makes non-blackbox use of the collapsing hash function. Above, x refers to the QMA statement, and |x| is its bit length. In particular, |x| · poly(λ) has no dependence on the witness length or the time required to run the original QMA verifier on x and a witness state |ψ⟩. Note that, because of the non-black-box use of the collapsing hash function, we do not automatically obtain a succinct argument for QMA in the quantum random oracle model. Remark 1.2 (Prepare-and-send verifier). One potentially desirable aspect of our protocol is that it does not require the verifier to keep any quantum memory between rounds. In particular, each of the verifier’s quantum messages can be prepared from its classical state immediately before sending, and no auxiliary quantum registers are kept by the verifier after the message is sent.
2
Our main technical ingredient is a new construction of blind delegation of quantum computation, which asks whether a resource-constrained client can delegate a quantum computation to a server in such a manner that the server learns nothing about the client’s computation. One natural resource constraint is the size of the quantum circuit that the client runs during the course of the protocol. If the size is 0, we refer to this as classical blind delegation of quantum computation, and if the size is bounded by a fixed polynomial in the security parameter, independent of the size of the computation being delegated, we refer to this as quantum-succinct blind delegation of quantum computation. It was shown by [Zha21] that quantum-succinct blind delegation of quantum computation exists in the quantum random oracle model. In this work, we design and prove the security of a vastly simpler protocol that only requires one-way functions, yielding the following theorem. Theorem 1.3. Assuming one-way functions, there exists quantum-succinct blind delegation of quantum computation. Discussion. Recall that Kilian’s result used collision-resistant hash functions to compile a PCP for NP into a succinct argument for NP. Recently, a quantum analogue of Kilian’s compiler was worked out by [GJMZ23], establishing that PCPs for QMA can be compiled into succinct arguments for QMA, utilizing only unstructured cryptography. In fact, they assume only the existence of pseudorandom unitaries, a “Microcrypt” assumption that is weaker than even one-way functions. Unfortunately, it remains a major unresolved problem whether PCPs for QMA actually exist. Another point worth making is that [GJMZ23] and our protocol both make use of quantum communication and thus a quantum verifier. One could ask whether the verifier can be made completely classical, while remaining succinct. This is indeed known, but under public-key assumptions such as LWE. However, improving the result to classical, even non-succinct, verification of QMA in Minicrypt would be considered a major breakthrough, so we regard the quantum communication component of our protocol as a crucial relaxation given current techniques. Therefore, we can summarize the state of succinct arguments for QMA as follows. • [GJMZ23]: Assuming the quantum PCP conjecture, there exist succinct arguments for QMA from pseudorandom unitaries. That is, assuming the quantum PCP conjecture, succinct arguments for QMA exist in Microcrypt. • Our result: Succinct arguments for QMA exist in Minicrypt, without assuming the quantum PCP conjecture. In particular, succinct arguments for QMA exist assuming only collapsing hash functions. • [MNZ24, GTNV25, BLM26]: Succinct arguments for QMA with classical verification exist in Cryptomania, without assuming the quantum PCP conjecture. In particular, succinct classically-verifiable arguments for QMA exist assuming a standard public-key assumption such as LWE.
1.2
Technical Outline
Before we explain our approach to the problem, let us recall some necessary background information to motivate our design choices. Our starting point is the recent work of [BLM26], who proposed a compiler that, assuming collapsing hash functions, compresses the communication complexity of
3
any classical-verifier interactive protocol Π with r(λ) rounds. For any ε = 1/ poly(λ), the compiled protocol Π̃ has negligible completeness loss, soundness loss O(ε) + negl(λ), and satisfies e ≤ r(λ) poly(λ, 1/ε), CC(Π)
verifier time ≤ |x| r(λ) poly(λ, 1/ε),
where x is the common input and the polynomial is fixed independently of the original message lengths. Thus, for our purposes, the remaining task is to construct a QMA argument with a fixed poly(λ) number of rounds but otherwise arbitrary classical communication, which can be fed into the above compiler. Prior work [BLM26] constructs such a round-efficient argument using the compiled non-local games framework [KLVY23, NZ23, BK25, BKM+ 25]. The approach here is to start from an information-theoretically secure two-prover protocol and compile it into a single-prover protocol using cryptography. The cryptographic ingredient is blind delegation, which is an interactive protocol between a server and a client, where the client holds a private classical input x, the server has a quantum input ρ, and they both have the public description of a quantum circuit Q. In the ideal honest execution, the client obtains Pauli keys (r, s) and the server obtains σ such that Zs Xr σXr Zs = Q(x, ρ). Correctness allows negligible error and includes arbitrary reference systems, as specified in Definition 5.4. We require that, for every QPT server A and every pair of equal-length inputs (x0 , x1 ), the views of the server are computationally indistinguishable: ViewA (ρ, x0 ) ≈c ViewA (ρ, x1 ). [BLM26] shows how to combine a blind delegation protocol from [BK25, BKM+ 25] with a twoprover game from [MNZ24] to obtain the desired round-efficient argument. These protocols however require the existence of public-key assumptions such as oblivious state preparation or trapdoor clawfree functions. Constructing blind delegation from collapsing hashes alone appears unlikely (or at least very difficult given known techniques), since blind delegation implies (classical-communication) key agreement [BK25]. Idea I: Relaxing the Model. Our first simple, but crucial, observation is that the client does not need to be completely classical in the above interaction. For instance, it could be acceptable to construct a blind delegation protocol where the client performs a fixed polynomial amount of quantum operations, so long as we can still apply the aforementioned communication-compression compiler to the (potentially long) classical messages. Henceforth, we refer to such a protocol as quantum succinct. With this observation in mind, let us try to simplify the problem even further: In [BK25] it is shown that a blind delegation protocol can be generically derived from claw-state generation, an interactive protocol where at the end, the server obtains multiple claw states 1 √ (|0, x0 ⟩ + |1, x1 ⟩) 2 and the client obtains a classical description of their labels (x0 , x1 ). The only security guarantee that we require is that the server should not be able to guess both x0 and x1 . Thus, our problem further reduces to designing a round-efficient and quantum-succinct claw-state generation protocol: Allowing the client to use poly(λ, log T ) quantum gates and a (possibly large) amount of classical communication, we want an interactive protocol where the server obtains T such claw states. Climbing up the chain of implications explained above, this will suffice for our main result. 4
In fact, a very similar problem was considered by Zhang [Zha21], precisely motivated by the construction of a blind delegation protocol with a quantum-succinct client. He shows how to bootstrap a small initial quantum communication into an arbitrary polynomial number of claw states, using classical communication only. However his approach has two limitations: First, the round complexity of his protocol is polynomial in T , rendering it unusable for us since we require a round-efficient protocol. Second, the security is proved in the quantum random-oracle model. This is also problematic, since the communication-compression compiler makes non-black-box use of the underlying protocol (in this case, it would require the circuit description of the underlying hash function). This would render the security claim of the underlying protocol vacuous. Instead, we propose a new approach to quantum-succinct claw-state generation, which relies only on (quantum secure) one-way functions and has the added benefit of being dramatically simpler than Zhang’s protocol. Next, we give a more detailed overview of our protocol. Idea II: Quantum-Succinct Claw-Generation from One-Way Functions. Assume that T is a power of 2 and set n = λ. Prior to the interaction, the client samples several PRF keys denoted by k ∈ {0, 1}λ and ki,b ∈ {0, 1}λ , along with random strings xi,b ∈ {0, 1}n , for i ∈ [log T ] and b ∈ {0, 1}. For any index t ∈ [T ] ∼ = {0, 1}log T we will think of (yt,0 , yt,1 ) = fk (t) as the strings that determine the t-th output claw. The client prepares and sends the quantum state X O |0, yt,0 ⟩ + |1, yt,1 ⟩ 1 √ √ (1) |ti , xi,ti , ki,ti ⟩ 2 T log T i∈[log T ] t∈{0,1}
to the server, which can be prepared efficiently (that is, in time poly(λ, log T )) with the knowledge of the client’s randomness. In addition the client also sends the large, but classical, table ct,i = fk (t) ⊕ fki,1−ti (t)
for t ∈ {0, 1}log T , i ∈ [log T ].
(2)
To get some intuition, it is useful to think about each of the T states in the superposition of Equation (1): In the “t-subspace”, the server can compute (yt′ ,0 , yt′ ,1 ) for every t′ except for t. Indeed, for t′ ̸= t, choose any i with t′i ̸= ti . Then ct′ ,i ⊕ fki,ti (t′ ) = fk (t′ ) = (yt′ ,0 , yt′ ,1 ). We also mention that while the random xi,ti are not used in this derivation, their presence will be useful for arguing security. Coherently preparing the missing claws and placing every output at its designated index, the server can then prepare the state O |0, xi,0 , ki,0 ⟩ + |1, xi,1 , ki,1 ⟩ O |0, yt,0 ⟩ + |1, yt,1 ⟩ ⊗ √ √ . (3) 2 2 log T i∈[log T ] t∈{0,1}
To complete the protocol, the server measures the first registers in the Hadamard basis and returns (0) (1) (2) d = (d1 , . . . , dlog T ), parsed as di = (di , di , di ) ∈ {0, 1} × {0, 1}n × {0, 1}λ . The client accepts exactly when, for every i, (1)
di
̸= 0,
⟨di , (1, xi,0 ⊕ xi,1 , ki,0 ⊕ ki,1 )⟩ = 0. (1)
(4)
Honest Hadamard measurements satisfy the parity constraint, and di = 0 occurs with negligible probability. The honest server thereby deletes the first registers and retains the output claw states. Moreover, notice that the round complexity of this protocol is constant, and the client’s quantum 5
operations are bounded by poly(log T, n, λ) = poly(λ), whereas the client’s classical runtime and the server’s total runtime are poly(T, λ). For security, we will only be able to prove that, for a random choice of index t∗ ← [T ] sampled at the conclusion of the protocol, the adversary cannot both pass Equation (4) and output fk (t∗ ) = (yt∗ ,0 , yt∗ ,1 ) with better than constant probability. We refer the reader to the technical sections for a precise analysis, and here we just say that the proof will boil down to splitting the state of the adversary into two components: • The first component will be bounded by the success probability of an experiment where the adversary is given only the part of the state indexed by t∗ , instead of the superposition in Equation (1), which allows us to appeal to the security of the PRF and replace the table entries ct∗ ,i by uniform strings and fk (t∗ ) by a uniform pair. In this hybrid experiment, the success probability of outputting fk (t∗ ) can therefore be bounded by negligible. • The second component is a residual “unbalanced” state derived by subtracting off the (appropriately weighted) t∗ branch, and whose averaged squared norm after the deletion check can only be at most 14 : each individual branch passes the checks with probability at most T1 , and the imbalance in the amplitudes of the branches can then be used to derive the 41 bound. Overall, we combine the two bounds using standard inequalities, and obtain a total bound on passing Equation (4) and guessing the randomly selected output pair by 14 (plus an irrelevant negligible term). The next goal is therefore to amplify the hardness of these output claw states. Hardness Amplification. To amplify, we use an idea from Zhang [Zha21], which consists in running λ independent copies of the expansion protocol sequentially and then combining λ weaklysecure claw states into one strongly-secure claw state. Only after all copies terminate, the client chooses independent uniform permutations πi ∈ ST for each repetition i ∈ [λ] and sends them to the server. For an output index t, the server combines the λ claws indexed by {πi (t)}i∈[λ] by measuring the XOR of the first claw’s leading qubit with each other leading qubit, obtaining the outcomes e2,t , . . . , eλ,t . This effectively glues together independent claw states into a single claw |0,Yt,0 ⟩+|1,Yt,1 ⟩ √ , where 2 (1)
(2)
(1)
(2)
(λ)
Yt,0 = yπ1 (t),0 ∥ yπ2 (t),e2,t ∥ · · · ∥ yπλ (t),eλ,t , (λ)
Yt,1 = yπ1 (t),1 ∥ yπ2 (t),1⊕e2,t ∥ · · · ∥ yπλ (t),1⊕eλ,t . The important observation is that guessing Yt,0 , Yt,1 implies also guessing all λ constituents simultaneously. We can therefore hope to conclude that, if each individual claw is 14 secure, then the probability of guessing the combined claw state must be bounded by 4−λ + negl(λ). Idea III: Sequential Repetition for Quantum Search Games. To make this intuition formal, we prove a general sequential repetition theorem for quantum search games: A quantum search game is an interactive protocol between a prover and a verifier, where the goal of the prover is to guess some secret x, and the verifier can either accept or reject. In ℓ sequential copies, the verifier uses independent fresh randomness for each, the adversary retains arbitrary quantum memory, and it may postpone all predictions until every interaction has finished. We show that the combined success probability degrades exponentially with ℓ. As usual in this context, the difficulty is that 6
conditioning on success in other copies can disturb the quantum memory, and the verifier’s secret target is unavailable to a reduction. For any round j, we denote by qj the maximum probability, over arbitrary starting states just before copy j, of guessing all targets from j through ℓ using the remaining strategy. Our goal will be to prove that qj ≲ εqj+1 where ε is the bound on the single search game, with a reduction to the bound on the single-copy search game. We can imagine giving the reduction the best-possible quantum state as non-uniform advice, then let the reduction interact with the challenger for the j-th copy and simulate the rest of the interactions locally. If qj+1 is sufficiently close to one, simply running that suffix already contradicts the one-copy bound. Otherwise, we need to amplify the successful part of the suffix coherently. We do this using the quantum singular value transformation (QSVT) [GSLW19], which is a powerful quantum rewinding technique. In particular, rewinding enables us to effectively condition on the adversary successfully answering targets j + 1 through ℓ (note that the reduction knows what these targets are, the only missing information is target j), and only then output its guess for target j. This increases its overall probability of success by a factor of roughly 1/qj+1 , so if we had assumed for contradiction that qj > εqj+1 , then our reduction outputs the j-th target with probability > ε, a contradiction. We refer the reader to the technical sections for more details. Putting Things Together. Taking a step back, we have therefore obtained, from quantumsecure one-way functions, a poly(λ)-round claw-state generation protocol for any polynomial T : At N |0,Yt,0 ⟩+|1,Yt,1 ⟩ √ the end of the interaction, the honest server holds t , and outputting any classical 2 pair is computationally hard. Quantum communication is only client-to-server, with poly(λ, log T ) preparation cost and circuits fixed before interaction. The [BK25] transformation converts these correlations into a blind delegation protocol with the same efficiency properties, which supplies the missing ingredient for the communication-compression compiler of [BLM26]. Combining all the steps, we obtain a succinct argument for QMA from collapsing hash functions.
1.3
Concurrent work
In a concurrent and independent work, [CH26] also construct succinct arguments for QMA in Minicrypt via a completely different approach. In particular, they compile the quantum IOP of [SV26] into a succinct argument for QMA that is proven unconditionally secure in the quantum random oracle model. They do not claim a construction in the plain model.
1.4
AI usage
The overall architecture and general proof strategy were developed without AI assistance. ChatGPT was used to refine the protocol, assist with technical proofs, revise the exposition, and check references. The authors take full responsibility for the content.
2
Preliminaries
Let λ be the security parameter. We write [n] = {1, . . . , n} and use logarithms to base 2. For a finite set S, we write s ∼ S when s is sampled uniformly from S. All inner products between bit strings are over F2 . 7
All registers are finite-dimensional Hilbert spaces. We consider security against non-uniform QPT adversaries that may initialize a polynomial-size register to an arbitrary non-uniform state independent of fresh honest randomness. All cryptographic assumptions and computational indistinguishability statements quantify over adversaries with such auxiliary input; negligible terms may depend on the adversary. Instance and circuit sizes are polynomially bounded in the security parameter, while the polynomials in succinctness bounds are fixed independently of the original verification time and witness size. We use sans-serif letters such as A, B, R for registers, HA for the Hilbert space of register A, and IA for its identity operator. Register labels on states and operators indicate where they act; omitted registers are left unchanged. Braces with subscripts denote indexed lists. We write ∥ for concatenation of bit strings, ∥ · ∥ for vector or operator norm, and √ ∥A∥1 := Tr A† A for the trace norm. The trace distance of states ρ, σ is 21 ∥ρ − σ∥1 . A POVM is a family of positive operators summing to the identity. We write ≈c for computational indistinguishability and negl(λ) for a function smaller than every inverse polynomial. We use compressing collapsing hash functions in the sense of [Unr16]: After a hash is evaluated coherently and its output is measured, additionally measuring the input is computationally undetectable, even given the remaining workspace. We use this property through the compiler of [BLM26]. All one-way functions and pseudorandom functions are assumed secure against the quantum adversaries specified above.
2.1
Succinct Arguments for QMA
Fix a QMA promise problem L = (Lyes , Lno ), with a polynomial-time uniform quantum verifier V = {Vx }. For x ∈ Lyes , there exists a polynomial-size quantum witness ρ such that Vx (ρ) accepts with probability at least 2/3; for x ∈ Lno , no witness causes Vx to accept with probability greater than 1/3. We recall the definition of succinct arguments for QMA below [BTL+ 22]. Definition 2.1 (Succinct Argument for QMA). A succinct argument for the QMA promise problem L is an interactive protocol Π between a prover and a verifier where the common input is (1λ , x) and the prover additionally receives a quantum state ρ. The protocol satisfies the following properties. • Correctness: For x ∈ Lyes , there exists a QPT prover that, on input a valid witness ρ, causes the verifier to accept with probability at least 32 . • Soundness: For x ∈ Lno and all QPT provers on input an arbitrary state ρ, the probability that the verifier accepts is bounded by 31 . • Succinctness: The communication complexity of the protocol is bounded by poly(λ) and the verifier’s complexity is bounded by |x| · poly(λ).
2.2
Claw States
We refer to states of the form |ψx0 ,x1 ⟩ :=
|0, x0 ⟩ + |1, x1 ⟩ √ 2
8
for x0 , x1 ∈ {0, 1}n , as claw states. Let ρx0 ,x1 := |ψx0 ,x1 ⟩⟨ψx0 ,x1 |, it is easy to see that ρx0 ,x1 can be prepared by a polynomial-size quantum circuit, given (x0 , x1 ). The following lemma shows that a uniformly sampled claw state is hard to guess. Lemma 2.2. Consider the following experiment: • Sample x0 , x1 ∼ {0, 1}n , then prepare the state ρx0 ,x1 and send it to the adversary. • The adversary returns (x∗0 , x∗1 ). • The adversary wins if (x0 , x1 ) = (x∗0 , x∗1 ). The probability that any adversary succeeds in this experiment is at most 21−n . n+1 Proof. Let C be the claw register, with HC ∼ = C2 , and let A be the adversary’s auxiliary register. We may assume without loss of generality that its initial state is pure, say |α⟩A : a mixed state can be purified by enlarging A. This state is independent of (x0 , x1 ).
Let {Mx0 ,x1 }x0 ,x1 be the POVM on CA describing the adversary’s guess. To obtain a measurement on the claw register alone, define Nx0 ,x1 := (IC ⊗ ⟨α|A )Mx0 ,x1 (IC ⊗ |α⟩A ). P Each Nx0 ,x1 is positive, and x0 ,x1 Nx0 ,x1 = IC , thus these operators form a POVM. They give exactly the same guessing probabilities because Tr(Mx0 ,x1 (ρx0 ,x1 ⊗ |α⟩⟨α|)) = Tr(Nx0 ,x1 ρx0 ,x1 ). The adversary’s success probability is therefore 1 X 1 X Tr(N Tr(Nx0 ,x1 ) ρ ) ≤ x ,x x ,x 0 1 0 1 22n x ,x 22n x ,x 0
1
0
1
X 1 Nx0 ,x1 = 2n Tr 2 x ,x 0
!
1
1 Tr(IC ) 22n = 21−n ,
=
where the inequality uses ρx0 ,x1 ⪯ IC .
2.3
Pseudorandom Functions
Let T be a power of 2 and fk : {0, 1}log T → {0, 1}2n be a keyed function, for k ∈ {0, 1}λ . We say that fk is a pseudorandom function if its table of outputs is computationally indistinguishable from a uniformly random table. In this work we consider the special case where T = poly(λ) and we assume that the function satisfies the following notion of pseudorandomness, which is implied by the regular definition of a pseudorandom function.
9
Definition 2.3 (Pseudorandomness). A function fk : {0, 1}log T → {0, 1}2n is pseudorandom if, for all x∗ ∈ {0, 1}log T , the following distributions are computationally indistinguishable {fk (x)}x̸=x∗ , fk (x∗ ) ≈c {fk (x)}x̸=x∗ , y ∗ . Here k ∼ {0, 1}λ and y ∗ ∼ {0, 1}2n are independent, and the non-target entries are listed in the same fixed order on both sides. Such pseudorandom functions can be constructed assuming the existence of (quantum-secure) one-way functions [Zha12].
3
Claw-State Generation Protocol
3.1
Protocol Description
Set n = λ and let T = poly(λ) be a power of 2. We consider the following interactive protocol between a client and a server. (i) The client samples k ∼ {0, 1}λ , then for all i ∈ [log T ] and b ∈ {0, 1} it samples xi,b ∼ {0, 1}n and ki,b ∼ {0, 1}λ . (ii) For all t ∈ {0, 1}log T and i ∈ [log T ], the client sends to the server ct,i := fk (t) ⊕ fki,1−ti (t) ∈ {0, 1}2n . (iii) The client computes the state O |0, xi,0 , ki,0 ⟩ + |1, xi,1 , ki,1 ⟩ 1 √ =√ 2 T i∈[log T ]
X
O
|ti , xi,ti , ki,ti ⟩ .
t∈{0,1}log T i∈[log T ]
Let (yt,0 , yt,1 ) = fk (t). The client applies the isometry |t⟩ |0⟩ 7→ |t⟩ ψyt,0 ,yt,1 to the leading qubits of the above state and a fresh output register to obtain X O 1 √ |ti , xi,ti , ki,ti ⟩ ⊗ ψyt,0 ,yt,1 . T t∈{0,1}log T i∈[log T ] The client returns its auxiliary qubits to zero and sends the resulting state to the server. (iv) The server maps the state received from the client to X O O 1 √ |ti , xi,ti , ki,ti ⟩ ψyt,0 ,yt,1 . T t∈{0,1}log T i∈[log T ] log T t∈{0,1} Note that this isometry can be implemented efficiently, given {ct,i }t,i . Indeed, for any fixed t and any t′ ̸= t, the server can recover fk (t′ ) by selecting an index i such that t′i ̸= ti , so that ki,1−t′i = ki,ti , and computing ct′ ,i ⊕ fki,ti (t′ ) = fk (t′ ) = (yt′ ,0 , yt′ ,1 ). Then the server can compute the claw state |ψyt′ ,0 ,yt′ ,1 ⟩ by evaluating the claw-preparation circuit. Running this algorithm coherently and reordering the registers leads to the state as described above. 10
(v) The server measures its first registers in the Hadamard basis to obtain d = (d1 , . . . , dlog T ), where di ∈ {0, 1} × {0, 1}n × {0, 1}λ , which are sent to the client. (0)
(1)
(2)
(1)
(vi) The client parses di = (di , di , di ), and for all i ∈ [log T ] it checks that di
̸= 0 and that
⟨di , (1, xi,0 ⊕ xi,1 , ki,0 ⊕ ki,1 )⟩ = 0. We say that the server passes the protocol if all checks of the client succeed. If this is the case, the client returns {yt,0 , yt,1 }t∈{0,1}log T as its private local output. Note that the client’s quantum operations are confined in step (iii) and their runtime is bounded by some poly(log T, n, λ). On the other hand, the client’s classical runtime as well as the server’s total runtime is bounded by poly(T, n, λ). Moreover, it is easy to see that an honest server passes the protocol except with probability at (1) most (log T )2−n , since the probability that di = 0 is exactly 2−n .
3.2
Analysis
Next, we show that the output claw states are hard to guess. Assuming n = Ω(λ), we show the following. Theorem 3.1. Consider the following experiment: • Run the client-server protocol from Section 3.1. • After the server sends d, the client samples t∗ ∼ {0, 1}log T and sends this index and the strings {yt,0 , yt,1 }t̸=t∗ to the server. • The server replies with (y0∗ , y1∗ ) and wins if (y0∗ , y1∗ ) = (yt∗ ,0 , yt∗ ,1 ) and d passes the client’s checks. Assuming quantum-secure one-way functions, for every QPT server there is a negligible function µ such that its success probability is at most 1/4 + µ(λ). Proof. Let X contain the client’s random choices of k and {xi,b , ki,b }i∈[log T ], b∈{0,1} , and let ValidX (d) be its verification predicate. We use the following registers throughout this proof and the two lemmas below: C contains the client’s quantum message, A contains the server’s pure auxiliary input |α⟩, D contains the client’s copy of d, B contains all registers retained by the server after sending d, and L contains the client’s final classical message. Let A : CA → DB be a unitary dilation of the server’s first stage. Its dependence on the classical table {ct,i }t,i is implicit. The server may retain its own copy of d in B, but all its subsequent operations act trivially on D. Define X ΠX := |d⟩⟨d|D ⊗ IB . d:ValidX (d)=1
For fixed X, the client sends its final message by applying the isometry Vt |φ⟩DB = |φ⟩DB ⊗ |t, {yu,0 , yu,1 }u̸=t ⟩L . 11
The dependence of Vt on X is implicit. Let {Mt,y0 ,y1 }y0 ,y1 ∈{0,1}n be the POVM on BL describing the server’s second message, extended by the identity on D. We omit register subscripts in the remaining state formulas. The subnormalized state for which the client accepts, right before the final measurement, is X O 1 |ξX,t∗ ⟩ := √ Vt∗ ΠX A |ti , xi,ti , ki,ti ⟩ ψyt,0 ,yt,1 |α⟩ . T t i∈[log T ] Define also the possibly subnormalized state O |ζX,t∗ ⟩ := Vt∗ ΠX A
E
t∗i , xi,t∗i , ki,t∗i ψyt∗ ,0 ,yt∗ ,1 |α⟩ .
i∈[log T ]
Both states are on DBL. We use the decomposition ! √ √ T T |ξX,t∗ ⟩ = |ξX,t∗ ⟩ − |ζX,t∗ ⟩ + |ζX,t∗ ⟩ . 2 2 Intuitively, the second summand isolates the contribution obtained when the server is given the single claw state |ψyt∗ ,0 ,yt∗ ,1 ⟩, which we will bound by the hardness of recovering both strings from one claw state. The residual term can be bounded using only the verification constraints. The √ coefficient T /2 is chosen so that, after averaging over t∗ , the cross term in the expansion of the residual squared norm cancels its ∥ |ξX,t∗ ⟩ ∥2 term. By Cauchy–Schwarz and using 0 ⪯ Mt∗ ,yt∗ ,0 ,yt∗ ,1 ⪯ I, the square root of the prover’s total success probability satisfies s 1X E ⟨ξX,t∗ | Mt∗ ,yt∗ ,0 ,yt∗ ,1 |ξX,t∗ ⟩ (5) T t∗ X v u √ 2 s u1 X 1 X T t ≤ E |ξX,t∗ ⟩ − |ζX,t∗ ⟩ + E ⟨ζX,t∗ | Mt∗ ,yt∗ ,0 ,yt∗ ,1 |ζX,t∗ ⟩. T t∗ X 2 2 t∗ X For fixed X, the definitions and the isometry property give 1 X † Vu |ζX,u ⟩ . Vt† |ξX,t ⟩ = √ T u In particular, the left-hand side is independent of t. Thus X √ Re ⟨ξX,t |ζX,t ⟩ = T ∥ |ξX,t∗ ⟩ ∥2
for every t∗ .
t
Expanding the squared norm on the right-hand side of Equation (5) now gives √ 2 T 1X 1X 1 X 1X |ξX,t ⟩ − |ζX,t ⟩ = ∥ |ξX,t ⟩ ∥2 + ∥ |ζX,t ⟩ ∥2 − √ Re ⟨ξX,t |ζX,t ⟩ T t 2 T t 4 t T t 1X = ∥ |ζX,t ⟩ ∥2 . 4 t 12
Averaging over X and applying Lemma 3.2 (proven below) bounds the expression under the first square root on the right-hand side of Equation (5) by 1/4. For the second term, Lemma 3.3 (proven below) gives 21−n + µ(λ) 1X E ⟨ζX,t∗ | Mt∗ ,yt∗ ,0 ,yt∗ ,1 |ζX,t∗ ⟩ ≤ . 4 t∗ X 4 Combining these bounds, the success probability is at most 2 1 1 p 1−n 1 2 + µ(λ) = + negl(λ), + 2 2 4 since n = Ω(λ). Using the notation introduced above, we prove the two remaining technical statements in the following. Lemma 3.2. X
E ∥ |ζX,t ⟩ ∥2 ≤ 1.
t∈{0,1}log T
X
Proof. Fix t ∈ {0, 1}log T and condition on all client randomness except {xi,1−ti }i∈[log T ] . Write O X A |ti , xi,ti , ki,ti ⟩ ψyt,0 ,yt,1 |α⟩ = |d⟩ |ϕt,d ⟩ d
i∈[log T ]
for possibly subnormalized states |ϕt,d ⟩ on B, with |d⟩ on D. These states are fixed under the conditioning: the input state contains only {xi,ti }i∈[log T ] , and the classical table {ct,i }t,i depends only on the keys. Since Vt is an isometry, 2
E
2
{xi,1−ti }i
∥ |ζX,t ⟩ ∥ = =
E
{xi,1−ti }i
X d
E
ΠX
X
|d⟩ |ϕt,d ⟩
d
{xi,1−ti }i
1ValidX (d)=1 ∥ |ϕt,d ⟩ ∥2
1X 1 ≤ ∥ |ϕt,d ⟩ ∥2 = . T T d
The second equality uses the orthogonality of the states |d⟩, and the inequality follows from E
{xi,1−ti }i
1ValidX (d)=1 =
1 1 . (1) T ∀i∈[log T ], di ̸=0
(6)
(1)
Indeed, if di = 0 for some i, both sides vanish. Otherwise, each verification check is a nonconstant affine equation in the independent uniform string xi,1−ti , and hence holds with probability exactly 1/2. There are log T independent checks, so their joint probability is 2− log T = 1/T . Averaging over the remaining client randomness and summing over t proves the claim. Lemma 3.3. Assuming quantum-secure one-way functions, for every QPT server there is a negligible function µ such that X E ⟨ζX,t | Mt,yt,0 ,yt,1 |ζX,t ⟩ ≤ 21−n + µ(λ). t∈{0,1}log T
X
13
Proof. Consider the following modified experiment: • Sample t∗ ∼ {0, 1}log T , then generate the client’s complete setup and classical table {ct,i }t,i as in Section 3.1, except that the client sends the state ! log E OT t∗i , xi,t∗i , ki,t∗i ⊗ ψyt∗ ,0 ,yt∗ ,1 i=1
to the server. • After the server sends d, the client always sends t∗ and {yt,0 , yt,1 }t̸=t∗ to the server. (1)
• The server replies with (y0∗ , y1∗ ). It wins if di
̸= 0 for all i ∈ [log T ] and
(y0∗ , y1∗ ) = (yt∗ ,0 , yt∗ ,1 ). We first show that the success probability in this modified experiment equals the sum in the statement. Fix t and condition on all client randomness except {xi,1−ti }i∈[log T ] . As in Lemma 3.2, write O X A |ti , xi,ti , ki,ti ⟩ ψyt,0 ,yt,1 |α⟩ = |d⟩ |ϕt,d ⟩ . d
i∈[log T ]
The states |ϕt,d ⟩, the isometry Vt , and the operator Mt,yt,0 ,yt,1 are fixed under this conditioning. Since Vt and Mt,yt,0 ,yt,1 act trivially on D and ⟨d′ |d⟩ = 0 for d′ ̸= d, all terms with different values of d vanish. Therefore, X ⟨ζX,t | Mt,yt,0 ,yt,1 |ζX,t ⟩ = 1ValidX (d)=1 · ⟨d| ⟨ϕt,d | Vt† Mt,yt,0 ,yt,1 Vt |d⟩ |ϕt,d ⟩ . d
Every quadratic form on the right is nonnegative and independent of the hidden strings. Applying Equation (6) therefore gives E
{xi,1−ti }i
⟨ζX,t | Mt,yt,0 ,yt,1 |ζX,t ⟩ =
1 T
⟨d| ⟨ϕt,d | Vt† Mt,yt,0 ,yt,1 Vt |d⟩ |ϕt,d ⟩ .
X (1)
d:∀i, di ̸=0
Averaging over the remaining randomness and summing over t yields X t
E ⟨ζX,t | Mt,yt,0 ,yt,1 |ζX,t ⟩ =
X
1X E T t X
X
⟨d| ⟨ϕt,d | Vt† Mt,yt,0 ,yt,1 Vt |d⟩ |ϕt,d ⟩ .
(1)
d:∀i, di ̸=0
The right-hand side is exactly the success probability of the modified experiment: the factor 1/T samples t∗ uniformly, the restriction on d enforces the nonzero checks, and the POVM element enforces the correct output. It remains to bound this probability. Fix a target t∗ ∈ {0, 1}log T and consider the following hybrids: • Hybrid 0: This is the modified experiment above, with target t∗ .
14
• Hybrid 1: Replace the entries {ct∗ ,i }i∈[log T ] by independent uniform strings. We make these replacements one at a time. For the ith replacement, the masking key ki,1−t∗i does not occur in the state sent to the server. A reduction uses the PRF challenge table for this key to construct the entire table, changing only its value at t∗ . It samples the other keys itself and simulates all remaining messages. Because the parity checks have been omitted, the simulation never needs the key ki,1−t∗i itself. Thus, Definition 2.3 makes each replacement computationally indistinguishable. • Hybrid 2: Replace (yt∗ ,0 , yt∗ ,1 ) = fk (t∗ ) by an independent uniform pair. The t∗ -th row of the classical table is now uniform and independent of this pair. A reduction can therefore use its PRF challenge table for the master key k to prepare the target claw and all remaining messages. Again, only the value at t∗ changes, so Definition 2.3 makes this hybrid computationally indistinguishable from Hybrid 1. Note that these simulations are efficient because the PRF domain has size T = poly(λ). In Hybrid 2, the target pair is uniform, and the server receives only its claw state together with data independent of that pair. Even after dropping the nonzero checks, its success probability is at most 21−n , by Lemma 2.2. The log T + 1 replacements change this probability by a negligible amount. Averaging over t∗ proves the statement; non-uniform security makes the negligible bound uniform over the polynomially many targets.
4
Sequential Repetition
In this section, we give a generic sequential repetition theorem for any quantum interactive search game. Definition 4.1 (Quantum interactive search game). A quantum interactive search game Γ is specified by a polynomial-size quantum interactive circuit family V = {Vλ }λ . At the end of an execution it outputs a classical string x ∈ {0, 1}m(λ) ∪ {⊥} in a designated classical register X. For any polynomial-size interactive strategy B with input register M and output register M′ , interaction with Vλ defines the map ExecΓ,λ [B] : M −→ M′ X.
(7)
Definition 4.2 (Success probability). A QPT adversary B = (|ψ⟩ , B, Bout ) against a quantum interactive search game Γ consists of a polynomial-size advice family {|ψλ ⟩}λ , a polynomial-size interactive strategy B, and a polynomial-size predictor circuit Bout that takes register M′ as input and produces a classical string y ∈ {0, 1}m(λ) in a designated classical register Y. The success probability pΓ,λ (B) of the adversary is defined as pΓ,λ (B) := Tr[Πwin (Bout ⊗ IX )ExecΓ,λ [B](|ψλ ⟩⟨ψλ |)] , where Πwin :=
X
|x⟩⟨x|X ⊗ |x⟩⟨x|Y .
x∈{0,1}m(λ)
The winning projector acts as the identity on unmentioned registers. 15
Definition 4.3 (Sequential success probability). Given a repetition parameter ℓ = ℓ(λ), a QPT adversary A = (|ψ⟩ , A1 , . . . , Aℓ , Aout ) against the ℓ-sequentially-repeated quantum interactive search game Γ has success probability pℓΓ,λ (A) defined as follows. Each copy uses fresh verifier randomness and workspace. • Set σ0 := |ψλ ⟩⟨ψλ | on register M0 . • For i ∈ [ℓ], set σi := ExecΓ,λ [Ai ]Mi−1 →Mi Xi ⊗ IX1 ,...,Xi−1 (σi−1 ). • pℓΓ,λ (A) := Tr Πℓwin (Aout ⊗ IX1 ,...,Xℓ )(σℓ ) , where Πℓwin :=
X
|x1 , . . . , xℓ ⟩⟨x1 , . . . , xℓ |X1 ,...,Xℓ ⊗ |x1 , . . . , xℓ ⟩⟨x1 , . . . , xℓ |Y1 ,...,Yℓ .
x1 ,...,xℓ ∈{0,1}m(λ)
Theorem 4.4. For any quantum interactive search game Γ, any polynomial ℓ = ℓ(λ) ≥ 1, and any ε(λ) ∈ [0, 1], if for all QPT adversaries B, pΓ,λ (B) ≤ ε(λ) + negl(λ), then for all QPT adversaries A against the ℓ-sequentially-repeated game, pℓΓ,λ (A) ≤ ε(λ)ℓ + negl(λ). The main quantum information tool that we use to prove Theorem 4.4 is the following uniform singular value amplification result from [GSLW19]. Lemma 4.5 ([GSLW19, Theorem 30 and the paragraph immediately following it]). Let U be a unitary and Πin , Πout be two projectors such that U, U † and coherent tests of the projectors are implementable by quantum circuits of size at most s. Let γ > 1, δ, ζ ∈ (0, 1/2), define K := Πout U Πin , and suppose that ∥K∥ ≤ 1−δ γ . Then there exists a unitary W , using one additional qubit C and implementable by a circuit of size at most poly(s, γ, 1/δ, log(1/ζ)), such that ∥ (⟨0|C ⊗ Πout ) W (|0⟩C ⊗ Πin ) − γK∥ < ζ. Next we give a direct corollary stated in a manner that will be convenient for our proof of Theorem 4.4. √ Corollary 4.6. Let U, Πin , Πout , K, δ, ζ be as above and suppose that c > 0 and ∥K∥ ≤ c < 1 − δ. Then there exists a unitary W implementable by a circuit of size at most poly(s, 1/c, 1/δ, log(1/ζ)) such that the following holds. Define L := (⟨0|C ⊗ Πout ) W (|0⟩C ⊗ Πin ) . For any register R, normalized state |ψ⟩ in the image of Πin ⊗ IR , and any projector Π, ∥Π(L ⊗ IR ) |ψ⟩ ∥2 ≥
(1 − δ)2 ∥Π(K ⊗ IR ) |ψ⟩ ∥2 − ζ. c
√ , ζ ′ = ζ/2, and apply Lemma 4.5 with parameters γ ′ , δ, ζ ′ to obtain L as defined Proof. Set γ ′ = 1−δ c
in the corollary statement such that ∥L − γ ′ K∥ < ζ2 . Let |ν⟩ := (L − γ ′ K) ⊗ IR |ψ⟩
16
and note that ∥ |ν⟩ ∥ < ζ/2. We have that ∥Π(L ⊗ IR ) |ψ⟩ ∥2 = ∥γ ′ Π(K ⊗ IR ) |ψ⟩ + Π |ν⟩ ∥2 = ∥γ ′ Π(K ⊗ IR ) |ψ⟩ ∥2 + 2γ ′ Re ⟨ψ| (K † ⊗ IR )Π |ν⟩ + ∥Π |ν⟩ ∥2 ≥ ∥γ ′ Π(K ⊗ IR ) |ψ⟩ ∥2 − 2∥γ ′ Π(K ⊗ IR ) |ψ⟩ ∥∥Π |ν⟩ ∥ >
(1 − δ)2 ∥Π(K ⊗ IR ) |ψ⟩ ∥2 − ζ. c
Here the last step uses ∥γ ′ K∥ ≤ 1 − δ < 1 and ∥Π |ν⟩ ∥ < ζ/2. Finally, we prove Theorem 4.4. Proof. (of Theorem 4.4) Fix a search game Γ, polynomial ℓ = ℓ(λ), ε = ε(λ) and any adversary A = (|ψ⟩ , A1 , . . . , Aℓ , Aout ). For j ∈ [ℓ], define qj as follows. Start immediately before copy j and initialize Aj with an arbitrary state. Run Aj through Aℓ interacting with V , run Aout to produce guesses yj , . . . , yℓ , and accept if yj = xj , . . . , yℓ = xℓ . Then qj is the maximum over all initial states of the probability of accepting. Define qℓ+1 = 1, and note that pℓΓ,λ (A) ≤ q1 ≤ q2 ≤ · · · ≤ qℓ+1 . The theorem follows if maxj∈[ℓ] (qj − εqj+1 )+ is negligible, where (u)+ := max{u, 0}: iterating this uniform recurrence gives q1 ≤ εℓ + ℓ · negl(λ). Towards contradiction, suppose that there exist a polynomial r(λ) ≥ 1, an infinite set of security parameters, and an index j = j(λ) ∈ [ℓ] such that, on this infinite set, qj > εqj+1 + η, where η := 1/r(λ). Include j in the non-uniform advice. Note that qj+1 ≥ qj ≥ η, and consider the following two cases. First suppose that qj+1 ≥ 1 − η/16. Define an adversary B = (|ϕ⟩ , B, Bout ) against the j’th sequential game as follows. Let |ϕ⟩ be a pure state that attains qj , B = Aj , and Bout run the remainder of Aj+1 , . . . , Aℓ , Aout while internally simulating V in each game, and outputting the value yj output by Aout . Then the probability that yj = xj is at least εqj+1 + η ≥ ε −
εη 15η +η ≥ε+ , 16 16
a contradiction. Next suppose that qj+1 < 1−η/16. Let U be a purification, retaining all measurement outcomes and discarded registers, of the procedure that runs Aj+1 , . . . , Aℓ , Aout while internally simulating V in each game. Let M be the register passed to Aj+1 and Z be the auxiliary register needed to define the purification U , initialized to |0⟩Z . Define Πin = IM ⊗ |0⟩⟨0|Z and define Πout to be the projector applied to the output of U that checks that yi = xi for all i ∈ {j + 1, . . . , ℓ}. Then defining K = Πout U Πin , we have that ∥K∥2 = qj+1 . The circuits for U, U † and coherent tests of both projectors have polynomial size. Set b = ⌈log2 (32/η)⌉ and c = 2−b ⌈2b qj+1 ⌉, included in the non-uniform advice, so that qj+1 ≤ c ≤ qj+1 + η/32 < 1, and apply Corollary 4.6 with δ, ζ = η/128. Note that the hypothesis holds since c < 1 − η/32 < (1 − η/128)2 = (1 − δ)2 . Since c ≥ η, we obtain a polynomial-size circuit W which we will use to define an adversary B = (|ϕ⟩ , B, Bout ) as follows. Let |ϕ⟩ be a pure state that attains qj and B = Aj . Let Bout prepare |0⟩Z and an additional single-qubit register |0⟩C , run W ,
17
and attempt to project the output onto |0⟩⟨0|C ⊗ Πout . If successful it measures and outputs yj . Otherwise, it outputs an arbitrary string. Let |ϕ′ ⟩M,Z,Xj ,E be a purification of the output of B interacting with V , tensored with |0⟩Z , where Xj holds V ’s output and E purifies the interaction. Then Bout acts on M, Z, C and we take R = Xj E to be the register that it does not touch. Let Π be the projector checking that xj = yj and let L be as defined in the statement of Corollary 4.6. Then the probability that B succeeds is at least Π(L ⊗ IR ) ϕ′
2
(1 − δ)2 2 −ζ Π(K ⊗ IR ) ϕ′ c qj qj = (1 − ζ)2 − ζ ≥ − 3ζ c c εqj+1 + η η − ε(c − qj+1 ) ≥ − 3ζ = ε + − 3ζ c c η − η/32 31η ≥ε+ − 3ζ ≥ ε + − 3ζ c 32 121η , =ε+ 128
≥
a contradiction.
5
Succinct Arguments for QMA
Let T = T (λ) be a polynomial in the security parameter and a power of 2, and identify [T ] with {0, 1}log T using its canonical encoding. Consider the following protocol between a client and a (possibly malicious) server. (i) Run λ independent copies of the protocol in Section 3.1 in sequence. Denote the output state held by the (honest) server in the i-th copy by O ψy(i) ,y(i) t∈{0,1}log T
t,0
t,1
up to an irrelevant global phase. (ii) After the completion of all the protocols, the client samples independent uniform permutations πi ∼ ST and sends them to the server. (iii) For every t ∈ {0, 1}log T , the server takes the states indexed by πi (t). For each i ∈ {2, . . . , λ}, it applies a CNOT from the first leading qubit to the i-th leading qubit, measures the latter in the computational basis, and records the outcome ei,t ∈ {0, 1}. After discarding the measured leading qubits, the remaining state is ψYt,0 ,Yt,1 , where (1)
(2)
(1)
(2)
(λ)
Yt,0 := yπ1 (t),0 ∥yπ2 (t),e2,t ∥ · · · ∥yπλ (t),eλ,t , (λ)
Yt,1 := yπ1 (t),1 ∥yπ2 (t),1⊕e2,t ∥ · · · ∥yπλ (t),1⊕eλ,t . The server sends the outcomes {ei,t }i,t to the client.
18
(8)
(iv) The client aborts if the verification in any of the copies fails and otherwise it locally computes {Yt,0 , Yt,1 }t as specified above. Clearly the only quantum communication between the client and the server is the one happening in the protocol from Section 3.1. Therefore, quantum states are only sent from the client to the server. Moreover, before any message is exchanged, the client can sample the classical description of a circuit Ci of size poly(log T, λ) = poly(λ) and compute Ci |0⟩Q |0⟩W = |ψi ⟩Q |0⟩W where |ψi ⟩ is the state sent from the client to the server in the i-th quantum communication round. In particular, the state sent in the i-th round is independent of the protocol transcript (but might depend on the client’s internal randomness). We refer to an interactive protocol that satisfies such properties as being quantum-succinct and history-independent. Definition 5.1 (Quantum-Succinctness and History-Independence). A protocol with public input x is quantum-succinct and history-independent if the client: (i) samples a uniform classical seed s of fixed poly(λ) length before interaction; (ii) computes from (s, x), in time |x| poly(λ), descriptions of circuits Ci of fixed total size poly(λ), each preparing a message in fresh registers Ci |0⟩Qi |0⟩Wi = |ψi ⟩Qi |0⟩Wi , sends Qi at a publicly pre-determined round, and discards Wi ; and (iii) is otherwise classical, with messages and acceptance determined by s, x, any private classical input, and the classical transcript. The protocol above satisfies this definition: Its preparation circuits use only the short sampled key and string lists and efficient PRF evaluation. These lists may be sampled directly, with only the remaining classical coins expanded from a PRG seed. Replacing those coins by PRG output changes QPT views only negligibly; the proofs below use uniform coins. Moreover, we say that a protocol is a claw-state correlation protocol if it satisfies Lemma 5.2 and Lemma 5.3, which we prove in the following. Lemma 5.2. When both parties are honest, except with negligible probability, at the end of the protocol execution the server holds the state O ψYt,0 ,Yt,1 t∈{0,1}log T
and the client holds {Yt,0 , Yt,1 }t∈{0,1}log T . Proof. Fix t. By correctness of the weak protocol, before gluing the server holds the tensor product of the λ claws indexed by πi (t). After the CNOTs this state is 2
−λ/2
X
|b1 , b1 ⊕ b2 , . . . , b1 ⊕ bλ ⟩
λ O
(i) yπi (t),bi
E
.
i=1
b1 ,...,bλ ∈{0,1}
Measuring the last λ − 1 leading qubits fixes bi = b1 ⊕ ei,t for i ≥ 2, leaving two equally weighted terms. After normalization and discarding the measured qubits, the remaining state is therefore |0, Yt,0 ⟩ + |1, Yt,1 ⟩ √ = ψYt,0 ,Yt,1 , 2 19
with strings given by Equation (8). The gluing operations act separately for each t, so the resulting states form the claimed tensor product, and the communicated measurement outcomes let the client compute the same strings. Finally, each weak copy rejects an honest server with probability at most (log T )2−n . By a union bound over the λ copies, the abort probability is at most λ(log T )2−n = negl(λ). The following lemma establishes the security of the protocol. Lemma 5.3. For every non-uniform QPT server and every t∗ ∈ {0, 1}log T , consider the experiment that runs the protocol, gives the server {Yt,0 , Yt,1 }t̸=t∗ after the client produces its output, and asks it to return (Yt∗ ,0 , Yt∗ ,1 ). Assuming the existence of quantum-secure one-way functions, the probability that the client does not abort and the server returns the correct pair is negligible. Proof. Fix any t∗ = t∗ (λ) ∈ {0, 1}log T . We reduce recovery of its pair of strings to winning λ sequential copies of the search game in Theorem 3.1. The private output of each game is its target pair if the check passes, and ⊥ otherwise. The reduction forwards each weak-protocol interaction to the server, but stores the disclosed target index ui and strings for the other claws without revealing them. After all copies have finished, the reduction samples independent permutations uniformly subject to πi (t∗ ) = ui and sends them to the server. Since the ui are independent uniform indices and were withheld during the weak interactions, this has exactly the joint distribution of the original protocol. Once the server sends its gluing bits, the stored strings determine every combined pair at t ̸= t∗ , so the reduction can supply all the required leakage. A correct guess of (Yt∗ ,0 , Yt∗ ,1 ) gives every raw target pair by splitting the strings into blocks and undoing the swaps specified in Equation (8). Failed checks can be followed by dummy continuations, since those branches cannot win. Thus Theorems 3.1 and 4.4 give Pr[no abort and a correct target pair] ≤ 4−λ + negl(λ) = negl(λ). Non-uniformity makes this bound uniform over target sequences. A union bound over the polynomially many targets also gives hardness of recovering any pair without being given the other strings.
5.1
Blind Delegation
We recall the definition of a blind delegation protocol. Definition 5.4 (Blind Delegation). A blind delegation protocol for a public quantum circuit, viewed as a map Q : XB → O, takes a private classical input x from the client and a quantum input on B from the server. In an honest execution, the client obtains one-time-pad keys (r, s). For every input state ρBR with arbitrary reference R, let σOR be the server’s output and reference after applying Zs Xr on O whenever the client does not abort, averaged over all randomness and measurement outcomes. Represent abort by an orthogonal flag in O, and embed the ideal output in the non-abort subspace. Correctness requires 1 σOR − (Q ⊗ IR ) |x⟩⟨x|X ⊗ ρBR 1 ≤ negl(λ). 2 For every QPT server A, every ρBR , and all equal-length inputs x0 , x1 , blindness requires ViewA (ρBR , x0 ) ≈c ViewA (ρBR , x1 ), 20
where the view includes the server’s entire output, R, and the abort flag, with the same public circuit Q in both experiments. The factor IR leaves the reference untouched. Using the protocol defined above and a result from [BK25], we can establish the existence of a quantum-succinct and history-independent blind delegation protocol. Lemma 5.5. Assuming the existence of quantum-secure one-way functions, for any polynomialsize quantum circuit Q, there exists a quantum-succinct and history-independent (Definition 5.1) blind delegation protocol for Q. Moreover, its round complexity is bounded by poly(λ, δ), where δ is the T-depth of Q. Proof. Use a Clifford+T realization of Q, including any negligible approximation error in correctness. Let T = poly(λ) be a power-of-two upper bound on its number of T gates and let Πclaw be a quantum-succinct and history-independent claw-state correlation protocol with T output claw states and round complexity poly(λ), i.e. it satisfies Definition 5.1, Lemma 5.2, and Lemma 5.3. Above we showed that Πclaw exists assuming quantum-secure one-way functions. Unused correlations may be discarded; if there are no T gates, omit this setup. We will use Πclaw to construct a blind delegation protocol Πblind for Q by applying two transformations from [BK25]: (1) BB84 correlations from claw-state correlations, and (2) blind delegation from BB84 correlations. First, we specify the definition of a BB84 correlation protocol ΠBB84 . Let T = poly(λ) be the number of output correlations. • Correctness: When both parties are honest, except with negligible probability, at the end of the protocol execution the server holds the state O Hθi |xi ⟩ , i∈[T ]
and the client holds {θi , xi }i∈[T ] . • Security: For every non-uniform QPT server and every i∗ = i∗ (λ) ∈ [T ], let ok denote that the client does not abort. On this branch give the server {θj , xj }j̸=i∗ and let θbi∗ be its guess. We require h i Pr ok ∧ θbi∗ = θi∗ − 12 Pr[ok] ≤ negl(λ). (9) The view includes the abort flag and the server’s full workspace. On abort the verifier samples the basis bits θi independently and uniformly at random. For the first transformation, [BK25, Theorem 4.7] converts a claw-state generator into an oblivious state preparation (OSP) protocol. Apply this conversion in parallel to each of our T claws. To meet its requirement that the two strings be distinct, set Li,b := b∥Yi,b and have the server copy its leading qubit into a fresh data qubit, obtaining √12 (|0, Li,0 ⟩ + |1, Li,1 ⟩). Recovering both strings recovers the original pair. For security of coordinate i, the reduction receives the other pairs of strings, simulates the other conversion clients, and computes their BB84 labels. The Goldreich– Levin reduction in that theorem then applies jointly with this leakage and the server’s workspace: a noticeable advantage in the unconditional bound above gives a noticeable probability of recovering the target pair without abort, contradicting Lemma 5.3. Correctness follows from the cited conversion and Lemma 5.2. The transformation adds only classical communication and polynomially many rounds, so the resulting ΠBB84 remains quantum-succinct and history-independent. 21
Generate this entire batch before sending any message depending on the client’s input. For the second transformation, [BK25, Lemma 6.10 and Theorem 6.11] gives a protocol for blind delegation from any OSP. The BK25 protocol runs one OSP for each T-gate, and here we will use the i-th OSP correlation Hθi |xi ⟩ , (θi , xi ) in place of the OSP protocol for the i-th T-gate. In [BK25], the protocol for the i-th T-gate requires the client to input a chosen basis θi′ , while our OSP correlation yields a basis θi that is not controlled by the client. To remedy this, we simply have the client first send the bit bi = θi ⊕ θi′ to the server, who applies Hbi to its state. After this, correctness follows directly from the arguments in [BK25]. Further, note that the security of the OSP correlation protocol implies that the server’s view on client input θ′ = 0 and θ′ = 1 are indistinguishable even given {θj , xj }j̸=i . For blindness, switch the chosen bases to 0 in reverse gate order, as in [BK25, Theorem 6.11]. At gate k, the reduction knows all labels except (θk , xk ): the earlier labels and transcript determine θk′ , while all later chosen bases have already been replaced by 0. The BB84 guarantee makes θk indistinguishable from a fresh uniform bit jointly with the known labels and the server’s state, so sending θk ⊕ θk′ or θk gives indistinguishable views. Subsequent visible messages use only known labels; the unknown xk affects only private key updates. After polynomially many switches, the only input-dependent message is protected by the initial classical one-time pad, giving statistical blindness. Finally, as also observed in [BLM26], the client and server can participate in all OSPs for a given layer of T-gates in parallel, with that layer’s chosen bases fixed before its messages are sent. Thus, the round complexity of the blind delegation protocol is bounded by poly(λ, δ). Moreover, since this transformation requires only classical communication, the blind delegation protocol remains quantum-succinct and history-independent.
5.2
Putting Things Together
In [BLM26, Theorem 54] it is shown that a blind delegation protocol implies an argument for QMA. Lemma 5.6. Assuming a blind delegation protocol with round complexity poly(λ, δ) with δ the Tdepth of the computed quantum circuit, there is an argument for QMA with completeness 1−negl(λ), soundness at most a constant s < 1, and a fixed poly(λ) number of rounds. Moreover, if the blind delegation protocol satisfies Definition 5.1, then so does the resulting interactive argument. The moreover part of the above statement is not explicitly stated in [BLM26], but it is implicit in their proof because the protocol uses the blind delegation (see also [BLM26, Theorem 40]) as a black-box and everything else is classical communication. Next, we invoke the communication compression compiler from [BLM26]. Lemma 5.7. Let Π be an r(λ)-round interactive protocol satisfying Definition 5.1, with no private client input besides s, where r is bounded by a fixed polynomial and the public input x specifies the classical next-message and decision algorithms with description size O(|x|). Assuming collapsing hash functions, for every ε = 1/poly(λ) there is a compiled protocol Π̃ with negligible honestcompleteness loss such that, for every QPT compiled prover P̃ ∗ , there is a QPT original prover P ∗
22
with
i h ∗ i h ∗ Pr Ṽ P̃ accepts ≤ Pr V P accepts + O(ε) + negl(λ).
Its communication is at most r(λ) poly(λ, 1/ε) and its verifier time is at most |x|r(λ) poly(λ, 1/ε). Proof. [BLM26, Theorem 18] states the same theorem for a protocol with a completely classical verifier, but we argue that the same holds for any interactive protocol satisfying Definition 5.1. First, recall that we can assume without loss of generality that the verifier’s classical computation is deterministic once it samples a random seed s ∼ {0, 1}poly(λ) prior to any interaction. Keep the short randomness for quantum preparation explicitly in s and derive the remaining classical coins using a quantum-secure PRG. Note that by history-independence (Definition 5.1), this also means that the quantum states sent by the verifier are fully determined prior to any interaction. Let us now recall the compilation procedure for a classical verifier from [BLM26]. For any round of interaction: • The prover computes locally its next message of the protocol and sends a succinct commitment to it, together with a state-preserving succinct argument of knowledge for its pre-image. • The prover and the verifier engage in a chosen-input committed secure function sampling (SFS) protocol, where the verifier’s input is s and the prover’s inputs are the committed messages. At the end of the interaction, the prover receives the value of the verifier’s nextmessage function. At the end of the interaction, the verifier reveals s, and the prover supplies a succinct argument of knowledge proving that the committed messages form an accepting transcript. The verifier also sends the original quantum states at their prescribed positions. For soundness, keep s and all external registers as an untouched reference. Following [BLM26, Definitions 11 and 19, Lemma 20, and Section 5.4], extract each committed message using the state-preserving extractor and simulate the corresponding chosen-input SFS from the next-message value on the extracted transcript. These guarantees preserve the joint state up to the prescribed distinguishing error, including correlations between the prover’s quantum registers and s; the chosen-input transformation uses fresh garbling randomness. At quantum-message positions, the reduction forwards the original verifier’s register once, without knowing s or cloning the state. Choose the inversepolynomial per-call accuracies so that all extraction and simulation errors sum to O(ε); the fixed polynomial bound on r absorbs the resulting overhead. After the last commitment, extract the final accepting-transcript witness. Collision resistance forces its messages to equal those already extracted, except with negligible probability. Hence compiled acceptance implies that the original verifier’s classical predicate accepts the extracted transcript, up to the stated errors. The final seed reveal and proof cannot change those fixed messages and can be omitted for this upper bound. Thus an original prover forwards the extracted classical messages, uses the verifier’s classical replies as SFS-simulator inputs, and forwards its quantum replies as above. Honest correctness of the subprotocols separately gives negligible completeness loss. Their efficiency and Definition 5.1 give the claimed bounds. Combining Lemmas 5.3 and 5.5 to 5.7, along with the fact that collapsing hashes imply the existence of one-way functions, we obtain a succinct argument for QMA with constant soundness. Sequential repetition of Theorem 5.8 yields our main result Theorem 1.1.
23
Theorem 5.8. Assuming collapsing hash functions, there exists a constant 0 < s < 1 and a succinct argument for QMA with completeness 1 − negl(λ), soundness error s, total communication bounded by poly(λ), and verifier runtime |x| · poly(λ). Proof. Let s0 < 1 be the soundness in Lemma 5.6. Choose the compilation accuracy so that Lemma 5.7 gives soundness at most s = (1 + s0 )/2 < 1 for sufficiently large λ, while honest completeness remains 1 − negl(λ). The fixed round bound gives the claimed communication and verifier time. For Theorem 1.1, repeat sequentially λ times with fresh verifier randomness, accepting only if every copy accepts, and give the honest prover fresh witness copies. Completeness loss is still negligible by a union bound. Apply Theorem 4.4 to the search game whose private target is 0 on acceptance and ⊥ otherwise, soundness is at most sλ + negl(λ).
Acknowledgments JB is supported by the Air Force Office of Scientific Research under agreement number FA9550261B239. GM is supported by the European Research Council through an ERC Starting Grant (Grant agreement No. 101077455, ObfusQation) and by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy - EXC 2092 CASA – 390781972.
References [ALM+ 98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501–555, 1998. https://doi.org/10.1145/278298.278306. 2 [AS98]
Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70–122, 1998. https://doi.org/10.1145/273865. 273901. 2
[BK25]
James Bartusek and Dakshita Khurana. On the power of oblivious state preparation. In Advances in Cryptology—CRYPTO 2025, volume 16001 of Lecture Notes in Computer Science, pages 575–607. Springer, 2025. Full version: https://arxiv.org/abs/2411. 04234v1. 2, 4, 7, 21, 22
[BKM+ 25] Kaniuar Bacho, Alexander Kulpe, Giulio Malavolta, Simon Schmidt, and Michael Walter. Compiled nonlocal games from any trapdoor claw-free function. In Advances in Cryptology—CRYPTO 2025, volume 16001 of Lecture Notes in Computer Science, pages 642–673. Springer, 2025. https://eprint.iacr.org/2024/1829. 4 [BLM26]
James Bartusek, Jiahui Liu, and Giulio Malavolta. A modular approach to succinct arguments for QMA. In Advances in Cryptology—EUROCRYPT 2026, volume 16547 of Lecture Notes in Computer Science, pages 446–474. Springer, 2026. Full version: https://arxiv.org/abs/2606.10408v1. 2, 3, 4, 7, 8, 22, 23
[BMM26]
Pedro Branco, Giulio Malavolta, and Zayd Maradni. Fully-homomorphic encryption from lattice isomorphism. In Theory of Cryptography—TCC 2025, volume 16268 of Lecture Notes in Computer Science, pages 220–252. Springer, 2026. First published online in December 2025. https://eprint.iacr.org/2025/993. 2
24
[BTL+ 22] James Bartusek, Yael Tauman Kalai, Alex Lombardi, Fermi Ma, Giulio Malavolta, Vinod Vaikuntanathan, Thomas Vidick, and Lisa Yang. Succinct classical verification of quantum computation. In Advances in Cryptology—CRYPTO 2022, volume 13508 of Lecture Notes in Computer Science, pages 195–211. Springer, 2022. https://arxiv. org/abs/2206.14929. 2, 8 [CH26]
Alessandro Chiesa and Zihan Hu. Succinct arguments for QMA in the quantum random oracle model. Cryptology ePrint Archive, Paper 2026/2099, 2026. 7
[CMSZ22] Alessandro Chiesa, Fermi Ma, Nicholas Spooner, and Mark Zhandry. Post-quantum succinct arguments: Breaking the quantum rewinding barrier. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 49–58. IEEE, 2022. https://arxiv.org/abs/2103.08140. 2 [GJMZ23] Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry. Commitments to quantum states. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pages 1579–1588. ACM, 2023. https://arxiv.org/abs/2210.05138. 3 [GSLW19] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 193–204. ACM, 2019. Full version: https: //arxiv.org/abs/1806.01838v1. 7, 16 [GTNV25] Sam Gunn, Yael Tauman Kalai, Anand Natarajan, and Ági Villányi. Classical commitments to quantum states. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 234–244. ACM, 2025. https://arxiv.org/abs/2404.14438. 2, 3 [Kil92]
Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC), pages 723–732. ACM, 1992. https://doi.org/10.1145/129712.129782. 2
[KLVY23] Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. Quantum advantage from any non-local game. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pages 1617–1628. ACM, 2023. https://arxiv.org/abs/ 2203.15877. 4 [MNZ24]
Tony Metger, Anand Natarajan, and Tina Zhang. Succinct arguments for QMA from standard assumptions via compiled nonlocal games. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1193–1201. IEEE, 2024. https://arxiv.org/abs/2404.19754. 2, 3, 4
[NZ23]
Anand Natarajan and Tina Zhang. Bounding the quantum value of compiled nonlocal games: From CHSH to BQP verification. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1342–1348. IEEE, 2023. https:// arxiv.org/abs/2303.01545v2. 4
[SV26]
Baocheng Sun and Thomas Vidick. Probabilistically Checking Quantum Proofs, with Interaction. In Dana Moshkovitz, editor, 41st Computational Complexity Conference (CCC 2026), volume 383 of Leibniz International Proceedings in Informatics (LIPIcs), 25
pages 4:1–4:49, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 7 [Unr16]
Dominique Unruh. Computationally binding quantum commitments. In Advances in Cryptology—EUROCRYPT 2016, volume 9666 of Lecture Notes in Computer Science, pages 497–527. Springer, 2016. https://eprint.iacr.org/2015/361. 2, 8
[Zha12]
Mark Zhandry. How to construct quantum random functions. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 679–687. IEEE, 2012. https://eprint.iacr.org/2012/182. 10
[Zha21]
Jiayu Zhang. Succinct blind quantum computation using a random oracle. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1370–1383. ACM, 2021. https://arxiv.org/abs/2004.12621. 3, 5, 6
26