Lightweight detection of a small number of large errors in a quantum circuit

Suppose we want to implement a unitary U, for instance a circuit for some quantum algorithm. Suppose our actual implementation is a unitary U , which we can only apply as a black-box. In general it is an exponentially-hard task to decide whether U equals the intended U, or is significantly different in a worst-case norm. In this paper we consider two special cases where relatively efficient and lightweight procedures exist for this task. First, we give an efficient procedure under the assumption that U and U (both of which we can now apply as a black-box) are either equal, or differ significantly in only one k-qubit gate, where k = O(1) (the k qubits need not be contiguous). Second, we give an even more lightweight procedure under the assumption that U and U are Clifford circuits which are either equal, or different in arbitrary ways (the specification of U is now classically given while U can still only be applied as a black-box). Both procedures only need to run U a constant number of times to detect a constant error in a worst-case norm. We note that the Clifford result also follows from earlier work of Flammia and Liu [FL11] and da Silva, Landon-Cardinal, and Poulin [dSLCP11]. In the Clifford case, our error-detection procedure also allows us efficiently to learn (and hence correct) U if we have a small list of possible errors that could have happened to U; for example if we know that only O(1) of the gates of U are wrong, this list will be polynomially small and we can test each possible erroneous version of U for equality with U