Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2604.26900 · Leibniz international proceedings in informatics

Strict Hierarchy for Quantum Channel Certification to Unitary

Kean Chen, Qisheng Wang, Zhicheng Zhang

quant-phcs.CCcs.DSSubmitted Apr 29, 2026• Announced Apr 30, 2026• 3 citations
arXivHTMLPDF

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.

Journal reference
Proceedings of the 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026), pp. 59:1-59:12, 2026
DOI
10.4230/LIPIcs.ICALP.2026.59
Comments
13 pages, 3 algorithms

Related papers

Optimal Diamond Distance Estimation for Unitary Channels

Jinge Bao, Qisheng Wang

The diamond distance between two quantum channels determines the optimal probability of distinguishing them from a single use. We give a quantum algorithm that estimates the diamond distance between two unknown $d$-dimensional unitary channels to within additive error $\varepsilon$, using $O(\sqrt{d}/\varepsilon)$ queries to the unitary channels and their inverses. The query complexity is optimal, as it matches the lower bound due to Jeon and Oh (npj Quantum Inf. 2026).

quant-pharXiv:2610.40623•Oct 30, 2026•0 citations

On the query complexity of unitary channel certification

Sangwoo Jeon, Changhun Oh

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 ε -far in diamond distance from a target unitary operation. We show that incoherent algorithms—those without quantum memory—require Ω( d / ε 2 ) queries, matching the known upper bound. In addition, for general quantum algorithms, we prove a lower bound of \(\Omega (\sqrt{d}/\varepsilon )\) and present a matching quantum algorithm based on quantum singular value transformation, establishing a tight query complexity of \(\Theta (\sqrt{d}/\varepsilon )\) . 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 \({\mathcal{O}}(1/{\varepsilon }^{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.

arXiv:2507.17254•npj Quantum Information•Dec 29, 2025•5 citations

Unitary Channel Testing Under a Depolarizing Noise Assumption

Hirak Ghosh, Andrew Jackson, Animesh Datta

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 $\varepsilon$-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 $Θ(1/\varepsilon).$ The query complexity of the relaxed problem of testing whether the black-box channel is $\varepsilon_1$-close to a target unitary or $\varepsilon_2$-far in the diamond distance is $Θ\bigl(\varepsilon_2/(\varepsilon_2 - \varepsilon_1)^2\bigr).$ In both cases, we provide matching lower bounds that hold even for adaptive, ancilla-assisted protocols with multi-outcome incoherent measurements.

quant-pharXiv:2606.10730•Jun 10, 2026•1 citation

Optimal Quantum Junta Testing without Inverse Queries

Jinge Bao, Minbo Gao, Penghui Yao

We study the query complexity of testing quantum juntas. Given an unknown $n$-qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most $k$ qubits or is $\varepsilon$-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to $U$, but not to $U^\dagger$ or controlled-$U$. We give tight bounds for both unitary and channel junta testing. For sufficiently large $k$, $n \ge 2k$, and a broad range of $\varepsilon$, both problems have query complexity $Θ\left(k/(\varepsilon^2\log k)\right)$. Our upper bounds are achieved by simple nonadaptive testers using product inputs and single-qubit measurements. For junta channels, this closes the gap by Bao and Yao (COLT 23, TPAMI 2025) between an $\widetilde{O}(k)$ upper bound and a $\widetildeΩ(\sqrt{k})$ lower bound at constant $\varepsilon$, establishing the optimal $Θ(k/\log k)$ query complexity. At the heart of both bounds is a strong connection between quantum junta testing and classical support-size testing. For the upper bounds, we reduce quantum junta testing to a generalized support-size problem for distributions over random subsets, and develop a new tester with improved sample complexity. For the lower bounds, we proceed in the reverse direction, reducing classical support-size testing to quantum junta testing through a phase-masked hard ensemble and showing that forward quantum queries can be exactly classicalized on average. Together, these reductions identify support-size testing as the classical core of quantum junta testing and yield matching lower bounds. At constant $\varepsilon$, they also give a separation between $Θ(k/\log k)$ forward queries and $\widetilde{O}(\sqrt{k})$ queries with inverse access.

quant-pharXiv:2609.37926•Sep 30, 2026•1 citation

Unitarity Estimation for Quantum Channels

Kean Chen, Qisheng Wang, Peixun Long +1 more

Estimating the unitarity of an unknown quantum channel$\mathcal {E}$provides information on how much it is unitary, which is a basic and important problem in quantum device certification and benchmarking. Unitarity estimation can be performed with either coherent or incoherent access, where the former in general leads to better query complexity while the latter allows more practical implementations. In this paper, we provide a unified framework for unitarity estimation, which induces ancilla-efficient algorithms that use$O(\epsilon ^{-2})$and$O(\sqrt {d}\cdot \epsilon ^{-2})$calls to$\mathcal {E}$with coherent and incoherent accesses, respectively, where$d$is the dimension of the system that$\mathcal {E}$acts on and$\epsilon $is the required precision. We further show that both the$d$-dependence and$\epsilon $-dependence of our algorithms are optimal. As part of our results, we settle the query complexity of the distinguishing problem for depolarizing and unitary channels with incoherent access by giving a matching lower bound$\Omega (\sqrt {d})$, improving the prior best lower bound$\Omega (\sqrt [{3}]{d})$by (Aharonov et al., 2022) and (Chen et al., FOCS 2021).

arXiv:2212.09319•IEEE Transactions on Information Theory•Mar 31, 2023•31 citations

Query-optimal unitary channel tomography in diamond distance with parallel access

Entong He, Zihao Li, Yuxiang Yang

In the study of quantum process tomography, it has remained open how to learn a unitary channel in diamond distance with strictly parallel queries as efficiently as with sequential queries. Sequential queries allow one to exploit adaptivity to refine the estimate and adjust the learning strategy accordingly, whereas such adjustments are impossible for parallel queries. From the perspective of higher-order quantum operations, any parallel learning strategy can be simulated by a sequential one, whereas the converse does not hold in general, suggesting that sequential learning strategies are potentially more powerful. Contrary to this intuition, we present a new protocol for learning an unknown $d$-dimensional unitary channel to within $\varepsilon$ in diamond distance using $\mathcal{O}(d^2/\varepsilon)$ parallel queries, matching the lower bound presented in [Haah, Kothari, O'Donnell, and Tang, FOCS '23]. Our protocol thus closes the gap between parallel and sequential strategies for unitary channel tomography. As applications, it achieves optimal query complexity for boundary-regime quantum channel tomography and improves the query efficiency of the best-known protocol for tomography of fermionic linear optics.

quant-pharXiv:2609.38145•Sep 30, 2026•1 citation
We consider the problem of quantum channel certification to unitary, where one is given access to an unknown ddd-dimensional channel E\mathcal{E}E, and wants to test whether E\mathcal{E}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/ε2)Θ(d/\varepsilon^2)Θ(d/ε2) queries suffice for incoherent access model, matching the lower bound due to Fawzi, Flammarion, Garivier, and Oufkir (COLT 2023).
(ii) Θ(d/ε)Θ(d/\varepsilon)Θ(d/ε) queries suffice for coherent access model, matching the lower bound due to Regev and Schiff (ICALP 2008).
(iii) Θ(d/ε)Θ(\sqrt{d}/\varepsilon)Θ(d​/ε) 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.
The diamond distance between two quantum channels determines the optimal probability of distinguishing them from a single use. We give a quantum algorithm that estimates the diamond distance between two unknown ddd-dimensional unitary channels to within additive error ε\varepsilonε, using O(d/ε)O(\sqrt{d}/\varepsilon)O(d​/ε) queries to the unitary channels and their inverses. The query complexity is optimal, as it matches the lower bound due to Jeon and Oh (npj Quantum Inf. 2026).
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 ε -far in diamond distance from a target unitary operation. We show that incoherent algorithms—those without quantum memory—require Ω( d / ε 2 ) queries, matching the known upper bound. In addition, for general quantum algorithms, we prove a lower bound of Ω(d/ε)\Omega (\sqrt{d}/\varepsilon )Ω(d​/ε) and present a matching quantum algorithm based on quantum singular value transformation, establishing a tight query complexity of Θ(d/ε)\Theta (\sqrt{d}/\varepsilon )Θ(d​/ε) . 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/ε2){\mathcal{O}}(1/{\varepsilon }^{2})O(1/ε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.
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 ε\varepsilonε-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 Θ(1/ε).Θ(1/\varepsilon).Θ(1/ε). The query complexity of the relaxed problem of testing whether the black-box channel is ε1\varepsilon_1ε1​-close to a target unitary or ε2\varepsilon_2ε2​-far in the diamond distance is Θ(ε2/(ε2−ε1)2).Θ\bigl(\varepsilon_2/(\varepsilon_2 - \varepsilon_1)^2\bigr).Θ(ε2​/(ε2​−ε1​)2). In both cases, we provide matching lower bounds that hold even for adaptive, ancilla-assisted protocols with multi-outcome incoherent measurements.
We study the query complexity of testing quantum juntas. Given an unknown nnn-qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most kkk qubits or is ε\varepsilonε-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to UUU, but not to U†U^\daggerU† or controlled-UUU. We give tight bounds for both unitary and channel junta testing. For sufficiently large kkk, n≥2kn \ge 2kn≥2k, and a broad range of ε\varepsilonε, both problems have query complexity Θ(k/(ε2log⁡k))Θ\left(k/(\varepsilon^2\log k)\right)Θ(k/(ε2logk)). Our upper bounds are achieved by simple nonadaptive testers using product inputs and single-qubit measurements. For junta channels, this closes the gap by Bao and Yao (COLT 23, TPAMI 2025) between an O~(k)\widetilde{O}(k)O(k) upper bound and a Ω~(k)\widetildeΩ(\sqrt{k})Ω(k​) lower bound at constant ε\varepsilonε, establishing the optimal Θ(k/log⁡k)Θ(k/\log k)Θ(k/logk) query complexity. At the heart of both bounds is a strong connection between quantum junta testing and classical support-size testing. For the upper bounds, we reduce quantum junta testing to a generalized support-size problem for distributions over random subsets, and develop a new tester with improved sample complexity. For the lower bounds, we proceed in the reverse direction, reducing classical support-size testing to quantum junta testing through a phase-masked hard ensemble and showing that forward quantum queries can be exactly classicalized on average. Together, these reductions identify support-size testing as the classical core of quantum junta testing and yield matching lower bounds. At constant ε\varepsilonε, they also give a separation between Θ(k/log⁡k)Θ(k/\log k)Θ(k/logk) forward queries and O~(k)\widetilde{O}(\sqrt{k})O(k​) queries with inverse access.
Estimating the unitarity of an unknown quantum channelE\mathcal {E}Eprovides information on how much it is unitary, which is a basic and important problem in quantum device certification and benchmarking. Unitarity estimation can be performed with either coherent or incoherent access, where the former in general leads to better query complexity while the latter allows more practical implementations. In this paper, we provide a unified framework for unitarity estimation, which induces ancilla-efficient algorithms that useO(ϵ−2)O(\epsilon ^{-2})O(ϵ−2)andO(d⋅ϵ−2)O(\sqrt {d}\cdot \epsilon ^{-2})O(d​⋅ϵ−2)calls toE\mathcal {E}Ewith coherent and incoherent accesses, respectively, wheredddis the dimension of the system thatE\mathcal {E}Eacts on and$\epsilon istherequiredprecision.Wefurthershowthatboththeis the required precision. We further show that both theistherequiredprecision.Wefurthershowthatboththed−dependenceand-dependence and−dependenceand\epsilon −dependenceofouralgorithmsareoptimal.Aspartofourresults,wesettlethequerycomplexityofthedistinguishingproblemfordepolarizingandunitarychannelswithincoherentaccessbygivingamatchinglowerbound-dependence of our algorithms are optimal. As part of our results, we settle the query complexity of the distinguishing problem for depolarizing and unitary channels with incoherent access by giving a matching lower bound−dependenceofouralgorithmsareoptimal.Aspartofourresults,wesettlethequerycomplexityofthedistinguishingproblemfordepolarizingandunitarychannelswithincoherentaccessbygivingamatchinglowerbound\Omega (\sqrt {d}),improvingthepriorbestlowerbound, improving the prior best lower bound,improvingthepriorbestlowerbound\Omega (\sqrt [{3}]{d})$by (Aharonov et al., 2022) and (Chen et al., FOCS 2021).
In the study of quantum process tomography, it has remained open how to learn a unitary channel in diamond distance with strictly parallel queries as efficiently as with sequential queries. Sequential queries allow one to exploit adaptivity to refine the estimate and adjust the learning strategy accordingly, whereas such adjustments are impossible for parallel queries. From the perspective of higher-order quantum operations, any parallel learning strategy can be simulated by a sequential one, whereas the converse does not hold in general, suggesting that sequential learning strategies are potentially more powerful. Contrary to this intuition, we present a new protocol for learning an unknown ddd-dimensional unitary channel to within ε\varepsilonε in diamond distance using O(d2/ε)\mathcal{O}(d^2/\varepsilon)O(d2/ε) parallel queries, matching the lower bound presented in [Haah, Kothari, O'Donnell, and Tang, FOCS '23]. Our protocol thus closes the gap between parallel and sequential strategies for unitary channel tomography. As applications, it achieves optimal query complexity for boundary-regime quantum channel tomography and improves the query efficiency of the best-known protocol for tomography of fermionic linear optics.