Cross-verification of quantum computers

How can we verify that a quantum computer performing a classically-intractable calculation produces the correct result? This is a particularly important question given that current quantum processors are noisy and prone to errors. 

For example, in the recent quantum supremacy experiments by Google and USTC, the quantum circuits essentially functioned as random bitstring generators, making verification of their output extremely challenging. Verification of the circuits' output was based on cross-entropy benchmarking, which compares the sampled bitstrings against ideal probability distributions computed using classical supercomputers. Thus, applying cross-entropy benchmarking in the quantum supremacy regime was not possible; instead, the authors performed the benchmarking on classically-simulable circuits employing either fewer qubits, or the full number of qubits and classically-tractable gate sequences. The benchmarking could not be performed on the exact circuits used to claim quantum supremacy, leaving loopholes for skeptics to attack.

An article by C. Greganti and coauthors just published in Physical Review X proposes a neat scheme for verifying the outputs generated by quantum computers. Their cross-verification scheme is based on generating families of circuits comprising different gate sequences and qubit numbers that, nevertheless, correspond to the same computation and should therefore (ideally) generate the same output distribution. 

The required circuit families can be designed using the paradigm of measurement-based quantum computation, in which gates are replaced by measurements on auxiliary qubits. 

Crucially, this cross-verification scheme does not require a classical computer to verify the circuit outputs, making it scalable to the quantum supremacy regime.

This method is more efficient than standard benchmarking methods thanks to a variant of the birthday paradox: verification is based on estimating the probability to obtain collisions between bitstrings generated by pairs of circuits; estimating collision probabilities turns out to be much much easier  than estimating the probabilities of measuring individual bitstrings.

While this method is an improvement, the required number of measurements still grows exponentially with the number of qubits that are compared during the verification procedure, which is related to how different the two gate sequences are. Nevertheless, with the noise level on current quantum devices this verification scheme can already resolve differences between different hardware platforms using a modest number of qubits (up to 6).