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

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

quant-pharXiv:2610.40623Oct 30, 20260 citations

Unitary Channel Testing Under a Depolarizing Noise Assumption

Hirak Ghosh, Andrew Jackson, Animesh Datta

quant-pharXiv:2606.10730Jun 10, 20260 citations

Optimal Quantum Junta Testing without Inverse Queries

Jinge Bao, Minbo Gao, Penghui Yao

quant-pharXiv:2609.37926Sep 30, 20260 citations

On the query complexity of unitary channel certification

Sangwoo Jeon, Changhun Oh

arXiv:2507.17254npj Quantum InformationDec 29, 20250 citations

Quantum channel tomography and estimation by local test

Kean Chen, Nengkun Yu, Zhicheng Zhang

quant-pharXiv:2512.13614Dec 16, 20250 citations

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

Entong He, Zihao Li, Yuxiang Yang

quant-pharXiv:2609.38145Sep 30, 20260 citations

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

arXiv HTML PDF

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).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.40623Oct 30, 20260 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.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.10730Jun 10, 20260 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.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.37926Sep 30, 20260 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.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.17254npj Quantum InformationDec 29, 20250 citations

Quantum channel tomography and estimation by local test

Kean Chen, Nengkun Yu, Zhicheng Zhang

We study the estimation of an unknown quantum channel $\mathcal{E}$ with input dimension $d_1$ , output dimension $d_2$ and Kraus rank at most $r$ . We establish a connection between the query complexities in two models: (i) access to $\mathcal{E}$ , and (ii) access to a random dilation of $\mathcal{E}$ . Specifically, we show that for parallel (possibly coherent) testers, access to dilations does not help. This is proved by constructing a local tester that uses $n$ queries to $\mathcal{E}$ yet faithfully simulates the tester with $n$ queries to a random dilation. As application, we show that: - $O(rd_1d_2/\varepsilon^2)$ queries to $\mathcal{E}$ suffice for channel tomography to within diamond norm error $\varepsilon$ . Moreover, when $rd_2=d_1$ , we show that the Heisenberg scaling $O(1/\varepsilon)$ can be achieved, even if $\mathcal{E}$ is not a unitary channel: - $O(\min\{d_1^{2.5}/\varepsilon,d_1^2/\varepsilon^2\})$ queries to $\mathcal{E}$ suffice for channel tomography to within diamond norm error $\varepsilon$ , and $O(d_1^2/\varepsilon)$ queries suffice for the case of Choi state trace norm error $\varepsilon$ . - $O(\min\{d_1^{1.5}/\varepsilon,d_1/\varepsilon^2\})$ queries to $\mathcal{E}$ suffice for tomography of the mixed state $\mathcal{E}(|0\rangle\langle 0|)$ to within trace norm error $\varepsilon$ .We study the estimation of an unknown quantum channel $\mathcal{E}$ with input dimension $d_1$, output dimension $d_2$ and Kraus rank at most $r$. We establish a connection between the query complexities in two models: (i) access to $\mathcal{E}$, and (ii) access to a random dilation of $\mathcal{E}$. Specifically, we show that for parallel (possibly coherent) testers, access to dilations does not help. This is proved by constructing a local tester that uses $n$ queries to $\mathcal{E}$ yet faithfully simulates the tester with $n$ queries to a random dilation. As application, we show that: - $O(rd_1d_2/\varepsilon^2)$ queries to $\mathcal{E}$ suffice for channel tomography to within diamond norm error $\varepsilon$. Moreover, when $rd_2=d_1$, we show that the Heisenberg scaling $O(1/\varepsilon)$ can be achieved, even if $\mathcal{E}$ is not a unitary channel: - $O(\min\{d_1^{2.5}/\varepsilon,d_1^2/\varepsilon^2\})$ queries to $\mathcal{E}$ suffice for channel tomography to within diamond norm error $\varepsilon$, and $O(d_1^2/\varepsilon)$ queries suffice for the case of Choi state trace norm error $\varepsilon$. - $O(\min\{d_1^{1.5}/\varepsilon,d_1/\varepsilon^2\})$ queries to $\mathcal{E}$ suffice for tomography of the mixed state $\mathcal{E}(|0\rangle\langle 0|)$ to within trace norm error $\varepsilon$.

quant-pharXiv:2512.13614Dec 16, 20250 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.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.38145Sep 30, 20260 citations

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.

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).

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

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.

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

We study the estimation of an unknown quantum channel

\mathcal{E}

with input dimension

d_1

, output dimension

d_2

and Kraus rank at most

r

. We establish a connection between the query complexities in two models: (i) access to

\mathcal{E}

, and (ii) access to a random dilation of

\mathcal{E}

. Specifically, we show that for parallel (possibly coherent) testers, access to dilations does not help. This is proved by constructing a local tester that uses

n

queries to

\mathcal{E}

yet faithfully simulates the tester with

n

queries to a random dilation. As application, we show that: -

O(rd_1d_2/\varepsilon^2)

queries to

\mathcal{E}

suffice for channel tomography to within diamond norm error

\varepsilon

. Moreover, when

rd_2=d_1

, we show that the Heisenberg scaling

O(1/\varepsilon)

can be achieved, even if

\mathcal{E}

is not a unitary channel: -

O(\min\{d_1^{2.5}/\varepsilon,d_1^2/\varepsilon^2\})

queries to

\mathcal{E}

suffice for channel tomography to within diamond norm error

\varepsilon

, and

O(d_1^2/\varepsilon)

queries suffice for the case of Choi state trace norm error

\varepsilon

. -

O(\min\{d_1^{1.5}/\varepsilon,d_1/\varepsilon^2\})

queries to

\mathcal{E}

suffice for tomography of the mixed state

\mathcal{E}(|0\rangle\langle 0|)

to within trace norm error

\varepsilon

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.