On the query complexity of unitary channel certification

Abstract

Certifying the correct functioning of a unitary channel is a critical step toward reliable quantum information processing. In this work, we investigate the query complexity of the unitary channel certification task: testing whether a given $d$-dimensional unitary channel is identical to or $\epsilon$-far in diamond distance from a target unitary operation. We show that incoherent algorithms-those without quantum memory-require $\Omega (d/{\epsilon }^2)$ queries, matching the known upper bound. In addition, for general quantum algorithms, we prove a lower bound of $\Omega (\sqrt{d}/\epsilon )$ and present a matching quantum algorithm based on quantum singular value transformation, establishing a tight query complexity of $\Theta (\sqrt{d}/\epsilon )$. On the other hand, notably, we prove that for almost all unitary channels drawn from a natural average-case ensemble, certification can be accomplished with only $O(1/{\epsilon }^2)$ queries. This demonstrates an exponential query complexity gap between worst- and average-case scenarios in certification, implying that certification is significantly easier for most unitary channels encountered in practice. Together, our results offer both theoretical insights and practical tools for verifying quantum processes.

38 pages, 7 figures

References in corpus (26)

• Strengths and Weaknesses of Quantum Computing
• Randomized Benchmarking of Quantum Gates
• Reliable Quantum Computers
• Robust randomized benchmarking of quantum processes
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Scalable Noise Estimation with Random Unitary Operators
• Ancilla-assisted quantum process tomography
• Quantum certification and benchmarking
• Local random quantum circuits are approximate polynomial-designs
• Information-theoretic bounds on quantum advantage in machine learning
• Theory of quantum system certification: a tutorial
• Comparing Experiments to the Fault-Tolerance Threshold
• Optimal estimation of quantum dynamics
• Quantum ranging with Gaussian entanglement
• Quantum advantages for Pauli channel estimation
• Optimal universal programming of unitary gates
• Query-optimal estimation of unitary channels in diamond distance
• Protecting Quantum Information via Destructive Interference of Correlated Noise
• Entanglement-enabled advantage for learning a bosonic random displacement channel
• Tight bounds on Pauli channel learning without entanglement
• Unitarity estimation for quantum channels
• Quantum learning advantage on a scalable photonic platform
• Exponential advantage in continuous-variable quantum state learning
• Trapped-ion two-qubit gates with >99.99% fidelity without ground-state cooling
• Quantum Channel Testing in Average-Case Distance