Abstract:
Suppose we want to implement a unitary , for instance a circuit for some quantum algorithm. Suppose our actual implementation is a unitary , which we can only apply as a black-box. In general it is an exponentially-hard task to decide whether equals the intended , 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 and (both of which we can now apply as a black-box) are either equal, or differ significantly in only one -qubit gate, where (the qubits need not be contiguous). Second, we give an even more lightweight procedure under the assumption that and are circuits which are either equal, or different in arbitrary ways (the specification of is now classically given while can still only be applied as a black-box). Both procedures only need to run 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, and da Silva, Landon-Cardinal, and Poulin.
In the Clifford case, our error-detection procedure also allows us efficiently to learn (and hence correct) if we have a small list of possible errors that could have happened to ; for example if we know that only of the gates of are wrong, this list will be polynomially small and we can test each possible erroneous version of for equality with .
