PaperlayerView exact revision on arXiv

Source-linked AI summary

Succinct Arguments for QMA in the Quantum Random Oracle Model

Alessandro Chiesa, Zihan Hu

arXiv:2609.37429v2quant-phcs.CR

TL;DR

Known succinct arguments for QMA rely on structured cryptographic assumptions or an unresolved QPCP conjecture. This paper compiles public-query-sound QIOPs into quantum arguments in the QROM using extractable quantum-state commitments, yielding a succinct argument for QMA with communication poly(λ, log ν).

  • Problem

    Known succinct arguments for QMA rely on structured cryptographic assumptions or a QPCP for QMA whose existence remains an open problem.

    Source: §1 · p. 3

  • Method

    The paper compiles public-query-sound QIOPs into quantum arguments in the QROM and constructs extractable quantum-state commitments with local openings.

    Source: §1.1 · pp. 4–5

  • Results

    Communication complexity is poly(λ, log ν) for a succinct quantum interactive argument for QMA in the QROM.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The compiler applies to any public-query-sound QIOP while essentially preserving efficiency.

    Source: §1.1 · p. 4

    The formal model treats public-coin QIOPs and assumes query positions can be taken as {0, 1}^n without loss of generality.

    Source: §3.3 · p. 20, §5.2 · p. 24

Abstract

from arXiv · show

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.

1 Introduction

Classical commit-and-open techniques yield succinct arguments from unstructured hardness, but known QMA constructions rely on structured assumptions or an unresolved QPCP conjecture. The paper answers whether QMA arguments can instead be obtained from unstructured hardness in the QROM, using a quantum commit-and-open compiler and extractable quantum-state commitments.

1.2 Related work

  • Earlier succinct-QMA approaches used structured assumptions or required a QPCP for QMA, whose existence remains conjectural.The QPCP-based commit-and-open approaches include and [GJMZ23].Source: §1 · p. 3, §1.2 · p. 7

1.1 Our results

  • In the QROM, a succinct quantum interactive argument for QMA has communication complexity poly(λ, log ν) for instance size ν and security parameter λ.The result uses a uniformly sampled random oracle accessible to all parties, including malicious ones.Source: §1.1 · p. 3
  • The compiler transforms any public-query-sound QIOP into a quantum interactive argument in the QROM while essentially preserving efficiency.Its communication is O(λk + λq log l + vc), with soundness error O(spq + k · poly(t, l, q) · 2^-λ).Source: §1.1 · p. 4
  • The QIOP model supports superposition queries, returned proof oracles, and adaptive queries before those oracles are returned.These features occur across recent QIOP constructions and are supported by the compiler’s target model.Source: §1.1 · p. 4
  • Public-query soundness for QIOPs requires soundness to hold even when a malicious prover accesses query-location registers immediately before and after each superposition query.The efficient QIOP in [SV26] satisfies this definition.Source: §1.1 · p. 5
  • The QSVC interface adds coherent query-record erasure and recovery of a quantum message when the verifier returns its commitment.These procedures address the dephasing risk from superposition openings and support returned proof oracles.Source: §1.1 · p. 5
  • The paper constructs an unconditionally extractable QSVC in the QROM using a quantum-state tree commitment, with extraction error O(t^3 · poly(n, λ) · 2^-λ) for t-query adversaries making a single opening.The construction combines a Merkle tree with a basic extractable quantum-state commitment and supports adaptive local openings.Source: §1.1 · p. 6

2 Preliminaries

The preliminaries establish the paper’s notation and formal framework for quantum computation, oracle access, QMA relations, and quantum interactive arguments in the quantum random oracle model.

2.1 Quantum states, operators, and circuits

  • A register is a finite-dimensional complex Hilbert space, and the preliminaries fix bra-ket, tensor-product, circuit, operator, and measurement conventions.Source: §2.1 · p. 8

2.2 Oracle circuits and oracle algorithms

  • Oracle-aided circuits query functions through a unitary gate, while stateful-oracle algorithms may become entangled with the oracle’s state register.Source: §2.2 · p. 9

2.3 Compressed oracles

  • The compressed-oracle framework represents a random oracle through a database of queried images and provides tools for analyzing collision-free executions.Source: §2.3 · pp. 10–11

2.4 Relations and languages

  • A relation pairs classical instances with quantum witness states, and QMA consists of languages whose relations have efficient deciders.Source: §2.4 · p. 13

2.5 Quantum interactive arguments

  • A quantum interactive argument has a polynomial-time prover and verifier exchanging quantum messages, with both parties accessing a random oracle in the QROM.Source: §2.5 · p. 13

3 Quantum interactive oracle proofs

