Unitary Channel Testing Under a Depolarizing Noise Assumption

Abstract

We present fast algorithms $\unicode{x2013}$ under the depolarizing noise assumption, often made in fault-tolerant quantum computations $\unicode{x2013}$ to test its strength. Our optimal algorithms answer the following question: is the quantum channel implemented by a given black box identical to a target unitary or $\epsilon$-far from it in the diamond distance, assuming that the deviation is a depolarizing channel with unknown parameter? Our algorithm has a query complexity of $\hat{I}˜(1/\epsilon ).$ The query complexity of the relaxed problem of testing whether the black-box channel is ${\epsilon }_1$-close to a target unitary or ${\epsilon }_2$-far in the diamond distance is $\hat{I}˜({\epsilon }_2/({\epsilon }_2-{\epsilon }_1{)}^2).$ In both cases, we provide matching lower bounds that hold even for adaptive, ancilla-assisted protocols with multi-outcome incoherent measurements.

14 Pages, 3 Figures