Verifying quantum supremacy by doubling the circuit depth

Any fruitful use of the noisy intermediate-scale quantum computing devices being developed relies crucially on our ability to verify the correctness of their outputs. This verification must be achievable within these noisy intermediate-scale devices. We present a verification protocol in the circuit model where the “desired” computation is verified running several independent “trap” computations, each of which requires (i) no more qubits than the desired computation and (ii) a circuit-depth twice that of the desired computation. Our protocol exploits the fact that single qubit gates are often the best components in noisy intermediate-scale quantum devices. We begin with the assumption that only the single-qubit gates are prefect, and then extend our protocol to account for all operations in intermediate-scale quantum computing devices being noisy. Our protocol applies to sampling problems that underlie quantum supremacy. In particular we provide a verification scheme, with a doubling of the circuit depth, to bound the variation distance between ideal and noisy probability distributions resulting from random circuit sampling - a candidate for quantum supremacy.