Strict Hierarchy for Quantum Channel Certification to Unitary
2026-04-29 • Computational Complexity
Computational ComplexityData Structures and Algorithms
AI summaryⓘ
The authors study how to verify if a given quantum channel (a process acting on quantum states) is exactly a certain unitary operation or far from it. They provide optimal quantum algorithms for three different ways you can access the channel, each requiring fewer queries as the access method gets more powerful. Their results show that when you have more advanced access, you can confirm the channel’s identity with significantly fewer queries. This establishes a clear order of difficulty for this verification task depending on the access model used.
quantum channelunitary operationdiamond normquery complexityquantum algorithmcoherent accessincoherent accesssource-code accessquantum channel certification
Authors
Kean Chen, Qisheng Wang, Zhicheng Zhang
Abstract
We consider the problem of quantum channel certification to unitary, where one is given access to an unknown $d$-dimensional channel $\mathcal{E}$, and wants to test whether $\mathcal{E}$ is equal to a target unitary channel or is $\varepsilon$-far from it in the diamond norm. We present optimal quantum algorithms for this problem, settling the query complexities in three access models with increasing power. Specifically, we show that: (i) $Θ(d/\varepsilon^2)$ queries suffice for incoherent access model, matching the lower bound due to Fawzi, Flammarion, Garivier, and Oufkir (COLT 2023). (ii) $Θ(d/\varepsilon)$ queries suffice for coherent access model, matching the lower bound due to Regev and Schiff (ICALP 2008). (iii) $Θ(\sqrt{d}/\varepsilon)$ queries suffice for source-code access model, matching the lower bound due to Jeon and Oh (npj Quantum Inf. 2026). This demonstrates a strict hierarchy of complexities for quantum channel certification to unitary across various access models.