arXiv CSopen access

Succinct Arguments for QMA in the Quantum Random Oracle Model

arXiv:2609.37429v1 [quant-ph] 29 Sep 2026

Succinct Arguments for QMA in the Quantum Random Oracle Model Alessandro Chiesa

Zihan Hu

[email protected] EPFL

[email protected] EPFL

September 30, 2026

Abstract Succinct arguments are a fundamental cryptographic primitive for verifying computational claims with small communication. In the classical setting, succinct arguments for NP can be constructed from unstructured hardness alone (e.g., hash functions) by compiling probabilistically checkable proofs (PCPs) or interactive oracle proofs (IOPs) for NP via the commit-and-open paradigm. In contrast, known succinct arguments for QMA rely on “structured” cryptographic primitives, or on the quantum PCP conjecture. We construct the first succinct argument for QMA in the quantum random oracle model (QROM) without relying on additional cryptographic assumptions or unproven conjectures. This yields succinct arguments for QMA from unstructured hardness alone, showing that ideal hash functions not only suffice for succinct arguments for NP but also for QMA. Underlying our result is an efficiency-preserving transformation that compiles quantum interactive oracle proofs (QIOPs), a recently introduced interactive generalization of quantum PCPs, into quantum arguments for the same language, via a natural quantum commit-and-open paradigm. Our transformation applies to every QIOP with public-query soundness, a notion that we formalize to capture a natural requirement of the commit-and-open paradigm and is satisfied by a known QIOP for QMA. As a key ingredient in our transformation, we formalize and construct extractable vector commitments for quantum states with local openings in the QROM, which may be of independent interest. Keywords: succinct arguments for QMA; quantum random oracle model; quantum interactive oracle proofs

Contents 1

Introduction 1.1 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 4

2

Preliminaries 2.1 Quantum states, operators, and circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Oracle circuits and oracle algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Compressed oracles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Relations and languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Quantum interactive arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 6 7 8 11 11

3

Quantum interactive oracle proofs 3.1 Review: quantum interactive proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Our notion of QIOPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Public-query QIOPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13 13 14 17

4

Defining extractable quantum state commitments 4.1 A canonical quantum state commitment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 The extractability definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19 19 20

5

Construction of extractable commitments to quantum states 5.1 An extractable basic succinct commitment scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Extractor for the commitment scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Analysis of the commitment scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Proof of Theorem 5.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Proof of Theorem 5.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22 22 22 24 26 34

6

Defining extractable quantum state vector commitments 6.1 Syntax for quantum state vector commitments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 The extractability definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38 38 39

7

Construction of extractable quantum state vector commitments 7.1 Labeling the Merkle tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 An extractable quantum state vector commitment scheme . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Extractor for the vector commitment scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Security analysis of the vector commitment scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5 Proof of Theorem 7.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41 41 41 43 44 47

8

Quantum interactive arguments based on QIOPs 8.1 Our transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 The malicious QIOP prover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Proof of Theorem 8.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54 54 56 56

A The QIOP that we use

61

Acknowledgments

62

AI disclosure

62

References

62

1

Introduction

Succinct arguments enable a verifier to check a computational claim using communication substantially smaller than the cost of checking the claim directly. A remarkable feature of the classical theory is that such arguments do not require public-key cryptography or other highly structured assumptions: suitable hash functions suffice. Indeed, the commit-and-open paradigm compiles probabilistically checkable proofs and interactive oracle proofs for NP into succinct arguments using hash-based vector commitments [Kil92; Mic00; BG08; BCS16; CDGS23]. This paradigm is also known to remain secure against quantum adversaries under unstructured post-quantum assumptions [CMS19; CMSZ21; CDDGS25]. These results naturally raise the question of whether succinct arguments based solely on unstructured hardness can be extended from NP to its quantum analogue, QMA, which involves a quantum witness and can be verified in quantum polynomial time. In particular, [BLM26] poses the following question: Are there succinct arguments for QMA based on hash functions, or any unstructured hardness? A line of work [Bar+22; MNZ24; GKNV25; BLM26] constructs succinct arguments for QMA, even with a classical verifier. However, these constructions rely on structured hardness assumptions (see Section 1.2). A different approach, more closely aligned with our goal of succinct arguments for QMA from unstructured hardness, is to extend the classical commit-and-open paradigm to the fully quantum setting [CM24; GJMZ23]. In particular, [GJMZ23] proposes a quantum analogue of Kilian’s protocol [Kil92] that compiles a quantum probabilistically checkable proof (QPCP) into a quantum interactive argument while preserving the efficiency of the QPCP. Crucially, [GJMZ23] requires only unstructured hardness: any collapsing hash function, or more generally any succinct quantum state commitment (see Section 1.2 for more details). However, obtaining a succinct argument for QMA via their transformation requires a QPCP for QMA with polynomial length and small query complexity, whose existence is a weak form of the QPCP conjecture [AALV09; AAV13] and remains a major open problem in quantum complexity theory. In sum, succinct arguments for QMA have not matched their classical counterparts in terms of assumptions. Known constructions rely on structured cryptographic hardness, or on an unresolved complexity conjecture.

1.1

Our results

We construct the first succinct argument for QMA in the quantum random oracle model (QROM) [BDFLSZ11], without relying on additional cryptographic assumptions or unsolved conjectures. Theorem 1. In the QROM, there exists a succinct quantum interactive argument for QMA with communication complexity poly(λ, log ν) for instance size ν and security parameter λ. Here all parties, including malicious ones, have quantum query access to a uniformly sampled random oracle with output length λ. Thus, our result establishes the feasibility of succinct arguments for QMA from an idealized form of unstructured hardness, without additional cryptographic assumptions; this answers the aforementioned open question of [BLM26] in the oracle model. Establishing an analogous result in the plain model (from collapsing hash functions) is done in independent and concurrent work.1 1 [BM26] constructs succinct arguments for QMA from (a non-black-box use of) collapsing hash functions in the standard model, via quantum-succinct blind delegation and the communication-compression compiler of [BLM26]. Our approach is different: we give a quantum commit-and-open compiler for QIOPs and construct the extractable quantum-state vector commitments to instantiate it in the QROM. The two works independently resolve the feasibility question through different techniques and in different models.

1

We obtain this result from a general transformation, which is our main technical contribution: a quantum analogue of the classical hash-based commit-and-open transformation. We compile any public-query quantum interactive oracle proof (QIOP) into a quantum interactive argument in the QROM while essentially preserving its efficiency. Instantiating the compiler with the recent QIOP for QMA in [SV26] yields Theorem 1. Publicquery soundness is inherent to this commit-and-open approach because the prover must learn the queried locations in order to open them; we formulate the appropriate quantum analogue further below. Theorem 2 (Theorem 8.1, informal). There exists a transformation T satisfying the following. Let QIOP be a QIOP for a relation R, with round complexity k, proof length l, query complexity q, and verifier-to-prover communication complexity vc. Then QARG := T[QIOP] is a quantum interactive argument for R in the QROM with communication complexity O(λk + λq log l + vc). If QIOP has public-query soundness error spq , then QARG has soundness error O(spq + k · poly(t, l, q) · 2−λ ) against t-query quantum adversaries. Extending the commit-and-open paradigm to an appropriate notion of QIOP requires overcoming delicate definitional and technical challenges. In particular, we introduce a suitable notion of quantum-state vector commitment (QSVC) with a strong extraction property, and prove that a natural quantum-state tree commitment (QSTC) in the QROM satisfies it. Below we elaborate on these challenges and results. Flavor of QIOP. Quantum interactive oracle proofs (QIOPs) [SV25] extend quantum probabilistically checkable proofs (QPCPs) to the interactive setting, just as classical IOPs extend PCPs [BCS16; RRR16]. Several recent works consider different, sometimes incomparable, models of QIOPs [SV25; SV26; CGMV26]. We formulate our compiler for a QIOP model that simultaneously supports the relevant features appearing across these constructions: superposition queries, the return of previously submitted quantum proof states, and adaptive queries made before those states are returned. This formulation also identifies expressive QIOP features supported by our QROM compiler, thereby providing a flexible target model for future QIOP constructions. See Section 3.2 for details. • Superposition queries. We equip the QIOP verifier with superposition query access to the quantum proof oracles [CGMV26]. Informally, the verifier can specify query sets in superposition in a quantum register and coherently swap the corresponding locations of the quantum proof oracle to designated registers held by the verifier. Superposition query access generalizes the “point access” used in the definition of QPCPs and some QIOP constructions [SV25; SV26]. • Returning proof oracles. The verifier may return quantum proof oracles from earlier rounds to the prover after querying them, and the size of the returned registers is not charged to its query complexity or verifier-to-prover communication. This feature plays a key role in known QIOPs [SV25; SV26; CGMV26]. In contrast to a classical prover, a quantum prover cannot generally retain a copy of a transmitted proof state. The verifier may therefore need to return a previously submitted proof oracle for use by the prover in later rounds. • Adaptive queries and delayed returns. We allow the verifier to retain quantum proof oracles across multiple rounds and make adaptive superposition queries to them in later rounds until they are returned to the prover. Delayed returns are used in the QIOP in [SV26] (but not, e.g., the QIOP in [CGMV26]). Each feature creates an obstacle for commit-and-open compilation, addressed via the QSVC interface below. Public-query soundness. The commit-and-open paradigm in the classical setting does not apply to every IOP: the argument prover learns the verifier’s query locations to open the corresponding proof locations, so the IOP must satisfy public-query soundness. That is, soundness must hold even when the verifier’s queries are leaked to the malicious prover whenever they occur [CDGS23]. We need an appropriate quantum

2

formulation because the query locations may be in superposition and therefore cannot, in general, be revealed by measurement without disturbing the verifier’s computation. We introduce a definition of public-query soundness for QIOPs, where soundness holds even when the malicious prover has access to the query location register immediately before and after each superposition query. That is, immediately before the query, the location registers are transferred to the malicious prover, who may act jointly on them and its private state before returning them. The same interaction occurs immediately after the query. Public-query soundness requires the original soundness guarantee to continue to hold even with this additional interface. This notion extends classical public-query soundness [CDGS23], and is satisfied by the efficient QIOP in [SV26] (see more in Section A). See Theorem 3.4 for the formal definition. Quantum-state vector commitment schemes. At a minimum, achieving succinctness in the compiled protocol requires a commitment scheme that produces a short commitment to a long quantum state and provides efficient openings of a few locations. In the classical setting, succinct commitment schemes with such local openings are known as vector commitments, whose standard commitment, opening, and verification procedures suffice for the commit-and-open paradigm [BCS16; CDGS23; CDDGS25]. In the quantum setting, this standard vector-commitment interface does not suffice when query locations may be in superposition, even when formulated for quantum messages. • In a Merkle opening, the prover selects authentication-path registers according to query locations. If those locations are in superposition, the registers retained by the prover become entangled with the verifier’s location register. Unless this which-path information is coherently erased, the location register is dephased, and even an honest execution of the compiled protocol may not reproduce the QIOP verifier’s computation. • A distinct problem arises when the QIOP verifier returns a previously submitted proof oracle. The compiled verifier holds only a succinct commitment to that state, so the commitment scheme must allow the prover to recover the updated underlying state after the verifier has queried it. Prior work [GJMZ23] defines quantum-state commitments for compiling QPCPs with classical (nonsuperposition) queries. They do not provide a standalone quantum-state vector-commitment interface, nor provide the additional procedures that we require for coherent openings and returned proof states. In light of this, we provide a new definition of quantum-state vector commitment (QSVC) in the QROM. Our definition incorporates key additional procedures: (a) an Update procedure to allow the honest prover to coherently erase its record of the query locations; (b) a Recover procedure to allow the honest prover to recover the underlying quantum message when the verifier returns a commitment, thereby supporting the return of proof oracles in a QIOP. These procedures (see Section 6.1 for details) ensure completeness of the resulting succinct argument for the aforementioned broad class of QIOPs. We also need a suitable security notion, discussed next. Online quantum extraction of quantum messages. We formulate a notion of online extractability for QSVCs in the QROM. Informally, a QSVC scheme is extractable if there is an efficient extractor, with access to the compressed-oracle database, such that the following two ways of implementing superposition query access to the committed quantum message are indistinguishable. (Both implementations abort if any validity check fails.) • Real access. The receiver verifies the supplied local openings and performs the desired superposition query through the commitment. • Extracted access. Before seeing any openings, the extractor recovers a complete quantum state associated with the commitment. It later validates each opening, performs the same query directly on the extracted state, and reconstructs the updated commitment. Crucially, extraction occurs online and before the sender chooses its openings. Formalizing the above intuition is subtle. The extractor must check the validity of the openings after the commitment has already been used 3

to extract the message; see Theorem 6.3 for the formal definition. Our online extractability notion enables a straightline reduction from the soundness of the compiled quantum argument to the public-query soundness of the underlying QIOP. Given a malicious argument prover, the reduction constructs a malicious QIOP prover by using the QSVC extractor to recover the committed proof states. When the QIOP verifier returns a proof state after querying it, the reduction reconstructs a corresponding commitment and resumes the simulation. The swap-binding notion for quantum-state commitments in [GJMZ23] does not provide the online guarantee required for such a straightline reduction. Extractable quantum-state tree commitment. We construct an extractable QSVC in the QROM (unconditionally) where a commitment has size poly(λ) and an opening proof has size poly(λ, q, log n), for message length n and a superposition query where each branch is for at most q locations. (This efficiency is comparable to that of the Merkle commitment scheme in the ROM.) The extraction error is as follows. Theorem 3 (Theorem 7.3, informal). There exists a QSVC in the QROM (with the above efficiency and) with extraction error ξExt = O(t3 · poly(n, λ) · 2−λ ) against t-query quantum adversaries that ask a single opening. Here n is the length of the message and λ is the security parameter (output length of the oracle). For simplicity, the theorem states the extraction error for a single opening. More generally, our formal definition of extraction supports multiple openings (see Theorem 6.3) to handle QIOPs with adaptive queries across rounds, and our analysis directly establishes an extraction error for this adaptive query setting. The underlying construction is a quantum-state tree commitment (QSTC). We combine a Merkle tree structure with a basic extractable succinct quantum-state commitment (see Sections 4 and 5 for details). This follows the structure in [GJMZ23] with two differences: (i) a random oracle replaces the cryptographic hash function; (ii) our construction additionally includes the extra procedures required by our QSVC definition. Informally, at each tree node, the basic commitment coherently evaluates the random oracle on the computational-basis labels of the message register and, separately, on its Hadamard-basis labels. The two resulting image registers form the commitment, while the message register is retained as the opening. Using the compressed-oracle database, the extractor coherently recovers preimages associated with both image registers. Opening verification can then be related to an EPR-type consistency test between the two recovered descriptions. Excluding branches containing a random-oracle collision (and other small probability events), this test ensures that extracted access behaves like honest recovery of the committed state. We compose this basic commitment in a Merkle tree and prove that extraction remains secure under local, adaptive openings. Our analysis of this construction addresses online extraction, coherent openings, and adaptive queries; all of these are not considered in [GJMZ23]. See Theorem 7.1 for the full construction.

1.2

Related work

Hash-based succinct arguments for NP. The commit-and-open paradigm [Kil92; Mic00; BCS16; CDGS23] originated with Kilian’s protocol [Kil92] and was later generalized from PCPs to IOPs [BCS16]; it has become a standard approach to constructing hash-based succinct arguments for NP. Using a hashbased vector commitment scheme (typically a Merkle commitment scheme), these transformations map a public-coin IOP into a succinct public-coin interactive argument. The prover replaces each long proof string with a succinct commitment and subsequently opens only the locations queried by the verifier. (To obtain a non-interactive argument, one further applies the Fiat–Shamir transformation.) Security of the hash-based commit-and-open paradigm is studied in two settings: (i) in the plain model, classical security is established in [CDGS23] based on collision-resistant hash functions and post-quantum security is established in [CDDGS25] based on collapsing hash functions; and (ii) in the random oracle model, classical security is established in [BCS16; CY24] and post-quantum security is established in [CMS19; CDHZ26]. 4

Succinct arguments for QMA. Succinct arguments for QMA can be constructed under various assumptions. A line of work [Bar+22; MNZ24; GKNV25; BLM26] constructs such arguments based solely on cryptographic assumptions. Their protocols build either on Mahadev’s measurement protocol [Bar+22; GKNV25] or on the compiled non-local game paradigm [MNZ24; BLM26], and additionally have classical verifiers. Most recently, [BLM26] shows the feasibility of succinct arguments for QMA from oblivious state preparation (OSP) and collapsing hash functions. Since OSP can be based on plain trapdoor claw-free functions, their result is the first such construction that does not inherently rely on the hardness of learning with errors. No construction of OSP from purely unstructured assumptions is currently known. A different approach, more closely related to ours, follows the commit-and-open paradigm. [CM24] proposes a candidate transformation that compiles a QPCP into a succinct interactive quantum argument by committing to the QPCP succinctly and later opening only the locations queried by the verifier, and [GJMZ23] constructs another transformation following the same paradigm and proves the security of their transformation. Neither transformation relies on structured cryptographic assumptions; we discuss the assumptions underlying their commitment schemes below. However, obtaining a succinct argument for QMA through their approaches requires an efficient QPCP for QMA, whose existence remains a conjecture. Commitments to quantum states. Two prior works study quantum-state vector commitments by adapting the Merkle tree paradigm to quantum states. [CM24] proposes a candidate construction called the quantum Merkle tree in the quantum Haar random oracle model, using a Haar random unitary to compress the quantum state at each level of the tree until we reach the root, without proving the security of the candidate construction against a malicious sender. [GJMZ23] studies how to obtain a quantum-state vector commitment in the plain model by first constructing a succinct quantum-state commitment (without local opening) and composing them using a Merkle tree. Their construction can be based on collapsing hash functions and even on potentially weaker quantum cryptographic assumptions. Neither work formalizes quantum-state vector commitments as a standalone cryptographic primitive with a dedicated security definition. A related notion is the classical commitment to quantum states in [GKNV25]. Their scheme allows a quantum sender to produce a classical commitment to a quantum state and later provide classical openings corresponding to measurements of selected qubits in either the computational or Hadamard basis. Openings for measurement results in these two bases do not suffice for our application. Extractable commitments. Online extractability requires that an extractor, given some trapdoor information, can recover the underlying message from the commitment without rewinding the sender. [Pas03] shows that the basic hash-based commitment (“hash the message”) is extractable in the ROM. [DFMS22] prove the same scheme is post-quantum extractable in the QROM; given a classical commitment y from a quantum adversary, it is possible to recover the message x given the quantum database obtained via the compressed oracle technique [Zha19]. [CDHZ26] further strengthens this notion by showing that such an extraction can be applied coherently to commitments y appearing in superposition within the adversary’s random oracle queries without being detected by the adversary. These works consider only commitments to classical messages and therefore do not directly provide extractability for commitments to quantum states.

5

2

Preliminaries

For every non-negative integer n, we use [n] to denote the set {1, 2, · · · , n}. In particular, [0] denotes the empty set. We denote the empty string by ε. Let {0, 1}<ℓ , {0, 1}≤ℓ be the sets of strings of length less than ℓ and no more than ℓ, respectively. For every game G, we use Pr [G] to denote the probability that the output of game G is 1. We use hm (z) to denote the Hamming weight of a vector z (the number of non-zero elements in z).

2.1

Quantum states, operators, and circuits

We use the standard bra-ket notation. We abbreviate the tensor product |0⟩⊗n as |0n ⟩, or simply |0⟩ when the number of qubits is clear from context. A register is a named finite-dimensional complex Hilbert space. We use serif font, for example, A, to represent registers. For registers A, B, C, the concatenation ABC is the tensor product of the associated Hilbert spaces. Sometimes we need to group several registers into one register, in which case, we use notations like A := (B, C). We also often divide a register into several registers, in which case, we use notations like (A, B) := C when the size of each register is clear from the context. For a linear transformation L and a quantum state ρ, we sometimes add a subscript R to them to emphasize that LR is acting on the register R, and ρR is a quantum state in the register R. We denote the identity transformation over a register R as IR . p For a vector |ϕ⟩, we write ∥ |ϕ⟩ ∥ to denote its ℓ2 norm ∥ |ϕ⟩ ∥ := ⟨ϕ|ϕ⟩. For a linear transformation L, the operator norm of L is denoted by ∥L∥ := max|ϕ⟩ ∥L |ϕ⟩ ∥ where the max is among all the vectors of norm 1. Then for two operators A and B, ∥A + B∥ ≤ ∥A∥ + ∥B∥ and ∥AB∥ ≤ ∥A∥∥B∥. If A and B satisfy A† B = 0 and AB † = 0 (i.e. they have orthogonal images and orthogonal supports), then ∥A + B∥ ≤ max{∥A∥, ∥B∥} . (1) P In particular, the operator norm of a controlled operator A = |x⟩⟨x| ⊗ Ax can be upper bounded by the x maximum of the norms of the operators A as shown in [DFMS22]: ∥A∥ ≤ max ∥Ax ∥ . x

(2)

For two linear transformations A and B, their commutator is [A, B] := AB − BA, whose norm measures how nearly A and B commute. For three operators A, B and C such that ∥A∥, ∥B∥, ∥C∥ ≤ 1, if both A and B are almost commutative with C, AB is almost commutative with C, formally, as shown in [CMS19]: ∥ [AB, C] ∥ ≤ ∥ [A, C] ∥ + ∥ [B, C] ∥ .

(3)

We fix the universal gate set {H, CNOT, T } [NC10]. In this work, we consider unitary quantum circuits consisting of unitary gates from this gate set. The size of a unitary quantum circuit C is the number of gates in C. For a unitary quantum circuit C, the inverse of C, denoted as C † , has size linear in the size of C. A quantum algorithm can, without loss of generality, be written in the form of introducing ancilla qubits initialized as |0⟩, applying a unitary quantum circuit, and making measurements, by the deferred measurement principle. Thus we sometimes specify a quantum algorithm with a unitary quantum circuit together with the ancilla register and the output register. For two registers A and B of the same size, we use SWAPAB to denote the unitary that maps |ϕ⟩A |ψ⟩B to |ψ⟩A |ϕ⟩B for each |ϕ⟩ and |ψ⟩. X is the Pauli matrix which flips a qubit,   0 1 X := . 1 0 6

2.2

Oracle circuits and oracle algorithms

For a function f : {0, 1}∗ → {0, 1}m , an oracle-aided unitary quantum circuit C f is a unitary quantum circuit with the additional query gate Uf : |x⟩ |y⟩ → |x⟩ |y ⊕ f (x)⟩. Notice that the inverse of Uf is Uf . For an oracle-aided quantum circuit C f , the inverse of C f can also be implemented with oracle access to f . More generally, we consider stateful oracles, which can be written as U (S) for a unitary U and a state register S. An oracle-aided unitary quantum circuit C U (S) is a unitary quantum circuit where all the gates do not act on the state register S, with the additional query gate UXYS acting on the registers XYS where X is the query register and Y is the answer register. We use the sans-serif font with a stateful oracle in the superscript, e.g., AU (S) , to denote an oracle-aided quantum algorithm. Similarly, an oracle-aided quantum algorithm can be written in the form of introducing some ancilla qubits in |0⟩, applying an oracle-aided unitary quantum circuit, and making measurements, by the deferred measurement principle. For an oracle-aided quantum algorithm AU (S) which has input register I and output register O, we use O ← AU (S) (I) to denote the following process: 1. A is given an input on register I, which might entangle with the state register S of the oracle U . 2. After interacting with the oracle U , A outputs a state on register O, which might also be entangled with the state register S. An algorithm A with oracle access to multiple oracles (Ui (Si ))i∈[t] may query them in superposition, the registers (Si )i∈[t] may not be distinct. Specifically, A has an oracle-selection register N, and a query is implemented by the controlled gate X |i⟩⟨i|N ⊗ (Ui )XYSi . i∈[t]

We use query probability mass to quantify how heavily an oracle is queried. Definition 2.1. Let A be an algorithm with access to multiple oracles (Ui (Si ))i∈[t] . We define the query probability mass of A on the i-th unitary Ui at its j-th query as mass(A, i, j) := ∥ |i⟩⟨i|N |ψj ⟩ ∥2 , where |ψj ⟩ is the joint quantum state of the algorithm A and the state registers of the unitaries (Ui )i∈[t] just before the algorithm makes its j-th oracle query. A quantum query can simultaneously access each oracle, but the sum of query probability mass across different oracles cannot exceed 1. P Remark 2.2. Since i∈[t] |i⟩⟨i|N = IN , for every algorithm A with access to oracles (Ui (Si ))i∈[t] , and integer j, X mass(A, i, j) = 1 . i∈[t]

We define the total (query) probability mass as the sum of the query probability masses over all oracle queries. Definition 2.3. For an algorithm A that makes q queries to oracles (Ui (Si ))i∈[t] , we define the total query probability mass of A on the i-th unitary Ui as follows: TotalMass(A, i) :=

q X j=1

7

mass(A, i, j) .

In the paper, we slightly overload the notation to use TotalMass(A, Ui (Si )) to also denote the total query (probability) mass of A to Ui .

2.3

Compressed oracles

