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:2003.10712

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

Tomoyuki Morimae

Published Mar 24, 2020• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2003.10712

Related papers

Trusted center verification model and classical channel remote state preparation

Tomoyuki Morimae, Yuki Takeuchi

The classical channel remote state preparation (ccRSP) is an important two-party primitive in quantum cryptography. Alice (classical polynomial-time) and Bob (quantum polynomial-time) exchange polynomial rounds of classical messages, and Bob finally gets random single-qubit states while Alice finally gets classical descriptions of the states. In [T. Morimae, arXiv:2003.10712], an information-theoretically-sound non-interactive protocol for the verification of quantum computing was proposed. The verifier of the protocol is classical, but the trusted center is assumed that sends random single-qubit states to the prover and their classical descriptions to the verifier. If the trusted center can be replaced with a ccRSP protocol while keeping the information-theoretical soundness, an information-theoretically-sound classical verification of quantum computing is possible, which solves the long-standing open problem. In this paper, we show that it is not the case unless BQP is contained in MA. We also consider a general verification protocol where the verifier or the trusted center first sends quantum states to the prover, and then the prover and the verifier exchange a constant round of classical messages. We show that the first quantum message transmission cannot be replaced with an (even approximate) ccRSP protocol while keeping the information-theoretical soundness unless BQP is contained in AM. We finally study the verification with the computational soundness. We show that if a ccRSP protocol satisfies a certain condition even against any quantum polynomial-time malicious prover, the replacement of the trusted center with the ccRSP protocol realizes a computationally-sound classical verification of quantum computing. The condition is weaker than the verifiability of the ccRSP.

arXiv:2008.05033•Aug 11, 2020•2 citations

Robust verification of quantum computation

Alexandru Gheorghiu

Quantum computers promise to offer a considerable speed-up in solving certain problems, compared to the best classical algorithms. In many instances, the gap between quantum and classical running times is conjectured to be exponential. While this is great news for those applications where quantum computers would provide such an advantage, it also raises a significant challenge: how can classical computers verify the correctness of quantum computations? In attempting to answer this question, a number of protocols have been developed in which a classical client (referred to as verifier) can interact with one or more quantum servers (referred to as provers) in order to certify the correctness of a quantum computation performed by the server(s). These protocols are of one of two types: either there are multiple non-communicating provers, sharing entanglement, and the verifier is completely classical; or, there is a single prover and the classical verifier has a device for preparing or measuring quantum states. The latter type of protocols are, arguably, more relevant to near term quantum computers, since having multiple quantum computers that share a large amount of entanglement is, from a technological standpoint, extremely challenging. Before the realisation of practical single-prover protocols, a number of challenges need to be addressed: how robust are these protocols to noise on the verifier's device? Can the protocols be made fault-tolerant without significantly increasing the requirements of the verifier? How do we know that the verifier's device is operating correctly? Could this device be eliminated completely, thus having a protocol with a fully classical verifier and a single quantum prover? Our work attempts to provide answers to these questions. First, we consider a single-prover verification protocol developed by Fitzsimons and Kashefi and show that this protocol is indeed robust with respect to deviations on the quantum state prepared by the verifier. We show that this is true even if those deviations are the result of a correlation with the prover's system. We then use this result to give a verification protocol which is device- independent. The protocol consists of a verifier with a measurement device and a single prover. Device-independence means that the verifier need not trust the measurement device (nor the prover) which can be assumed to be fully malicious (though not communicating with the prover). A key element in realising this protocol is a robust technique of Reichardt, Unger and Vazirani for testing, using non-local correlations, that two untrusted devices share a large number of entangled states. This technique is referred to as rigidity of non-local correlations. Our second result is to prove a rigidity result for a type of quantum correlations known as steering correlations. To do this, we first show that steering correlations can be used in order to certify maximally entangled states, in a setting in which each test is independent of the previous one. We also show that the fidelity with which we characterise the state, in this specific test, is optimal. We then improve the previous result by removing the independence assumption. This then leads to our desired rigidity result. We make use of it, in a similar fashion to the device-independent case, in order to give a verification protocol that is one-sided device-independent. The importance of this application is to show how different trust assumptions affect the efficiency of the protocol. Next, we describe a protocol for fault-tolerantly verifying quantum computations, with minimal "quantum requirements" for the verifier. Specifically, the verifier only requires a device for measuring single-qubit states. Both this device, and the prover's operations are assumed to be prone to errors. We show that under standard assumptions about the error model, it is possible to achieve verification of quantum computation using fault-tolerant principles. As a proof of principle, and to better illustrate the inner workings of the protocol, we describe a toy implementation of the protocol in a quantum simulator, and present the results we obtained, when running it for a small computation. Finally, we explore the possibility of having a verification protocol, with a classical verifier and a single prover, such that the prover is blind with respect to the verifier's computation. We give evidence that this is not possible. In fact, our result is only concerned with blind quantum computation with a classical client, and uses complexity theoretic results to argue why it is improbable for such a protocol to exist. We then use these complexity theoretic techniques to show that a client, with the ability to prepare and send quantum states to a quantum server, would not be able to delegate arbitrary NP problems to that server. In other words, even a client with quantum capabilities cannot exploit those capabilities to delegate the computation of NP problems, while keeping the input, to that computation, private. This is again true, provided certain complexity theoretic conjectures are true.

