by Stacey Jeffery (CWI)
As the race to build the first quantum computer heats up, we can soon expect some lab to claim to have a quantum computer. How will they prove that what they have built is truly a quantum computer?
It is already possible to buy quantum hardware for certain cryptographic tasks, such as random number generation and key distribution. In cryptographic scenarios, being able to test that your devices behave as advertised is clearly of paramount importance.
The first commercial quantum computers are likely to run as shared servers, where clients can pay to have a quantum computation run. This is another scenario where we would like the client, who does not have a quantum computer, to have some guarantee that the correct computation has been performed.
These scenarios are captured by a verification protocol, in which a verifier, who would like to run some quantum computation, interacts with one or more provers who have a quantum computer. By the end of the protocol, the verifier either “accepts” or “rejects” the output of the computation. The verifier might represent an experimenter testing a quantum system, and the provers a personification of nature, or more precisely, the physical systems being tested. If the provers are “honest” and follow the protocol – that is, they behave as predicted – the verifier should learn the result of the quantum computation. However, if the provers are deviating from the protocol, the verifier should detect this and “reject”.
Verifying quantum computations is related to the more fundamental task of experimentally verifying quantum mechanics. A quantum system has an internal state that an observer cannot perceive directly. To learn about this state, a quantum measurement can be performed, giving some incomplete information. If an experimentalist hypothesises that a particular quantum system has a particular state, this can be verified by performing measurements, but this presupposes some trusted quantum measurement device. If one wants to verify the theory of quantum mechanics, one cannot circularly assume that the measurement device behaves as predicted by the theory quantum mechanics.
However, there are means of verifying certain aspects of quantum mechanics that do not require the experimenter to have a trusted quantum device, called Bell tests. In a Bell test, two provers play a game with a verifier. The verifier asks each prover a question, and they must each return an answer, without communicating during the game. What makes a Bell test special is that they can win the game with higher probability if they share a quantum resource called entanglement than if they are classical. Thus, such a game offers a way to experimentally test quantum mechanics.
Analogous to the situation in testing quantum mechanics, testing a quantum computer can be accomplished in either of two regimes. In the quantum-verifier regime, the verifier must have a simple trusted quantum device, like a measurement device. In this regime, several efficient verification protocols are known. However, the requirement that the verifier have a trusted quantum device is a big drawback.
In the two-prover regime, analogous to a Bell test, a classical verifier interacts with two provers who do not communicate. The first protocol in this regime was a significant breakthrough, providing, for the first time, a method for a classical verifier to verify any quantum computation [3]. However, the protocol had the major disadvantage of requiring resources that scale like g8192 to verifiably implement a quantum circuit of size g. For comparison, there are an estimated 2286 elementary particles in the universe. Subsequent improvements decreased this overhead to g2048, but this is still thoroughly impractical, even for a quantum circuit of size g = 2.
In collaboration with researchers from Université Paris Diderot and Caltech, we presented the first efficient protocol in the two-prover regime [2]. This protocol requires resources that scale like O(g log g) to verify a quantum circuit of size g.
We begin with a quantum-verifier protocol due to Broadbent [1]. The provers in our protocol are asked to simulate Broadbent's verifier and prover, respectively. We call our provers Prover V, for verifier, and Prover P, for prover.
By the properties of Broadbent’s Protocol, we can use Prover V to test Prover P, to make sure he is following the protocol. Then it only remains to ensure that Prover V is, in fact, following the protocol. We develop new Bell tests that are used to make Prover P test Prover V. While the classical verifier may not be powerful enough to keep a quantum prover in check, she can use the two provers to control one another.
In the future, we hope to see experimental realisations of our protocol, which is possible for the first time, due to its efficiency. Its near-optimal efficiency means that verifying a particular quantum computation does not require much more resources than simply implementing that computation.
Figure 1: Quantum-verifier Regime. A verifier with a simple quantum device interacts with a prover with a full quantum computer.
Figure 2: Two-prover Regime. A classical verifier interacts with two quantum provers.
Figure 3: Our new two-prover protocol. The provers play the role of the verifier and prover from Broadbent’s Protocol, which is a quantum-verifier protocol.
Links:
CWI’s algorithms and complexity group: https://kwz.me/hBD
QuSoft: http://www.qusoft.org/
References:
[1] A. Broadbent: “How to Verify a Quantum Computation” Arxiv preprint arXiv:1509.09180, 2015.
[2] A. Coladangelo, A. Grilo, S. Jeffery, T. Vidick: “Verifier-on-a-Leash: new schemes for verifiable delegated quantum computation, with quasilinear resources” Arxiv preprint arXiv:1708.07359, 2017.
[3] B. W. Reichardt, F. Unger and U. Vazirani: “Classical command of quantum systems” Nature 496, 456-460, 2013.
Please contact:
Stacey Jeffery, CWI and QuSoft,