The section defines QIOPs as quantum interactive proofs with local verifier access to prover-message registers. It formalizes superposition queries and public-query soundness, including the case where query locations are leaked to the prover.

3 Quantum interactive oracle proofs

  • QIOPs combine QPCPs with QIPs, allowing the verifier to read only part of a prover’s message.Source: §3 · p. 15

3.1 Review: quantum interactive proofs

  • A QIP is a multi-round interaction between a computationally unbounded prover and a quantum polynomial-time verifier, with completeness and soundness conditions.Source: §3.1 · p. 15

3.2 Our notion of QIOPs

  • QIOPs define local access through superposition queries to prover-message subregisters, while allowing previously submitted registers to return to the prover without locality cost.The model also specifies round, query, proof-length, and verifier-to-prover communication measures.Source: §3.2 · pp. 16–18

3.3 Public-query QIOPs

  • Public-query soundness requires soundness to persist when query locations are leaked to the malicious prover before and after superposition queries.Every public-coin QIOP with soundness s has public-query soundness spq(ν) = s(ν).Source: §3.3 · pp. 19–20

4 Defining extractable quantum state commitments

Section 4 defines canonical quantum state commitments in the QROM and formalizes extractability through a simulator and message extractor. Canonical commitments are perfectly correct, and extraction compares adversarial openings with the extractor’s recovered message.

4.1 A canonical quantum state commitment

  • Canonical commitments apply a unitary to the message and zero-initialized ancillas, split the output into commitment and opening registers, and verify by applying the inverse and checking the ancillas.A valid check returns the original message while preserving its entanglement with external registers.Source: §4.1 · p. 21
  • A commitment is succinct when its commitment register is shorter than the quantum message; an n-to-t scheme commits to n qubits using t commitment qubits.Source: §4.1 · p. 21
  • Every canonical quantum state commitment scheme in the defined form has perfect correctness.Perfect correctness is defined against every oracle function, unbounded quantum adversary, and unbounded quantum distinguisher.Source: §4.1 · p. 21

4.2 The extractability definition

  • The extractor recovers a message and auxiliary state from the commitment, then uses the opening and auxiliary state to decide whether the opening is valid.The simulator maintains oracle side information in a state register; the extractor oracle is required not to disturb the simulation, and parallel calls to either oracle commute.Source: §4.2 · p. 22
  • Extractability compares the adversary’s outcome in a simulated-oracle game with an extraction game that substitutes the recovered message and alternative opening check.The adversary can query both simulator and extractor oracles, with query-mass bounds specified in the definition.Source: §4.2 · p. 23

5 Construction of extractable commitments to quantum states

This section constructs and analyzes extractable commitments to quantum states, using random-oracle queries in the standard and Hadamard bases. It develops extraction and opening analyses, including bounds on an adversary’s opening state and a general operator bound.

5.1 An extractable basic succinct commitment scheme

  • Construction 5.2 uses a 2m-qubit ancilla, computes the hash in the standard basis with Z1 and in the Hadamard basis with Z2, and has perfect correctness.Source: §5.1 · p. 24

5.2 Extractor for the commitment scheme

  • The extractor uses the simulator’s database and a preimage-finding unitary to recover the committed message from the commitment, then checks the opening with auxiliary registers.Its ExtMsg procedure invokes the coherent inverse and oracle operations on two message registers, and AltCheck tests the opening against the extracted state.Source: §5.2 · pp. 24–25

5.3 Analysis of the commitment scheme

  • The analysis establishes extractability using a simulator with database side information and the extractor with preimage-finding access.A collision-free variant supports offline extraction after the adversary produces an opening, provided no collision occurs during extraction and checking.Source: §5.3 · p. 26

5.4 Proof of Lemma 5.6

  • The proof of Lemma 5.6 bounds the discrepancy between the opening check and the extractor’s alternative check using intermediate claims about the extractor operations.The proof invokes Claim 5.9 to bound the relevant state difference and compares the projections used to test opening validity.Source: §5.3 · p. 26, §5.4 · pp. 33–34
  • The proof of Lemma 5.6 decomposes the opening-state error and bounds it using database size at most t and the fact that error accrues only when the adversary queries Inv.Combining the bounds yields the claim via Equation (13).Source: §5.4 · pp. 35–36

5.5 Proof of Claim 5.7

  • Claim 5.11 bounds the commutator for self-adjoint A commuting with each empty-database projector by partitioning database occupancy patterns and bounding patterns with at most t occupied locations.The proof uses that the occupancy-pattern measurement commutes with both ΠNoHatZero and A, then applies Cauchy–Schwarz.Source: §5.5 · pp. 36–37
  • Claim 5.7 follows by applying Claim 5.11 to ΠNoCol and Inv, which commute with every empty-database projector, together with two further claims.Source: §5.5 · p. 37

