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:2606.10730

Unitary Channel Testing Under a Depolarizing Noise Assumption

Hirak Ghosh, Andrew Jackson, Animesh Datta

quant-phSubmitted Jun 9, 2026• Announced Jun 10, 2026• 0 citations
arXivHTMLPDF

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 $\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.

Comments
14 Pages, 3 Figures

Related papers

Quantum Channel Certification with Incoherent Strategies

Omar Fawzi, Nicolas Flammarion, Aurélien Garivier +1 more

In the problem of quantum channel certification, we have black box access to a quantum process and would like to decide if this process matches some predefined specification or is $\varepsilon$-far from this specification. The objective is to achieve this task while minimizing the number of times the black box is used. Here, we focus on optimal incoherent strategies for two relevant extreme cases of channel certification. The first one is when the predefined specification is a unitary channel, e.g., a gate in a quantum circuit. In this case, we show that testing whether the black box is described by a fixed unitary operator in dimension $d$ or $\varepsilon$-far from it in the trace norm requires $Θ(d/\varepsilon^2)$ uses of the black box. The second setting we consider is when the predefined specification is a completely depolarizing channel with input dimension $d_{\text{in}}$ and output dimension $d_{\text{out}}$. In this case, we prove that, in the non-adaptive setting, $\tildeΘ(d_{\text{in}}^2d_{\text{out}}^{1.5}/\varepsilon^2)$ uses of the channel are necessary and sufficient to verify whether it is equal to the depolarizing channel or $\varepsilon$-far from it in the diamond norm. Finally, we prove a lower bound of $Ω(d_{\text{in}}^2d_{\text{out}}/\varepsilon^2)$ for this problem in the adaptive setting. Note that the special case $d_{\text{in}} = 1$ corresponds to the well-studied quantum state certification problem.

arXiv:2303.01188•Mar 2, 2023•1 citation

Strict Hierarchy for Quantum Channel Certification to Unitary

Kean Chen, Qisheng Wang, Zhicheng Zhang

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.

quant-pharXiv:2604.26900•Leibniz international proceedings in informatics•Apr 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•0 citations

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

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•0 citations

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•12 citations
We present fast algorithms \unicodex2013\unicode{x2013}\unicodex2013 under the depolarizing noise assumption, often made in fault-tolerant quantum computations \unicodex2013\unicode{x2013}\unicodex2013 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.
In the problem of quantum channel certification, we have black box access to a quantum process and would like to decide if this process matches some predefined specification or is ε\varepsilonε-far from this specification. The objective is to achieve this task while minimizing the number of times the black box is used. Here, we focus on optimal incoherent strategies for two relevant extreme cases of channel certification. The first one is when the predefined specification is a unitary channel, e.g., a gate in a quantum circuit. In this case, we show that testing whether the black box is described by a fixed unitary operator in dimension ddd or ε\varepsilonε-far from it in the trace norm requires Θ(d/ε2)Θ(d/\varepsilon^2)Θ(d/ε2) uses of the black box. The second setting we consider is when the predefined specification is a completely depolarizing channel with input dimension dind_{\text{in}}din​ and output dimension doutd_{\text{out}}dout​. In this case, we prove that, in the non-adaptive setting, Θ~(din2dout1.5/ε2)\tildeΘ(d_{\text{in}}^2d_{\text{out}}^{1.5}/\varepsilon^2)Θ~(din2​dout1.5​/ε2) uses of the channel are necessary and sufficient to verify whether it is equal to the depolarizing channel or ε\varepsilonε-far from it in the diamond norm. Finally, we prove a lower bound of Ω(din2dout/ε2)Ω(d_{\text{in}}^2d_{\text{out}}/\varepsilon^2)Ω(din2​dout​/ε2) for this problem in the adaptive setting. Note that the special case din=1d_{\text{in}} = 1din​=1 corresponds to the well-studied quantum state certification problem.
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.
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.
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).
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).