💻 computer science

Succinct Arguments for QMA in the Quantum Random Oracle Model

This paper presents the first succinct argument for QMA in the quantum random oracle model that relies solely on unstructured hardness by transforming public-query sound quantum interactive oracle proofs into quantum arguments using a novel commit-and-open paradigm with extractable vector commitments for quantum states.

Original authors: Alessandro Chiesa, Zihan Hu

Published 2026-09-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alessandro Chiesa, Zihan Hu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of modern computing, there is a persistent tension between the power of a machine and the ability of a human to verify its work. Imagine a supercomputer that can solve a problem in seconds, a task that would take a human lifetime to check. To trust the answer, we need a way to verify the result without re-doing the entire calculation. This is the realm of succinct arguments, a cryptographic tool that allows a verifier to check a claim with a tiny amount of communication, far smaller than the effort required to generate the claim itself. For classical computers, which process information in simple on-off switches, this problem has been largely solved using basic, unstructured tools like hash functions, which act as digital fingerprints. However, the next generation of computing promises to operate on quantum principles, where information exists in delicate states of superposition, allowing for a different kind of processing power. The question that has long hung over this field was whether these same simple, unstructured tools could verify the work of quantum computers, or if the complexity of the quantum world demanded entirely new, more complicated cryptographic structures.

A team of researchers at EPFL has now answered this question by constructing the first succinct argument for quantum verification that relies solely on unstructured hardness, specifically within a theoretical framework known as the quantum random oracle model. Their work demonstrates that idealized hash functions are sufficient not only for classical verification but also for the quantum realm. This is a significant departure from previous methods, which either required highly structured and complex cryptographic assumptions or relied on unproven conjectures about the nature of quantum complexity. By proving that the fundamental building blocks of classical cryptography can be extended to quantum systems, the researchers have shown that the path to verifying quantum computations is more direct and robust than previously thought.

The core of their achievement is a new method for translating a quantum interactive oracle proof into a succinct argument. To understand this, one must first picture a quantum interactive oracle proof as a conversation between a prover and a verifier. In this dialogue, the prover holds a massive amount of quantum data, a "witness," and the verifier wants to check if this data is valid. Instead of sending the entire dataset, which would be impossible, the prover commits to the data in a way that creates a short, unique summary. The verifier then asks specific questions, and the prover provides only the small pieces of data needed to answer those questions. The challenge in the quantum world is that the verifier's questions might be asked in a superposition, meaning they are asking about many locations at once, and the prover cannot simply copy the data to keep a record of what was asked due to the laws of quantum mechanics.

To solve this, the researchers developed a sophisticated "commit-and-open" compiler. This system acts as a translator that takes the complex, multi-round quantum dialogue and compresses it into a highly efficient argument. A critical innovation in their work is the creation of a new type of commitment scheme for quantum states. In classical computing, a commitment scheme is like a sealed envelope: you put a message inside, seal it, and later you can open it to prove what was inside. In the quantum world, the researchers had to design a scheme that not only seals the message but also allows the prover to coherently erase their memory of which specific parts of the message were opened, and to recover the original state if the verifier returns a previously used piece of data. They achieved this by constructing a "quantum state vector commitment" that functions like a digital tree structure, where each branch is secured by the random oracle. This structure allows for local openings, meaning the prover can reveal just a few leaves of the tree without exposing the whole thing, while maintaining the integrity of the entire system.

The researchers proved that this new system is extractable, meaning that if a malicious prover attempts to submit an invalid proof, a special algorithm can extract the true underlying quantum state from their commitment. This property is essential for security; it ensures that the prover cannot fake a valid proof without actually possessing the correct quantum witness. By combining this extractable commitment with a known quantum interactive oracle proof, they created a protocol where the communication cost grows only logarithmically with the size of the problem. This means that even for massive quantum computations, the amount of data exchanged to verify the result remains small and manageable.

The significance of this result lies in its simplicity and its reliance on minimal assumptions. Previous attempts to verify quantum computations required complex, structured cryptographic primitives that were difficult to implement and analyze. By showing that unstructured hardness alone is sufficient, the researchers have removed a major barrier to the practical application of quantum verification. Their work establishes that the idealized hash functions, which are already the backbone of classical security, are powerful enough to secure the quantum future. This finding resolves a long-standing open question in the field, confirming that the tools needed to verify quantum claims are not fundamentally different from those used for classical ones, but rather require a new way of applying them to the unique properties of quantum states. The result is a robust, efficient, and theoretically sound method for ensuring the integrity of quantum computations, paving the way for more secure and trustworthy quantum technologies.

Technical Summary: Succinct Arguments for QMA in the Quantum Random Oracle Model

Problem Statement

Succinct arguments are cryptographic primitives allowing a verifier to check computational claims with communication complexity significantly smaller than the cost of direct verification. In the classical setting, succinct arguments for NP are well-established and can be constructed from "unstructured" hardness assumptions alone (e.g., hash functions) by compiling Probabilistically Checkable Proofs (PCPs) or Interactive Oracle Proofs (IOPs) via the commit-and-open paradigm.

However, extending these results to QMA (Quantum Merlin-Arthur), the quantum analogue of NP involving quantum witnesses, has remained an open challenge. Prior constructions for succinct arguments for QMA relied on either:

Structured cryptographic assumptions (e.g., lattice-based hardness, oblivious state preparation).
Unproven complexity conjectures, specifically the Quantum PCP (QPCP) conjecture, which posits the existence of efficient quantum proofs with constant query complexity.

The central question addressed by this paper is: Can succinct arguments for QMA be constructed based solely on unstructured hardness (like hash functions), without relying on structured assumptions or the QPCP conjecture?

