Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1911.08101 · Lecture notes in computer science

Non-interactive Classical Verification of Quantum Computation

Gorjan Alagic, Andrew M. Childs, Alex B. Grilo, Shih-Han Hung

Published Jan 1, 2020• 54 citations
arXivHTMLPDF
DOI
10.1007/978-3-030-64381-2_6

Related papers

Succinct Classical Verification of Quantum Computation

James Bartusek, Yael Tauman Kalai, Alex Lombardi +5 more

arXiv:2206.14929•Lecture notes in computer science•Jan 1, 2022•21 citations

Separating Non-Interactive Classical Verification of Quantum Computation from Falsifiable Assumptions

Mohammed Barhoush, Tomoyuki Morimae, Ryo Nishimaki +1 more

Mahadev [SIAM J. Comput. 2022] introduced the first protocol for classical verification of quantum computation based on the Learning-with-Errors (LWE) assumption, achieving a 4-message interactive scheme. This breakthrough naturally raised the question of whether fewer messages are possible in the plain model. Despite its importance, this question has remained unresolved. In this work, we prove that there is no quantum black-box reduction of non-interactive classical verification of quantum computation of $\textsf{QMA}$ to any falsifiable assumption. Here, "non-interactive" means that after an instance-independent setup, the protocol consists of a single message. This constitutes a strong negative result given that falsifiable assumptions cover almost all standard assumptions used in cryptography, including LWE. Our separation holds under the existence of a $\textsf{QMA} \text{-} \textsf{QCMA}$ gap problem. Essentially, these problems require a slightly stronger assumption than $\textsf{QMA}\neq \textsf{QCMA}$. To support the existence of such problems, we present a construction relative to a quantum unitary oracle.

quant-pharXiv:2602.18034•Lecture notes in computer science•Feb 23, 2026•1 citation

Classical Verification of Quantum Computations with Efficient Verifier

Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa

arXiv:1912.00990•Lecture notes in computer science•Jan 1, 2020•34 citations

On the Cryptographic Foundations of Interactive Quantum Advantage

Kabir Tomer, Mark Zhandry

In this work, we study the hardness required to achieve proofs of quantumness (PoQ), which in turn capture (potentially interactive) quantum advantage. A “trivial” or non-interactive PoQ simply assumes an (efficiently-verifiable) average-case hard problem for classical computers that is easy for quantum computers. However, there is much interest in “non-trivial” PoQs that actually rely on quantum hardness assumptions, instead of an assumed separation between quantum and classical computation for search problems, especially since these are often a starting point for more sophisticated protocols such as classical verification of quantum computation (CVQC). We show several lower-bounds for the hardness required to achieve non-trivial PoQ, specifically showing that they likely require cryptographic hardness, with different types of cryptographic hardness being required for different variations of non-trivial PoQ. In particular, our results help explain the challenges in using lattices to build publicly verifiable PoQ and its various extensions such as CVQC.

arXiv:2510.05082•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•4 citations

Experimental verification of quantum computation

Stefanie Barz, Joseph F. Fitzsimons, Elham Kashefi +1 more

arXiv:1309.0005•Nature Physics•Sep 29, 2013•150 citations

Information-theoretically-sound non-interactive classical verification of quantum computing with trusted center

Tomoyuki Morimae

The posthoc verification protocol [J. F. Fitzsimons, M. Hajdu{\v s}ek, and T. Morimae, Physical Review Letters {\bf120}, 040501 (2018)] enables an information-theoretically-sound non-interactive verification of quantum computing, but the message from the prover to the verifier is quantum and the verifier has to do single-qubit measurements. The Mahadev protocol removes these quantum parts, but the soundness becomes the computational one. In this paper, we construct an information-theoretically-sound non-interactive classical verification protocol for quantum computing with a trusted center. The trusted center sends random BB84 states to the prover, and the classical descriptions of these BB84 states to the verifier. The messages from the center to the prover and the verifier are independent of the instance. By slightly modifying our protocol, we also construct a non-interactive statistical zero-knowledge proof system for QMA with the trusted center.

arXiv:2003.10712•Mar 24, 2020•5 citations
Mahadev [SIAM J. Comput. 2022] introduced the first protocol for classical verification of quantum computation based on the Learning-with-Errors (LWE) assumption, achieving a 4-message interactive scheme. This breakthrough naturally raised the question of whether fewer messages are possible in the plain model. Despite its importance, this question has remained unresolved. In this work, we prove that there is no quantum black-box reduction of non-interactive classical verification of quantum computation of QMA\textsf{QMA}QMA to any falsifiable assumption. Here, "non-interactive" means that after an instance-independent setup, the protocol consists of a single message. This constitutes a strong negative result given that falsifiable assumptions cover almost all standard assumptions used in cryptography, including LWE. Our separation holds under the existence of a QMA-QCMA\textsf{QMA} \text{-} \textsf{QCMA}QMA-QCMA gap problem. Essentially, these problems require a slightly stronger assumption than QMA≠QCMA\textsf{QMA}\neq \textsf{QCMA}QMA=QCMA. To support the existence of such problems, we present a construction relative to a quantum unitary oracle.
In this work, we study the hardness required to achieve proofs of quantumness (PoQ), which in turn capture (potentially interactive) quantum advantage. A “trivial” or non-interactive PoQ simply assumes an (efficiently-verifiable) average-case hard problem for classical computers that is easy for quantum computers. However, there is much interest in “non-trivial” PoQs that actually rely on quantum hardness assumptions, instead of an assumed separation between quantum and classical computation for search problems, especially since these are often a starting point for more sophisticated protocols such as classical verification of quantum computation (CVQC). We show several lower-bounds for the hardness required to achieve non-trivial PoQ, specifically showing that they likely require cryptographic hardness, with different types of cryptographic hardness being required for different variations of non-trivial PoQ. In particular, our results help explain the challenges in using lattices to build publicly verifiable PoQ and its various extensions such as CVQC.
The posthoc verification protocol [J. F. Fitzsimons, M. Hajdu{\v s}ek, and T. Morimae, Physical Review Letters {\bf120}, 040501 (2018)] enables an information-theoretically-sound non-interactive verification of quantum computing, but the message from the prover to the verifier is quantum and the verifier has to do single-qubit measurements. The Mahadev protocol removes these quantum parts, but the soundness becomes the computational one. In this paper, we construct an information-theoretically-sound non-interactive classical verification protocol for quantum computing with a trusted center. The trusted center sends random BB84 states to the prover, and the classical descriptions of these BB84 states to the verifier. The messages from the center to the prover and the verifier are independent of the instance. By slightly modifying our protocol, we also construct a non-interactive statistical zero-knowledge proof system for QMA with the trusted center.