Theo and Animesh publish quantum verification paper in Quantum
Theodoros and Animesh have published a work which sets out a method to verify quantum computational supremacy in near-future quantum devices. This work published in Quantum (DOI:10.22331/q-2019-07-12-164) introduces a verification scheme for an Ising sampler, which if implemented could prove quantum computational supremacy.
The considerable experimental efforts being directed towards building quantum computers rest on the belief that they are more powerful than classical computers. Formal mathematical proof for this belief has, however, been rather limited. `Quantum computational supremacy' (QCS) is the ability of a quantum computer to perform a task beyond the capability of any classical computer. Crucially, QCS has been proven for solving easier problems that do not require all the powers of a universal quantum computer.
Two challenges plague experimental demonstration of QCS. The first is our limited trust in the experimental devices to produce the correct output, especially in the regime where predictions via classical simulation of the same system are impossible. The second is the presence of noise in each device which, if not dealt with, accumulates and overwhelms the computation, introducing errors. In both cases the output can be statistically far from the correct one, which prohibits the demonstration of QCS.
Our paper provides a scheme which resolves both challenges by verifying that the outputs of the experiment are sufficiently close to the desired distribution. The distribution we sample from comes from the 2D Ising model, a mathematical model of magnetism that has many applications in statistical physics and is an instance of a QCS task. Our analysis only requires that single qubit states can be prepared reliably, and the experimentalist possesses devices with noise rates below 1.97%. The latter permits larger noise levels than required for universal quantum computing. Our scheme is based on building trust in the correctness of a large computation by checking the correctness of small computations and takes a constant amount of time independent of the size of the lattice in the Ising model. It can therefore be used to prove the correct operation of a QCS demonstrator before building a universal quantum computer becomes possible.