Methodology

The authors propose a solution in the Quantum Random Oracle Model (QROM), where all parties have quantum access to a uniformly sampled random oracle. Their approach generalizes the classical commit-and-open paradigm to the fully quantum setting. The methodology consists of three main technical pillars:

1. Quantum Interactive Oracle Proofs (QIOPs)

The authors define a robust model for Quantum Interactive Oracle Proofs (QIOPs). Unlike standard Quantum Interactive Proofs (QIPs), QIOPs allow the verifier to make "local" queries to the prover's message registers. To support the commit-and-open compilation, the authors introduce specific features to the QIOP model:

Superposition Queries: The verifier can query the prover's proof registers in superposition.
Returning Proof Oracles: The verifier may return previously submitted proof registers to the prover for use in later rounds (crucial for multi-round interactions where the prover cannot clone states).
Public-Query Soundness: A new security notion formalized for QIOPs. It requires that soundness holds even if the verifier's query locations (which may be in superposition) are leaked to a malicious prover immediately before and after each query. This is necessary because, in the compiled argument, the prover must learn the query locations to provide openings.

2. Extractable Quantum State Vector Commitments (QSVC)

To compile a QIOP into a succinct argument, the prover must commit to a long quantum state and later open specific locations queried by the verifier. The authors identify that standard vector commitments are insufficient for the quantum setting due to:

Coherent Openings: If query locations are in superposition, the prover's retained registers become entangled with the verifier's location register. Without coherent erasure of "which-path" information, the protocol fails.
State Recovery: When the verifier returns a proof oracle, the prover must recover the underlying updated quantum state from the succinct commitment.

To address this, the authors define Extractable Quantum State Vector Commitments (QSVC) in the QROM. Their definition includes:

Update Procedure: Allows the honest prover to coherently erase records of query locations after opening.
Recover Procedure: Allows the prover to recover the underlying quantum message when a commitment is returned.
Online Extractability: A strong security notion where an extractor, given access to the compressed oracle database, can recover the committed quantum state online (before the prover chooses openings) and validate openings subsequently. This enables a straightline reduction from the soundness of the argument to the public-query soundness of the underlying QIOP.

3. Construction and Compilation

The authors construct an extractable QSVC using a Quantum State Tree Commitment (QSTC). This combines a Merkle tree structure with a basic extractable succinct quantum state commitment. The basic commitment evaluates a random oracle on both the computational and Hadamard bases of the message register. The extractor uses the compressed oracle technique to coherently recover preimages, relating opening verification to an EPR-type consistency test.

Finally, they present a transformation that compiles any public-query QIOP into a succinct quantum interactive argument in the QROM. This transformation preserves the efficiency of the underlying QIOP.

Key Contributions

First Succinct Argument for QMA from Unstructured Hardness: The paper constructs the first succinct argument for QMA in the QROM that relies only on the existence of a random oracle (idealized unstructured hardness), without structured assumptions or the QPCP conjecture.
Formalization of Public-Query QIOPs: The authors formalize the notion of public-query soundness for QIOPs, capturing the requirement that soundness holds even when query locations are leaked to the prover in superposition.
Extractable QSVCs: They define and construct extractable quantum state vector commitments with local openings, Update, and Recover procedures. This primitive is of independent interest for quantum cryptography.
Efficiency-Preserving Compiler: They provide a compiler that transforms any public-query QIOP into a succinct argument, maintaining the round and communication complexity of the underlying proof system (up to logarithmic factors).

Results

The main results are summarized as follows:

Theorem 1: In the QROM, there exists a succinct quantum interactive argument for QMA with communication complexity $poly(\lambda, \log \nu)$ , where $\nu$ is the instance size and $\lambda$ is the security parameter.
Theorem 2 (Informal): There exists a transformation $T$ that compiles a QIOP with round complexity $k$ , proof length $l$ , query complexity $q$ , and verifier-to-prover communication $vc$ into a quantum interactive argument with communication complexity $O(\lambda k + \lambda q \log l + vc)$ . The soundness error is $O(s_{pq} + k \cdot poly(t, l, q) \cdot 2^{-\lambda})$ , where $s_{pq}$ is the public-query soundness error of the QIOP.
Theorem 3 (Informal): They construct an extractable QSVC in the QROM with extraction error $\xi_{Ext} = O(t^3 \cdot poly(n, \lambda) \cdot 2^{-\lambda})$ against $t$ -query quantum adversaries.
Corollary 8.3: By instantiating the compiler with the recent efficient QIOP for QMA from [SV26] (which satisfies public-query soundness), the authors obtain a succinct argument for QMA with polylogarithmic round complexity and total communication complexity $poly(\log \nu, \lambda)$ .

Significance and Claims

The paper claims to resolve the open question posed by [BLM26] regarding the feasibility of succinct arguments for QMA based solely on unstructured hardness, within the oracle model.

Unification of NP and QMA: The result demonstrates that ideal hash functions (modeled by the random oracle) suffice for succinct arguments not only for NP but also for QMA.
Independence from QPCP: Unlike previous approaches that required the unresolved QPCP conjecture, this construction relies on known efficient QIOPs (specifically [SV26]) and the QROM.
Technical Novelty: The work introduces the first framework for "online" extraction of quantum states from commitments, handling the complexities of superposition queries and state recovery, which were previously unaddressed in the context of succinct arguments.

The authors note that while their result is in the QROM, establishing an analogous result in the plain model (from collapsing hash functions) is being addressed in independent concurrent work. Their contribution specifically lies in the QROM construction and the development of the extractable QSVC primitive and the public-query QIOP compiler.