arXiv:2609.37429
Succinct Arguments for QMA in the Quantum Random Oracle Model
Alessandro Chiesa, Zihan Hu
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.
AI Summary
Can succinct arguments for $\mathrm{QMA}$ be obtained from unstructured cryptographic hardness without assuming a quantum PCP conjecture? This paper establishes feasibility in the quantum random oracle model (QROM), where all parties have quantum access to an ideal random hash function. The resulting quantum interactive argument has communication $\mathrm{poly}(\lambda,\log n)$ for instance size $n$ and security parameter $\lambda$. The main construction is a commit-and-open compiler for quantum interactive oracle proofs (QIOPs). For a QIOP with $r$ rounds, total proof length $L$, query complexity $q$, and verifier-to-prover communication $v$, the compiled argument communicates $O(\lambda r+\lambda q\log L+v)$ qubits. Its soundness error is $O(s+r\,\mathrm{poly}(Q,L,q)2^{-\lambda})$ against $Q$-query adversaries, where $s$ is the QIOP’s public-query soundness error. Instantiating the compiler with an existing QIOP gives the QMA result. The technical ingredient is an online-extractable quantum-state vector commitment with local openings, built from a Merkle-style tree and commitments hashing computational- and Hadamard-basis labels. Compressed-oracle techniques enable coherent extraction before openings are chosen and a straightline soundness reduction. Additional procedures preserve superposition-query coherence and recover updated proof states when returned to the prover. The compiler requires soundness even when the prover accesses query-location registers before and after each query; ordinary QIOP soundness alone is insufficient. The result uses an ideal oracle and quantum communication and verification, rather than giving a plain-model or classical-verifier construction. Independent concurrent work establishes plain-model feasibility through different techniques.
The authors used GPT-6 Astra to assist with identifying related work, improving the writing, and reviewing the proofs.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 66 pages. v2: Minor changes