Intermediate-scale quantum devices are becoming more reliable and may soon be harnessed to solve useful computational tasks. At the same time, common classical methods used to verify their computational output become intractable due to a prohibitive scaling of required resources with system size. Inspired by recent experimental progress, here we describe and analyze efficient cross-platform verification protocols for quantum states and show how these can be used to verify computations. We focus on the pairwise comparison between distant nodes of a quantum network, identify the most promising protocols, and discuss possible implementations in laboratory settings. As a proof of principle, we implement basic versions of these schemes on available quantum processors.
Intermediate-scale quantum devices are becoming more reliable and may soon be harnessed to solve useful computational tasks. At the same time, common classical methods used to verify their computational output become intractable due to a prohibitive scaling of required resources with system size. Inspired by recent experimental progress, here we describe and analyze efficient cross-platform verification protocols for quantum states and show how these can be used to verify computations. We focus on the pairwise comparison between distant nodes of a quantum network, identify the most promising protocols, and discuss possible implementations in laboratory settings. As a proof of principle, we implement basic versions of these schemes on available quantum processors.
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.
We describe a protocol for cross-platform verification of quantum simulators and quantum computers. We show how to measure directly the overlap Tr[ρ_{1}ρ_{2}] and the purities Tr[ρ_{1,2}^{2}], and thus a fidelity of two, possibly mixed, quantum states ρ_{1} and ρ_{2} prepared in separate experimental platforms. We require only local measurements in randomized product bases, which are communicated classically. As a proof of principle, we present the measurement of experiment-theory fidelities for entangled 10-qubit quantum states in a trapped ion quantum simulator.
How can a user with limited quantum resources verify the output of an untrusted, fully quantum server? This manuscript provides a conceptual synthesis of some recent developments toward answering this question under statistical (information-theoretic) security. Rather than duplicating the dense technical proofs of the underlying publications, our focus here is on the physical motivations, the structural connections between different protocols, and the path toward hardware-efficient implementation.
We begin by introducing a modular, composable framework that partitions verification into three distinct, independent primitives: remote state preparation, trap-based deviation detection, and error-correcting embedding. Using this framework, we show how the demanding hardware requirements of early protocols can be systematically relaxed. We review schemes that eliminate the spatial overhead, remove the need to prepare computational-basis dummy states, and replace single-photon sources with trusted local rotations or weak coherent pulses. Finally, we examine how these techniques scale, both to asymmetric multi-party settings and to the delegation of fully fault-tolerant computations in the presence of gate-level noise. This document is intended as a guide to the architectural principles of practical quantum verification.
As progress on experimental quantum processors continues to advance, the problem of verifying the correct operation of such devices is becoming a pressing concern. The recent discovery of protocols for verifying computation performed by entangled but non-communicating quantum processors holds the promise of certifying the correctness of arbitrary quantum computations in a fully device-independent manner. Unfortunately, all known schemes have prohibitive overhead, with resources scaling as extremely high degree polynomials in the number of gates constituting the computation. Here we present a novel approach based on a combination of verified blind quantum computation and Bell state self-testing. This approach has dramatically reduced overhead, with resources scaling as only O(m4lnm) in the number of gates.
The promise of scalable quantum technology appears more realistic, after recent advances in both theory and experiment. Assuming a quantum computer is developed, the task of verifying the correctness of its outcome becomes crucial. Unfortunately, for a system that involves many particles, predicting its evolution via classical simulation becomes intractable. Moreover, verification of the outcome by computational methods, i.e. involving a classical witness, is believed inefficient for the hardest problems solvable by a quantum computer. A feasible alternative to verify quantum computation is via cryptographic methods, where an untrusted prover has to convince a weak verifier for the correctness of his outcome. This is the approach we take in this thesis. In the most standard configuration the prover is capable of computing all polynomial-time quantum circuits and the verifier is restricted to classical with very modest quantum power. The goal of existing verification protocols is to reduce the quantum requirements for the verifier - ideally making it purely classical - and reduce the communication complexity. In Part II we propose a composition of two existing verification protocols [Fitzsimons and Kashefi, 2012], [Aharonov et al., 2010] that achieves quadratic improvement in communication complexity, while keeping the quantum requirements for the verifier modest. Along this result, several new techniques are proposed, including the generalization of [Fitzsimons and Kashefi, 2012] to prime dimensions. In Part III we discuss the idea of model-specific quantum verification, where the prover is restricted to intermediate quantum power, i.e. between full-fledged quantum and purely classical, thus more feasible experimentally. As a proof of principle we propose a verification protocol for the One-Pure-Qubit computer [Knill and Laflamme, 1998], which tolerates noise and is capable of computing hard problems such as large matrix trace estimation. The verification protocol is an adaptation of [Fitzsimons and Kashefi, 2012] running on Measurement-Based Quantum Computing with newly proved properties of the underlying resources. Connections of quantum verification to other security primitives are considered in Part IV. Authenticated quantum communication has been already proved to relate to quantum verification. We expand this by proposing a quantum authentication protocol derived from [Fitzsimons and Kashefi, 2012] and discuss implications to verification with purely classical verifier. Connections between quantum security primitives, namely blindness - prover does not learn the computation -, and classical security are considered in Part V. We introduce a protocol where a client with restricted classical resources computes blindly a universal classical gate with the help of an untrusted server, by adding modest quantum capabilities to both client and server. This example of quantum-enhanced classical security we prove to be a task classically impossible.
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.