Verifying quantum computations on noisy intermediate-scale quantum devices.

Single-qubit gates are often the most accurate operations in prominent quantum computing platforms, such as trapped ions and superconducting qubits. We devise a verification protocol in the circuit model for checking the correctness of computations running on devices with accurate single-qubit gates. Our protocol has low overheads, as it only requires the capability of running several independent computations that take as input the same number of qubits as the computation being verified, and have a circuit depth between two and four times larger than that of the computation being verified. We begin with the assumption that the single-qubit gates are perfect, all other operations being affected by noise potentially correlated in time and space. We then extend our protocol to account for all the operations being noisy, with single-qubit gates inducing bounded (but not necessarily local in space and time) noise. With a doubling of the circuit depth, our protocol can provide a bound on the variation distance between noiseless and noisy probability distributions resulting from random circuit sampling on 2D architectures - a candidate for quantum supremacy.