In this work, we consider quantum random oracle models (QROMs) where every party has quantum access to an oracle f , sampled uniformly at random from the set of all the functions from {0, 1}∗ to {0, 1}m . We use RO to emphasize that it is a random oracle and write the process of sampling a random oracle RO as RO ← U(m). P ′ For y ∈ {0, 1}m , we define |ŷ⟩ := 2−m/2 y′ ∈{0,1}m (−1)⟨y,y ⟩ |y ′ ⟩ where ⟨y, y ′ ⟩ is the inner product of ⊗m m ⟩. y and y ′ . To simplify notation, we often use |0̂m ⟩ to denote the state |0̂⟩ = 2−m/2 (|0⟩ + |1⟩)⊗m = |0c Since an efficient oracle-aided quantum algorithm with running time T cannot query RO on input length greater than T , we often set the domain X to be a set of bit strings of bounded length instead of {0, 1}∗ in order to represent it in a finite-dimensional complex Hilbert space. Applying the query gate URO : |x⟩ |y⟩ → |x⟩ |y ⊕ RO(x)⟩ is equivalent to applying the unitary U : |x⟩ |y⟩ |f ⟩ → |x⟩ |y ⊕ f (x)⟩ |f ⟩ to a state whose last register is initialized as the truth table of RO on X. Since U commutes with computational N := basis measurement on the last register, we can initialize a database register D x∈X D[x] to be a uniform superposition of the truth tables of all the possible functions from X to {0, 1}m and use U as the query gate, instead of sampling RO and using URO . More interestingly, Zhandry [Zha19] introduced a way to compress the database register D, taking advantage of the fact that most of the registers D[x] are not queried and thus remain in |0̂m ⟩ during the process. Formally, the state of each D[x] lies in the span of {|y⟩}y∈{0,1}m ∪ {|⊥⟩} where ⊥ is a special symbol. We can apply O FD := FD[x] x∈X

with FD[x] := |0̂m ⟩⟨⊥|D[x] + |⊥⟩⟨0̂m |D[x] +

X

|ŷ⟩⟨ŷ|D[x]

y∈{0,1}m /{0m }

to the state

N

x∈X





P √1 m y∈{0,1}m |y⟩ 2

= D[x]

m x∈X |0̂ ⟩D[x] to get an initial state

N

N

x∈X |⊥⟩D[x] before

any query is made. Upon receiving a query with query register X and answer register Y, we can apply the oracle unitary X OXYD := |x⟩⟨x|X ⊗ FD[x] CNOTD[x]Y FD[x] x∈X

where CNOTD[x]Y |yx ⟩D[x] |y⟩Y = |yx ⟩D[x] |y ⊕ yx ⟩Y for y, yx ∈ {0, 1}m and CNOTD[x]Y acts as an identity on |⊥⟩D[x] |y⟩Y for y ∈ {0, 1}m . N For every set S ⊆ X, the register D[S] := x∈S D[x] records the images of the set S. We view a database D as an array of length |X| with alphabet {0, 1}m ∪ {⊥}. We use D[x] to denote the image of x, as stored in the database D, and we use D[S] to denote the array of images of x ∈ S, as stored in the database D. The size of D is denoted as |D|, which is the number of non-⊥ elements in the array D. Let ΠNoCol be the projector that projects to all the databases without any collision. Formally, we denote the set of all possible databases as SD := ({0, 1}m ∪ {⊥})X and the set of all databases without collisions as 8

SNoCollision := {D ∈ SD : ∀x, x′ ∈ X s.t. x ̸= x′ , D[x] ̸= ⊥, and D[x′ ] ̸= ⊥, we have thatD[x] ̸= D[x′ ]}, and we have that X ΠNoCol := |D⟩⟨D| . D∈SNoCollision

Πt is the projector that projects to all the databases with size at most t. Formally, X Πt := |D⟩⟨D| , D∈St

where St := {D ∈ SD : |D| ≤ t} . We will use the following lemma from [CMS19]. Lemma 2.4 (Lemmas 5.10 and 6.11 in [CMS19]). For every random oracle output length m and bound t for the size of the database, √ ∥(ID − ΠNoCol ) (Πt OΠt ) ΠNoCol ∥ ≤ 6t · 2−m/2 . Readers may wonder how to implement the above compressed oracle efficiently. As in [Zha19], we can make the compressed oracle efficient by mapping the extremely long table into a short database. There exists compressed table and returns a compressed database. Namely, given input N a unitary UToDB that takes a m |z ⟩ where z ∈ {0, 1} ∪ {⊥}, UToDB returns |x1 , zx1 , x2 , zx2 , . . . , xk , zxk ⟩ where x1 , . . . , xk x x∈X x D[x] enumerate all x ∈ X such that zx ̸= ⊥, in increasing order. All the computations can also be done with this short database efficiently. We show that restricting a procedure to run on databases without collisions won’t change the final result too much. Lemma 2.5. Let A be a t-query algorithm with query access to the oracles O(D) and U (D) for a unitary U such that [ΠNoCol , U ] = 0 and [Πq , U ] = 0 for every q. Let O denote the output register of the algorithm A. Denote A’s query mass to O(D) as w := TotalMass(A, O(D)). Let D be a computationally unbounded distinguisher. Let ANoCollision be a variant of A that runs as A except that before and after each query, the measurement {ΠNoCol , ID − ΠNoCol } is performed over D until A outputs register O. If at least one of the measurement outcomes is ID − ΠNoCol , then ANoCollision outputs 0 and O; otherwise, ANoCollision outputs 1 and O. Then for every random oracle output length m, v   v 2 u u  D ← |⊥⟩ D ← |⊥⟩ u u u  u (D)  tPr b = 1 O ← AO(D),U (D)  − tPr b ∧ b′ = 1 (b′ , O) ← AO(D),U NoCollision b ← D(O, D) b ← D(O, D) ≤ 24 · t2 w · 2−m . In general, the same bound holds for A′ , which runs as A except that the measurement {ΠNoCol , ID − ΠNoCol } is performed over D before the i-th query for i in a prescribed set I ⊆ [t + 1]: v   v 2 u  u D ← |⊥⟩ D ← |⊥⟩ u u u  u tPr b = 1 O ← AO(D),U (D)  − tPr b ∧ b′ = 1 (b′ , O) ← A′ O(D),U (D)  b ← D(O, D) b ← D(O, D) ≤ 24 · t2 w · 2−m . 9

Proof. We prove the first part of the lemma. The second part of the lemma can be proved with the same idea. By the deferred measurement principle, we can assume A always performs a unitary Ui to prepare the i-th query for i ∈ [t] and performs the unitary Ut+1 to prepare the output register. Without loss of generality, we can assume the distinguisher D performs a projective measurement {M0 , M1 }. Define |ψi ⟩ := Ui+1 O′ · · · O′ U1 |0̄⟩ where the unitary O′ := |0⟩⟨0|N ⊗ O + |1⟩⟨1|N ⊗ U is the controlled unitary that implements the superposition queries to the two oracles O and U . Then the state |ψt ⟩ = Ut+1 O′ · · · O′ U1 |0̄⟩ is the state on registers (O, D) immediately after A is finished. ′ ′ Define |ϕi ⟩ := Ui+1 ONoCollision · · · ONoCollision U1 |0̄⟩, where ′ := ΠNoCol O′ ΠNoCol . ONoCollision ′ ′ Then the subnormalized state |ϕt ⟩ = Ut+1 ONoCollision · · · ONoCollision U1 |0̄⟩ is the state on registers (O, D) immediately after A is finished conditioned on all of the measurement outcomes being ΠNoCol . Then we have that v   v 2 u u  D ← |⊥⟩ D ← |⊥⟩ u u u  u (D)  tPr b = 1 O ← AO(D),U (D)  − tPr b ∧ b′ = 1 (b′ , O) ← AO(D),U NoCollision b ← D(O, D) b ← D(O, D)

≤ |∥M1 |ψt ⟩ ∥ − ∥M1 |ϕt ⟩ ∥|2 ≤ ∥M1 (|ψt ⟩ − |ϕt ⟩)∥2

(By the triangle inequality)

≤ ∥ |ψt ⟩ − |ϕt ⟩ ∥2 . Since one query to the oracle O increases the size of the database by at most 1, and one query to the oracle U does not change the size of the database (as [Πq , U ] = 0 for every q), the states satisfy that for every i ∈ [t], |ψi ⟩ = Ui+1 Πt O′ Πt · · · Πt O′ Πt U1 |0̄⟩ and ′ ′ |ϕi ⟩ = Ui+1 Πt ONoCollision Πt · · · Πt ONoCollision Πt U1 |0̄⟩ .

As a result, ∥ |ψt ⟩ − |ϕt ⟩ ∥ ≤

≤

≤

≤

t−1 X i=0 t−1 X i=0 t−1 X i=0 t−1 X i=0

′ ′ ′ ∥Ut+1 Πt ONoCollision · · · ONoCollision Πt Ui+2 Πt (ONoCollision − O′ )Πt |ψi ⟩ ∥

(By the triangle inequality)

′ ′ ′ ∥Ut+1 Πt ONoCollision · · · ONoCollision Πt Ui+2 (ΠNoCol + ID − ΠNoCol )Πt (ONoCollision − O′ )Πt |ψi ⟩ ∥

′ ∥ΠNoCol Πt (ONoCollision − O′ )Πt |ψi ⟩ ∥ + ∥(ID − ΠNoCol )Πt O′ Πt |ψt−1 ⟩ ∥

′ ∥ΠNoCol Πt (ONoCollision − O′ )Πt |ψi ⟩ ∥ +

t−1 X

∥(ID − ΠNoCol )Πt O′ Πt ΠNoCol |ψi ⟩ ∥

i=0

(By the triangle inequality) 10

=

t−1 X

′ ∥ΠNoCol Πt (ONoCollision − O′ )Πt |0⟩⟨0|N |ψi ⟩ ∥ +

i=0

≤

t−1 X

t−1 X

∥(ID − ΠNoCol )Πt O′ Πt ΠNoCol |0⟩⟨0|N |ψi ⟩ ∥

i=0

′ ∥ΠNoCol Πt (ONoCollision − O′ )Πt ∥ + ∥(ID − ΠNoCol )Πt O′ Πt ΠNoCol ∥ ∥ |0⟩⟨0|N |ψi ⟩ ∥

i=0

=2

X

p ∥(ID − ΠNoCol ) (Πt OΠt ) ΠNoCol ∥ mass(A, O(D), i)

i∈[t]

s X √ mass(A, O(D), i) ≤ 2 6t · 2−m/2 t

(By Theorem 2.4 and Cauchy–Schwarz inequality)

i∈[t]

√ √ ≤ 2 6t · 2−m/2 tw ,

′ where in the sixth line, we use that [ΠNoCol , U ] = 0 and [Πt , U ] = 0, and thus ΠNoCol Πt (ONoCollision − ′ ′ O )Πt |1⟩⟨1|N = 0 and (ID − ΠNoCol )Πt O Πt ΠNoCol |1⟩⟨1|N = 0. The lemma follows from the above two inequalities.

2.4

Relations and languages

We consider quantum arguments for relations, where the honest prover additionally gets a quantum witness as input. Thus we need to define a relation between the classical instance and the quantum witness state. Definition 2.6 (Relations and languages). A relation R is a set of tuples of a classical string and a quantum state. Namely, R ⊆ {(x, ρ) : x ∈ {0, 1}∗ , ρ is a quantum state}. A language for a relation R is defined as L(R) = {x : ∃ρ, (x, ρ) ∈ R}. We say a relation has a decider Decider, if Decider is a quantum algorithm such that for every (x, ρ) ∈ R, Pr [Decider(x, ρ) = 1] ≥

2 , 3

and for every x ∈ / L(R) and quantum state ρ, Pr [Decider(x, ρ) = 1] ≤

1 . 3

A decider is efficient, if it takes a quantum state of poly(ν) qubits, and runs in time poly(ν) where ν is the length of the instance x. Then QMA is the set of languages L(R) such that R has an efficient decider.

2.5

Quantum interactive arguments

A quantum interactive argument (P, V) for a relation R consists of a quantum polynomial-time prover P and a quantum polynomial-time verifier V that exchange quantum messages. Both parties receive an instance x as input, while P receives a quantum state ρ as the witness. After the interaction, the verifier V outputs a bit, indicating whether V accepts. We write Pr[⟨P(x, ρ), V(x)⟩ = 1] for the probability that the verifier accepts after the interaction. In this paper, we consider quantum interactive arguments in the quantum random oracle model where both prover P and V have quantum query access to a random oracle RO sampled from U(m). We write Pr[⟨P RO (x, ρ), V RO (x)⟩ = 1] for the probability that the verifier accepts after the interaction when the prover and the verifier have access to RO. 11

Definition 2.7 (Completeness). A quantum interactive argument (P, V) for a relation R in the quantum random oracle model has completeness cQARG if for every integer λ, ν, function RO : {0, 1}∗ → {0, 1}m where the output length m of the random oracle is a function of the security parameter λ specified by the scheme, and (x, ρ) ∈ R such that |x| ≤ ν, Pr[⟨P RO (x, ρ), V RO (x)⟩ = 1] ≥ cQARG (ν, λ) . Definition 2.8 (Soundness). A quantum interactive argument (P, V) for a relation R in the quantum random e oracle model has soundness sQARG if for every integer λ, ν, t, and t-query quantum adversary P, |x| ≤ ν  / L(R) Pr ∧ x ∈ ∧b = 1 

 RO ← U(m)  ≤ sQARG (ν, λ, t) , x ← PeRO RO RO e , V (x)⟩ b ← ⟨P

where the output length m of the random oracle is a function of the security parameter λ specified by the scheme.

12

3

Quantum interactive oracle proofs

A quantum interactive oracle proof (QIOP) system is a proof system that combines the QPCPs and the quantum interactive proof (QIP) systems. In this section, we define the syntax of the QIOPs and the notions of completeness and soundness for QIOP systems. Basically, QIOPs are QIPs such that the verifier does not necessarily read all qubits of the prover’s message.

3.1

Review: quantum interactive proofs

We review the quantum interactive proofs [Wat03] and introduce our notation conventions that are also useful to define QIOPs in Section 3.2. In the standard notation, a quantum interactive proof system is an interactive protocol between two parties, the computationally unbounded prover P and the quantum polynomial-time verifier V, where the prover P has a private working register P and the verifier V has a private working register V, and they exchange messages through a specified register M for k rounds. In this work, we consider the doubly-efficient setting, where the honest prover P can be implemented in quantum polynomial time given the witness ρ along with the instance x for the relation R, and we specify different registers for messages and the internal states for different rounds. In more detail, we name the register that holds the i-th prover’s message by Mpi , and the register that holds the i-th prover’s internal state by Pi , and similarly, name the register that holds the i-th verifier’s message by Mvi , and the register that holds the i-th verifier’s internal state by Vi . Before the interaction, both P and V are given an instance x for a relation R. Furthermore, the honest prover P is given a quantum witness ρ in a specified part of the private working register P1 in the first round. The prover P and the verifier V interact as follows. In the i-th round for i ∈ [k], the prover P applies a quantum polynomial-time algorithm Pi on the instance x, the verifier’s message register Mvi−1 , and the private working register Pi to produce an output on the prover’s message register Mpi and the private working register Pi+1 . We write this procedure as (Mpi , Pi+1 ) ← Pi (x, Mvi−1 , Pi ) where Mv0 is an empty register. In the i-th round for i ∈ [k − 1], the verifier V applies a quantum polynomial-time algorithm Vi on the instance x, the prover’s message register Mpi , and the private working register Vi to produce an output on the verifier’s message register Mvi and the private working register Vi+1 . We write this procedure as (Mvi , Vi+1 ) ← Vi (x, Mpi , Vi ). In the final round, the verifier V runs a quantum polynomial-time algorithm Vk on the instance x, the prover’s message register Mpk , and the private working register Vk to get a single-qubit output register O, and measures O in the computational basis to get an outcome b, which indicates whether V accepts or rejects. We write this procedure as b ← Vk (x, Mpk , Vk ). We overload the notation and write V = (Vi )i∈[k] and P = (Pi )i∈[k] . Notice that here Vi may touch all parts of Mpi , similar to the classical interactive proofs, where the verifier may read the prover’s message in full. The protocol satisfies the usual completeness and soundness notions. The completeness states that given (x, ρ) ∈ R, the honest prover P can make the verifier accept with probability at least c(|x|). The soundness states that no computationally unbounded cheating prover, who implements an arbitrary channel P∗i instead of the polynomial-time algorithms Pi in the i-th round, can make the verifier V accept on a no instance x ∈/ L(R) with probability more than s(|x|).

13

3.2

Our notion of QIOPs

We define QIOPs by restricting the access of the QIP verifier to the register Mpi to be “local”. This definition is inspired by the QIPCP definition of [SV26] and extends it by allowing the verifier to return the i-th round prover’s message for any i ∈ [k]. Analogous to the classical case, where the proof oracle is a string divided into l symbols over an alphabet Σ, we need to first divide each prover’s message register into subregisters before defining the local access to the prover’s message registers. Dividing the prover’s message registers into subregisters. For round i ∈ [k], we decompose the i-th prover’s message register Mpi to li registers (Mpi [j])j∈[li ] for a prescribed proof length li , where Mpi [j] is a quantum register with prescribed alphabet Σ, whose Hilbert space can be written as span{|σ⟩ : σ ∈ Σ}. The locality: the first attempt. A natural way to define the locality of a QIOP verifier is to count the prover-message registers on which it acts. More precisely, the algorithm Vi that V applies in the i-th round has locality qi if Vi only acts on registers (Mpi′ [j])(i′ ,j)∈Qi for a query set Qi of size at most qi , and the private working register Vi . This definition, however, does not capture a coherent version of classical local query access. For example, consider an operation that prepares a uniform superposition state over the location register, and then applies a CNOT gate over registers (Mpi [j], Y) coherently, controlled on a location register containing |j⟩. Under the above naive definition, this operation would be charged as li queries because it touches each of the li registers (Mpi [j])j∈[li ] , even though it is just a coherent version of reading a random location of the i-th prover’s message and thus should be regarded as a local operation. Superposition access to quantum registers. To capture such operations, we adopt the notion of superposition queries introduced in [CGMV26] and equip the verifier V with quantum superposition access to the registers (Mpi [j])i∈[k],j∈[li ] . Generally, for a list of registers (Bi )i∈L with the same size, a quantum superposition query of width w to the oracle (Bi )i∈L consists of w pairs of registers (Locι , Yι )ι∈[w] . The oracle applies the unitary X U qry := |i⟩⟨i|Locι ⊗ SWAP [Bi , Yι ] i∈L

on the registers (Locι , Yι , (Bi )i∈L ) for each ι ∈ [w] before sending the registers (Locι , Yι )ι∈[w] back. We say that an algorithm A has quantum superposition access to a list of registers (Bi )i∈L with query depth d and query width w if its computation consists of unitaries (A(i) )i∈{0,1,...,d} , none of which acts directly on (Bi )i∈L , interleaved with d quantum superposition queries with width at most w to the oracle (Bi )i∈L , where d and w are polynomially bounded. We denote an algorithm with such access by A(Bi )i∈L . For simplicity, we only consider algorithms whose superposition queries all have the same width. We define the query complexity of A to be q := d · w. Returning the prover’s message registers. So far, the above QIOP model gives a reasonable definition of locality for the verifier, but it may be too restrictive for multi-round interactions. In the classical interactive oracle proofs, messages sent in later rounds may depend on messages from earlier rounds to help the verifier check claims about those earlier messages. A classical prover can support such interactions by retaining copies of its previous messages, whereas a quantum prover cannot in general do so because of the no-cloning theorem. We therefore allow previously submitted prover’s message registers to be returned to the prover in later rounds, as in the QIOP constructions of [SV26; CGMV26] and, more generally, in quantum interactive proofs. The remaining question is how such returns should be charged toward locality. The cost of returning registers. Returning a prover’s message register may involve many subregisters and can be implemented simply by having the verifier include the corresponding prover’s message in the 14