6 Defining extractable quantum state vector commitments

Section 6 defines quantum state vector commitments with local openings and formalizes their extractability in the QROM. Their interface supports commitment, opening, queries, updates, and recovery, while extraction reconstructs and checks the message against adversarial openings.

6.1 Syntax for quantum state vector commitments

  • A quantum state vector commitment provides algorithms for committing, locally opening, querying, updating, and recovering a quantum message.The commitment register is polynomial in the security parameter, while the opening size is polynomial in the query-set size, log n, and security parameter.Source: §6.1 · pp. 40–41
  • The opening algorithm returns an opening and unused auxiliary state; the query algorithm validates the opening, recovers the queried message positions, swaps them into the answer register, and restores the updated commitment and opening.Source: §6.1 · p. 40
  • Perfect correctness requires valid local decommitments and recovery of the updated message after queries.The correctness experiment commits, opens, queries, updates, and recovers, accepting only when both query validation and recovery succeed.Source: §6.1 · pp. 40–41

6.2 The extractability definition

  • The extractor recovers a message and auxiliary state, checks openings against the query set, and can form an alternative commitment to the updated extracted message.Source: §6.2 · pp. 41–42
  • The extractability games compare adversarial superposition queries against the original commitment with queries checked using the extracted message and alternative commitment.The definition also requires the extractor oracle not to disturb the simulator and constrains adversarial query mass across the two oracles.Source: §6.2 · p. 42

7 Construction of extractable quantum state vector commitments

This section constructs an extractable quantum state vector commitment by composing succinct quantum commitments over a Merkle tree, with succinct commitment and local-opening sizes. It proves extractability by comparing simulator and extractor worlds through hybrid games, bounding changes involving query locations and using the triangle and Cauchy–Schwarz inequalities.

7.1 Labeling the Merkle tree

  • Merkle-tree vertices use bit-string labels encoding left-or-right path choices; parents, siblings, paths, and authentication paths are defined from those labels.The root is ε, and each child appends 0 for left or 1 for right.Source: §7.1 · p. 43

7.2 An extractable quantum state vector commitment scheme

  • QSTC has commitment size O(λ) and opening size O(λ |Q| log n), satisfying local opening and perfect completeness.The construction composes succinct quantum commitments along a Merkle tree; perfect completeness follows from the underlying commitment’s perfect completeness.Source: §7.2 · pp. 43, 45

7.3 Extractor for the vector commitment scheme

  • EQSTC recursively applies the underlying commitment extractor at each Merkle-tree node to recover the message and auxiliary registers, with alternative checking and commitment interfaces.Its alternative commitment reverses extraction except that it does not check whether the ancilla qubits return to zero.Source: §7.3 · pp. 45–46

7.4 Security analysis of the vector commitment scheme

  • Theorem 7.3 establishes that QSTC is extractable using simulator O(D), extractor oracle Inv(D), and extractor EQSTC.The theorem’s stated extractability parameter is truncated in the supplied passage.Source: §7.4 · p. 46
  • For a single opening, the simulated-query and offline-extraction worlds are indistinguishable absent collisions; standard hybrids and low collision probability yield the extractability proof.The argument invokes that a quantum algorithm cannot obtain a database collision with high probability.Source: §7.4 · p. 46

7.5 Proof of Lemma 7.4

  • The proof fixes the query set and uses hybrids to replace each extractor message-extraction call with CM.Check and each inverse call with CM.Com.The reduction uses the corresponding subnormalized states and the triangle inequality.Source: §7.5 · p. 49
  • The states in QSVCSimWorld1Open* and QSVCOffExtWorld1Open* are shown to be close in ℓ2 norm.The proof combines the hybrid comparisons using T ≤ n and the triangle inequality.Source: §7.5 · pp. 52, 55
  • Fixing the query set Q makes the first and final hybrid games equivalent to QSVCOffExtWorld1Open* and QSVCSimWorld1Open*, respectively.The proof identifies H1_1 with the fixed-query extractor world and H4 with the fixed-query simulator world.Source: §7.5 · p. 53
  • Replacing CM.CheckNoCollision with ECM.ExtMsgNoCollision followed by ECM.AltCheck incurs a loss bounded by w2 + 4n + 8 · 2^-m/2.This replacement is analyzed when a location is extracted and then checked in the hybrid sequence.Source: §7.5 · p. 53
  • The step incurs an error of 6(t + 8n) · 2^(-m/2), with database size always bounded by t+8n and collision checks at the beginning and end of each game.Source: §7.5 · p. 55
  • The proof of Lemma 7.4 uses the triangle inequality and then the Cauchy–Schwarz inequality.Source: §7.5 · p. 55

