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.
Bibliographical noteFunding Information:
NL was partially supported by the UK Engineering and Physical Sciences Research Council through grants EP/R043957/1, EP/S005021/1, EP/T001062/1. RdW was partially supported by ERC Consolidator Grant 615307-QPROGRESS (which ended February 2019), and by the Dutch Research Council (NWO) through Gravitation-grant Quantum Software Consortium, 024.003.037, and through QuantERA ERA-NET Cofund project QuantAlgo 680-91-034.
© 2021 Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften. All right reserved.