•Nov 29, 2018•0 citations

Classical zero-knowledge arguments for quantum computations

Thomas Vidick, Tina Zhang

We show that every language in QMA admits a classical-verifier, quantum-prover zero-knowledge argument system which is sound against quantum polynomial-time provers and zero-knowledge for classical (and quantum) polynomial-time verifiers. The protocol builds upon two recent results: a computational zero-knowledge proof system for languages in QMA, with a quantum verifier, introduced by Broadbent et al. (FOCS 2016), and an argument system for languages in QMA, with a classical verifier, introduced by Mahadev (FOCS 2018).

arXiv:1902.05217•Quantum•May 14, 2020•20 citations

How to Classically Verify a Quantum Cat without Killing It

Yael Tauman Kalai, Dakshita Khurana, Justin Raizes

A quantum verifier decides membership in QMA using a (single) quantum witness state. This witness may be arbitrary, and no requirement is placed on it beyond its acceptance probability. A protocol claiming to classically verify QMA should offer the same guarantee: any witness that would convince a quantum verifier should also suffice to convince a classical verifier. Unfortunately, existing classical verification of quantum computation (CVQC) protocols behave quite differently from the original QMA verifier: they require many copies of the witness and destroy every one, effectively demanding that the prover solve the hard problem of witness duplication before verification can begin. We build a protocol to classically verify QMA languages that uses a single copy of the prover's QMA witness. Whenever the original QMA verifier accepts that witness with overwhelming probability, our protocol has negligible completeness and soundness errors and returns the witness negligibly disturbed after interaction with an honest verifier. The soundness of our CVQC is based on the post-quantum Learning With Errors (LWE) assumption. As an intermediate step of independent interest, we introduce witness-preserving classical arguments for NP which enable provers that start out with a superposition over NP witnesses to convince a verifier without disturbing their superposition.

quant-pharXiv:2602.09282•Feb 11, 2026•0 citations

Classical Verification of Quantum Computations

Urmila Mahadev

We present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation. We achieve this by constructing a measurement protocol, which enables a classical verifier to use a quantum prover as a trusted measurement device. The protocol forces the prover to behave as follows: the prover must construct an $n$ qubit state of his choice, measure each qubit in the Hadamard or standard basis as directed by the verifier, and report the measurement results to the verifier. The soundness of this protocol is enforced based on the assumption that the learning with errors problem is computationally intractable for efficient quantum machines.

SIAM Journal on Computing•Jul 21, 2022•28 citations

Classical Verification of Quantum Computations

Urmila Mahadev

