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) over tilde, which we can only apply as a black-box. In general it is an exponentially-hard task to decide whether (U) over tilde 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) over tilde (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) over tilde are Clifford circuits which are either equal, or different in arbitrary ways (the specification of U is now classically given while (U) over tilde can still only be applied as a black-box). Both procedures only need to run (U) over tilde 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 Flasnmia and Liu [FL11] and da Silva, Landon-Cardinal, and Poulin [dSLCP 11].In the Clifford case, our error-detection procedure also allows us efficiently to learn (and hence correct) (U) over tilde 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) over tilde are wrong, this list will be polynomially small and we can test each possible erroneous version of U for equality with U.