next message to the prover. However, the verifier does not “read” the contents of the register, but merely transfers the register back to the prover. Charging such an operation according to the size of the returned register would therefore not reflect the intended notion of locality. We thus adopt a more convenient way to formalize this model: we view all prover’s message registers as being held by a trusted third party O, who answers the verifier’s superposition queries to these registers. When the prover needs a previously submitted register, the trusted third party removes that register from the verifier’s query access and transfers it back to the prover. We therefore assign no additional cost to such a return operation, regardless of the size of the returned prover message. Putting the pieces together. We give the formal definition of QIOPs. Let QIOP = (P, V) where P = (Pi )i∈[k] is a tuple of polynomial-time quantum algorithms and V = (Vi )i∈[k] is a tuple of polynomialtime quantum algorithms with superposition access to registers. We say that QIOP is a k-round quantum interactive oracle proof for a relation R with completeness c and soundness s if the following holds. Definition 3.1 (Completeness). For every integer ν and instance-witness pair (x, ρ) ∈ R such that |x| ≤ ν,   P1 ← ρ   (Mp1 , P2 ) ← P1 (x, P1 )     (Mp1 [j])j∈[l1 ] := Mp1     I ← {1}, L ← {(1, j) : j ∈ [l ]}   1 1   For i = 2, . . . , k :    ≥ c(ν) . (Mpi [j])(i,j)∈L Pr  b = 1  (Ji , Mvi−1 , Vi ) ← Vi−1 (x, Vi−1 )     (Mpi , Pi+1 ) ← Pi (x, Mvi−1 , Pi , (Mpj )j∈Ji )     (Mpi [j])j∈[li ] := Mpi     ′ ′ ′ ′ ′ I ← I ∪ {i} \ J , L ← {(i , j ) : i ∈ I , j ∈ [l ]} i i−1 i i i   (Mp [j]) b ← Vk i (i,j)∈L (x, Vk ) We abbreviate the interaction in the above experiment by b ← ⟨P(x, ρ), V(x)⟩ . Accordingly, the completeness condition can be written more compactly as Pr [⟨P(x, ρ), V(x)⟩ = 1] ≥ c(ν) . e Definition 3.2 (Soundness). For every integer ν and computationally unbounded quantum adversary P,   e x←P   e x, P1 ) (Mp1 , P2 ) ← P(     := (Mp [j]) Mp   j∈[l1 ] 1 1   I1 ← {1}, L ← {(1, j) : j ∈ [l1 ]}    |x| ≤ ν  For i = 2, . . . , k :    ≤ s(ν) . / L(R) Pr  (Mpi [j])(i,j)∈L  ∧x ∈  (Ji , Mvi−1 , Vi ) ← Vi−1 (x, Vi−1 )  ∧b = 1    e x, Mvi−1 , Pi , (Mpj )j∈J ) (Mpi , Pi+1 ) ← P(   i   := (Mp [j]) Mp   j∈[li ] i i   Ii ← Ii−1 ∪ {i} \ Ji , L ← {(i′ , j ′ ) : i′ ∈ Ii , j ′ ∈ [li′ ]}   (Mp [j]) b ← Vk i (i,j)∈L (x, Vk ) 15

We abbreviate the interaction in the above experiment by e b ← ⟨P, e V(x)⟩ . x ← P, Accordingly, the soundness condition can be written more compactly as   |x| ≤ ν e x←P  / L(R) Pr  ∧ x ∈ e V(x)⟩ ≤ s(ν) . b ← ⟨P, ∧b = 1 We consider the following efficiency measures of a QIOP. • The round complexity k is the number of rounds of interactions between the prover and the verifier. • The alphabet Σ is the set indexing the computational basis of each prover-message subregister. In particular, each subregister has Hilbert space span{|σ⟩ : σ ∈ Σ}. • The query depth is the total query depth of the verifier algorithms (Vi )i∈[k] . Namely, let di denote the query depth of Vi , and we define the query depth of the QIOP X d := di . i∈[k]

• The query width is an upper bound for the query width of verifier algorithms (Vi )i∈[k] . Namely, let wi denote the query width of Vi , and we define the query width of the QIOP w := max wi . i∈[k]

• The query complexity is the total query complexity of (Vi )i∈[k] . Namely, let qi := wi · di denote the query complexity of Vi , and we define the query complexity of the QIOP X q := qi . i∈[k]

• The total proof length is the sum of the lengths of the prover messages over all rounds, while the maximum proof length is the maximum length of a prover message in any round. Namely, X l := li , lmax := max li . i∈[k]

i∈[k]

• The verifier-to-prover communication is the total size of the verifier’s message registers over all rounds. Namely, let vci denote the size, in qubits, of the verifier’s message register Mvi in the i-th round, and we define the verifier-to-prover communication of the QIOP X vc := vci . i∈[k]

In particular, we do not count the returned prover messages toward the verifier-to-prover communication, since they are returned by the trusted third party O, rather than by the verifier. 16

3.3

Public-query QIOPs

As in the classical IBCS transformation [CDGS23], our compiler from quantum interactive oracle proofs to succinct quantum interactive arguments applies only to public-query QIOPs. This restriction arises because the query locations must be revealed to the argument prover in order to open the corresponding locations, and this additional information may be exploited by a malicious argument prover. In the classical setting, the public-query property roughly requires soundness to hold even when the query locations are revealed to the prover at the time the queries are made [CDGS23]. In the quantum setting, however, the query locations are stored in superposition in the registers (Loci )i∈[w] . We therefore adopt a natural quantum analogue of the classical notion. Namely, we say that a QIOP is public-query if its soundness continues to hold even when the verifier’s superposition queries are replaced by leaked superposition queries. Informally, a leaked superposition query with respect to an adversary B is performed as follows. Upon receiving a query (Loci , Yi )i∈[w] , the trusted third party O sends the query location registers (Loci )i∈[w] to B. The adversary B may then apply an arbitrary quantum operation jointly to the registers (Loci )i∈[w] and the private register before returning (Loci )i∈[w] to O, who answers the query by applying the same query unitary U qry as in the ordinary superposition query setting. After O performs the query, the query location registers (Loci )i∈[w] are leaked to B again, who may then apply another arbitrary quantum operation jointly to the registers (Loci )i∈[w] and the private register before returning (Loci )i∈[w] . We formalize this interaction below. Definition 3.3 (Leaked superposition queries). Let (Mi )i∈L be a list of registers of equal size, and let B be an adversary with internal register J. Let A be an algorithm with leaked superposition access to (Mi )i∈L of query depth d and query width w. Let x denote the classical input of A, let I(q) denote its private register after the q-th invocation of its internal unitary, and let O denote its output register. The computation of A with superposition queries leaked to the adversary B is given by the following experiment:   ((Locι , Yι )ι∈[w] , I(1) ) ← A(0) (x, I(0) )    ((Locι )ι∈[w] , J) ← B((Locι )ι∈[w] , J)     For q = 1, . . . , d − 1 :       ((Locι , Yι )ι∈[w] , (Mi )i∈L ) ← O((Locι , Yι )ι∈[w] , (Mi )i∈L )      ((Loc ) , J) ← B((Loc ) , J)   ι ι∈[w] ι ι∈[w]    ((Loc , Y )  (q+1) (q) (q) , I ) ← A (x, (Loc , Y ) , I ) ι ι ι∈[w] ι ι ι∈[w]       ((Locι )ι∈[w] , J) ← B((Locι )ι∈[w] , J)      ((Locι , Yι )ι∈[w] , (Mi )i∈L ) ← O((Locι , Yι )ι∈[w] , (Mi )i∈L )      ((Loc ) , J) ← B((Loc ) , J)   ι ι∈[w] ι ι∈[w] (O, I(d+1) ) ← A(d) (x, (Locι , Yι )ι∈[w] , I(d) ), where O is the trusted party that answers the superposition queries by applying the unitary X U qry := |i⟩⟨i|Locι ⊗ SWAP [Mi , Yι ] i∈L

on the registers (Locι , Yι , (Mi )i∈L ) for each ι ∈ [w].

17

We abbreviate this computation as (O, I(d+1) ) ← ALeaked(O,B,(Mi )i∈L ) (x, I(0) ). For algorithms with multiple inputs or outputs, we use the analogous notation. We formalize the public-query soundness notion for QIOPs, where a trusted third party O is storing the prover’s message registers and answering the superposition queries for the verifier, while leaking the query e location registers to the adversary P. Definition 3.4 (Public-query soundness). A k-round quantum interactive oracle proof QIOP = (P, V) for a relation R is public-query if the soundness property continues to hold even if the verifier’s queries to the e registers are leaked to the malicious prover P. Specifically, let O be the trusted party that implements the oracle access. QIOP has public-query e soundness spq if for every integer ν and computationally unbounded quantum adversary P,   e x←P   e x, P1 ) (Mp1 , P2 ) ← P(     (Mp1 [j])j∈[l1 ] := Mp1       I1 ← {1}, L ← {(1, j) : j ∈ [l1 ]}   | x | ≤ ν   For i = 2, . . . , k :   e / L(R) Pr  ∧ x ∈ Leaked(O,P,(Mp  ≤ spq (ν) . i [j])(i,j)∈L )  (Ji , Mvi−1 , Vi ) ← Vi−1 (x, Vi−1 )    ∧b = 1 e x, Mvi−1 , Pi , (Mpj )j∈J )   (Mpi , Pi+1 ) ← P( i     := (Mp [j]) Mp j∈[l ] i i i   ′ ′ ′ ′  Ii ← Ii−1 ∪ {i} \ Ji , L ← {(i , j ) : i ∈ Ii , j ∈ [li′ ]}    e Leaked(O,P,(Mp i [j])(i,j)∈L ) b ← Vk (x, Vk ) Furthermore, when the intermediate registers can be omitted, we further abbreviate the interaction in the above experiment by e b ← ⟨P, e V(x)⟩pq . x ← P, Accordingly, the public-query soundness condition can be written more compactly as   |x| ≤ ν e x←P  / L(R) Pr  ∧ x ∈ e V(x)⟩pq ≤ spq (ν) . b ← ⟨P, ∧b = 1 Public-coin QIOPs. A QIOP is public-coin if each verifier’s message register Mvi consists of fresh classical random coins. Moreover, for each round i ∈ [k], both the returned index set Ji and the classical query set used by the verifier for point queries in that round are determined by publicly known deterministic functions of the instance x and the random coins contained in the preceding verifier’s message registers (Mvj )j∈[i−1] . For public-coin QIOPs, we assume without loss of generality that, immediately after each leakage in round i, the verifier derives the query set from the instance x and the random coins in (Mvj )j∈[i−1] , and the verifier rejects if the query set given by the prover differs from this derived set. These checks do not affect the ordinary execution of the public-coin QIOP and ensure that the malicious prover does not modify the query set. Moreover, the leaked query locations are determined by the instance x and the random coins in the preceding verifier’s message registers (Mvj )j∈[i−1] . Thus, they reveal no additional information to the malicious prover. Consequently, we obtain the following. Lemma 3.5. Every public-coin QIOP with soundness s has public-query soundness spq (ν) = s(ν).

18

4

Defining extractable quantum state commitments

We describe the syntax of (non-interactive) quantum state commitments we will consider, and then provide a formal definition of extractability.

4.1

A canonical quantum state commitment

Following [Yan22; GJMZ23], we consider quantum state commitments in the following canonical form, where to commit to a quantum message, the sender always applies a unitary quantum circuit to the quantum message along with enough ancilla qubits initialized as |0⟩, and the receiver always does the inverse of what the sender does and checks whether the ancilla qubits are |0⟩. Definition 4.1 (Quantum state commitment scheme in the QROM). Let m ∈ N be the output length of the random oracle and n ∈ N be the length of the quantum state which we want to commit to. Let RO be sampled uniformly at random from all the functions with range {0, 1}m . In the QROM, a quantum state commitment (QSC) is a pair of oracle-aided quantum algorithms (ComRO , CheckRO ) with oracle access to RO where ComRO and CheckRO are specified by a poly(m, n)-qubit RO ancilla register A and an oracle-aided poly(m, n)-size unitary quantum circuit Cm,n , as follows. ComRO (ρM ): 1. Initialize A as all |0⟩ states. RO 2. To commit to an n-qubit quantum message ρM , apply Cm,n to the registers M and A to get a state σCO , which is divided into two registers C and O. 3. Output the state on C as the commitment, and the state on O as the decommitment. CheckRO (σCO ): RO 1. Apply the inverse of Cm,n to the registers C and O to get a state ϱMA . 2. Make a computational measurement on the register A. 3. If the outcome is not all 0, output b = 0 and a dummy quantum message |0n ⟩ on register M. 4. Otherwise, output b = 1 and the state ρM in register M. A commitment is succinct if the length of C is less than the length of the quantum message. A commitment is n-to-t if the quantum message has n qubits while C has t qubits. A canonical commitment scheme always satisfies the perfect correctness as defined below. Definition 4.2 (Perfect correctness). Let m ∈ N be the output length of the random oracle. Let RO be sampled uniformly at random from all the functions with range {0, 1}m . A quantum state commitment scheme (ComRO , CheckRO ) has perfect correctness if for every function RO with output length m, unbounded quantum adversary A, and unbounded quantum distinguisher D, the following holds:   (M, E) ← ARO  = Pr [1 ← DRO (1, M, E) | (M, E) ← ARO ] . Pr 1 ← DRO (b, M, E) (C, O) ← ComRO (M) RO (b, M) ← Check (C, O) Lemma 4.3. Every canonical quantum state commitment scheme (ComRO , CheckRO ) defined in Theorem 4.1 has perfect correctness (Theorem 4.2). Proof. By definition, CheckRO does exactly the inverse of ComRO . Since in ComRO , A is properly initialized, before the computational measurement in CheckRO , qubits of A are all in the |0⟩ state, so CheckRO always outputs b = 1, and the original quantum message (while preserving the entanglement between M and E). 19

4.2

The extractability definition

We first provide the syntax of an extractor in this case. In addition to the state in the commitment register C, an extractor should have some side information of the oracle, provided by a quantum simulator. Ideally, the simulator maintains the side information in its internal state register S without disturbing any adversary’s execution. Definition 4.4 (Quantum simulator). A stateful oracle USim with the state register S is a ξSim (t, m)-quantum simulator for the random oracle if for any t-query quantum adversary A, h i Pr 1 ← AUSim (S) (|⊥⟩S ) − Pr [1 ← ARO |RO ← U(m)] ≤ ξSim (t, m) , where m is the output length of the random oracle. A ξSim -quantum simulator is a perfect quantum simulator for the random oracle if ξSim = 0. Theorem 4.5 ([Zha19]). O with the state register D is a perfect quantum simulator for the random oracle, where X OXYD = |x⟩⟨x|X ⊗ FD[x] CNOTD[x]Y FD[x] x∈X

is the oracle unitary defined in Section 2.3. Now we are ready to define the syntax of an extractor. Definition 4.6 (Quantum message extractor). A quantum message extractor E with query access to USim and UExt (both have the state register S) has the following syntax: 1. E.ExtMsg takes as input a commitment in register C, makes queries to USim and UExt , and outputs two registers M and Aux (which will be used for AltCheck). 2. E.AltCheck takes as input the opening in register O and the auxiliary information in register Aux, and outputs b = 0 or 1, indicating whether the sender gives a valid opening. We will write the above two procedures as (M, Aux) ← E.ExtMsgUSim (S),UExt (S) (C) and b ← E.AltCheck(O, Aux). Definition 4.7 (Extractability). A quantum state commitment scheme in the quantum random oracle model (1) (2) (3) (1) (ComRO , CheckRO ) is (ξExt , ξExt , ξExt )-extractable if there exist a ξExt -quantum simulator USim with state register S for the random oracle, a stateful oracle UExt with the same state register S, and a polynomial-time quantum message extractor E with query access to USim and UExt as in Theorem 4.6 such that the following holds: (2)

1. (UExt does not disturb the simulation.) For every integer m, ∥ [UExt , USim ] ∥2 ≤ ξExt (m), where m is the output length of the random oracle. 2. Two parallel USim oracles commute, and two parallel UExt oracles commute. 3. (E gives the only state that the adversary A can open to.) For every integer m, t, real numbers w1 , w2 ∈ [0, t] such that w1 + w2 ≤ t, t-query quantum adversary A with query access to USim and UExt such that TotalMass(A, USim ) ≤ w1 and TotalMass(A, UExt ) ≤ w2 , and unbounded quantum distinguisher D, p p 2 (3) Pr [SimWorld(A, D)] − Pr [ExtWorld(A, D)] ≤ ξExt (t, w1 , w2 , m) , where m is the output length of the random oracle, and the games SimWorld(A, D) and ExtWorld(A, D) are defined below: 20

•

SimWorld(A, D): (a) The game initializes the state register: S ← |⊥⟩. (b) The adversary generates a commitment: (C, E) ← AUSim (S),UExt (S) . (c) The adversary generates an opening: (O, E) ← AUSim (S),UExt (S) (E). (d) The game checks if the opening is valid: (b, M) ← CheckUSim (S) (C, O). (e) The game generates the output: If b = 0, output 0; otherwise, compute b′ ← D(M, E, S) and output b′ .

•

ExtWorld(A, D): (a) The game initializes the state register: S ← |⊥⟩. (b) The adversary generates a commitment: (C, E) ← AUSim (S),UExt (S) . (c) The game uses the extractor to extract the underlying message: (M, Aux) ← E.ExtMsgUSim (S),UExt (S) (C). (d) The adversary generates an opening: (O, E) ← AUSim (S),UExt (S) (E). (e) The game uses the alternative check to check if the opening is valid: b ← E.AltCheck(O, Aux). (f) The game generates the output: If b = 0, output 0; otherwise, compute b′ ← D(M, E, S) and output b′ .

21

5

Construction of extractable commitments to quantum states

5.1

An extractable basic succinct commitment scheme

In this work, we will use the following basic succinct commitment in the quantum random oracle model. This is essentially an idealization of the commitment scheme in [GJMZ23], with a cryptographic hash function replaced by its idealization, a random oracle RO. Construction 5.1. Let RO be sampled uniformly from all the functions with range {0, 1}m . We construct RO the oracle-aided circuit Cm,n as follows, where n is the length of the quantum message ρM . RO Cm,n (ρMA ): 1. Rename the first half of the ancilla qubits as Z1 , and the second half of the ancilla qubits as Z2 . 2. Compute the hash value in the standard basis: make a query URO : |x⟩ |y⟩ → |x⟩ |y ⊕ RO(x)⟩ with query register M and answer register Z1 . 3. Compute the hash value in the Hadamard basis. (a) Apply the Hadamard gate on each qubit of the register M. (b) Make a query URO : |x⟩ |y⟩ → |x⟩ |y ⊕ RO(x)⟩ with query register M and answer register Z2 . (c) Apply the Hadamard gate on each qubit of the register M. 4. Set C := Z1 Z2 and O := M.

Construction 5.2 (An extractable quantum state commitment). Let RO be sampled uniformly from all the functions with range {0, 1}m . (ComRO , CheckRO ) is a canonical quantum state commitment as defined RO in Theorem 4.1, where the ancilla register A is a 2m-qubit register, and the oracle-aided circuit Cm,n is instantiated as Theorem 5.1. Perfect correctness. This candidate construction in Theorem 5.2 is in the canonical form as Theorem 4.1. By Theorem 4.3, this candidate construction has perfect correctness.

5.2

Extractor for the commitment scheme

Let (ComRO , CheckRO ) be the quantum state commitment scheme in Theorem 5.2. We consider the following perfect quantum simulator for the random oracle X OXYD = |x⟩⟨x|X ⊗ FD[x] CNOTD[x]Y FD[x] , x∈X

which maintains some side information in register D during the simulation without disturbing any adversary’s execution. Let’s construct an extractor for (ComRO , CheckRO ) and the quantum simulator O(D). Our extractor will use the side information from the database register D. Let’s start with several setups. Recall that m is the output length of the random oracle and X is the set of possible query positions made by the adversary. Without loss of generality, we can assume X = {0, 1}n where n is the length of the quantum message. Let W := BM′ for a single-qubit register B and an n-qubit register M′ . For each y ∈ {0, 1}m , the (y) purified measurement MDW writes the first x ∈ X (if any) such that the image of x in D is y into the register M′ . Otherwise, it flips the flag register B. Namely, X (y) (y) x MDW := Σ(y) (4) x ⊗ X M′ + Σ ⊥ ⊗ X B , x∈X

22

(y)

where {Σx }x∈X∪{⊥} is the measurement on the database register D that outputs the first preimage x ∈ X (if any) of y and outputs ⊥ otherwise; in other words, for every x ∈ X,  O ′ := Σ(y) I − |y⟩⟨y| ⊗ |y⟩⟨y|D[x] , ′ D[x ] x D[x ] x′ <x

and

(y) Σ⊥ := ID −

X

Σ(y) . x

x∈X

The following lemma states that the oracle unitary OXYD almost commutes with the above purified (y) measurement MDW . Lemma 5.3 (Theorem 3.1 and Lemma 3.4 in [DFMS22]). For every y ∈ {0, 1}m and every operator V such that it acts only on D[x] within the database register D and it does not act on W, the purified measurement (y) MDW defined in Equation (4) almost commutes with V , as long as |y⟩⟨y|D[x] almost commutes with V : h i h i h i h i (y) (y) ∥ V, MDW ∥ ≤ 3∥ V, |y⟩⟨y|D[x] ∥ + ∥ V, Σ⊥ ∥ ≤ 4∥ V, |y⟩⟨y|D[x] ∥ . (y)

Besides, the purified measurement MDW almost commutes with the oracle unitary OXYD : i h √ (y) ∥ OXYD , MDW ∥ ≤ 8 2 · 2−m/2 . (y)

We can also use a value in a quantum register T as y, and do MDW coherently, as the unitary Inv: X (y) InvTDW := |y⟩⟨y|T ⊗ MDW .

(5)

y∈{0,1}m

Now we are ready to present the quantum message extractor E. Construction 5.4 (The extractor E). We consider the following E for (ComRO , CheckRO ) with query access to O(D) and Inv(D). E: 1. E.ExtMsg: Upon receiving a commitment in register C, E.ExtMsg does the following. (a) Parse C as Z1 and Z2 . (b) Initialize two n-qubit registers M1 and M2 in the zero state, and three single-qubit registers B, B1 and B2 in the zero state, and set working registers W1 := B1 M1 , W2 := B2 M2 . (c) Call InvZ2 DW2 and OM2 Z2 D . (d) Call InvZ1 DW1 and OM1 Z1 D . (e) Apply the Hadamard gate on each qubit of the register M2 . (f) Run CNOT on each qubit of the register M1 (as the control bit) and register M2 (as the target bit). (g) Set M := M1 and Aux := B1 B2 M2 Z1 Z2 . Output the state in registers M and Aux. 2. E.AltCheck: Upon receiving an opening in register O, E.AltCheck checks whether the state in registers O and Aux is 1 X |ψAltCheck ⟩ := p |0, 0, 0m , 0m , x, x⟩B1 B2 Z1 Z2 OM2 |X| x∈X and outputs b = 1 if so. Otherwise, output b = 0. 23

5.3

Analysis of the commitment scheme (1)

(2)

(3)

Theorem 5.5 (Extractability). Theorem 5.2 is (ξExt , ξExt , ξExt )-extractable with the quantum simulator O(D), the extractor oracle Inv(D), and the extractor E in Theorem 5.4 where (1)

ξExt := 0 , (2)

ξExt (m) := 2−m+7 , (3)

ξExt (t, w1 , w2 , m) := 2−m+14 (t + 2)2 (w1 + w2 + 3) . Define CNOTXX′ |⊥⟩ |y⟩ = |y⟩ |⊥⟩ (in case that at least one of X and X′ is |⊥⟩, do the swap unitary.) We first present a lemma that is used to prove Theorem 5.5. The following lemma basically says that the extractor can extract offline the message from the commitment (after the adversary produces the opening) as long as there is no collision during the process of E.ExtMsg and Check. To this end, we define a no-collision variant for an algorithm with access to O(D) and Inv(D). For every algorithm A with oracle access to O(D) and Inv(D), let ANoCollision denote the algorithm which has an additional query access that tells whether the database has a collision by making a projective measurement {ΠNoCol , ID − ΠNoCol }. ANoCollision does the same thing as A except that ANoCollision always makes a projective measurement {ΠNoCol , ID − ΠNoCol } (by issuing a query) before and after applying each unitary, and outputs a bit bNoCollision , indicating whether all of the measurement results say there is no collision (i.e. the result is O(D),Inv(D) ΠNoCol ), in addition to the original outputs. We omit the additional query access and write ANoCollision as the additional query access is clear from the context. Lemma 5.6. Let (ComRO , CheckRO ) be the quantum state commitment in Theorem 5.2, and E be the extractor in Theorem 5.4 with oracle access to O(D) and Inv(D) that works on an internal database register D. For every integer m, t, real numbers w1 , w2 ∈ [0, t] such that w1 + w2 ≤ t, t-query quantum adversary A such that TotalMass(A, O) ≤ w1 and TotalMass(A, Inv) ≤ w2 , and unbounded quantum distinguisher D, p p 2 √ Pr [SimWorld∗ (A, D)] − Pr [OffExtWorld∗ (A, D)] ≤ (12t + 16 + 32t w2 )2 · 2−m , where • m is the output length of the random oracle; • The game SimWorld∗ (A, D) is obtained by replacing the algorithm Check in the game SimWorld with the algorithm CheckNoCollision ; • The game OffExtWorld∗ (A, D) is obtained by doing extraction after the adversary outputs the openings, and replacing the algorithm E.ExtMsg by E.ExtMsgNoCollision in the game ExtWorld(A, D). Specifically, the followings are the formal definitions of the games SimWorld∗ (A, D) and OffExtWorld∗ (A, D): •

SimWorld∗ (A, D): 1. The game initializes the database register: D ← |⊥⟩. 2. The adversary generates a commitment: (C, E) ← AO(D),Inv(D) . 3. The adversary generates an opening: (O, E) ← AO(D),Inv(D) (E). O(D) 4. The game checks if the opening is valid: (bNoCollision , b, M) ← CheckNoCollision (C, O). 24

5. The game generates the output: If bNoCollision ∧ b = 0, output 0; otherwise, compute b′ ← D(M, E, D) and output b′ . •

OffExtWorld∗ (A, D): 1. The game initializes the database register: D ← |⊥⟩. 2. The adversary generates a commitment: (C, E) ← AO(D),Inv(D) . 3. The adversary generates an opening: (O, E) ← AO(D),Inv(D) (E). O(D),Inv(D) (C). 4. The game uses the extractor to extract the underlying message: (bNoCollision , M, Aux) ← E.ExtMsgNoCollision 5. The game uses the alternative check to check if the opening is valid: b ← E.AltCheck(O, Aux). 6. The game generates the output: If bNoCollision ∧ b = 0, output 0; otherwise, compute b′ ← D(M, E, D) and output b′ . The proof of Theorem 5.6 is deferred to Section 5.4. We first show how Theorem 5.6 implies Theorem 5.5.

Proof of Theorem 5.5. We use Zhandry’s compressed oracle O as the unitary USim to do the simulation and (1) use D as the state register S. By Theorem 4.5, O simulates the random oracle perfectly and thus ξExt = 0. We use the preimage-finding unitary Inv as the unitary UExt . By Theorem 5.3 and Equations (2) and (5), h i √ (y) ∥ [UExt , USim ] ∥2 ≤ max ∥ MDW , OXYD ∥2 ≤ (8 2 · 2−m/2 )2 = 2−m+7 , y

(2)

and thus ξExt (m) = 2−m+7 . By the definition of O and Inv, two O oracles commute, and two Inv oracles commute no matter which registers they act on. (3) To bound ξExt , we first introduce a new game OffExtWorld that does the extraction offline, where the difference between OffExtWorld and ExtWorld is highlighted in blue. OffExtWorld(A, D): 1. The game initializes the database register: D ← |⊥⟩. 2. The adversary generates a commitment: (C, E) ← AO(D),Inv(D) . 3. The adversary generates an opening: (O, E) ← AO(D),Inv(D) (E). 4. The game uses the extractor to extract the underlying message: (M, Aux) ← E.ExtMsgO(D),Inv(D) (C). 5. The game uses the alternative check to check if the opening is valid: b ← E.AltCheck(O, Aux). 6. The game generates the output: If b = 0, output 0; otherwise, compute b′ ← D(M, E, D) and output b′ . The only difference between OffExtWorld and ExtWorld is whether the adversary first generates the opening or the game first extracts the underlying message. As a result, for every t-query quantum adversary A and unbounded quantum distinguisher D, p p √ Pr [ExtWorld(A, D)] − Pr [OffExtWorld(A, D)] ≤ 4t · ∥ [UExt , USim ] ∥ ≤ 32 2 · t · 2−m/2 . (6) p p It remains to bound Pr [SimWorld(A, D)] − Pr [OffExtWorld(A, D)] . Then the only difference between SimWorld(A, D) and SimWorld∗ (A, D) is whether we check if there are collisions before and after each O(D) query in the algorithm Check. By Theorem 2.5, p p Pr [SimWorld(A, D)] − Pr [SimWorld∗ (A, D)] p ≤ 2 6(t + 2)2 (w1 + 2) · 2−m/2 , 25

(7)

since Check makes two queries to the random oracle. By the same reasoning, p p p Pr [OffExtWorld(A, D)] − Pr [OffExtWorld∗ (A, D)] ≤ 2 6(t + 2)2 (w1 + 2) · 2−m/2 ,

(8)

since E.ExtMsg makes two queries to the random oracle. Combining Equations (7) and (8) and Theorem 5.6, we can obtain p p Pr [SimWorld(A, D)] − Pr [OffExtWorld(A, D)] √ √ √ ≤ 4 6 · (t + 2) w1 + 2 · 2−m/2 + (12t + 16 + 32t w2 ) · 2−m/2 , which can be further combined with Equation (6) to get that p p Pr [SimWorld(A, D)] − Pr [ExtWorld(A, D)] √ √ √ ≤ 4 6 · (t + 2) w1 + 2 · 2−m/2 + (60t + 16 + 32t w2 ) · 2−m/2 , and therefore, (3)

ξExt (t, w1 , w2 , m) 2  √ √ √ ≤ 4 6 · (t + 2) w1 + 2 · 2−m/2 + (60t + 16 + 32t w2 ) · 2−m/2
≤ 2−m+2 96(t + 2)2 (w1 + 2) + 3600t2 + 256 + 1024t2 w2 (By Cauchy–Schwarz inequality) ≤ 2−m+14 (t + 2)2 (w1 + w2 + 3) .

5.4

Proof of Theorem 5.6

We need the following claims to prove Theorem 5.6. Q Let ΠNoHatZero := x (ID[x] − |0̂m ⟩⟨0̂m |D[x] ) be the projector that checks whether each point of the database register is set to be non-0̂m . Claim 5.7. For every query bound t, ∥Πt [ΠNoCol , ΠNoHatZero ] Πt ∥ ≤ 2−(m−3)/2 t , and

√ ∥Πt [InvTDW , ΠNoHatZero ] Πt ∥ ≤ 2−m/2+4 t . We defer the proof to Section 5.5.

Claim 5.8. ⊗n ⊗n ⊗n HM CNOTMM2 HM CNOTMM1 |0, 0⟩M1 M2 = HM CNOTM1 M2 SWAPM1 M |ϕEPR ⟩M1 M2 , 2

where |ϕEPR ⟩ := √1

|X|

P

z∈X |z, z⟩.

26

Proof. This equation can be shown by a direct computation. We omit the proof. Claim 5.9. Let W := BM′ . For every subnormalized state |ϕ⟩ on registers M, T, E and D, ∥ ⟨0|WT CNOTMM′ OM′ TD InvTDW |ϕ⟩MTED |0⟩W − ⟨0|T OMTD |ϕ⟩MTED ∥ 4 ≤√ + ∥(ID − ΠNoCol ) |ϕ⟩MTED ∥ + ∥(ID − ΠNoHatZero ) |ϕ⟩MTED ∥ . 2m Furthermore, for every subnormalized state |ψ⟩ on registers M, E and D, ∥ΠNoCol InvTDW OM′ TD CNOTMM′ |ψ⟩MED |0⟩WT − ΠNoCol OMTD |ψ⟩MED |0⟩WT ∥ √ 2 ≤√ + 2∥(ID − ΠNoHatZero ) |ψ⟩MED ∥ . 2m Proof. Let |θ⟩ := √12 (|⊥⟩ − |0̂m ⟩) be a normalized quantum state. By the definition of F , we can get that for 1 |θ⟩. each y ∈ {0, 1}m , F |y⟩ = |y⟩ + √ m−1 2 P We start with the first inequality. We write |ϕ⟩MTED := x∈X,y∈{0,1}m ,e,D αx,y,e,D |x, y, e, D⟩MTED . Then by the definition of Inv, we can compute InvTDW |ϕ⟩MTED |0⟩W according to whether y ∈ Im(D). Specifically,

InvTDW |ϕ⟩MTED |0⟩W X =

X

αx,y,e,D |x, y, e, D, 0, x′ ⟩MTEDBM′ +

x,e,x′ ,y,D s.t. D[x′ ]=y and ∀x′′ <x′ ,D[x′′ ]̸=y

αx,y,e,D |x, y, e, D, 1, 0⟩MTEDBM′ ,

x,e,D,y ∈Im(D) /

which implies X

⟨0|B InvTDW |ϕ⟩MTED |0⟩W =

αx,y,e,D |x, y, e, D, x′ ⟩MTEDM′ .

x,e,x′ ,y,D s.t. D[x′ ]=y and ∀x′′ <x′ ,D[x′′ ]̸=y

Moreover, X

⟨0|T OM′ TD

αx,y,e,D |x, y, e, D, x′ ⟩MTEDM′

x,e,x′ ,y,D s.t. D[x′ ]=y and ∀x′′ <x′ ,D[x′′ ]̸=y

=

X

|x′ , x, e⟩M′ ME

x′ ,x,e

=

X

X

αx,y,e,D ⟨0|T FD[x′ ] CNOTD[x′ ]T FD[x′ ] |y, D⟩TD

y,D s.t. D[x′ ]=y and ∀x′′ <x′ ,D[x′′ ]̸=y

|x′ , x, e⟩M′ ME

x′ ,x,e

=

X

X

αx,y,e,D ⟨0|T FD[x′ ] CNOTD[x′ ]T (|y⟩ + √

y,D s.t. D[x′ ]=y and ∀x′′ <x′ ,D[x′′ ]̸=y

|x′ , x, e⟩M′ ME

x′ ,x,e

X

1 2m−1

|θ⟩)D[x′ ] |y, D − x′ ⟩TD[X/{x′ }]

αx,y,e,D FD[x′ ] |D⟩D

y,D s.t. D[x′ ]=y and ∀x′′ <x′ ,D[x′′ ]̸=y

+√

1 2m−1

⟨0|T

X

FD[x′ ] CNOTD[x′ ]T αx,y,e,D |x′ , x, e⟩M′ ME |θ⟩D[x′ ] |y, D − x′ ⟩TD[X/{x′ }] .

x,e,x′ ,y,D s.t. D[x′ ]=y and ∀x′′ <x′ ,D[x′′ ]̸=y

27

Therefore, X

⟨0|M′ T CNOTMM′ OM′ TD

αx,y,e,D |x, y, e, D, x′ ⟩MTEDM′

x,e,x′ ,y,D s.t. D[x′ ]=y and ∀x′′ <x′ ,D[x′′ ]̸=y

=

X

X

|x, e⟩ME

x,e

+√

αx,y,e,D FD[x] |D⟩D

y,D s.t. D[x]=y and ∀x′′ <x,D[x′′ ]̸=y

1 2m−1

X

⟨0|T

αx,y,e,D FD[x] CNOTD[x]T |x, e⟩ME |θ⟩D[x] |y, D − x⟩TD[X/{x}] ,

x,e,y,D s.t. D[x]=y and ∀x′′ <x,D[x′′ ]̸=y

which implies X

∥ ⟨0|WT CNOTMM′ OM′ TD InvTDW |ϕ⟩MTED |0⟩W −

αx,y,e,D FD[x] |x, e, D⟩MED ∥

x,e,y,D s.t. D[x]=y and ∀x′′ <x,D[x′′ ]̸=y

1 ∥ ⟨0|T =√ 2m−1 1 ≤√ ∥ 2m−1

αx,y,e,D FD[x] CNOTD[x]T |x, e⟩ME |θ⟩D[x] |y, D − x⟩TD[X/{x}] ∥

x,e,y,D s.t. D[x]=y and ∀x′′ <x,D[x′′ ]̸=y

X

αx,y,e,D FD[x] CNOTD[x]T |x, e⟩ME |θ⟩D[x] |y, D − x⟩TD[X/{x}] ∥

x,e,y,D s.t. D[x]=y and ∀x′′ <x,D[x′′ ]̸=y

!

1

X

=√ ∥ 2m−1 1 ∥ =√ 2m−1

X

X

|x⟩⟨x|M ⊗ FD[x] CNOTD[x]T

x

αx,y,e,D |x, e⟩ME |θ⟩D[x] |y, D − x⟩TD[X/{x}] ∥

x,e,y,D s.t. D[x]=y ′′ ∧∀x <x,D[x′′ ]̸=y

X

αx,y,e,D |x, e, y, D − x⟩METD[X/{x}] ∥

x,e,y,D s.t. D[x]=y ∧∀x′′ <x,D[x′′ ]̸=y

v u u =√ u 2m−1 u t 1

X

|αx,y,e,D |2

x,e,y,D s.t. D[x]=y ∧∀x′′ <x,D[x′′ ]̸=y

P 1 . (By normalization, we have that x,y,e,D |αx,y,e,D |2 ≤ 1 for the subnormalized state |ϕ⟩.) ≤√ m−1 2 On the other hand, ⟨0|T OMTD |ϕ⟩MTED X X = |x, e⟩ME αx,y,e,D ⟨0|T FD[x] CNOTD[x]T FD[x] |y, D⟩TD x,e

=

X

y,D

|x, e⟩ME

x,e

+

X x,e

X

αx,y,e,D ⟨0|T FD[x] CNOTD[x]T FD[x] |y, D⟩TD

y,D s.t. D(x)=⊥

|x, e⟩ME

X

αx,y,e,D ⟨0|T FD[x] CNOTD[x]T FD[x] |y, D⟩TD

y,D s.t. D(x)=y

28

+

X

X

|x, e⟩ME

x,e

αx,y,e,D ⟨0|T FD[x] CNOTD[x]T FD[x] |y, D⟩TD

y,D s.t. D(x)̸=⊥ and D(x)̸=y

X 1 X αx,y,e,D FD[x] |y⟩D[x] |D⟩D[X/{x}] |x, e⟩ME =√ 2m x,e y,D s.t. D(x)=⊥   X X 1 αx,y,e,D FD[x] |D⟩D + √ + |x, e⟩ME ⟨0|T FD[x] CNOTD[x]T |y⟩T |θ⟩D[x] |D − x⟩D[X/{x}] 2m−1 x,e y,D s.t. D(x)=y X X 1 |x, e⟩ME αx,y,e,D ⟨0|T FD[x] CNOTD[x]T |y⟩T |θ⟩D[x] |D − x⟩D[X/{x}] , +√ 2m−1 x,e y,D s.t. D(x)̸=⊥ and D(x)̸=y which implies X

∥ ⟨0|T OMTD |ϕ⟩MTED −

αx,y,e,D FD[x] |x, e, D⟩MED ∥

x,e,y,D s.t. D[x]=y

X X 1 ≤√ ∥ |x, e⟩ME αx,y,e,D FD[x] |y⟩D[x] |D⟩D[X/{x}] ∥ 2m x,e y,D s.t. D(x)=⊥ X X 1 +√ ∥ |x, e⟩ME αx,y,e,D ⟨0|T FD[x] CNOTD[x]T |y⟩T |θ⟩D[x] |D − x⟩D[X/{x}] ∥ 2m−1 x,e y,D s.t. D(x)̸=⊥ X 1 1 1 ∥√ αx,y,e,D FD[x] |x, e⟩ME |y⟩D[x] |D − x⟩D[X/{x}] ∥ +√ ≤√ 2m 2m−1 2m+1 x,e,y,D s.t. D(x)̸=⊥ X 1 +√ ∥ αx,0,e,D FD[x] |x, e⟩ME |⊥⟩D[x] |D⟩D[X/{x}] ∥ 2m x,e,D s.t. D(x)̸=⊥ X 1 1 + m∥ αx,y,e,D |x, e⟩ME |y⟩D[x] |D − x⟩D[X/{x}] ∥ =√ 2m 2 x,e,y,D s.t. D(x)̸=⊥

1 αx,0,e,D |x, e⟩ME |D − x⟩D ∥ +√ ∥ 2m x,e,D s.t. D(x)̸=⊥ v u 2 u X X 1 1 u =√ + αx,y,e,D+[x7→z] t 2m 2m z X

x,e,y,D s.t. D(x)=⊥

! +∥

X

|x⟩⟨x|M ⊗ |0̂m ⟩⟨0̂m |D[x]

x

1 1 ≤√ + m m 2 2

X

αx,0,e,D |x, 0, e, D⟩MTED ∥

x,e,D

s

X

x,e,y,D s.t. D(x)=⊥

2m ·

X

αx,y,e,D+[x7→z]

2

+ ∥(ID − ΠNoHatZero ) |ϕ⟩MTED ∥

z

2 ≤√ + ∥(ID − ΠNoHatZero ) |ϕ⟩MTED ∥ . 2m Therefore, we have that ∥ ⟨0|WT CNOTMM′ OM′ TD InvTDW |ϕ⟩MTED |0⟩W − ⟨0|T OMTD |ϕ⟩MTED ∥ 4 ≤√ + ∥(ID − ΠNoHatZero ) |ϕ⟩MTED ∥ 2m 29

+∥

X

X

αx,y,e,D FD[x] |x, e, D⟩MED −

x,e,y,D s.t. D[x]=y

αx,y,e,D FD[x] |x, e, D⟩MED ∥

x,e,y,D s.t. D[x]=y and ∀x′′ <x,D[x′′ ]̸=y

X 4 αx,y,e,D |x, e, D⟩MED ∥ + ∥(ID − ΠNoHatZero ) |ϕ⟩MTED ∥ + ∥ =√ 2m x,e,y,D s.t. D[x]=y and ∃x′′ <x,D[x′′ ]=y

v X u 4 =√ + ∥(ID − ΠNoHatZero ) |ϕ⟩MTED ∥ + u |αx,y,e,D |2 . u 2m t x,e,y,D s.t. D[x]=y and ∃x′′ <x,D[x′′ ]=y

Recall that |ϕ⟩MTED :=

P

x∈X,y∈{0,1}m ,e,D αx,y,e,D |x, y, e, D⟩MTED . We can get that

X

∥(ID − ΠNoCol ) |ϕ⟩MTED ∥2 =

|αx,y,e,D |2 .

x,y,e,D∈S / NoCollision

Thus by the non-negativity of each |αx,y,e,D |, ∥ ⟨0|WT CNOTMM′ OM′ TD InvTDW |ϕ⟩MTED |0⟩W − ⟨0|T OMTD |ϕ⟩MTED ∥ 4 + ∥(ID − ΠNoCol ) |ϕ⟩MTED ∥ + ∥(ID − ΠNoHatZero ) |ϕ⟩MTED ∥ . ≤√ 2m We now prove the second inequality. Define |ψ0 ⟩ :=ΠNoCol OMTD |ψ⟩MED |0⟩WT , |ψ1 ⟩ :=ΠNoCol InvTDW OM′ TD CNOTMM′ |ψ⟩MED |0⟩WT =ΠNoCol InvTDW CNOTMM′ OMTD |ψ⟩MED |0⟩WT =InvTDW CNOTMM′ |ψ0 ⟩ , where we use that copying the value in M and querying M′ is equivalent to querying M and then performing the copy because M′ is initialized as all-zero states. We show that to bound the left hand side of the Psecond inequality, which equals ∥ |ψ0 ⟩ − |ψ1 ⟩ ∥, it suffices to bound the error ∥Π̸= |ψ0 ⟩ ∥, where Π̸= := x,y,D s.t. D[x]̸=y |x, y, D⟩⟨x, y, D|MTD projects to the bad branches such that D[x] ̸= y after making the query OMTD where T is initialized as all-zero states. P This is because, for |ψ0 ⟩ := x,y,e,D∈SNoCollision αx,y,e,D |x, y, e, D⟩MTED |0⟩W , X

|ψ1 ⟩ = InvTDW CNOTMM′ |ψ0 ⟩ =

αx,y,e,D |x, y, e, D⟩MTED |g(x, y, D)⟩W ,

x,y,e,D∈SNoCollision

for a classical function g such that g(x, y, D) = 0 if and only if D[x] = y. Thus X ∥ |ψ1 ⟩ − |ψ0 ⟩ ∥ = ∥ αx,y,e,D |x, y, e, D⟩MTED (|g(x, y, D)⟩W − |0⟩W )∥ x,y,e,D∈SNoCollision

= =

√ √

X

2∥

αx,y,e,D |x, y, e, D⟩MTED ∥

x,y,e,D∈SNoCollision s.t. g(x,y,D)̸=0

2∥Π̸= |ψ0 ⟩ ∥ . 30

Intuitively, the error ∥Π̸= |ψ0 ⟩ ∥ should be small because T is initialized as 0, and after making a query, it should store D[x]. This can be shown by direct calculation. We decompose the input as |ψ⟩ = ΠNoHatZero |ψ⟩ + (ID − ΠNoHatZero ) |ψ⟩. Then ∥Π̸= |ψ0 ⟩ ∥ = ∥Π̸= ΠNoCol OMTD |ψ⟩MED |0⟩WT ∥ ≤ ∥Π̸= OMTD |ψ⟩MED |0⟩T ∥ ≤ ∥Π̸= OMTD ΠNoHatZero |ψ⟩MED |0⟩T ∥ + ∥Π̸= OMTD (ID − ΠNoHatZero ) |ψ⟩MED |0⟩T ∥ X ≤ ∥Π̸= FD |x⟩⟨x|M ⊗ CNOTD[x]T FD ΠNoHatZero |ψ⟩MED |0⟩T ∥ + ∥(ID − ΠNoHatZero ) |ψ⟩MED ∥ . x

P We write the state FD ΠNoHatZero |ψ⟩MED = x,e,f αx,e,f |x, e, f ⟩MED . Here f does not contain ⊥ on any location since the state before applying FD is supported over ΠNoHatZero . We bound the first term in the above inequality: X ∥Π̸= FD |x⟩⟨x|M ⊗ CNOTD[x]T FD ΠNoHatZero |ψ⟩MED |0⟩T ∥ x

= ∥Π̸= FD

X

αx,e,f |x, e, f ⟩MED |f [x]⟩T ∥

x,e,f

= ∥Π̸=

X

αx,e,f FD[x] |x, e, f ⟩MED |f [x]⟩T ∥

x,e,f

= ∥Π̸=

X

αx,e,f |x, e, f − x⟩MED[X/{x}] (|f (x)⟩ + √

x,e,f

=√ ≤√

1 2m−1 1 2m−1

∥Π̸=

X

1 2m−1

|θ⟩)D[x] |f [x]⟩T ∥

αx,e,f |x, e, f − x⟩MED[X/{x}] |θ⟩D[x] |f [x]⟩T ∥

x,e,f

.

The second inequality of this claim follows from the above equations. ⊗n ⊗n Claim 5.10. Define VCheck := ΠNoCol OMZ1 D ΠNoCol HM OMZ2 D ΠNoCol HM to be the operation that CheckNoCollision 2m does, and define |ψCheck ⟩ := |0 ⟩Z1 Z2 to be the state that CheckNoCollision projects onto to see if the opening is valid. ⊗n Define VExtMsg := SWAPM1 M CNOTM1 M2 HM ΠNoCol OM1 Z1 D ΠNoCol InvZ1 DW1 OM2 Z2 D ΠNoCol InvZ2 DW2 2 to be the operation that NoCollision does (SWAPM1 M is just for renaming the registers), and define P E.ExtMsgm |ψAltCheck ⟩ := √1 |0, 0, 0 , 0m , x, x⟩B1 B2 Z1 Z2 M1 M2 to be the state that E.ExtMsgNoCollision projects x∈X |X|

onto to see if the opening is valid. Then for every subnormalized state |ϕ⟩CODE , ∥(⟨ψCheck | VCheck − ⟨ψAltCheck | VExtMsg |0⟩W1 W2 ) |ϕ⟩CODE ∥ 8 ≤√ + ∥(ID − ΠNoHatZero ) |ϕ1 ⟩ ∥ + ∥(ID − ΠNoHatZero ) |ϕ2 ⟩ ∥ , 2m ⊗n ⊗n ⊗n where |ϕ1 ⟩ := ΠNoCol HM OMZ2 D ΠNoCol HM |ϕ⟩CODE and |ϕ2 ⟩ := ΠNoCol HM |ϕ⟩CODE .

31

Furthermore, for every subnormalized state |ψ⟩MED , † † ∥(VCheck |ψCheck ⟩ |0⟩W1 W2 − VExtMsg |ψAltCheck ⟩) |ψ⟩MED ∥ √ √ 4 ≤√ + 2∥(ID − ΠNoHatZero ) |ψ1 ⟩ ∥ + 2∥(ID − ΠNoHatZero ) |ψ2 ⟩ ∥ , 2m ⊗n where |ψ1 ⟩ := HM ΠNoCol OMZ1 D ΠNoCol |ψ⟩MED |ψCheck ⟩ and |ψ2 ⟩ := ΠNoCol |ψ⟩MED .

Proof. For the first inequality, invoking Theorem 5.9 on the subnormalized state |ϕ1 ⟩, we obtain that ∥ ⟨0|W1 Z1 CNOTMM1 OM1 Z1 D InvZ1 DW1 |ϕ1 ⟩ |0⟩W1 − ⟨0|Z1 OMZ1 D |ϕ1 ⟩ ∥ 4 ≤√ + ∥(ID − ΠNoCol ) |ϕ1 ⟩ ∥ + ∥(ID − ΠNoHatZero ) |ϕ1 ⟩ ∥ 2m 4 =√ + ∥(ID − ΠNoHatZero ) |ϕ1 ⟩ ∥ , 2m

(9)

where W1 := (M1 , B1 ), M := O, and (Z1 , Z2 ) := C. Notice that by the definition of VCheck and |ψCheck ⟩, ⟨ψCheck | VCheck |ϕ⟩CODE = ⟨0|Z2 ⟨0|Z1 ΠNoCol OMZ1 D |ϕ1 ⟩ . By Equation (9) and the triangle inequality, ∥ ⟨0|W1 Z1 Z2 ΠNoCol CNOTMM1 OM1 Z1 D InvZ1 DW1 |ϕ1 ⟩ |0⟩W1 − ⟨ψCheck | VCheck |ϕ⟩CODE ∥ 4 + ∥(ID − ΠNoHatZero ) |ϕ1 ⟩ ∥ . ≤√ 2m

(10)

Again invoking Theorem 5.9 on the subnormalized state |ϕ2 ⟩, we obtain that ∥ ⟨0|W2 Z2 CNOTMM2 OM2 Z2 D InvZ2 DW2 |ϕ2 ⟩ |0⟩W2 − ⟨0|Z2 OMZ2 D |ϕ2 ⟩ ∥ 4 + ∥(ID − ΠNoCol ) |ϕ2 ⟩ ∥ + ∥(ID − ΠNoHatZero ) |ϕ2 ⟩ ∥ ≤√ 2m 4 ≤√ + ∥(ID − ΠNoHatZero ) |ϕ2 ⟩ ∥ , 2m

(11)

where W2 := (M2 , B2 ). ⊗n Notice that |ϕ1 ⟩ = ΠNoCol HM OMZ2 D |ϕ2 ⟩. By Equation (11) and the triangle inequality, ⊗n ∥ ⟨0|W2 Z2 ΠNoCol HM CNOTMM2 OM2 Z2 D InvZ2 DW2 |ϕ2 ⟩ |0⟩W2 − ⟨0|Z2 |ϕ1 ⟩ ∥ 4 + ∥(ID − ΠNoHatZero ) |ϕ2 ⟩ ∥ . ≤√ 2m

Equations (10) and (12) imply that ′ ∥ ⟨ψCheck | VCheck |ϕ⟩CODE − ⟨0|W1 W2 Z1 Z2 VCheck |ϕ⟩CODE |0⟩W1 W2 ∥ 8 ≤√ + ∥(ID − ΠNoHatZero ) |ϕ1 ⟩ ∥ + ∥(ID − ΠNoHatZero ) |ϕ2 ⟩ ∥ , 2m

32

(12)

⊗n ⊗n ′ := ΠNoCol CNOTMM1 OM1 Z1 D InvZ1 DW1 ΠNoCol HM . CNOTMM2 OM2 Z2 D InvZ2 DW2 ΠNoCol HM where VCheck ′ It remains to show that ⟨0|W1 W2 Z1 Z2 VCheck |0⟩W1 W2 = ⟨ψAltCheck | VExtMsg |0⟩W1 W2 . We use Theorem 5.8 to prove the above equation. Let W := (W1 , W2 ). ′ ⟨0|W1 W2 Z1 Z2 VCheck |0⟩W ⊗n ⊗n |0⟩W CNOTMM2 OM2 Z2 D InvZ2 DW2 ΠNoCol HM = ⟨0|W1 W2 Z1 Z2 ΠNoCol CNOTMM1 OM1 Z1 D InvZ1 DW1 ΠNoCol HM ⊗n ⊗n OM1 Z1 D InvZ1 DW1 ΠNoCol OM2 Z2 D InvZ2 DW2 ΠNoCol |0⟩W CNOTMM2 HM = ⟨0|W1 W2 Z1 Z2 ΠNoCol CNOTMM1 HM ⊗n = ⟨ϕEPR |M1 M2 ⟨0|B1 B2 Z1 Z2 SWAPM1 M CNOTM1 M2 HM ΠNoCol OM1 Z1 D ΠNoCol InvZ1 DW1 OM2 Z2 D ΠNoCol InvZ2 DW2 |0⟩W 2

= ⟨ψAltCheck | VExtMsg |0⟩W ,

(Definitions of |ψAltCheck ⟩ and VExtMsg )

where we use the commutativity of unitaries on different registers, and the commutativity of ΠNoCol and Inv. The second inequality follows similarly by invoking Theorem 5.9 on the states |ψ1 ⟩ and |ψ2 ⟩. Now we are ready to prove Theorem 5.6. Proof of Theorem 5.6. By the triangle inequality, p p 2 Pr [SimWorld∗ (A, D)] − Pr [OffExtWorld∗ (A, D)] ≤ ∥(⟨ψCheck | VCheck − ⟨ψAltCheck | VExtMsg |0⟩W1 W2 ) |ϕ⟩CODE ∥2 , where |ϕ⟩CODE is the joint state after the adversary provides the opening. By Theorem 5.10, ∥(⟨ψCheck | VCheck − ⟨ψAltCheck | VExtMsg |0⟩W1 W2 ) |ϕ⟩CODE ∥ 8 + ∥(ID − ΠNoHatZero ) |ϕ1 ⟩ ∥ + ∥(ID − ΠNoHatZero ) |ϕ2 ⟩ ∥ , ≤√ 2m ⊗n ⊗n ⊗n where |ϕ1 ⟩ := ΠNoCol HM OMZ2 D ΠNoCol HM |ϕ⟩CODE and |ϕ2 ⟩ := ΠNoCol HM |ϕ⟩CODE . We bound the term ∥(ID − ΠNoHatZero ) |ϕ1 ⟩ ∥. Notice that |ϕ⟩CODE has database size at most t,

∥(ID − ΠNoHatZero ) |ϕ1 ⟩ ∥ = ∥(ID − ΠNoHatZero )Πt+1 |ϕ1 ⟩ ∥ ≤ 2∥Πt+1 [ΠNoCol , ΠNoHatZero ] Πt+1 ∥ + ∥(ID − ΠNoHatZero ) |ϕ⟩CODE ∥ ≤ 2(t + 1) · 2−(m−3)/2 + ∥(ID − ΠNoHatZero ) |ϕ⟩CODE ∥ . Similarly, ∥(ID − ΠNoHatZero ) |ϕ2 ⟩ ∥ = ∥(ID − ΠNoHatZero )Πt+1 |ϕ2 ⟩ ∥ ≤ ∥Πt [ΠNoCol , ΠNoHatZero ] Πt ∥ + ∥(ID − ΠNoHatZero ) |ϕ⟩CODE ∥ ≤ t · 2−(m−3)/2 + ∥(ID − ΠNoHatZero ) |ϕ⟩CODE ∥ . Furthermore, as the error for (ID − ΠNoHatZero ) only accumulates when the adversary queries Inv, ∥(ID − ΠNoHatZero ) |ϕ⟩CODE ∥ 33

(13)

≤

X

∥Πt [InvTDW , ΠNoHatZero ] Πt ∥

p mass(A, Inv, i)

i∈[t]

√s X mass(A, Inv, i) ≤ 2−m/2+4 t t i∈[t] −m/2+4

≤2

·t·

√

w2 .

Combining the above inequalities, we obtain ∥(⟨ψCheck | VCheck − ⟨ψAltCheck | VExtMsg |0⟩W1 W2 ) |ϕ⟩CODE ∥ √ ≤ (12t + 16 + 32t w2 ) · 2−m/2 .

(14)

Then the claim follows from Equation (13).

5.5

Proof of Theorem 5.7

We first prove a bound for a more general operator A. Claim 5.11. For an operator A, if A = A† , and for every x ∈ X, A commutes with |⊥⟩⟨⊥|D[x] , then the following inequality holds: √
∥Πt [ΠNoHatZero , A] Πt ∥ ≤ 2 t max ∥Πt I − |0̂m ⟩⟨0̂m | D[x] A |0̂m ⟩⟨0̂m |D[x] Πt ∥ . x∈X

Proof. To bound ∥Πt [ΠNoHatZero , A] Πt ∥, it suffices to bound ∥Πt ΠNoHatZero A (I − ΠNoHatZero ) Πt ∥ because by the triangle inequality, ∥Πt [ΠNoHatZero , A] Πt ∥ ≤∥Πt ΠNoHatZero A (I − ΠNoHatZero ) Πt ∥ + ∥Πt (−I + ΠNoHatZero ) AΠNoHatZero Πt ∥ =∥Πt ΠNoHatZero A (I − ΠNoHatZero ) Πt ∥ + ∥Πt ΠNoHatZero A† (I − ΠNoHatZero ) Πt ∥ =2∥Πt ΠNoHatZero A (I − ΠNoHatZero ) Πt ∥ .

N I z[x]+1 I − |⊥⟩⟨⊥| We define a family of projectors ∆z := for each vector x∈X 2 + (−1) 2 D[x] X z ∈ {0, 1} . That is, ∆z projects onto |⊥⟩⟨⊥| on the registers D[x] when z[x] = 0, and projects onto I − |⊥⟩⟨⊥| otherwise. Then {∆z }z is in fact a measurement, where the outcome z indicates the locations where the database is non-empty. We observe that ΠNoHatZero commutes with ∆z , and in addition, since A commutes with |⊥⟩⟨⊥|D[x] for every x ∈ X, A commutes with ∆z , for each z ∈ {0, 1}X . As a result, ∥Πt ΠNoHatZero A (I − ΠNoHatZero ) Πt ∥ X =∥ ∆z Πt ΠNoHatZero A (I − ΠNoHatZero ) Πt ∆z ′ ∥ z,z ′ ∈{0,1}X

=∥

X

∆z ∆z ′ Πt ΠNoHatZero A (I − ΠNoHatZero ) Πt ∥

z,z ′ ∈{0,1}X

=∥

X

∆z ∆z Πt ΠNoHatZero A (I − ΠNoHatZero ) Πt ∥

z∈{0,1}X

34

X

=∥

∆z Πt ΠNoHatZero A (I − ΠNoHatZero ) Πt ∆z ∥

z∈{0,1}X

≤ max ∥∆z Πt ΠNoHatZero A (I − ΠNoHatZero ) Πt ∆z ∥ z∈{0,1}X

=

max

z∈{0,1}X s.t. hm(z)≤t

∥∆z Πt ΠNoHatZero A (I − ΠNoHatZero ) Πt ∆z ∥

(15)

where we use Equation (1), and the fact that for z with Hamming weight more than t, ∆z Πt = 0. Now let’s bound ∥∆z Πt ΠNoHatZero A (I − ΠNoHatZero ) Πt ∆z ∥. For z with Hamming weight hm (z) ≤ t, and every normalized state |ϕ⟩, we can write (I − ΠNoHatZero ) Πt ∆z |ϕ⟩ in the following form hm(z)

(I − ΠNoHatZero ) Πt ∆z |ϕ⟩ =

X

αi |0̂m ⟩D[xi ] |ϕi ⟩D[xi ]

i=1

where xi is the ith element in X such that z[x] = 1, D[xi ] is all the registers excluding D[xi ], and |0̂m ⟩D[xi ] |ϕi ⟩D[xi ] are orthonormal states. Plug (I − ΠNoHatZero ) Πt ∆z |ϕ⟩ into the following, and we can get that ∥∆z Πt ΠNoHatZero A (I − ΠNoHatZero ) Πt ∆z |ϕ⟩ ∥ =∥∆z Πt ΠNoHatZero AΠt (I − ΠNoHatZero ) Πt ∆z |ϕ⟩ ∥ hm(z)

≤

X

|αi | ∥Πt ΠNoHatZero AΠt |0̂m ⟩D[xi ] |ϕi ⟩D[xi ] ∥

i=1 hm(z)

=

X

|αi | ∥ΠNoHatZero Πt AΠt |0̂m ⟩⟨0̂m |D[xi ] |ϕi ⟩D[xi ] |0̂m ⟩D[xi ] ∥

i=1 hm(z)

≤

X

|αi | ∥ I − |0̂m ⟩⟨0̂m | D[x ] Πt AΠt |0̂m ⟩⟨0̂m |D[xi ] |ϕi ⟩D[xi ] |0̂m ⟩D[xi ] ∥ i

i=1



hm(z)

≤

X i=1


|αi | max ∥Πt I − |0̂m ⟩⟨0̂m | D[x] A |0̂m ⟩⟨0̂m |D[x] Πt ∥ x∈X

√
≤ t max ∥Πt I − |0̂m ⟩⟨0̂m | D[x] A |0̂m ⟩⟨0̂m |D[x] Πt ∥ , x∈X

where the last inequality is due to Cauchy-Schwarz, hm (z) ≤ t and ∥ (I − ΠNoHatZero ) Πt ∆z |ϕ⟩ ∥ ≤ 1. Combining Equation (15) and the above inequality, we get Theorem 5.11. Both ΠNoCol and Inv commute with |⊥⟩⟨⊥|D[x] for every x ∈ X, and thus Theorem 5.7 follows from Theorem 5.11 and the following two claims. Claim 5.12. For every x ∈ X and every query bound t, √
∥Πt I − |0̂m ⟩⟨0̂m | D[x] ΠNoCol |0̂m ⟩⟨0̂m |D[x] Πt ∥ ≤ 2−(m−1)/2 t .

35

Proof. For every normalized state |ϕ⟩, we can write |0̂m ⟩⟨0̂m |D[x] Πt |ϕ⟩ in the following form X X 1 αD[X/{x}] |D[X/{x}]⟩D[X/{x}] . |y⟩D[x] |0̂m ⟩⟨0̂m |D[x] Πt |ϕ⟩ = √ 2m y∈{0,1}m D[X/{x}] has size at most t − 1 Notice that
∥Πt I − |0̂m ⟩⟨0̂m | D[x] ΠNoCol |0̂m ⟩⟨0̂m |D[x] Πt |ϕ⟩ ∥
≤∥ I − |0̂m ⟩⟨0̂m | D[x] ΠNoCol |0̂m ⟩⟨0̂m |D[x] Πt |ϕ⟩ ∥ q = ∥ΠNoCol |0̂m ⟩⟨0̂m |D[x] Πt |ϕ⟩ ∥2 − ∥ ⟨0̂m |D[x] ΠNoCol |0̂m ⟩⟨0̂m |D[x] Πt |ϕ⟩ ∥2 To bound ∥ΠNoCol |0̂m ⟩⟨0̂m |D[x] Πt |ϕ⟩ ∥2 , we plug in |0̂m ⟩⟨0̂m |D[x] Πt |ϕ⟩ to get that ∥ΠNoCol |0̂m ⟩⟨0̂m |D[x] Πt |ϕ⟩ ∥2 X X 1 =∥ΠNoCol √ |y⟩D[x] αD[X/{x}] |D[X/{x}]⟩D[X/{x}] ∥2 2m y∈{0,1}m D[X/{x}] has size at most t − 1 X X 1 =∥ √ αD[X/{x}] |y⟩D[x] |D[X/{x}]⟩D[X/{x}] ∥2 2m D[X/{x}] has size at most t − 1 y∈{0,1}m and y ∈D[X/{x}] / and it doesn’t have collisions

X

=

D[X/{x}] has size at most t − 1 and it doesn’t have collisions y∈{0,1}m and y ∈D[X/{x}] /

X

≤

1 2 α 2m D[X/{x}]

αD[X/{x}]

2

D[X/{x}] has size at most t − 1 and it doesn’t have collisions

Similarly, ∥ ⟨0̂m |D[x] ΠNoCol |0̂m ⟩⟨0̂m |D[x] Πt |ϕ⟩ ∥2 X X 1 =∥ ⟨0̂m |D[x] √ αD[X/{x}] |y⟩D[x] |D[X/{x}]⟩D[X/{x}] ∥2 2m D[X/{x}] has size at most t − 1 y∈{0,1}m and y ∈D[X/{x}] / and it doesn’t have collisions 2

=

X

αD[X/{x}]

y∈{0,1}m and y ∈D[X/{x}] /

D[X/{x}] has size at most t − 1 and it doesn’t have collisions

≥

X D[X/{x}] has size at most t − 1 and it doesn’t have collisions

X

αD[X/{x}]

2

1 2m

  t 2 1− m . 2

As a result, for any normalized state |ϕ⟩,
∥Πt I − |0̂m ⟩⟨0̂m | D[x] ΠNoCol |0̂m ⟩⟨0̂m |D[x] Πt |ϕ⟩ ∥ q ≤ ∥ΠNoCol |0̂m ⟩⟨0̂m |D[x] Πt |ϕ⟩ ∥2 − ∥ ⟨0̂m |D[x] ΠNoCol |0̂m ⟩⟨0̂m |D[x] Πt |ϕ⟩ ∥2 36

v u ≤u t

s X

αD[X/{x}]

2

·

D[X/{x}] has size at most t − 1 and it doesn’t have collisions



t 1− 1− m 2

2

√ ≤2−(m−1)/2 t , which by definition, implies

√
∥Πt I − |0̂m ⟩⟨0̂m | D[x] ΠNoCol |0̂m ⟩⟨0̂m |D[x] Πt ∥ ≤ 2−(m−1)/2 t .

Claim 5.13. For every x ∈ X and every query bound t,
∥Πt I − |0̂m ⟩⟨0̂m | D[x] InvTDW |0̂m ⟩⟨0̂m |D[x] Πt ∥ ≤ 2−m/2+3 . Proof. Recall that InvTDW =

(y)

X

|y⟩⟨y|T ⊗ MDW

y∈{0,1}m

is a controlled unitary. By Equation (2), h i ∥ InvTDW , |0̂m ⟩⟨0̂m |D[x] ∥ ≤

h i (y) max ∥ MDW , |0̂m ⟩⟨0̂m |D[x] ∥ .

y∈{0,1}m

For every y ∈ {0, 1}m , since |0̂m ⟩⟨0̂m |D[x] only acts on D[x] within the database register D, by Theorem 5.3, h i h i (y) ∥ MDW , |0̂m ⟩⟨0̂m |D[x] ∥ ≤ 4∥ |y⟩⟨y|D[x] , |0̂m ⟩⟨0̂m |D[x] ∥ ≤ 2−m/2+3 . Therefore, InvTDW and |0̂m ⟩⟨0̂m |D[x] almost commute with each other, h i ∥ InvTDW , |0̂m ⟩⟨0̂m |D[x] ∥ ≤ 2−m/2+3 .
Now we are ready to bound ∥Πt I − |0̂m ⟩⟨0̂m | D[x] InvTDW |0̂m ⟩⟨0̂m |D[x] Πt ∥.
∥Πt I − |0̂m ⟩⟨0̂m | D[x] InvTDW |0̂m ⟩⟨0̂m |D[x] Πt ∥
≤∥ I − |0̂m ⟩⟨0̂m | D[x] InvTDW |0̂m ⟩⟨0̂m |D[x] ∥ i
h
≤∥ I − |0̂m ⟩⟨0̂m | D[x] |0̂m ⟩⟨0̂m |D[x] InvTDW ∥ + ∥ I − |0̂m ⟩⟨0̂m | D[x] InvTDW , |0̂m ⟩⟨0̂m |D[x] ∥ h i ≤∥ InvTDW , |0̂m ⟩⟨0̂m |D[x] ∥ ≤2−m/2+3 .

37

6

Defining extractable quantum state vector commitments

We define the syntax of quantum state vector commitments, and then provide a formal definition for extractable quantum state vector commitments.

6.1

Syntax for quantum state vector commitments

We consider non-interactive quantum state vector commitments in the quantum random oracle setting. Definition 6.1 (Quantum state vector commitments in the QROM). In the quantum random oracle model, a non-interactive quantum state vector commitment (QVC) for block size s and message length n is a tuple of polynomial-time oracle-aided quantum algorithms QSVC = (Com, Open, Query, Update, Recover) where • QSVC.ComRO (1λ , M) → (C, T): QSVC.ComRO has oracle access to RO and is given as inputs the security parameter 1λ and a n · s-qubit quantum state on the register M, which might entangle with the register E. It outputs a state on two registers C and T. The register C will be sent to the receiver in the commitment phase and the register T contains necessary information for the local opening in the open phase. • QSVC.OpenRO (1λ , Q, T) → (O, R): To open the commitment on positions Q ⊆ {1, 2, . . . , n}, QSVC.OpenRO , with oracle access to RO, takes the security parameter 1λ , the query set Q, and a state on T as inputs, and outputs a state on registers (O, R). The state in register O is interpreted as the opening and will be sent to the receiver for local decommitment, and R contains the unused part in the register T. • QSVC.QueryRO (1λ , Q, C, O, Y) → (b, C, O, Y): To make a query to the message, QSVC.QueryRO , with oracle access to RO, takes as inputs the security parameter 1λ , the query set Q ⊆ {1, 2, · · · , n}, and a state on registers (C, O, Y). It first checks the validity of the opening and outputs a bit b to indicate whether the decommitment is valid. If it is valid, it recovers the quantum message on positions Q, and swaps it with the register Y, then it does the reverse to get a new state on registers (C, O), and outputs a state on registers (C, O, Y) together with the validity bit b. • QSVC.UpdateRO (1λ , Q, O, R) → T: QSVC.UpdateRO , with oracle access to RO, takes as inputs the security parameter 1λ , a query set Q, and a state on registers (O, R), and reorganizes the states according to Q to erase the information about Q. It outputs a state on the register T. • QSVC.RecoverRO (1λ , C, T) → (b, M): To recover the messages, QSVC.RecoverRO , with oracle access to RO, takes as inputs the security parameter 1λ and a state on two registers (C, T). It outputs a validity bit b and a state on the register M, which is supposed to be the updated message after the queries. We slightly overload the notations QSVC.Open, QSVC.Query, and QSVC.Update to also denote the corresponding coherent implementations when the query set is provided in the register Q. In particular, we write (Q, O, R) ← QSVC.OpenRO (1λ , Q, T), (b, Q, C, O, Y) ← QSVC.QueryRO (1λ , Q, C, O, Y), and (Q, T) ← QSVC.UpdateRO (1λ , Q, O, R) for the coherent implementations. When it is clear from the context, we sometimes omit the security parameter λ. The vector commitment QSVC should satisfy the following correctness and efficiency requirements. Perfect correctness. An honest sender should be able to produce a valid decommitment for every part of the quantum message and recover the updated message after the queries. Namely, for every integer λ, s, function

38

RO with output length m, unbounded quantum adversary A, and unbounded quantum distinguisher D,   (M, E, Q, Y) ← ARO   (C, T) ← QSVC.ComRO (1λ , M)   RO λ   (Q, O, R) ← QSVC.Open (1 , Q, T)  RO  RO λ (1 , Q, C, O, Y)  Pr  D (b, M, E, Q, Y) (b1 , Q, C, O, Y) ← QSVC.Query  RO λ , Q, O, R)   (Q, T) ← QSVC.Update (1   RO λ   (b2 , M) ← QSVC.Recover (1 , C, T) b := b1 ∧ b2   (M, E, Q, Y) ← ARO RO = Pr D (1, M, E, Q, Y) , (Q, M, Y) ← U qry (Q, M, Y) where the random oracle output length m is a function of the security parameter λ specified by the scheme, and we slightly abuse notation by overloading U qry to also denote the unitary that, controlled on Q, swaps Y with the corresponding subsets of the message register M (i.e., a parallel application of the unitary U qry from Section 3.2). Local opening. For a vector commitment scheme to be non-trivial, we require that the sizes of C and O grow much slower than the message length. To be more specific, the size of C is poly(λ), and the size of O is poly(|Q| , log n, λ).

6.2

The extractability definition

Now we’re ready to define the extractability for quantum state vector commitments. The syntax of a quantum state vector commitment is different from the syntax for the basic quantum state commitment. Definition 6.2 (Quantum message extractor). A quantum message extractor E for a quantum state vector commitment scheme with query access to USim and UExt (both have the state register S) has the following syntax: 1. E.ExtMsgUSim (S),UExt (S) (C) → (M, Aux): E.ExtMsg takes as inputs a commitment in register C, makes queries to USim and UExt , and outputs a quantum state on two registers M and Aux (which will be used for AltCheck). 2. E.AltCheck(Q, O, Aux) → (b, O, Aux): E.AltCheck takes as inputs the query set Q, the opening in register O, and the auxiliary information in register Aux, and outputs b = 0 or 1, indicating whether the sender gives a valid opening, along with a quantum state on registers (O, Aux). 3. E.AltCommitUSim (S),UExt (S) (Aux, M) → C: E.AltCommit takes as inputs a quantum state on the register Aux, and the updated extracted quantum message on the register M, makes queries to USim and UExt , and outputs a quantum state on the register C. We slightly overload the notation E.AltCheck to also denote the corresponding coherent implementations when the query set is provided in the register Q. In particular, we write (b, Q, O, Aux) ← E.AltCheck(Q, O, Aux) for the coherent implementation. Definition 6.3 (Extractability). A quantum state vector commitment scheme QSVC = (Com, Open, Query, Update, Recover) (1) (2) (3) (1) is (ξExt , ξExt , ξExt )-extractable if there exist a ξExt -quantum simulator USim with state register S for the random oracle, a stateful oracle UExt with the same state register S, and a polynomial-time quantum message extractor E with query access to USim and UExt as in Theorem 6.2 such that the following holds: 39

(2)

1. (UExt does not disturb the simulation.) For every integer m, ∥ [UExt , USim ] ∥2 ≤ ξExt (m), where m is the output length of the random oracle. 2. (E gives the only state that the adversary A can open to.) For every integer m, t, real numbers w1 , w2 ∈ [0, t] such that w1 + w2 ≤ t, t-query p-phase quantum adversary A such that TotalMass(A, USim ) ≤ w1 and TotalMass(A, UExt ) ≤ w2 , and unbounded quantum distinguisher D, p p 2 (3) Pr [QSVCSimWorld(A, D)] − Pr [QSVCExtWorld(A, D)] ≤ ξExt (t, p, w1 , w2 , m, n) , where m is the output length of the random oracle, n is the message length of the scheme, and the games QSVCSimWorld(A, D) and QSVCExtWorld(A, D) are defined below: •

QSVCSimWorld(A, D): (a) The game initializes the registers: S ← |⊥⟩, Q ← |0̄⟩, Y ← |0̄⟩, O ← |0̄⟩. (b) The adversary generates a commitment: (C, E) ← AUSim (S),UExt (S) . (c) The adversary does the following: For i ∈ [p]: i. The adversary generates a query location and the corresponding opening, together with an answer register for the superposition query: (Q, O, Y, E) ← AUSim (S),UExt (S) (Q, O, Y, E). ii. The game implements the query: (bi , Q, C, O, Y) ← QSVC.QueryUSim (S) (1λ , Q, C, O, Y). (d) The game generates the output: If ∧i∈[p] bi = 0, output 0; otherwise, compute b′ ← D(Q, C, O, Y, E, S) and output b′ .

•

QSVCExtWorld(A, D): (a) The game initializes the registers: S ← |⊥⟩, Q ← |0̄⟩, Y ← |0̄⟩, O ← |0̄⟩. (b) The adversary generates a commitment: (C, E) ← AUSim (S),UExt (S) . (c) The game uses the extractor to extract the underlying message: (M, Aux) ← E.ExtMsgUSim (S),UExt (S) (C). (d) The adversary does the following: For i ∈ [p]: i. The adversary generates a query location and the corresponding opening, together with an answer register for the superposition query: (Q, O, Y, E) ← AUSim (S),UExt (S) (Q, O, Y, E). ii. The game uses the alternative check to check if the opening is valid: (bi , Q, O, Aux) ← E.AltCheck(Q, O, Aux). iii. The game implements the query: (Q, M, Y) ← U qry (Q, M, Y). (e) The game uses alternative commit to get the commitment: C ← E.AltCommitUSim (S),UExt (S) (Aux, M). (f) The game generates the output: If ∧i∈[p] bi = 0, output 0; otherwise, compute b′ ← D(Q, C, O, Y, E, S) and output b′ .

40

7

Construction of extractable quantum state vector commitments

7.1

Labeling the Merkle tree

We make some conventions on how to label each vertex in the Merkle tree before giving the construction for the quantum state vector commitment. A vertex v in a Merkle tree of depth d is labeled as a string ℓ ∈ {0, 1}≤d . The length of ℓ indicates the depth of the vertex v from the root, and the i-th bit of ℓ indicates whether we need to take the left edge or the right edge on the path from the root to v (0 for left and 1 for right). With the above convention, we have the following facts: • The root of the Merkle tree is labeled as the empty string ε; • For a string ℓ ∈ {0, 1}<d , the left child of a vertex v with label ℓ is labeled as ℓ ∥ 0; • For a string ℓ ∈ {0, 1}<d , the right child of a vertex v with label ℓ is labeled as ℓ ∥ 1; • For a non-empty string ℓ ∈ {0, 1}≤d , let Sib(ℓ) be the label of the sibling of the vertex with label ℓ. Then Sib(·) satisfies that Sib(ℓ) is the string of length |ℓ| and Sib(ℓ) equals ℓ on every bit except the last one. • For a non-empty string ℓ ∈ {0, 1}≤d , let Par(ℓ) be the label of the parent of the vertex with label ℓ. Then Par(ℓ) is the prefix of ℓ of length |ℓ| − 1. • For a string ℓ ∈ {0, 1}≤d , let Path(ℓ) be the set of labels of the vertices on the path from the root to the vertex v with label ℓ (including the root and the vertex v). Then Path(ℓ) contains the |ℓ| + 1 prefixes of ℓ (including the empty string ε and the string ℓ itself). We overload the notation to use the string ℓ ∈ {0, 1}≤d to mean the vertex with label ℓ. Furthermore, we overload the functions Sib(·) and Path(·) to take sets as input. For every set S ⊆ := {Sib(ℓ) : ℓ ∈ S and ℓ ̸= ε}, and {0, 1}≤d , we denote the set of siblings of the vertices inside S as Sib(S) S the set of vertices from the root to vertices inside S as Path(S) := ℓ∈S Path(ℓ). For each set S ⊆ {0, 1}d , we define AuthPath(S) := Sib(Path(S)) \ Path(S).

7.2

An extractable quantum state vector commitment scheme

We apply the Merkle tree to the succinct quantum state commitment construction in Theorem 5.2 to obtain a quantum state vector commitment scheme. Construction 7.1. We assume the number of blocks n is a power of 2 (otherwise, we just add padding of 0 at the end). Denote n = 2d for an integer d. Let RO be sampled uniformly from all the functions with range {0, 1}m , where we set m to be the security parameter λ, and let CM = (ComRO , CheckRO ) be the succinct quantum state commitment in Theorem 5.2. Let Cm,n be the circuit for ComRO where the quantum message has n := 4m qubits (in other words, it is the circuit in Theorem 5.1 for n = 4m). We construct QSTC = (Com, Open, Query, Update, Recover) for block size s := 2m as follows. QSTC.ComRO (M): 1. Divide the (n · s)-qubit register M into n registers (M[ℓ])ℓ∈{0,1}d each of size s. 2. For each ℓ ∈ {0, 1}d−1 , define M[ℓ] := (M[ℓ, 0], M[ℓ, 1]). 3. Initialize n − 1 registers (A[ℓ])ℓ∈{0,1}<d , each of size 2m, as all-zero states. 4. For j = d − 1, d − 2, . . . , 0: (a) For each ℓ ∈ {0, 1}j , apply Cm,n , where the quantum message is on the registers M[ℓ] (the quantum message has 2s = n qubits), the ancilla is on the register A[ℓ], and the oracle access is implemented by RO, to obtain (C[ℓ], O[ℓ]). 41

(b) If j ≥ 1, for each ℓ N ∈ {0, 1}j−1 , set M[ℓ] := (C[ℓ, 0], C[ℓ, 1]). 5. Set C := C[ε] and T := ℓ∈{0,1}<d O[ℓ]. 6. Output C and T. QSTC.OpenRO (Q, T): N 1. Parse T asN ℓ∈{0,1}<d O[ℓ]. N 2. Set O := ℓ∈Path(Q)\Q O[ℓ] and R := ℓ∈{0,1}<d \Path(Q) O[ℓ]. 3. Output O and R. QSTC.QueryRO (Q, C, O, Y): N N 1. Set C[ε] := C, parse O as ℓ∈Path(Q)\Q O[ℓ], and parse Y as ℓ∈Q Y[ℓ]. 2. For j = 0, 1, . . . , d − 1: (a) For each ℓ ∈ Path(Q) ∩ {0, 1}j , apply the inverse of Cm,n to (C[ℓ], O[ℓ]), where the oracle access is implemented by RO, to obtain the committed quantum message in M[ℓ] and the ancilla in A[ℓ]. (b) If j ̸= d − 1, for each ℓ ∈ Path(Q) ∩ {0, 1}j , parse M[ℓ] as (C[ℓ, 0], C[ℓ, 1]). (c) If j = d − 1, for each ℓ ∈ Path(Q) ∩ {0, 1}j , parse M[ℓ] as (M[ℓ, 0], M[ℓ, 1]). 3. For ℓ ∈ Q, apply SWAP operator: (M[ℓ], Y[ℓ]) ← SWAP(M[ℓ], Y[ℓ]). 4. Measure A[ℓ] for each ℓ ∈ Path(Q) \ Q in the computational basis, and set b = 1 if all the measurement outcomes are 0, and otherwise set b = 0. 5. For each ℓ ∈ Path(Q) ∩ {0, 1}d−1 , define M[ℓ] := (M[ℓ, 0], M[ℓ, 1]). 6. For j = d − 1, . . . , 1, 0: (a) For each ℓ ∈ Path(Q) ∩ {0, 1}j , apply Cm,n , where the quantum message is on the registers M[ℓ], the ancilla is on the register A[ℓ], and the oracle access is implemented by RO, to obtain (C[ℓ], O[ℓ]). j−1 (b) If j ̸= 0, for each M[ℓ] := (C[ℓ, 0], C[ℓ, 1]). Nℓ ∈ Path(Q) ∩ {0, 1} , setN 7. Set C := C[ε], O := ℓ∈Path(Q)\Q O[ℓ], and Y := ℓ∈Q Y[ℓ]. 8. Output (b, C, O, Y). QSTC.UpdateRO (Q, O, R): N N 1. Parse O asN ℓ∈Path(Q)\Q O[ℓ] and parse R as ℓ∈{0,1}<d \Path(Q) O[ℓ]. 2. Set T := ℓ∈{0,1}<d O[ℓ]. 3. Output T. QSTC.RecoverRO (C, T): N 1. Set C[ε] := C, and parse T as ℓ∈{0,1}<d O[ℓ]. 2. For j = 0, 1, . . . , d − 1: (a) For each ℓ ∈ {0, 1}j , apply the inverse of Cm,n to (C[ℓ], O[ℓ]), where the oracle access is implemented by RO, to obtain the committed quantum message in M[ℓ] and the ancilla in A[ℓ]. (b) If j ̸= d − 1, for each ℓ ∈ {0, 1}j , parse M[ℓ] as (C[ℓ, 0], C[ℓ, 1]). (c) If j = d − 1, for each ℓ ∈ {0, 1}j , parse M[ℓ] as (M[ℓ, 0], M[ℓ, 1]). 3. Measure A[ℓ] for each ℓ ∈ {0, 1}<d in the computational basis, and set b = 1 if all the measurement outcomes are 0, and otherwise set b = 0. 4. Output (b, M). Note that in our construction, QSTC.Recover just does the inverse of QSTC.Com. By construction, QSTC has the following efficiency: 42

• The size of C is always O(m) = O(λ) regardless of the message length. • The size of O for a set Q is O(m |Path(Q) \ Q|) = O(m |Q| d) = O(λ |Q| log n). Therefore, QSTC satisfies the local opening requirement of QSVC. Moreover, the perfect completeness of QSTC follows from the perfect completeness of Com.

7.3

Extractor for the vector commitment scheme

We present the extractor for the quantum state vector commitment scheme QSTC in Theorem 7.1 before showing QSTC is extractable. We begin with the oracle access of the extractor for QSTC, which is exactly the same as the oracle access of the extractor for the basic commitment in Theorem 5.4. Specifically, we use the unitary X OXYD = |x⟩⟨x|X ⊗ FD[x] CNOTD[x]Y FD[x] x∈X

to simulate the random oracle, and the unitary InvTDW as defined in Equation (5) to help the extractor, where W can be parsed as BM′ . Construction 7.2 (The extractor EQSTC ). Let ECM be the extractor for the scheme CM in Theorem 5.4. We consider the following EQSTC for QSTC = (Com, Open, Query, Update, Recover) in Theorem 7.1. EQSTC has query access to O(D) and Inv(D). EQSTC has the following interfaces: – EQSTC .ExtMsg(C): 1. Set C[ε] := C. 2. For j = 0, 1, · · · , d − 1: (a) For each ℓ ∈ {0, 1}j , run ECM .ExtMsg(C[ℓ]) with the working register (W1 [ℓ], W2 [ℓ]) initialized as all zero states by forwarding its queries to O(D) and Inv(D) to obtain M[ℓ] and Aux[ℓ]. (b) If j ̸= d − 1, for each ℓ ∈ {0, 1}j , parse M[ℓ] as (C[ℓ, 0], C[ℓ, 1]). (c) If j =Nd − 1, for each ℓ ∈ {0, 1}j ,N parse M[ℓ] as (M[ℓ, 0], M[ℓ, 1]). 3. Set M := ℓ∈{0,1}d M[ℓ] and Aux := ℓ∈{0,1}<d Aux[ℓ]. 4. Output (M, Aux). – EQSTC .AltCheck(Q, N O, Aux): N 1. Parse O as ℓ∈Path(Q)\Q O[ℓ] and Aux as ℓ∈{0,1}<d Aux[ℓ]. 2. For each ℓ ∈ Path(Q) \ Q, make the projective measurement as the algorithm ECM .AltCheck on registers (O[ℓ], Aux[ℓ]) to get a result bℓ (while the registers (O[ℓ], Aux[ℓ]) still hold the postmeasurement V state). N N 3. Set b := ℓ∈Path(Q)\Q bℓ , O := ℓ∈Path(Q)\Q O[ℓ], and Aux := ℓ∈{0,1}<d Aux[ℓ]. 4. Output (b, O, Aux). – EQSTC .AltCommit(Aux, M): N 1. Parse Aux as ℓ∈{0,1}<d Aux[ℓ]. 2. For each ℓ ∈ {0, 1}d−1 , define M[ℓ] := (M[ℓ, 0], M[ℓ, 1]). 3. For j = d − 1, · · · , 1, 0: (a) For each ℓ ∈ {0, 1}j in the reverse of lexicographic order, apply the reverse of ECM .ExtMsg by forwarding its queries to O(D) and Inv(D) on (M[ℓ], Aux[ℓ]) to obtain a state on the register C[ℓ] and the ancilla registers (W1 [ℓ], W2 [ℓ]). 43

(b) If j > 0, for each ℓ ∈ {0, 1}j−1 , set M[ℓ] := (C[ℓ, 0], C[ℓ, 1]). 4. Set C := C[ε]. 5. Set W := (W1 [ℓ], W2 [ℓ])ℓ∈{0,1}<d . 6. Output C. In the security analysis, we sometimes also let EQSTC .AltCommit output the register W, and we sometimes also let EQSTC .ExtMsg take an additional register W as an input register instead of initializing an all-zero register. Note that in our construction, EQSTC .AltCommit just does the inverse of EQSTC .ExtMsg except that EQSTC .AltCommit does not check whether the ancilla qubits return to the all-zero states.

7.4

Security analysis of the vector commitment scheme

We show the scheme QSTC is an extractable quantum state vector commitment scheme. (1)

(2)

(3)

Theorem 7.3 (Extractability). The scheme QSTC in Theorem 7.1 is (ξExt , ξExt , ξExt )-extractable with the quantum simulator O(D), the extractor oracle Inv(D), and the extractor EQSTC in Theorem 7.2 where (1)

ξExt := 0 , (2)

ξExt (m) := 2−m+7 ,
(3) ξExt (t, p, w1 , w2 , m, n) := 2−m+22 p2 n2 (t + 8np)2 n2 + w1 + w2 + p + 1 . We first present a lemma that shows for the single opening case, the world QSVCSimWorld1Open that does the query using QSTC, and the world QSVCOffExtWorld1Open that first extracts the underlying message, implements the query, and then recover the commitment are indistinguishable, as long as there is no collision during the execution of the games. Then Theorem 7.3 follows from the standard hybrid arguments and the fact that a quantum algorithm cannot obtain a collision in the database with high probability. Lemma 7.4. Let QSTC be the quantum vector state commitment in Theorem 7.1, and EQSTC be the extractor in Theorem 7.2 with oracle access to O(D) and Inv(D) that works on an internal database register D. For every integer m, t, real numbers w1 , w2 ∈ [0, t] such that w1 + w2 ≤ t, t-query quantum adversary A such that TotalMass(A, O) ≤ w1 and TotalMass(A, Inv) ≤ w2 , and unbounded quantum distinguisher D, p p 2 Pr [QSVCSimWorld1Open∗ (A, D)] − Pr [QSVCOffExtWorld1Open∗ (A, D)] ≤ ξ1Open (m, n, t, w1 , w2 ) , where m is the output length of the random oracle and n is the message length of the scheme, the error
ξ1Open (m, n, t, w1 , w2 ) := 2−m+20 n2 (t + 8n)2 n2 + w2 , and the games QSVCSimWorld1Open∗ (A, D) and QSVCOffExtWorld1Open∗ (A, D) are defined below: •

QSVCSimWorld1Open∗ (A, D): 1. The game initializes the database register: D ← |⊥⟩. 2. The adversary generates the query set, the commitment, the opening, and the answer register that might be entangled with the environment register: (Q, C, O, Y, E) ← AO(D),Inv(D) . 44

O(D)

3. The game implements the query: (bNoCollision , b, Q, C, O, Y) ← QSTC.QueryNoCollision (1λ , Q, C, O, Y). 4. The game initializes the working register: set W := (W1 [ℓ], W2 [ℓ])ℓ∈{0,1}<d and initialize it as all-zero states. 5. The game generates the output: If bNoCollision ∧b = 0, output 0; otherwise, compute b′ ← D(Q, C, O, Y, E, D, W) and output b′ . •

QSVCOffExtWorld1Open∗ (A, D): 1. The game initializes the database register: D ← |⊥⟩. 2. The adversary generates the query set, the commitment, the opening, and the answer register that might be entangled with the environment register: (Q, C, O, Y, E) ← AO(D),Inv(D) . O(D),Inv(D) 3. The game uses the extractor to extract the underlying message: (bNoCollision , M, Aux) ← EQSTC .ExtMsgNoCollision (C). 4. The game uses the alternative check to check if the opening is valid: (b, Q, O, Aux) ← EQSTC .AltCheck(Q, O, Aux). 5. The game implements the query: (Q, M, Y) ← U qry (Q, M, Y). O(D),Inv(D) 6. The game uses the extractor to recover the commitment: (b′NoCollision , C, W) ← EQSTC .AltCommitNoCollision (Aux, M). ′ 7. The game generates the output: If bNoCollision ∧ bNoCollision ∧ b = 0, output 0; otherwise, compute b′ ← D(Q, C, O, Y, E, D, W) and output b′ . The proof of Theorem 7.4 is deferred to Section 7.5. We first apply Theorem 7.4 to show Theorem 7.3.

Proof of Theorem 7.3. The extractor EQSTC uses the same oracles Inv(D) and O(D) as the extractor ECM for the scheme CM in Theorem 5.4. By Theorem 5.5, we have that (1)

ξExt = 0 , (2)

ξExt (m) = 2−m+7 , and two O oracles commute, and two Inv oracles commute no matter which registers they act on. 2 p p To bound the term Pr [QSVCSimWorld(A, D)] − Pr [QSVCExtWorld(A, D)] , we first introduce a new game QSVCOffExtWorld, which does the extraction after the adversary produces the openings. The differences between QSVCOffExtWorld and QSVCExtWorld are highlighted in blue. QSVCOffExtWorld(A, D): 1. The game initializes the registers: D ← |⊥⟩, Q ← |0̄⟩, Y ← |0̄⟩, O ← |0̄⟩. 2. The adversary generates a commitment: (C, E) ← AO(D),Inv(D) . 3. Set W := (W1 [ℓ], W2 [ℓ])ℓ∈{0,1}<d and initialize it as all-zero states. 4. For i ∈ [p]: (a) The adversary generates a query location and the corresponding opening, together with an answer register for the superposition query: (Q, O, Y, E) ← AO(D),Inv(D) (Q, O, Y, E). (b) The game uses the extractor to extract the underlying message: (M, Aux) ← E.ExtMsgO(D),Inv(D) (C, W). (c) The game uses the alternative check to check if the opening is valid: (bi , Q, O, Aux) ← E.AltCheck(Q, O, Aux). (d) The game implements the query: (Q, M, Y) ← U qry (Q, M, Y). (e) The game uses alternative commit to get the commitment: (C, W) ← E.AltCommitO(D),Inv(D) (Aux, M).
5. The game generates the output: If ∧i∈[p] bi = 0, output 0; otherwise, compute b′ ← D(Q, C, O, Y, E, D) and output b′ . As the unitary part of E.AltCommit is just the reverse of the unitary part of E.ExtMsg, the only difference between QSVCOffExtWorld and QSVCExtWorld is whether we do Item 4a first or Item 4b first. As a result, 45

for every t-query quantum adversary A and unbounded quantum distinguisher D, p p Pr [QSVCExtWorld(A, D)] − Pr [QSVCOffExtWorld(A, D)] √ ≤ 4tn · ∥ [O, Inv] ∥ ≤ 32 2tn · 2−m/2 .

(16)

p p It remains to bound Pr [QSVCOffExtWorld(A, D)] − Pr [QSVCSimWorld(A, D)] . We compare QSVCSimWorld and QSVCOffExtWorld using the following hybrids. For j ∈ {0, . . . , p}, let Hj use QSTC.Query in the first j phases and the offline extraction procedure in the remaining phases. Thus, Hp is QSVCSimWorld and H0 is QSVCOffExtWorld. Fix j ∈ [p]. The games Hj and Hj−1 differ only in phase j. Their common prefix, up to the submission of the opening for the j-th phase, is an ordinary QSVCSimWorld prefix. We regard this prefix as the adversary of Theorem 7.4. Since the preceding j − 1 phases make at most 4n(j − 1) queries to O and none to Inv, this adversary has at most t + 4n(j − 1) queries, with masses at most w1 + 4n(j − 1) and w2 , respectively, where w1 and w2 refer to the adversary’s query masses in QSVCSimWorld. (0) (1) Let Hj and Hj be obtained from Hj and Hj−1 , respectively, by inserting no-collision checks only during the j-th phase. By Theorem 2.5, r h q i (0) Pr [Hj (A, D)] − Pr Hj (A, D) p √ ≤ 2 6 (t + 4n(j − 1) + 8n) w1 + 4nj · 2−m/2 , and r

h i q (1) Pr Hj (A, D) − Pr [Hj−1 (A, D)]

p √ ≤ 2 6 (t + 4n(j − 1) + 8n) w1 + 4nj · 2−m/2 . Moreover, by Theorem 7.4, r

h i r h i2 (0) (1) Pr Hj (A, D) − Pr Hj (A, D)

≤ ξ1Open (m, n, t + 4n(j − 1), w1 + 4n(j − 1), w2 ) . Therefore, by the triangle inequality, we obtain q q 2 Pr [Hj (A, D)] − Pr [Hj−1 (A, D)]  √ p ≤ 4 6 (t + 4n(j − 1) + 8n) w1 + 4nj · 2−m/2 + (ξ1Open (m, n, t + 4n(j − 1), w1 + 4n(j − 1), w2 ))1/2  √ p ≤ 4 6 (t + 4n(p − 1) + 8n) w1 + 4np · 2−m/2

2

+ (ξ1Open (m, n, t + 4n(p − 1), w1 + 4n(p − 1), w2 ))1/2 46

2


 ≤ 2 96 (t + 4n(p − 1) + 8n)2 (w1 + 4np) · 2−m + 2−m+20 n2 (t + 8np)2 n2 + w2
≤ 2−m+21 n2 (t + 8np)2 n2 + w1 + w2 + p , where the third inequality follows from the Cauchy–Schwarz inequality. Summing over j ∈ [p], we obtain p p 2 Pr [QSVCSimWorld(A, D)] − Pr [QSVCOffExtWorld(A, D)]
≤ 2−m+21 p2 n2 (t + 8np)2 n2 + w1 + w2 + p . Therefore, p p 2 Pr [QSVCSimWorld(A, D)] − Pr [QSVCExtWorld(A, D)] p p 2 ≤ 2 Pr [QSVCExtWorld(A, D)] − Pr [QSVCOffExtWorld(A, D)] p p 2 +2 Pr [QSVCSimWorld(A, D)] − Pr [QSVCOffExtWorld(A, D)]
≤ 2−m+22 p2 n2 (t + 8np)2 n2 + w1 + w2 + p + 1 (3)

≤ ξExt (t, p, w1 , w2 , m, n) .

7.5

Proof of Theorem 7.4

Theorem 7.4 mainly follows from a standard hybrid argument over Theorem 5.6. Proof of Theorem 7.4. As in the proof of Theorem 5.6, by the triangle inequality, to prove Theorem 7.4, it is sufficient to upper bound the ℓ2 norm of the difference between the corresponding subnormalized states at the point immediately before applying D, denoted by |ϕQSVCSimWorld1Open∗ ⟩ and |ϕQSVCOffExtWorld1Open∗ ⟩, respectively. Specifically, it suffices to show that ∥ |ϕQSVCSimWorld1Open∗ ⟩ − |ϕQSVCOffExtWorld1Open∗ ⟩ ∥2 ≤ ξ1Open (m, n, t, w1 , w2 ) . We observe that, in both games QSVCSimWorld1Open∗ (A, D) and QSVCOffExtWorld1Open∗ (A, D), all operations performed prior to invoking the distinguisher D are controlled by the query set Q stored in the register Q. Thus it suffices to establish the above inequality for every fixed query set Q ⊆ {1, 2, . . . , n}, rather than for a query set chosen by the adversary in superposition, as ∥ |ϕQSVCSimWorld1Open∗ ⟩ − |ϕQSVCOffExtWorld1Open∗ ⟩ ∥2 X = ∥ |ϕQSVCSimWorld1Open∗ when Q is chosen ⟩ − |ϕQSVCOffExtWorld1Open∗ when Q is chosen ⟩ ∥2 Pr [Q is chosen] . Q

To this end, we fix a set Q ⊆ {1, 2, · · · , n}, and use the standard hybrid argument together with Theorem 5.6 to replace each call to the algorithm ECM .ExtMsg with CM.Check, and each call to the inverse of ECM .ExtMsg with CM.Com. We order the elements of Path(Q) \ Q first by increasing length and then lexicographically, and write Path(Q) \ Q = {ℓ1 , ℓ2 , . . . , ℓT }. Since Path(Q) \ Q ⊆ {0, 1}<d , the number of elements T < 2d = n. We define the following intermediate hybrid games: 47

H0 (A, D): it does the same as QSVCOffExtWorld1Open∗ except that instead of letting the adversary produce Q, we fix the query set to be Q. (i)

H1 (A, D): 1. The game initializes the database register: D ← |⊥⟩. 2. The adversary generates the query set, the commitment, the opening, and the answer register that might O(D),Inv(D) . be entangled Nwith the environment register: N (Q, C, O, Y, E) ← A 3. Parse O as ℓ∈Path(Q)\Q O[ℓ] and Y as ℓ∈Q Y[ℓ]. 4. The game uses the extractor to extract the underlying message: (a) Set C[ε] := C. (b) For ℓ ∈ {0, 1}<d : i. If ℓ ∈ {ℓ1 , ℓ2 , . . . , ℓi }, A. Apply CM.CheckNoCollision to (C[ℓ], O[ℓ]), where the oracle access is implemented by O(D), to obtain the committed quantum message in M[ℓ] and two validity bits b[ℓ] and bNoCollision [ℓ]. B. Output 0 if b[ℓ] ∧ bNoCollision [ℓ] = 0. C. Prepare a state |ψAltCheck ⟩ on the registers (O[ℓ], Aux[ℓ]). ii. If ℓ ∈ / {ℓ1 , ℓ2 , . . . , ℓi }, A. Run ECM .ExtMsgNoCollision (C[ℓ]) by forwarding its queries to O(D) and Inv(D) to obtain (M[ℓ], Aux[ℓ]), and a validity bit bNoCollision [ℓ], and output 0 if the bit bNoCollision [ℓ] = 0. B. If ℓ ∈ Path(Q) \ Q, run ECM .AltCheck(O[ℓ], Aux[ℓ]) to get a validity bit b[ℓ] while maintaining the post-measurement state on registers (O[ℓ], Aux[ℓ]), and output 0 if the bit b[ℓ] = 0. iii. If |ℓ| ̸= d − 1, parse M[ℓ] as (C[ℓ, 0], C[ℓ, 1]). iv. If |ℓ|N = d − 1, parse M[ℓ] as (M[ℓ, 0], M[ℓ, 1]). (c) Set M := ℓ∈{0,1}d M[ℓ]. 5. The game implements the query: for ℓ ∈ Q, (M[ℓ], Y[ℓ]) ← SWAP(M[ℓ], Y[ℓ]). O(D),Inv(D) 6. The game uses the extractor to recover the commitment: (b′NoCollision , C, W) ← EQSTC .AltCommitNoCollision (Aux, M). ′ 7. Output 0 if b = 0. N NoCollision 8. Set O := ℓ∈Path(Q)\Q O[ℓ]. 9. The game generates the output: compute b′ ← D(Q, C, O, Y, E, D, W) and output b′ . (i)

H2 (A, D): 1. The game initializes the database register: D ← |⊥⟩. 2. The adversary generates the query set, the commitment, the opening, and the answer register that might O(D),Inv(D) . be entangled Nwith the environment register: N (Q, C, O, Y, E) ← A 3. Parse O as ℓ∈Path(Q)\Q O[ℓ] and Y as ℓ∈Q Y[ℓ]. 4. The game uses the extractor to extract the underlying message: (a) Set C[ε] := C. (b) For ℓ ∈ {0, 1}<d : i. If ℓ ∈ Path(Q) \ Q, A. Apply CM.CheckNoCollision to (C[ℓ], O[ℓ]), where the oracle access is implemented by O(D), to obtain the committed quantum message in M[ℓ] and two validity bits b[ℓ] and bNoCollision [ℓ]. B. Output 0 if b[ℓ] ∧ bNoCollision [ℓ] = 0. 48

ii. If ℓ ∈ / Path(Q) \ Q, A. Run ECM .ExtMsgNoCollision (C[ℓ]) by forwarding its queries to O(D) and Inv(D) to obtain (M[ℓ], Aux[ℓ]), and a validity bit bNoCollision [ℓ]. B. Output 0 if bNoCollision [ℓ] = 0. iii. If |ℓ| ̸= d − 1, parse M[ℓ] as (C[ℓ, 0], C[ℓ, 1]). iv. If |ℓ| = d − 1, parse M[ℓ] as (M[ℓ, 0], M[ℓ, 1]). 5. The game implements the query: for ℓ ∈ Q, (M[ℓ], Y[ℓ]) ← SWAP(M[ℓ], Y[ℓ]). 6. The game uses the extractor and CM.Com to obtain the commitment: (a) For each ℓ ∈ {0, 1}d−1 , define M[ℓ] := (M[ℓ, 0], M[ℓ, 1]). (b) For each ℓ ∈ {0, 1}<d in the reverse order: i. If ℓ ∈ {ℓ1 , ℓ2 , . . . , ℓi }, A. Apply CM.ComNoCollision to M[ℓ], where the oracle access is implemented by O(D), to obtain the commitment and the opening (C[ℓ], O[ℓ]) and a validity bit bNoCollision [ℓ]. B. Output 0 if bNoCollision [ℓ] = 0. C. Initialize the register (W1 [ℓ], W2 [ℓ]) as all-zero states. ii. If ℓ ∈ / {ℓ1 , ℓ2 , . . . , ℓi }, A. If ℓ ∈ {ℓi+1 , ℓi+2 , . . . , ℓT }, prepare a state |ψAltCheck ⟩ on the registers (O[ℓ], Aux[ℓ]). B. Denote the reverse of ECM .ExtMsg as an algorithm ECM .AltCommit. C. Run ECM .AltCommitNoCollision (Aux[ℓ], M[ℓ]) by forwarding its queries to O(D) and Inv(D) to obtain C[ℓ], the ancilla registers (W1 [ℓ], W2 [ℓ]), and a validity bit bNoCollision [ℓ]. D. Output 0 if the bit bNoCollision [ℓ] = 0. iii. If ℓ ̸= ε and the last bit of ℓ is 0, set M[Par(ℓ)] as (C[ℓ], C[Sib(ℓ)]). (c) Set CN:= C[ε]. 7. Set O := ℓ∈Path(Q)\Q O[ℓ] and W := (W1 [ℓ], W2 [ℓ])ℓ∈{0,1}<d . 8. The game generates the output: compute b′ ← D(Q, C, O, Y, E, D, W) and output b′ . (i)

H3 (A, D): 1. The game initializes the database register: D ← |⊥⟩. 2. The adversary generates the query set, the commitment, the opening, and the answer register that might O(D),Inv(D) . be entangled Nwith the environment register: N (Q, C, O, Y, E) ← A 3. Parse O as ℓ∈Path(Q)\Q O[ℓ] and Y as ℓ∈Q Y[ℓ]. 4. Initialize a counter N ← 2d − 1 − i. 5. Check whether the database register D has a collision by measuring it with {ΠNoCol , ID − ΠNoCol }. Output 0 if there is a collision. 6. The game uses the extractor to extract the underlying message: (a) Set C[ε] := C. (b) For ℓ ∈ {0, 1}<d : i. If ℓ ∈ Path(Q) \ Q, A. Apply CM.CheckNoCollision to (C[ℓ], O[ℓ]), where the oracle access is implemented by O(D), to obtain the committed quantum message in M[ℓ] and two validity bits b[ℓ] and bNoCollision [ℓ]. B. Output 0 if b[ℓ] ∧ bNoCollision [ℓ] = 0. ii. If ℓ ∈ / Path(Q) \ Q and N > 0, A. Run ECM .ExtMsgNoCollision (C[ℓ]) by forwarding its queries to O(D) and Inv(D) to obtain (M[ℓ], Aux[ℓ]), and a validity bit bNoCollision [ℓ]. 49

B. Output 0 if bNoCollision [ℓ] = 0. iii. If ℓ ∈ Path(Q) \ Q or N > 0, A. If |ℓ| < d − 1, parse M[ℓ] as (C[ℓ, 0], C[ℓ, 1]). B. If |ℓ| = d − 1, parse M[ℓ] as (M[ℓ, 0], M[ℓ, 1]). iv. Decrease the counter by 1: N ← N − 1. 7. The game implements the query: for ℓ ∈ Q, (M[ℓ], Y[ℓ]) ← SWAP(M[ℓ], Y[ℓ]). 8. The game uses the extractor and CM.Com to obtain the commitment: (a) For each ℓ ∈ {0, 1}<d in the reverse order: i. Increase the counter by 1: N ← N + 1. ii. If ℓ ∈ Path(Q) \ Q, A. If |ℓ| = d − 1, define M[ℓ] := (M[ℓ, 0], M[ℓ, 1]). B. If |ℓ| < d − 1, define M[ℓ] := (C[ℓ, 0], C[ℓ, 1]). C. Apply CM.ComNoCollision to M[ℓ], where the oracle access is implemented by O(D), to obtain the commitment and the opening (C[ℓ], O[ℓ]) and a validity bit bNoCollision [ℓ]. D. Output 0 if bNoCollision [ℓ] = 0. E. Initialize the register (W1 [ℓ], W2 [ℓ]) as all-zero states. iii. If ℓ ∈ / Path(Q) \ Q and N > 0, A. If |ℓ| = d − 1, define M[ℓ] := (M[ℓ, 0], M[ℓ, 1]). B. If |ℓ| < d − 1, define M[ℓ] := (C[ℓ, 0], C[ℓ, 1]). C. Denote the reverse of ECM .ExtMsg as an algorithm ECM .AltCommit. D. Run ECM .AltCommitNoCollision (Aux[ℓ], M[ℓ]) by forwarding its queries to O(D) and Inv(D) to obtain C[ℓ], the ancilla registers (W1 [ℓ], W2 [ℓ]), and a validity bit bNoCollision [ℓ]. E. Output 0 if the bit bNoCollision [ℓ] = 0. iv. If ℓ ∈ / Path(Q) \ Q and N ≤ 0, A. Initialize the register (W1 [ℓ], W2 [ℓ]) as all-zero states. (b) Set C := C[ε]. 9. Check whether the database register D has a collision by measuring it with {ΠNoCol , ID − ΠNoCol }. Output 0 if Nthere is a collision. 10. Set O := ℓ∈Path(Q)\Q O[ℓ] and W := (W1 [ℓ], W2 [ℓ])ℓ∈{0,1}<d . 11. The game generates the output: compute b′ ← D(Q, C, O, Y, E, D, W) and output b′ . H4 (A, D): it does the same as QSVCSimWorld1Open∗ except that instead of letting the adversary produce Q, we fix the query set to be Q. Let |ϕHi ⟩ and |ϕH(j) ⟩ denote the corresponding subnormalized states at the point immediately before i

(j)

applying D in games Hi and Hi , respectively, for each i, j. We show through several lemmas that the states |ϕQSVCSimWorld1Open∗ ⟩ and |ϕQSVCOffExtWorld1Open∗ ⟩ are close in ℓ2 norm. Claim 7.5. |ϕQSVCOffExtWorld1Open∗ ⟩ = |ϕH(0) ⟩, |ϕH(T ) ⟩ = |ϕH(0) ⟩, |ϕH(T ) ⟩ = |ϕH(0) ⟩, and |ϕ (2d −1) ⟩ = 1

1

2

2

|ϕQSVCSimWorld1Open∗ ⟩.

3

H3

Proof. Since ECM .AltCheck does not act on the database register D, by the construction of EQSTC .AltCheck, (0) the game H1 (A, D) is equivalent to the game H0 (A, D), which is equivalent to QSVCOffExtWorld1Open∗ when the query set is fixed to Q, and thus |ϕQSVCOffExtWorld1Open∗ ⟩ = |ϕH0 ⟩ = |ϕH(0) ⟩ . 1

50

(0)

(T )

(T )

The game H2 is equivalent to the game H1 by construction, since in the game H1 , checking whether (0) ℓ ∈ {ℓ1 , ℓ2 , . . . , ℓi } is just the same as checking whether ℓ ∈ Path(Q) \ Q, and in the game H2 , we always (0) (T ) take the branch ℓ ∈ / {ℓ1 , ℓ2 , . . . , ℓi }. Similarly, the game H3 is equivalent to the game H2 by construction, and thus |ϕH(T ) ⟩ = |ϕH(0) ⟩ , 1

2

and |ϕH(T ) ⟩ = |ϕH(0) ⟩ . 2

3

(2d −1)

By the construction of H3 , in the procedure, the counter N is always non-positive since the iniO(D) tialization. Moreover, Items 5 and 9 can be absorbed in QSTC.QueryNoCollision (1λ , Q, C, O, Y) as the no collision variant of an algorithm would always check whether the database contains a collision before and (2d −1) after applying a unitary. Therefore, the game H3 (A, D) is equivalent to the game H4 (A, D), which is ∗ equivalent to the game QSVCSimWorld1Open when the query set is fixed to Q, and thus |ϕ (2d −1) ⟩ = |ϕH4 ⟩ = |ϕQSVCSimWorld1Open∗ ⟩ . H3

Claim 7.6. For i ∈ [T ], ∥ |ϕH(i−1) ⟩ − |ϕH(i) ⟩ ∥ 1

1

√ ≤ (16n + 5)(t + 8n) · 2−(m−3)/2 + 2−m/2+5 (t + 8n) w2 + 4n + 8 · 2−m/2 . (i−1)

(i)

(i)

Proof. The only difference between the games H1 and H1 is in how the location ℓi is handled. In H1 , the location ℓi is opened using CM.CheckNoCollision , after which the registers (O[ℓi ], Aux[ℓi ]) are initialized (i−1) to the state |ψAltCheck ⟩. In H1 , the location ℓi is instead extracted using ECM .ExtMsgNoCollision and is later checked using ECM .AltCheck. By Theorem 5.10, replacing CM.CheckNoCollision with ECM .ExtMsgNoCollision followed by ECM .AltCheck incurs a loss of at most 8 √ + ∥(ID − ΠNoHatZero ) |ϕ1 ⟩ ∥ + ∥(ID − ΠNoHatZero ) |ϕ2 ⟩ ∥ 2m ⊗n ⊗n ⊗n where |ϕ1 ⟩ = ΠNoCol HM OMZ2 D ΠNoCol HM |ϕ⟩CODE , |ϕ2 ⟩ = ΠNoCol HM |ϕ⟩CODE , and the state |ϕ⟩CODE is the joint state when the game handles the location ℓi . Since A makes at most t queries and the game makes at most 8n queries to the two oracles, the states |ϕ1 ⟩ and |ϕ2 ⟩ are invariant under Πt+8n . As a result, by a similar reasoning as Theorem 5.6, since to get |ϕ⟩CODE , we make at most 8n + 1 calls to ΠNoCol , and make at most t + 8n queries to Inv with total query mass at most w2 + 4n,

∥(ID − ΠNoHatZero ) |ϕ1 ⟩ ∥ + ∥(ID − ΠNoHatZero ) |ϕ2 ⟩ ∥ = ∥(ID − ΠNoHatZero )Πt+8n |ϕ1 ⟩ ∥ + ∥(ID − ΠNoHatZero )Πt+8n |ϕ2 ⟩ ∥ ≤ 3∥Πt+8n [ΠNoCol , ΠNoHatZero ] Πt+8n ∥ + 2∥(ID − ΠNoHatZero ) |ϕ⟩CODE ∥ p ≤ 3(t + 8n) · 2−(m−3)/2 + 2∥Πt+8n [InvTDW , ΠNoHatZero ] Πt+8n ∥ (t + 8n)(w2 + 4n) 51

+ 2(8n + 1)∥Πt+8n [ΠNoCol , ΠNoHatZero ] Πt+8n ∥

√ ≤ (16n + 5)(t + 8n) · 2−(m−3)/2 + 2−m/2+5 (t + 8n) w2 + 4n ,

where we notice that only queries to ΠNoCol or Inv would contribute error to ∥(ID − ΠNoHatZero ) |ϕ⟩CODE ∥. (i) Initializing the registers (O[ℓi ], Aux[ℓi ]) to |ψAltCheck ⟩ in the game H1 incurs no additional loss, since (i−1) conditioned on the validity bit being 1, these registers are also in the state |ψAltCheck ⟩ in the game H1 . Therefore, ∥ |ϕH(i−1) ⟩ − |ϕH(i) ⟩ ∥ 1

1

√ ≤ (16n + 5)(t + 8n) · 2−(m−3)/2 + 2−m/2+5 (t + 8n) w2 + 4n + 8 · 2−m/2 .

Claim 7.7. For i ∈ [T ], ∥ |ϕH(i−1) ⟩ − |ϕH(i) ⟩ ∥ 2

2

√ ≤ (24n + 8)(t + 8n) · 2−(m−3)/2 + 2−(m−11)/2 (t + 8n) w2 + 4n + 4 · 2−m/2 . (i−1)

(i)

Proof. The only difference between the games H2 and H2 is in how the location ℓi is handled after (i) the game implements the query. In H2 , the commitment and the opening of the location ℓi are obtained by initializing the ancilla qubits as |ψCheck ⟩ and applying the commitment scheme; the working registers (i−1) (W1 [ℓi ], W2 [ℓi ]) are then initialized to all-zero states. In H2 , the commitment and the opening of the location ℓi are instead obtained by initializing (O[ℓi ], Aux[ℓi ]) as the state |ψAltCheck ⟩, then applying ECM .AltCommitNoCollision while keeping the working registers (W1 [ℓi ], W2 [ℓi ]). This difference is exactly captured by † † ∥(VCheck |ψCheck ⟩ |0⟩W1 W2 − VExtMsg |ψAltCheck ⟩) |ψ⟩MED ∥ , † where |ψ⟩MED is the joint state when the game handles the location ℓi after the query is implemented, VCheck † is exactly what CM.ComNoCollision does, and VExtMsg is exactly what ECM .AltCommitNoCollision does. By Theorem 5.10, † † ∥(VCheck |ψCheck ⟩ |0⟩W1 W2 − VExtMsg |ψAltCheck ⟩) |ψ⟩MED ∥ √ √ 4 ≤√ + 2∥(ID − ΠNoHatZero ) |ψ1 ⟩ ∥ + 2∥(ID − ΠNoHatZero ) |ψ2 ⟩ ∥ , m 2 ⊗n where |ψ1 ⟩ := HM ΠNoCol OMZ1 D ΠNoCol |ψ⟩MED |ψCheck ⟩ and |ψ2 ⟩ := ΠNoCol |ψ⟩MED . Therefore, by the same reasoning as Theorem 7.6,

∥ |ϕH(i−1) ⟩ − |ϕH(i) ⟩ ∥ 2

2

√ ≤ (24n + 8)(t + 8n) · 2−(m−3)/2 + 2−(m−11)/2 (t + 8n) w2 + 4n + 4 · 2−m/2 .

 p √  Claim 7.8. For i ∈ [2d − 1], ∥ |ϕH(i−1) ⟩ − |ϕH(i) ⟩ ∥ ≤ 2−m/2 (16n + 8) 6(t + 8n) + 64 2n . 3

3

52

(i−1)

(i)

(i−1)

Proof. The difference between the games H3 and H3 is that H3 does an extra ECM .ExtMsgNoCollision (C[ℓ]) (i−1) before the game implements the query, and H3 does an extra ECM .AltCommitNoCollision (Aux[ℓ], M[ℓ]) after (i) the game implements the query, while H3 initializes (W1 [ℓ], W2 [ℓ]) as all-zeros in the computational basis. Notice that ECM .AltCommit does exactly the inverse of ECM .ExtMsg. The claim follows from the following two facts: • Replace this extra ECM .ExtMsgNoCollision (C[ℓ]) with ECM .ExtMsg(C[ℓ]), and ECM .AltCommitNoCollision (Aux[ℓ], M[ℓ]) (i−1) (i−1) with ECM .AltCommit(Aux[ℓ], M[ℓ]) in game H3 to form a game H′ 3 . As the database size is always bounded by t + 8n and in each game, we always check whether the database has a collision at the beginning and at the end, this step would incur an error p ∥ |ϕH(i−1) ⟩ − |ϕH′ (i−1) ⟩ ∥ ≤ 4∥(ID − ΠNoCol ) (Πt+8n OΠt+8n ) ΠNoCol ∥ ≤ 4 · 6(t + 8n) · 2−m/2 . 3

3

(i−1)

• Moving the operation ECM .AltCommit(Aux[ℓ], M[ℓ]) in game H′ 3 to just after the operation ECM .ExtMsg(C[ℓ]) (i) results in exactly the same game as H3 , where (W1 [ℓ], W2 [ℓ]) is initialized as all-zero states. This step would incur an error ∥ |ϕH(i) ⟩ − |ϕH′ (i−1) ⟩ ∥ 3

3

≤ 8T · ∥ [Inv, O] ∥ + (8T + 2) · ∥ [ΠNoCol , Πt+8n OΠt+8n ] ∥ p ≤ 8T · 2−(m−7)/2 + (16T + 4) · 6(t + 8n) · 2−m/2 . Notice that T ≤ n. A triangle inequality concludes the proof. Combining Theorems 7.5 to 7.8, we obtain ∥ |ϕQSVCSimWorld1Open∗ ⟩ − |ϕQSVCOffExtWorld1Open∗ ⟩ ∥2  √ ≤ n(40n + 13)(t + 8n) · 2−(m−3)/2 + 2−m/2+7 n(t + 8n) w2 + 4n + 12n · 2−m/2 2 p +2−m/2 n(16n + 8) 6(t + 8n) + 2−(m−13)/2 n2 ≤ 2−m+2 8n2 (40n + 13)2 (t + 8n)2 + 214 n2 (t + 8n)2 (w2 + 4n) + 6n2 (16n + 8)2 (t + 8n) + 215 n4
≤ 2−m+20 n2 (t + 8n)2 n2 + w2

≤ ξ1Open (m, n, t, w1 , w2 ) , where we use the triangle inequality in the second line, and the Cauchy–Schwarz inequality in the third line.

53

8

Quantum interactive arguments based on QIOPs

We show how to obtain a quantum-communication succinct interactive argument from public-query QIOPs. Theorem 8.1. Let QIOP be a quantum interactive oracle proof for relation R in the form of Section 3 with (1) (2) (3) public-query soundness spq . Let QSVC be an (ξExt , ξExt , ξExt )-extractable quantum state vector commitment scheme (Theorem 6.3). Let m be the output length of the random oracle. Then the protocol (P, V) = IBCS[QIOP, QSVC] in Theorem 8.2 is a quantum-communication interactive argument for relation R with soundness X (3) (1) ξExt (t + vq, m) + 2spq (ν) + 2k · ξExt (t, d, t, 0, m, li ) , i∈[k]

where vq is the number of queries that the argument verifier V makes to the random oracle RO. Furthermore, when QSVC is instantiated with the construction QSTC in Theorem 7.1, vq = O(q log lmax ).

8.1

Our transformation

We describe below our construction of the quantum-communication succinct interactive argument in the random oracle model, which we denote (P, V) := IBCS[QIOP, QSVC]. This is a quantum analogue of the IBCS transformation for IOPs [CDGS23]. Construction 8.2. Let (P, V) := QIOP. The argument prover P receives an instance x and a quantum witness ρ, and the argument verifier receives the same instance x. P and V both have access to a random function RO sampled from U(m). We do domain separation on RO to obtain k random functions {ROi }i∈[k] , where ROi (x) = RO(i, x) for x ∈ {0, 1}∗ and i ∈ [k]. Then P and V interact as follows. 1. P’s initialization: Initialize P1 to the quantum witness ρ, padded with all-zero states, let Mv0 be an empty register, and set I1 := {1}, J1 := ∅. 2. V’s initialization: Initialize V1 to all-zero states and set I1 := {1}, J1 := ∅. 3. For i ∈ [k]: (a) P’s i-th commitment. i. Compute the returned QIOP proofs: for j ∈ Ji , Mpj ← QSVC.RecoverROj (1λ , Cj , Tj ). ii. Compute the i-th QIOP state: (Mpi , Pi+1 ) ← P(x, Mvi−1 , Pi , (Mpj )j∈Ji ). iii. Parse Mpi as li subregisters: (Mpi [j])j∈[li ] := Mpi . iv. Compute a QVC commitment to the QIOP state where the message length is set to li : (Ci , Ti ) ← QSVC.ComROi (Mpi ). v. Send the QVC commitment Ci to V. (b) P answers the queries of V that the argument verifier V simulates. (0) i. V initializes (Locι , Yι )ι∈[wi ] as the all-zero states and sets Vi := Vi . ii. For q ∈ [di ]: (q) (q−1) (q−1) A. V computes the query locations: ((Locι , Yι )ι∈[wi ] , Vi ) ← Vi (x, (Locι , Yι )ι∈[wi ] , Vi ). B. V sends (Locι )ι∈[wi ] to P. C. P computes an opening: (RO ) ((Locι )ι∈[wi ] , (Oi′ , Ri′ )i′ ∈Ii ) ← QSVC.Open i′ i′ ∈Ii (1λ , (Locι )ι∈[wi ] , (Ti′ )i′ ∈Ii ). D. P sends ((Locι )ι∈[wi ] , (Oi′ )i′ ∈Ii ) to V. E. V implements the query for V: (RO ) (bi,q , (Locι , Yι )ι∈[wi ] , (Ci′ , Oi′ )i′ ∈Ii ) ← QSVC.Query i′ i′ ∈Ii (1λ , (Locι , Yι )ι∈[wi ] , (Ci′ , Oi′ )i′ ∈Ii ). 54

F. V sends ((Locι )ι∈[wi ] , (Oi′ )i′ ∈Ii ) to P. G. P erases the information about the query locations: (RO ) ((Locι )ι∈[wi ] , (Ti′ )i′ ∈Ii ) ← QSVC.Update i′ i′ ∈Ii (1λ , (Locι )ι∈[wi ] , (Oi′ , Ri′ )i′ ∈Ii ). H. P sends (Locι )ι∈[wi ] to V. (c) If i ̸= k, V generates the i-th message and returns some of the previous proofs. i. V computes the next message and the indices of proofs to be returned: (d ) (d ) (Ji+1 , Mvi , Vi+1 ) ← Vi i (x, (Locι , Yι )ι∈[wi ] , Vi i ). ii. V sends (Ji+1 , Mvi , (Ci′ )i′ ∈Ji+1 ) to P. iii. Both P and V set Ii+1 := (Ii ∪ {i + 1}) \ Ji+1 . (d) If i = k, V decides whether to accept: (dk ) (dk ) i. V computes whether V accepts: bQIOP
← Vk (x, (Locι , Yι )ι∈[wk ] , Vk ). ii. Compute bQSVC := ∧i∈[k] ∧q∈[di ] bi,q . iii. Output bQSVC ∧ bQIOP . Here in the construction, we overload QSVC.Open, QSVC.Query, and QSVC.Update to handle multiple proofs coherently, using their respective random oracles, and combining validity bits by conjunction. When QSVC satisfies perfect completeness, the protocol (P, V) = IBCS[QIOP, QSVC] in Theorem 8.2 has the same completeness guarantee as the quantum interactive oracle proof QIOP. Moreover, when we instantiate the quantum state vector commitment scheme with QSTC from Theorem 7.1, the efficiency measures of the interactive argument (P, V) := IBCS[QIOP, QSTC] satisfy the following: P • The round complexity kIBCS = 4 i∈[k] di + 2k − 1. P • The prover-to-verifier communication pcIBCS = O(mk+ i∈[k] di ·m·wi ·log lmax ) = O(λk+λq log lmax ). • The verifier-to-prover communication vcIBCS = vc + pcIBCS = O(vc + λk + λq log lmax ). • The verifier’s query complexity to the i-th random oracle vqi = O(di wi log li ) and the verifier’s query complexity vq = O(q log lmax ). Therefore, when we instantiate the quantum state vector commitment scheme with QSTC, the resulting protocol IBCS[QIOP, QSTC] is a quantum-communication succinct interactive argument in the quantum random oracle model as long as the underlying QIOP is efficient. Corollary 8.3. Let QIOP be a quantum interactive oracle proof for relation R in the form of Section 3 with public-query soundness spq . Let QSTC be the quantum state vector commitment scheme in Theorem 7.1. Then the protocol (P, V) = IBCS[QIOP, QSTC] is a quantum-communication interactive argument for relation R with soundness X (3) 2spq (ν) + 2k · ξExt (t, d, t, 0, λ, li ) , i∈[k] (3)

where ξExt (t, p, w1 , w2 , m, n) := 2−m+22 p2 n2 (t + 8np)2Pn2 + w1 + w2 + p + 1 . Furthermore, if QIOP satisfies that spq (ν) = negl(ν), i∈[k] di (ν) = O(poly(log ν)), q(ν) = O(poly(log ν)), li (ν) = O(poly(ν)), k(ν) = O(poly(log ν)), and vc(ν) = O(poly(log ν)), then (P, V) = IBCS[QIOP, QSTC] is a quantum-communication succinct interactive argument for the same relation R with round complexity O(poly(log ν)), total communication complexity O(poly(log ν, λ)), and soundness error negl(ν) + 2−λ t3 poly(ν) against t-query quantum adversaries. (P, V) also has the same completeness guarantee as the quantum interactive oracle proof QIOP. Proof. Theorem 8.3 follows from Theorem 8.1, Theorem 7.3, and the efficiency of the quantum-state vector commitment scheme QSTC from Theorem 7.1. 55

8.2

The malicious QIOP prover

e to attack the public-query soundness of the underlying quanWe construct a malicious QIOP prover P e for the argument (P, V) = tum interactive oracle proof system QIOP based on a malicious prover P e only has oracle access to k random functions {ROi }i∈[k] . IBCS[QIOP, QSVC]. Here P Construction 8.4. By Theorem 6.3, QSVC has a quantum extractor E with query access to the quantum e P) e as follows. simulator USim and UExt . We construct P( e P): e P( (a) Initialize the internal state register Si for the simulator USim for the random oracle in QSVC: for i ∈ [k], Si ← |⊥⟩. (b) Set I1 := {1}, J1 := ∅. e by answering the random oracle queries with USim and the internal state registers (Si )i∈[k] (c) Simulate P e outputs an instance x. Send the instance x to the QIOP verifier V. until P (d) For i ∈ [k]: e by answering the random oracle queries with USim and the internal state registers i. Simulate P e outputs a commitment Ci . (Si )i∈[k] until P ii. Run the extractor E on Ci to get the i-th prover’s message: (Mpi , Auxi ) ← E.ExtMsgUSim (Si ),UExt (Si ) (Ci ). iii. Send the i-th prover’s message Mpi to the trusted third party O that implements the queries to the prover’s messages for V. iv. For q ∈ [di ]: e A. On receiving the leaked query locations (Locι )ι∈[wi ] from V, send (Locι )ι∈[wi ] to P. e by answering the random oracle queries with USim and the internal state registers B. Simulate P e outputs ((Locι )ι∈[w ] , (Oi′ )i′ ∈I ). (Si )i∈[k] until P i i C. Check the opening: (bi , (Locι )ι∈[wi ] , (Oi′ , Auxi′ )i′ ∈Ii ) ← E.AltCheck((Locι )ι∈[wi ] , (Oi′ , Auxi′ )i′ ∈Ii ). D. Abort if bi = 0. E. Send (Locι )ι∈[wi ] to the QIOP verifier V, who asks the trusted third party O to implement the query with (Locι )ι∈[wi ] . e F. On receiving (Locι )ι∈[wi ] from the QIOP verifier V, send ((Locι )ι∈[wi ] , (Oi′ )i′ ∈Ii ) to P. e by answering the random oracle queries with USim and the internal state registers G. Simulate P e outputs (Locι )ι∈[w ] . (Si )i∈[k] until P i H. Send (Locι )ι∈[wi ] to the QIOP verifier V. v. If i ̸= k: A. On receiving the returned index set and the i-th verifier’s message (Ji+1 , Mvi ) from V, and the corresponding prover’s messages (Mpi′ )i′ ∈Ji+1 from the trusted third party O, compute the corresponding commitments in Ji+1 with the extractor E: for i′ ∈ Ji+1 , Ci′ ← E.AltCommitUSim (Si′ ),UExt (Si′ ) (Auxi′ , Mpi′ ). e B. Send (Ji+1 , Mvi , (Ci′ )i′ ∈Ji+1 ) to P. C. Set Ii+1 := (Ii ∪ {i + 1}) \ Ji+1 .

8.3

Proof of Theorem 8.1

e P) e in Theorem 8.4 has We first show that in the public-query soundness game, the malicious QIOP prover P( e a similar winning probability as the malicious argument prover P. 56

e Lemma 8.5. For every integer ν, t, m, and a t-query argument adversary P,   RO ← U(m) |x| ≤ ν  / L(R) x ← PeRO Pr  ∧ x ∈ RO RO e ∧b = 1 b ← ⟨P , V (x)⟩   |x| ≤ ν X (3) e P) e x ← P( (1)  + ξExt / L(R) ≤ 2 · Pr  ∧ x ∈ ξExt (t, d, t, 0, m, li ) . (t + vq, m) + 2k · e P), e V(x)⟩pq b ← ⟨P( ∧b = 1 i∈[k] We first show how Theorem 8.5 implies Theorem 8.1. Proof of Theorem 8.1. Theorem 8.1 follows from the definition of public-query soundness (Theorem 3.4). Specifically, if QIOP has public-query soundness spq , then   |x| ≤ ν e e x ← P(P)  / L(R) Pr  ∧ x ∈ e P), e V(x)⟩pq ≤ spq (ν) . b ← ⟨P( ∧b = 1

Next we prove Theorem 8.5 via two claims. The first claim replaces the random oracle with the simulator USim . e Claim 8.6. For every integer ν, t, m, and a t-query argument adversary P,   RO ← U(m) |x| ≤ ν  / L(R) x ← PeRO Pr  ∧ x ∈ RO RO e ∧b = 1 b ← ⟨P , V (x)⟩   S ← |⊥⟩ |x| ≤ ν (1)  + ξExt / L(R) x ← PeUSim (S) ≤ Pr  ∧ x ∈ (t + vq, m) . U (S) U (S) e Sim Sim ∧b = 1 b ← ⟨P ,V (x)⟩ Proof. This follows from the definition of quantum simulator (Theorem 4.4), and that the interaction between e and V, and the final check on x can be combined into a single distinguisher with t + vq queries to the P random oracle. The second claim replaces all the queries implemented by QSVC.Query to the i-th prover’s message e and the argument verifier V with queries during the interaction between the malicious argument prover P implemented by extractors one by one for i ∈ [k]. We first define the hybrid games. e Hi∗ (P): 1. Initialize the internal state register Si : for i ∈ [k], Si ← |⊥⟩. 2. Initialize the internal state of V, the register V1 , to all-zero states, set Mv0 to be the empty register, and set I1 := {1}, J1 := ∅. e by answering the random oracle queries with USim and the internal state registers (Si )i∈[k] 3. Simulate P e outputs an instance x. until P e and V for the first i∗ commitments of P e with QSVC. 4. Simulate the interaction of P ∗ For i ∈ [i ]: 57

e by answering the random oracle queries with USim on the input (Ji , Mvi−1 , (Ci′ )i′ ∈J ) (a) Simulate P i e until P outputs a commitment Ci . (0) (b) Initialize V’s registers (Locι , Yι )ι∈[wi ] as the all-zero states and set Vi := Vi . (c) For q ∈ [di ]: (q) (q−1) (q−1) (x, (Locι , Yι )ι∈[wi ] , Vi ). i. Simulate V to get the query locations: ((Locι , Yι )ι∈[wi ] , Vi ) ← Vi e ii. Simulate P by answering the random oracle queries with USim on the leaked query locations e outputs ((Locι )ι∈[w ] , (Oi′ )i′ ∈I ). (Locι )ι∈[wi ] until P i i iii. Implement the access to the underlying message for V: (bi,q , (Locι , Yι )ι∈[wi ] , (Ci′ , Oi′ )i′ ∈Ii ) ← QSVC.Query(USim (Si′ ))i′ ∈Ii (1λ , (Locι , Yι )ι∈[wi ] , (Ci′ , Oi′ )i′ ∈Ii ). iv. Output 0 and abort if bi,q = 0. e by answering the random oracle queries with USim on the registers ((Locι )ι∈[w ] , (Oi′ )i′ ∈I ) v. Simulate P i i e outputs the updated (Locι )ι∈[w ] . until P i (d) If i ̸= k: i. Compute the i-th V’s message and the index set for the proofs to be returned: (Ji+1 , Mvi , Vi+1 ) ← (d ) (d ) Vi i (x, (Locι , Yι )ι∈[wi ] , Vi i ). ii. Set Ii+1 := (Ii ∪ {i + 1}) \ Ji+1 . e wins: (e) If i = k, simulate V and check whether P (dk ) (d ) i. Compute bQIOP ← Vk (x, (Locι , Yι )ι∈[wk ] , Vk k ). ii. Output 1 if bQIOP = 1, |x| ≤ ν, and x ∈ / L(R); output 0 otherwise. e e e with the extractor. 5. Simulate the interaction of P(P) and V for the remaining k − i∗ commitments of P ∗ ∗ For i ∈ {i + 1, i + 2, · · · , k}: e by answering the random oracle queries with USim on the input (Ji , Mvi−1 , (Ci′ )i′ ∈J ) (a) Simulate P i e until P outputs a commitment Ci . (b) Run the extractor E on Ci to get the i-th prover’s message: (Mpi , Auxi ) ← E.ExtMsgUSim (Si ),UExt (Si ) (Ci ). (0) (c) Initialize V’s registers (Locι , Yι )ι∈[wi ] as the all-zero states and set Vi := Vi . (d) For q ∈ [di ]: (q) (q−1) (q−1) i. Simulate V to get the query locations: ((Locι , Yι )ι∈[wi ] , Vi ) ← Vi (x, (Locι , Yι )ι∈[wi ] , Vi ). e ii. Simulate P by answering the random oracle queries with USim on the leaked query locations e outputs ((Locι )ι∈[w ] , (Oi′ )i′ ∈I ). (Locι )ι∈[wi ] until P i i iii. Simulate the trusted third party O that implements the access to prover’s message registers: for i′ ∈ Ii ∩ {i∗ + 1, · · · , k}, ((Locι , Yι )ι∈[wi ] , Mpi′ ) ← O((Locι , Yι )ι∈[wi ] , Mpi′ ). iv. Check the opening: for i′ ∈ Ii ∩ {i∗ + 1, · · · , k}, (bi,q,i′ , (Locι )ι∈[wi ] , (Oi′ , Auxi′ )) ← E.AltCheck((Locι )ι∈[wi ] , (Oi′ , Auxi′ )). v. Output 0 and abort if ∧i′ ∈Ii ∩{i∗ +1,··· ,k} bi,q,i′ = 0. vi. Implement the access to the first i∗ messages for V: (bi,q , (Locι , Yι )ι∈[wi ] , (Ci′ , Oi′ )i′ ∈Ii ∩[i∗ ] ) ← QSVC.Query(USim (Si′ ))i′ ∈Ii ∩[i∗ ] (1λ , (Locι , Yι )ι∈[wi ] , (Ci′ , Oi′ )i′ ∈Ii ∩[i∗ ] ). vii. Output 0 and abort if bi,q = 0. e by answering the random oracle queries with USim on the registers ((Locι )ι∈[w ] , (Oi′ )i′ ∈I ) viii. Simulate P i i e until P outputs the updated (Locι )ι∈[wi ] . (e) If i ̸= k: i. Compute the i-th V’s message and the index set for the proofs to be returned: (d ) (d ) (Ji+1 , Mvi , Vi+1 ) ← Vi i (x, (Locι , Yι )ι∈[wi ] , Vi i ). ii. Compute the corresponding commitments in Ji+1 with the extractor E: 58

for i′ ∈ Ji+1 ∩ {i∗ + 1, · · · , k}, Ci′ ← E.AltCommitUSim (Si′ ),UExt (Si′ ) (Auxi′ , Mpi′ ). iii. Set Ii+1 := (Ii ∪ {i + 1}) \ Ji+1 . e wins: (f) If i = k, simulate V and check whether P (dk ) (d ) i. Compute bQIOP ← Vk (x, (Locι , Yι )ι∈[wk ] , Vk k ). ii. Output 1 if bQIOP = 1, |x| ≤ ν, and x ∈ / L(R); output 0 otherwise. e Then by Theorem 8.4 and the construction of hybrid games Hi∗ (P), |x| ≤ ν e = Pr  ∧ x ∈ / L(R) Pr Hk (P) ∧b = 1 

h

i

 S ← |⊥⟩  , x ← PeUSim (S) U (S) U (S) e Sim Sim b ← ⟨P ,V (x)⟩

(17)

 e e x ← P(P)  . e P), e V(x)⟩pq b ← ⟨P(

(18)

and  |x| ≤ ν h i e  / L(R) Pr H0 (P) = Pr ∧ x ∈ ∧b = 1

Furthermore, the only difference between two consecutive hybrid games is whether the message underlying a commitment is accessed through the QSVC interfaces or through the extractor, and thus can be bounded by the extractability of the quantum-state vector commitment scheme QSVC. e Claim 8.7. For every integer ν, t, m, i∗ ∈ [k], and a t-query argument adversary P, r

h i r h i2 (3) e − Pr Hi∗ −1 (P) e Pr Hi∗ (P) ≤ ξExt (t, d, t, 0, m, li∗ ) .

e and Hi∗ −1 (P) e is how they handle the i∗ -th commitment. Proof. The only difference between games Hi∗ (P) e all the queries of the underlying QIOP verifier V to the i∗ -th prover message are In the game Hi∗ (P), e all the queries of the underlying QIOP implemented by the interfaces of QSVC, while in the game Hi∗ −1 (P), verifier V to the i∗ -th prover message are implemented by the interfaces of the extractor. Consider an adversary A of QSVC that does the following: e where the queries to USim (Si∗ ) are forwarded to the oracles (instead of implementing 1. Simulate Hi∗ −1 (P) the access on its own) until the i∗ -th commitment Ci∗ is outputted. 2. Send Ci∗ to the game as the commitment, and keep all other registers in the register E as the internal state. 3. For i ∈ {i∗ , · · · , k}: (a) For q ∈ [di ]: e until queries to the i∗ -th prover’s message register are about to i. Continue to simulate Hi∗ −1 (P) be implemented. ii. Compute the query set to the i∗ -th prover’s message and denote it as Q, denote the corresponding answer register for these queries as Y, and denote the opening register for these queries as Oi∗ . Send (Q, Oi∗ , Y) to the game, and keep all other registers in the register E as the internal state. e until V outputs Ji+1 or V outputs the decision bit. (b) Continue to simulate Hi∗ −1 (P) ∗ (c) If i ∈ Ji+1 or V outputs the decision bit, inform the game that all queries to the underlying message are done.

59

e from where the adversary A stops. Consider a distinguisher D that continues to simulate Hi∗ −1 (P) e is exactly QSVCExtWorld(A, D). e ∗ Then the game Hi (P) is exactly QSVCSimWorld(A, D), and the game Hi∗ −1 (P) By the extractability of QSVC, r h i r h i2 e e Pr Hi∗ (P) − Pr Hi∗ −1 (P) =

p p 2 Pr [QSVCExtWorld(A, D)] − Pr [QSVCSimWorld(A, D)] (3)

≤ ξExt (t, d, t, 0, m, li∗ ) , P where we use the fact that the query depth of A to the underlying message is at most i≥i∗ di ≤ d, and moreover, A has at most t queries and at most query mass t to USim (Si∗ ) since simulating V does not require query access to USim (Si∗ ), and the queries of QSVC and the extractor to USim (Si∗ ) and UExt (Si∗ ) are all performed by the game. We combine Theorems 8.6 and 8.7 to prove Theorem 8.5. Proof of Theorem 8.5. By Theorem 8.7 and Eqs. (17) and (18) and the triangle inequality, v  2  v u u  S ← |⊥⟩ u u |x| ≤ ν |x| ≤ ν e e u  x ← P(P)  −u tPr ∧ x ∈ tPr  ∧ x ∈ / L(R) x ← PeUSim (S) / L(R) e P), e V(x)⟩pq b ← ⟨ P( U (S) U (S) e Sim , V Sim (x)⟩ ∧b = 1 ∧b = 1 b ← ⟨P  2 X q (3)  ≤ ξExt (t, d, t, 0, m, li ) i∈[k]

≤k·

X

(3)

ξExt (t, d, t, 0, m, li ) .

(By Cauchy–Schwarz inequality)

i∈[k]

Therefore,   RO ← U(m) |x| ≤ ν  / L(R) x ← PeRO Pr  ∧ x ∈ RO RO e , V (x)⟩ ∧b = 1 b ← ⟨P   S ← |⊥⟩ |x| ≤ ν (1)  + ξExt / L(R) x ← PeUSim (S) ≤ Pr  ∧ x ∈ (t + vq, m) (By Theorem 8.6) U (S) U (S) e Sim Sim ∧b = 1 b ← ⟨P ,V (x)⟩ v 2  u  s u |x| ≤ ν X (3) e P) e x ← P(  u (1) + k· / L(R) ξExt (t, d, t, 0, m, li ) + ξExt (t + vq, m) ≤ tPr  ∧ x ∈ e P), e V(x)⟩pq b ← ⟨P( ∧b = 1 i∈[k]   |x| ≤ ν X (3) e P) e x ← P( (1)  + 2k · / L(R) ξExt (t, d, t, 0, m, li ) + ξExt (t + vq, m) . ≤ 2Pr  ∧ x ∈ e P), e V(x)⟩pq b ← ⟨P( ∧b = 1 i∈[k] (By Cauchy–Schwarz inequality)

60

A

The QIOP that we use

We use the following QIOP in our transformation. Lemma A.1. There exists a QIOP for QMA with total proof length l = η · poly(ν), round complexity k = η · poly(log ν), query complexity q = η · poly(log ν), verifier-to-prover communication complexity vc = η · poly(log ν), completeness c = 1 − η · negl(ν), and public-query soundness spq = 3−η for instance size ν and positive integer η. In particular, taking η = ⌈(log ν)2 ⌉ yields a QIOP with polynomial total proof length, polylogarithmic round complexity, polylogarithmic query complexity, polylogarithmic verifier-to-prover communication, completeness negligibly close to 1, and negligible public-query soundness. Proof sketch. We show how to construct a public-coin QIOP for QMA with l = poly(ν), k = poly(log ν), q = poly(log ν), vc = poly(log ν), c = 1 − negl(ν), and s = 13 for instance size ν. The lemma then follows by repeating this QIOP sequentially η times, accepting only if all executions accept, and applying Theorem 3.5. Our construction is obtained by making three minor modifications to the protocol of [SV26]. This protocol satisfies all our requirements except that it allows the verifier to return only part of the prover’s first message register, has verifier-to-prover communication complexity vc = poly(ν), and is written as a private-coin protocol. Splitting the prover’s message. The verifier in [SV26] partitions the prover’s first message register into blocks and returns one block in each round. This partition is fixed in advance and publicly known. Therefore, we can modify the protocol by having the prover send these blocks in separate rounds, with the verifier sending dummy messages between consecutive prover messages. Then each return in the modified protocol consists of an entire prover’s message register from a single round. Reducing communication. Returning prover’s message registers do not contribute to vc. The only remaining long message is the final classical challenge specifying the Hamiltonian term used in the verification. As observed in Section 1.2.1 of [SV26], this communication can be reduced to O(log ν) bits by using the derandomized amplification technique of [BMVZ26]. Public-coin. The measurement basis and Hamiltonian-term challenges are already public in [SV26]. However, the choice of test branch and round, the sampled code stabilizers, and the PCPP verifier’s randomness are private in their formulation. We modify the protocol to make it public-coin as follows. Instead of choosing the test branch and round in advance, the verifier samples fresh public coins at each checkpoint to decide whether to continue or test and terminate, using conditional stopping probabilities that preserve the original distribution over tests. Each decision is made after all registers needed for the selected test have been received. The verifier then publicly samples the randomness needed for that test (e.g., the code stabilizers and PCPP randomness), performs the queries, and immediately accepts or rejects, without using any subsequent prover message. Thus, revealing the test randomness gives the prover neither an opportunity to alter the registers being tested nor an advantage in preparing subsequent proofs. The original soundness bound therefore continues to apply.

61

Acknowledgments The authors are supported in part by the Ethereum Foundation and the Global Chinese Community of Universal Digital Commons. The authors had access to OpenAI models through the ChatGPT for Academic Researchers program.

AI disclosure The authors used GPT-6 Astra to assist with identifying related work, improving the writing, and reviewing the proofs. The authors developed the proof ideas and wrote the final proofs, and take full responsibility for the paper.

References [AALV09]

Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani. “The Detectability Lemma and Quantum Gap Amplification”. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing. STOC ’09. ACM, 2009, pp. 417–426. DOI: 10.1145/1536414.1536472.

[AAV13]

Dorit Aharonov, Itai Arad, and Thomas Vidick. “Guest Column: The Quantum PCP Conjecture”. In: ACM SIGACT News 44.2 (2013), pp. 47–79. DOI: 10.1145/2491533.2491549.

[Bar+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: Proceedings of the 42nd Annual International Cryptology Conference. CRYPTO ’22. 2022, pp. 195– 211. DOI: 10.1007/978-3-031-15979-4_7.

[BCS16]

Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. “Interactive Oracle Proofs”. In: Proceedings of the 14th Theory of Cryptography Conference. TCC ’16-B. 2016, pp. 31–60. DOI: 10.1007/9783-662-53644-5_2.

[BDFLSZ11]

Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. “Random Oracles in a Quantum World”. In: Proceedings of the 17th International Conference on the Theory and Application of Cryptology and Information Security. ASIACRYPT ’11. 2011, pp. 41–69. DOI: 10.1007/978-3-642-25385-0_3.

[BG08]

Boaz Barak and Oded Goldreich. “Universal Arguments and Their Applications”. In: SIAM Journal on Computing 38.5 (2008). Preliminary version appeared in CCC ’02., pp. 1661–1694. DOI: 10.1137/ 070709244.

[BLM26]

James Bartusek, Jiahui Liu, and Giulio Malavolta. “A Modular Approach to Succinct Arguments for QMA”. In: Proceedings of the 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques. EUROCRYPT ’26. 2026, pp. 446–474. DOI: 10.1007/978-3-03225336-1_16.

[BM26]

James Bartusek and Giulio Malavolta. Succinct Arguments for QMA from Collapsing Hash Functions. Cryptology ePrint Archive, Report 2026/2040. 2026. URL: https://eprint.iacr.org/2026/ 2040.

[BMVZ26]

Thiago Bergamaschi, Tony Metger, Thomas Vidick, and Tina Zhang. “Derandomised Tensor Product Gap Amplification for Quantum Hamiltonians”. In: Proceedings of the 41st Annual IEEE Conference on Computational Complexity. CCC ’26. 2026, 15:1–15:22. DOI: 10.4230/LIPICS.CCC.2026.15. URL: https://doi.org/10.4230/LIPIcs.CCC.2026.15.

62

[CDDGS25]

Alessandro Chiesa, Marcel Dall’Agnol, Zijing Di, Ziyi Guan, and Nicholas Spooner. “Quantum Rewinding for IOP-Based Succinct Arguments”. In: Proceedings of the 23rd Theory of Cryptography Conference. TCC ’25. 2025, pp. 460–479. DOI: 10.1007/978-3-032-12296-4_16.

[CDGS23]

Alessandro Chiesa, Marcel Dall’Agnol, Ziyi Guan, and Nicholas Spooner. On the Security of Succinct Interactive Arguments from Vector Commitments. Cryptology ePrint Archive, Report 2023/1737. 2023. URL: https://eprint.iacr.org/2023/1737.

[CDHZ26]

Alessandro Chiesa, Zijing Di, Zihan Hu, and Yuxi Zheng. “How to Prove Post-Quantum Security for Succinct Non-Interactive Reductions”. In: Proceedings of the 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques. EUROCRYPT ’26. 2026, pp. 389–415. DOI: 10.1007/978-3-032-25336-1_14.

[CGMV26]

Alessandro Chiesa, Ziyi Guan, Ignacio Manzur, and Thomas Vidick. Succinctness Requires Probabilistic Checking in the Quantum World. Unpublished manuscript. 2026.

[CM24]

Lijie Chen and Ramis Movassagh. “Quantum Merkle Trees”. In: Quantum 8 (2024), p. 1380. DOI: 10.22331/q-2024-06-18-1380.

[CMS19]

Alessandro Chiesa, Peter Manohar, and Nicholas Spooner. “Succinct Arguments in the Quantum Random Oracle Model”. In: Proceedings of the 17th Theory of Cryptography Conference. TCC ’19. 2019, pp. 1–29. DOI: 10.1007/978-3-030-36033-7_1.

[CMSZ21]

Alessandro Chiesa, Fermi Ma, Nicholas Spooner, and Mark Zhandry. “Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier”. In: Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science. FOCS ’21. IEEE, 2021, pp. 49–58. DOI: 10.1109/ FOCS52979.2021.00014.

[CY24]

Alessandro Chiesa and Eylon Yogev. Building Cryptographic Proofs from Hash Functions. 2024. URL: https://github.com/hash-based-snargs-book/hash-based-snargs-book.

[DFMS22]

Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner. “Online-Extractability in the Quantum Random-Oracle Model”. In: Proceedings of the 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques. EUROCRYPT ’22. 2022, pp. 677–706. DOI: 10 . 1007/978-3-031-07082-2_24.

[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 ’23. ACM, 2023, pp. 1579–1588. DOI: 10.1145/3564246.3585198.

[GKNV25]

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 ’25. ACM, 2025, pp. 234–244. DOI: 10.1145/3717823.3718264.

[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 ’92. ACM, 1992, pp. 723–732. DOI: 10.1145/129712.129782.

[Mic00]

Silvio Micali. “Computationally Sound Proofs”. In: SIAM Journal on Computing 30.4 (2000). Preliminary version appeared in FOCS ’94., pp. 1253–1298. DOI: 10.1137/S0097539795284959.

[MNZ24]

Tony Metger, Anand Natarajan, and Tina Zhang. “Succinct Arguments for QMA from Standard Assumptions via Compiled Nonlocal Games”. In: Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science. FOCS ’24. IEEE, 2024, pp. 1193–1201. DOI: 10 . 1109 / FOCS61266.2024.00078.

[NC10]

Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. 10th Anniversary Edition. Cambridge University Press, 2010. DOI: 10.1017/CBO9780511976667.

[Pas03]

Rafael Pass. “On Deniability in the Common Reference String and Random Oracle Model”. In: Proceedings of the 23rd Annual International Cryptology Conference. CRYPTO ’03. 2003, pp. 316– 337. DOI: 10.1007/978-3-540-45146-4_19.

63

[RRR16]

Omer Reingold, Ron D. Rothblum, and Guy N. Rothblum. “Constant-Round Interactive Proofs for Delegating Computation”. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing. STOC ’16. ACM, 2016, pp. 49–62. DOI: 10.1145/2897518.2897652.

[SV25]

Baocheng Sun and Thomas Vidick. “Quantum Interactive Oracle Proofs”. In: Proceedings of the 23rd Theory of Cryptography Conference. TCC ’25. 2025, pp. 409–426. DOI: 10.1007/978-3-03212296-4_14.

[SV26]

Baocheng Sun and Thomas Vidick. “Probabilistically Checking Quantum Proofs, with Interaction”. In: Proceedings of the 41st Annual IEEE Conference on Computational Complexity. CCC ’26. 2026, 4:1–4:49. DOI: 10.4230/LIPIcs.CCC.2026.4.

[Wat03]

John Watrous. “PSPACE Has Constant-Round Quantum Interactive Proof Systems”. In: Theoretical Computer Science 292.3 (2003), pp. 575–588. DOI: 10.1016/S0304-3975(01)00375-9.

[Yan22]

Jun Yan. “General Properties of Quantum Bit Commitments (Extended Abstract)”. In: Proceedings of the 28th International Conference on the Theory and Application of Cryptology and Information Security. ASIACRYPT ’22. 2022, pp. 628–657. DOI: 10.1007/978-3-031-22972-5_22.

[Zha19]

Mark Zhandry. “How to Record Quantum Queries, and Applications to Quantum Indifferentiability”. In: Proceedings of the 39th Annual International Cryptology Conference. CRYPTO ’19. 2019, pp. 239–268. DOI: 10.1007/978-3-030-26951-7_9.

64