We present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation. We achieve this by constructing a measurement protocol, which enables a classical verifier to use a quantum prover as a trusted measurement device. The protocol forces the prover to behave as follows: the prover must construct an n qubit state of his choice, measure each qubit in the Hadamard or standard basis as directed by the verifier, and report the measurement results to the verifier. The soundness of this protocol is enforced based on the assumption that the learning with errors problem is computationally intractable for efficient quantum machines.

Annual Symposium on Foundations of Computer Science•Oct 1, 2018•172 citations
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.
The classical channel remote state preparation (ccRSP) is an important two-party primitive in quantum cryptography. Alice (classical polynomial-time) and Bob (quantum polynomial-time) exchange polynomial rounds of classical messages, and Bob finally gets random single-qubit states while Alice finally gets classical descriptions of the states. In [T. Morimae, arXiv:2003.10712], an information-theoretically-sound non-interactive protocol for the verification of quantum computing was proposed. The verifier of the protocol is classical, but the trusted center is assumed that sends random single-qubit states to the prover and their classical descriptions to the verifier. If the trusted center can be replaced with a ccRSP protocol while keeping the information-theoretical soundness, an information-theoretically-sound classical verification of quantum computing is possible, which solves the long-standing open problem. In this paper, we show that it is not the case unless BQP is contained in MA. We also consider a general verification protocol where the verifier or the trusted center first sends quantum states to the prover, and then the prover and the verifier exchange a constant round of classical messages. We show that the first quantum message transmission cannot be replaced with an (even approximate) ccRSP protocol while keeping the information-theoretical soundness unless BQP is contained in AM. We finally study the verification with the computational soundness. We show that if a ccRSP protocol satisfies a certain condition even against any quantum polynomial-time malicious prover, the replacement of the trusted center with the ccRSP protocol realizes a computationally-sound classical verification of quantum computing. The condition is weaker than the verifiability of the ccRSP.
Quantum computers promise to offer a considerable speed-up in solving certain problems, compared to the best classical algorithms. In many instances, the gap between quantum and classical running times is conjectured to be exponential. While this is great news for those applications where quantum computers would provide such an advantage, it also raises a significant challenge: how can classical computers verify the correctness of quantum computations? In attempting to answer this question, a number of protocols have been developed in which a classical client (referred to as verifier) can interact with one or more quantum servers (referred to as provers) in order to certify the correctness of a quantum computation performed by the server(s). These protocols are of one of two types: either there are multiple non-communicating provers, sharing entanglement, and the verifier is completely classical; or, there is a single prover and the classical verifier has a device for preparing or measuring quantum states. The latter type of protocols are, arguably, more relevant to near term quantum computers, since having multiple quantum computers that share a large amount of entanglement is, from a technological standpoint, extremely challenging. Before the realisation of practical single-prover protocols, a number of challenges need to be addressed: how robust are these protocols to noise on the verifier's device? Can the protocols be made fault-tolerant without significantly increasing the requirements of the verifier? How do we know that the verifier's device is operating correctly? Could this device be eliminated completely, thus having a protocol with a fully classical verifier and a single quantum prover? Our work attempts to provide answers to these questions. First, we consider a single-prover verification protocol developed by Fitzsimons and Kashefi and show that this protocol is indeed robust with respect to deviations on the quantum state prepared by the verifier. We show that this is true even if those deviations are the result of a correlation with the prover's system. We then use this result to give a verification protocol which is device- independent. The protocol consists of a verifier with a measurement device and a single prover. Device-independence means that the verifier need not trust the measurement device (nor the prover) which can be assumed to be fully malicious (though not communicating with the prover). A key element in realising this protocol is a robust technique of Reichardt, Unger and Vazirani for testing, using non-local correlations, that two untrusted devices share a large number of entangled states. This technique is referred to as rigidity of non-local correlations. Our second result is to prove a rigidity result for a type of quantum correlations known as steering correlations. To do this, we first show that steering correlations can be used in order to certify maximally entangled states, in a setting in which each test is independent of the previous one. We also show that the fidelity with which we characterise the state, in this specific test, is optimal. We then improve the previous result by removing the independence assumption. This then leads to our desired rigidity result. We make use of it, in a similar fashion to the device-independent case, in order to give a verification protocol that is one-sided device-independent. The importance of this application is to show how different trust assumptions affect the efficiency of the protocol. Next, we describe a protocol for fault-tolerantly verifying quantum computations, with minimal "quantum requirements" for the verifier. Specifically, the verifier only requires a device for measuring single-qubit states. Both this device, and the prover's operations are assumed to be prone to errors. We show that under standard assumptions about the error model, it is possible to achieve verification of quantum computation using fault-tolerant principles. As a proof of principle, and to better illustrate the inner workings of the protocol, we describe a toy implementation of the protocol in a quantum simulator, and present the results we obtained, when running it for a small computation. Finally, we explore the possibility of having a verification protocol, with a classical verifier and a single prover, such that the prover is blind with respect to the verifier's computation. We give evidence that this is not possible. In fact, our result is only concerned with blind quantum computation with a classical client, and uses complexity theoretic results to argue why it is improbable for such a protocol to exist. We then use these complexity theoretic techniques to show that a client, with the ability to prepare and send quantum states to a quantum server, would not be able to delegate arbitrary NP problems to that server. In other words, even a client with quantum capabilities cannot exploit those capabilities to delegate the computation of NP problems, while keeping the input, to that computation, private. This is again true, provided certain complexity theoretic conjectures are true.
We show that every language in QMA admits a classical-verifier, quantum-prover zero-knowledge argument system which is sound against quantum polynomial-time provers and zero-knowledge for classical (and quantum) polynomial-time verifiers. The protocol builds upon two recent results: a computational zero-knowledge proof system for languages in QMA, with a quantum verifier, introduced by Broadbent et al. (FOCS 2016), and an argument system for languages in QMA, with a classical verifier, introduced by Mahadev (FOCS 2018).
A quantum verifier decides membership in QMA using a (single) quantum witness state. This witness may be arbitrary, and no requirement is placed on it beyond its acceptance probability. A protocol claiming to classically verify QMA should offer the same guarantee: any witness that would convince a quantum verifier should also suffice to convince a classical verifier. Unfortunately, existing classical verification of quantum computation (CVQC) protocols behave quite differently from the original QMA verifier: they require many copies of the witness and destroy every one, effectively demanding that the prover solve the hard problem of witness duplication before verification can begin. We build a protocol to classically verify QMA languages that uses a single copy of the prover's QMA witness. Whenever the original QMA verifier accepts that witness with overwhelming probability, our protocol has negligible completeness and soundness errors and returns the witness negligibly disturbed after interaction with an honest verifier. The soundness of our CVQC is based on the post-quantum Learning With Errors (LWE) assumption. As an intermediate step of independent interest, we introduce witness-preserving classical arguments for NP which enable provers that start out with a superposition over NP witnesses to convince a verifier without disturbing their superposition.
We present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation. We achieve this by constructing a measurement protocol, which enables a classical verifier to use a quantum prover as a trusted measurement device. The protocol forces the prover to behave as follows: the prover must construct an nnn qubit state of his choice, measure each qubit in the Hadamard or standard basis as directed by the verifier, and report the measurement results to the verifier. The soundness of this protocol is enforced based on the assumption that the learning with errors problem is computationally intractable for efficient quantum machines.
We present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation. We achieve this by constructing a measurement protocol, which enables a classical verifier to use a quantum prover as a trusted measurement device. The protocol forces the prover to behave as follows: the prover must construct an n qubit state of his choice, measure each qubit in the Hadamard or standard basis as directed by the verifier, and report the measurement results to the verifier. The soundness of this protocol is enforced based on the assumption that the learning with errors problem is computationally intractable for efficient quantum machines.