8 Quantum interactive arguments based on QIOPs

This section transforms public-query-sound QIOPs into quantum-communication interactive arguments using extractable quantum state vector commitments; with QSTC, it yields succinct arguments in the QROM when the underlying QIOP is efficient. It establishes the extractability step by relating simulated hybrid games to the QSVC simulation and extraction worlds, then combines the claims to prove Lemma 8.5.

8.1 Our transformation

  • The IBCS transformation applies to public-query-sound QIOPs and extractable quantum state vector commitments; with QSTC, the verifier makes O(q log lmax) random-oracle queries.When the commitment has perfect completeness, the argument retains the QIOP’s completeness; with QSTC, prover-to-verifier communication is O(λk + λq log lmax).Source: §8 · p. 56, §8.1 · p. 57

8 Quantum interactive arguments based on QIOPs

  • With QSTC, an efficient public-query-sound QIOP yields a quantum-communication succinct interactive argument in the QROM, with O(poly(log ν)) rounds and O(poly(log ν, λ)) total communication.The resulting argument has the same completeness guarantee as the QIOP and soundness error negl(ν) + 2−λt3poly(ν) against t-query quantum adversaries.Source: §8.1 · p. 57

8.2 The malicious QIOP prover

  • The soundness reduction constructs a malicious QIOP prover that simulates the argument prover’s random-oracle access and extracts committed prover messages for the underlying QIOP verifier.It uses the commitment scheme’s simulator and extractor, with a trusted third party implementing queries to the extracted messages.Source: §8.2 · p. 58

8.3 Proof of Theorem 8.1

  • Theorem 8.1’s proof first replaces the random oracle with its simulator, then uses hybrids that replace commitment-query access with extractor access, bounding the change by extractability.The first replacement is analyzed with t + vq oracle queries; the hybrids handle commitments one at a time.Source: §8.3 · pp. 59, 61
  • The distinguisher’s continuation makes the adjacent hybrid games exactly the QSVC simulation and extraction worlds, enabling application of extractability.The adversary’s message-query depth is at most d, with at most t queries and query mass t to the simulator oracle, since verification requires no access to that oracle.Source: §8.3 · p. 62
  • Lemma 8.5 follows by combining Claims 8.6 and 8.7 with Eqs. (17) and (18), the triangle inequality, and Cauchy–Schwarz.The proof’s intermediate bound also invokes Claim 8.6.Source: §8.3 · p. 62

A The QIOP that we use

The paper adapts the [SV26] protocol into a public-coin QIOP for QMA with polynomial proof length and polylogarithmic rounds, queries, and verifier-to-prover communication. Sequential repetition yields negligible public-query soundness while preserving completeness negligibly close to 1.

A The QIOP that we use

  • Taking η = ⌈(log ν)2⌉ gives a QIOP for QMA with polynomial proof length, polylogarithmic rounds and queries, and negligible public-query soundness.Its completeness is negligibly close to 1.Source: A The QIOP that we use · p. 63
  • Sequentially repeating the public-coin QIOP η times and accepting only if every execution accepts yields the stated completeness and soundness parameters.The proof sketch starts from a protocol with polynomial proof length, polylogarithmic rounds, queries, and verifier-to-prover communication, and soundness 1/3.Source: A The QIOP that we use · p. 63

Splitting the prover’s message

  • The construction modifies [SV26] to split the prover’s first-message register into separate rounds, preserving the publicly known block partition.The verifier inserts dummy messages between consecutive prover messages, so each return is an entire message register from one round.Source: A The QIOP that we use · p. 63

Reducing communication

  • The protocol reduces verifier-to-prover communication to O(log ν) bits by applying derandomized amplification to the final Hamiltonian-term challenge [BMVZ26].Returning prover-message registers do not contribute to this communication complexity.Source: A The QIOP that we use · p. 63

Public-coin

  • The protocol makes test-branch, round, stabilizer, and PCPP randomness public only after the registers needed for each test are received.Conditional stopping preserves the original test distribution, and immediate accept/reject prevents later prover messages from exploiting revealed randomness; the original soundness bound therefore continues to apply.Source: A The QIOP that we use · p. 63

AI disclosure

The authors disclose using GPT-6 Astra to assist with related-work identification, writing improvements, and proof review; they state that they developed the proof ideas and wrote the final proofs.

AI disclosure

  • The authors state that they developed the proof ideas, wrote the final proofs, and take full responsibility for the paper.GPT-6 Astra assisted with identifying related work, improving writing, and reviewing proofs.Source: AI disclosure · p. 64
Loading 2609.37429v2…