Lightweight Detection of a Small Number of Large Errors in a Quantum Circuit

Quantum 5, 436 (2021).

https://doi.org/10.22331/q-2021-04-20-436

Suppose we want to implement a unitary $U$, for instance a circuit for some quantum algorithm. Suppose our actual implementation is a unitary $tilde{U}$, which we can only apply as a black-box. In general it is an exponentially-hard task to decide whether $tilde{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 $tilde{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 $tilde{U}$ are $textit{Clifford}$ circuits which are either equal, or different in arbitrary ways (the specification of $U$ is now classically given while $tilde{U}$ can still only be applied as a black-box). Both procedures only need to run $tilde{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) $tilde{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 $tilde{U}$ are wrong, this list will be polynomially small and we can test each possible erroneous version of $U$ for equality with $tilde{U}$.