**Abstract: **

Suppose we want to implement a unitary $U$, for instance a circuit for some quantum algorithm. Suppose our actual implementation is a unitary $\stackrel{~}{U}$, which we can only apply as a black-box. In general it is an exponentially-hard task to decide whether $\stackrel{~}{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 $\stackrel{~}{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 $\stackrel{~}{U}$ are $\mathit{\text{Clifford}}$ circuits which are either equal, or different in arbitrary ways (the specification of $U$ is now classically given while $\stackrel{~}{U}$ can still only be applied as a black-box). Both procedures only need to run $\stackrel{~}{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, and da Silva, Landon-Cardinal, and Poulin.

In the Clifford case, our error-detection procedure also allows us efficiently to learn (and hence correct) $\stackrel{~}{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 $\stackrel{~}{U}$ are wrong, this list will be polynomially small and we can test each possible erroneous version of $U$ for equality with $\stackrel{~}{U}$.