Scalable verification of quantum algorithm circuits*

In the near future quantum computers with ~100 qubits will become available, and, if this progress is accompanied by reductions in error rates, it will become possible to execute increasingly complex quantum algorithms. A significant challenge that awaits us is the verification of the correctness of the output of these computations. To what degree can we trust the solutions computed by noisy quantum computers, when they cannot be efficiently verified by classical means? We address this challenge by introducing a new protocol for verifying the correctness of algorithmic circuits. Our protocol allows approximation of the fidelity of the output state of a depth d circuit on n qubits by executing a small set of mirror circuits of depth ~2d. The procedure is scalable in the sense that both the complexity of the data analysis and the number of circuits that must be run have no dependence on n or d.