Rapid technological advances point to a near future where engineered devices based on the laws of quantum mechanics are able to implement computations that can no longer be emulated on a classical computer. Once that stage is reached, will it be possible to verify the results of the quantum device? Recently, Mahadev introduced a solution to the following problem: Is it possible to delegate a quantum computation to a quantum device in a way that the final outcome of the computation can be verified on a classical computer, given that the device may be faulty or adversarial and given only the ability to generate classical instructions and obtain classical readout information in return? Mahadev’s solution combines the framework of interactive proof systems from complexity theory with an ingenious use of classical cryptographic techniques to tie a “cryptographic leash” around the quantum device. In these notes I give a self-contained introduction to her elegant solution, explaining the required concepts from complexity, quantum computing, and cryptography, and how they are brought together in Mahadev’s protocol for classical verification of quantum computations.
Rapid technological advances point to a near future where engineered devices based on the laws of quantum mechanics are able to implement computations that can no longer be emulated on a classical computer. Once that stage is reached, will it be possible to verify the results of the quantum device? Recently, Mahadev introduced a solution to the following problem: Is it possible to delegate a quantum computation to a quantum device in a way that the final outcome of the computation can be verified on a classical computer, given that the device may be faulty or adversarial and given only the ability to generate classical instructions and obtain classical readout information in return? Mahadev’s solution combines the framework of interactive proof systems from complexity theory with an ingenious use of classical cryptographic techniques to tie a “cryptographic leash” around the quantum device. In these notes I give a self-contained introduction to her elegant solution, explaining the required concepts from complexity, quantum computing, and cryptography, and how they are brought together in Mahadev’s protocol for classical verification of quantum computations.
Abstract With today’s quantum processors venturing into regimes beyond the capabilities of classical devices, we face the challenge to verify that these devices perform as intended, even when we cannot check their results on classical computers. In a recent breakthrough in computer science, a protocol was developed that allows the verification of the output of a computation performed by an untrusted quantum device based only on classical resources. Here, we follow these ideas, and demonstrate in a first, proof-of-principle experiment the verification of the output of a quantum computation using only classical means on a small trapped-ion quantum processor. We contrast this to verification protocols, which require trust and detailed hardware knowledge, as in gate-level benchmarking, or additional quantum resources in case we do not have access to or trust in the device to be tested. While our experimental demonstration uses a simplified version of Mahadev’s protocol we demonstrate the necessary steps for verifying fully untrusted devices. A scaled-up version of our protocol will allow for classical verification, requiring no hardware access or detailed knowledge of the tested device. Its security relies on post–quantum secure trapdoor functions within an interactive proof. The conceptually straightforward, but technologically challenging scaled-up version of the interactive proofs, considered here, can be used for a variety of additional tasks such as verifying quantum advantage, generating and certifying quantum randomness, or composable remote state preparation.
With today’s quantum processors venturing into regimes beyond the capabilities of classical devices, we face the challenge to verify that these devices perform as intended, even when we cannot check their results on classical computers. In a recent breakthrough in computer science, a protocol was developed that allows the verification of the output of a computation performed by an untrusted quantum device based only on classical resources. Here, we follow these ideas, and demonstrate in a first, proof-of-principle experiment the verification of the output of a quantum computation using only classical means on a small trapped-ion quantum processor. We contrast this to verification protocols, which require trust and detailed hardware knowledge, as in gate-level benchmarking, or additional quantum resources in case we do not have access to or trust in the device to be tested. While our experimental demonstration uses a simplified version of Mahadev’s protocol we demonstrate the necessary steps for verifying fully untrusted devices. A scaled-up version of our protocol will allow for classical verification, requiring no hardware access or detailed knowledge of the tested device. Its security relies on post–quantum secure trapdoor functions within an interactive proof. The conceptually straightforward, but technologically challenging scaled-up version of the interactive proofs, considered here, can be used for a variety of additional tasks such as verifying quantum advantage, generating and certifying quantum randomness, or composable remote state preparation.
Quantum computers promise to efficiently solve not only problems believed to be intractable for classical computers, but also problems for which verifying the solution is also considered intractable. This raises the question of how one can check whether quantum computers are indeed producing correct results. This task, known as quantum verification , has been highlighted as a significant challenge on the road to scalable quantum computing technology. We review the most significant approaches to quantum verification and compare them in terms of structure, complexity and required resources. We also comment on the use of cryptographic techniques which, for many of the presented protocols, has proven extremely useful in performing verification. Finally, we discuss issues related to fault tolerance, experimental implementations and the outlook for future protocols.
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.
$ $ The problem of reliably certifying the outcome of a computation performed by a quantum device is rapidly gaining relevance. We present two protocols for a classical verifier to verifiably delegate a quantum computation to two non-communicating but entangled quantum provers, with statistical soundness. Our protocols have near-optimal complexity in terms of the total resources employed by the verifier and the honest provers, with the total number of operations of each party, including the number of entangled pairs of qubits required of the honest provers, scaling as O(glogg) for delegating a circuit of size g. This is in contrast to previous protocols, whose overhead in terms of resources employed, while polynomial, is far beyond what is feasible in practice. Our first protocol requires a number of rounds that is linear in the depth of the circuit being delegated, and is blind, meaning neither prover can learn the circuit or its input. The second protocol is not blind, but requires only a constant number of rounds of interaction. Our main technical innovation is an efficient rigidity theorem that allows a verifier to test that two entangled provers perform measurements specified by an arbitrary m-qubit tensor product of single-qubit Clifford observables on their respective halves of m shared EPR pairs, with a robustness that is independent of m. Our two-prover classical-verifier delegation protocols are obtained by combining this rigidity theorem with a single-prover quantum-verifier protocol for the verifiable delegation of a quantum computation, introduced by Broadbent (Theory of Computing, 2018). ------------------- A conference version of this paper appeared in the Proceedings of the 48th Ann. Internat. Conf. on Theory and Appl. of Cryptographic Techniques (EUROCRYPT 2019).
In the quantum computation verification problem, a quantum server wants to convince a client that the output of evaluating a quantum circuit C is some result that it claims. This problem is considered very important both theoretically and practically in quantum computation [1], [2], [3]. The client is considered to be limited in computational power, and one desirable property is that the client can be completely classical, which leads to the classical verification of quantum computation (CVQC) problem. In terms of the time complexity of server-side quantum computations (which typically dominate the total time complexity of both the client and the server), the fastest single-server CVQC protocol so far has complexity O(poly(κ)∣C∣3) where ∣C∣ is the size of the circuit to be verified and κ is the security parameter, given by Mahadev [4]. This leads to a similar cubic time blowup in many existing protocols including multiparty quantum computation, zero knowledge and obfuscation [5], [6], [7], [8], [9], [10]. Considering the preciousness of quantum computation resources, this cubic complexity barrier could be a big obstacle for theoretical and practical development of protocols for these problems.In this work, by developing new techniques, we give a new CVQC protocol with complexity O(poly(κ)∣C∣) (in terms of the total time complexity of both the client and the server), which is significantly faster than existing protocols. Our protocol is secure in the quantum random oracle model [11] assuming the existence of noisy trapdoor claw-free functions [12], which are both extensively used assumptions in quantum cryptography. Along the way, we also give a new classical channel remote state preparation protocol for states in {∣+θ⟩=21(∣0⟩+eiθπ/4∣1⟩):θ∈{0,1⋯7}}, another basic primitive in quantum cryptography. Our protocol allows for parallel verifiable preparation of L independently random states in this form (up to a constant overall error and a possibly unbounded server-side simulator), and runs in only O(poly(κ)L) time and constant rounds; for comparison, existing works (even for possibly simpler state families) all require very large or unestimated time and round complexities [13], [14], [15], [16].