arXiv:2303.01188

Quantum Channel Certification with Incoherent Strategies

Omar Fawzi, Nicolas Flammarion, Aurélien Garivier, Aadil Oufkir

Published Mar 2, 2023• 1 citation

Abstract

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.

DOI: 10.48550/arxiv.2303.01188

Related papers

Strict Hierarchy for Quantum Channel Certification to Unitary

Kean Chen, Qisheng Wang, Zhicheng Zhang

quant-pharXiv:2604.26900Leibniz international proceedings in informaticsApr 30, 20260 citations

Unitary Channel Testing Under a Depolarizing Noise Assumption

Hirak Ghosh, Andrew Jackson, Animesh Datta

quant-pharXiv:2606.10730Jun 10, 20260 citations

Quantum memory advantage for quantum process tomography

Carlos Bravo-Prieto, Weiyuan Gong, Antonio Anna Mele

quant-pharXiv:2607.13476Jul 16, 20260 citations

On the Power of Adaptivity in Testing Quantum States in Fidelity

Jan Seyfried, Sayantan Sen, Marco Tomamichel

quant-pharXiv:2609.08733Sep 9, 20260 citations

On the query complexity of unitary channel certification

Sangwoo Jeon, Changhun Oh

arXiv:2507.17254npj Quantum InformationDec 29, 20250 citations

Near-optimal incoherent tomography of low-rank quantum channels

Kean Chen, Aadil Oufkir

quant-pharXiv:2609.23752Sep 22, 20260 citations

arXiv:2303.01188

Quantum Channel Certification with Incoherent Strategies

Omar Fawzi, Nicolas Flammarion, Aurélien Garivier, Aadil Oufkir

Published Mar 2, 2023• 1 citation

arXiv HTML PDF

Abstract

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

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

DOI: 10.48550/arxiv.2303.01188

Related papers

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.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.26900Leibniz international proceedings in informaticsApr 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

Quantum memory advantage for quantum process tomography

Carlos Bravo-Prieto, Weiyuan Gong, Antonio Anna Mele

Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be $Θ(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$ , where $d_{\mathrm{in}}$ and $d_{\mathrm{out}}$ are the channel input and output dimensions, respectively, and $\varepsilon$ is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires $Ω(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$ queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound $O(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$ . Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case $d_{\mathrm{in}}=1$ . By contrast, coherent protocols with quantum memory achieve query complexity $Θ(d_{\mathrm{in}}^2 d_{\mathrm{out}}^2/\varepsilon^2)$ . Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be $Θ(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$, where $d_{\mathrm{in}}$ and $d_{\mathrm{out}}$ are the channel input and output dimensions, respectively, and $\varepsilon$ is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires $Ω(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$ queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound $O(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$. Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case $d_{\mathrm{in}}=1$. By contrast, coherent protocols with quantum memory achieve query complexity $Θ(d_{\mathrm{in}}^2 d_{\mathrm{out}}^2/\varepsilon^2)$. Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.

quant-pharXiv:2607.13476Jul 16, 20260 citations

On the Power of Adaptivity in Testing Quantum States in Fidelity

Jan Seyfried, Sayantan Sen, Marco Tomamichel

We study the problems of quantum state certification, equivalence testing and independence testing. In certification, given samples of an unknown quantum state $ρ$ and the description of a state $σ$ , the goal is to test whether $ρ=σ$ , or whether $ρ$ and $σ$ are far in a given distance measure. In equivalence testing, $σ$ is also unknown and only accessible via samples. Independence testing decides whether $ρ_{AC}=ρ_A\otimesρ_C$ , or is far from being a product. The sample complexities of these problems are now well-understood for a decision gap $\varepsilon$ in trace distance: in the single-copy measurement setting with $d$ -dimensional states, all three tasks can be solved using the same non-adaptive approach, which uses $Θ(d^{3/2}/\varepsilon^2)$ samples and is optimal in general, even without adaptivity. In this work, we consider decision gaps expressed in fidelity and study possible separations between these problems and how adaptivity can help. We prove that certification with respect to fidelity for a state $σ$ of rank $r$ does not benefit from adaptivity and requires $\widetildeΘ(r^{3/2}/\varepsilon)$ samples. For equivalence testing and independence testing, we provide adaptive algorithms using $\widetilde{O}(\min\{d^{3/2}/\varepsilon^2,d^{9/4}/\varepsilon\})$ and $\widetilde{O}(\min\{(d_Ad_C)^{3/2}/\varepsilon^2,d_A^{9/4}d_C^{3/4}/\varepsilon\})$ samples, for $d_A\geq d_C$ , respectively. Our main technique is a framework that uses partial learning and a reduction to testing in $\ell_2$ -distance, adapted from the distribution testing literature. We show that adaptivity matters for equivalence testing in fidelity by proving that $\widetildeΩ(1/\varepsilon^2)$ samples are necessary in the non-adaptive case even for qubits, showing a separation from certification.We study the problems of quantum state certification, equivalence testing and independence testing. In certification, given samples of an unknown quantum state $ρ$ and the description of a state $σ$, the goal is to test whether $ρ=σ$, or whether $ρ$ and $σ$ are far in a given distance measure. In equivalence testing, $σ$ is also unknown and only accessible via samples. Independence testing decides whether $ρ_{AC}=ρ_A\otimesρ_C$, or is far from being a product. The sample complexities of these problems are now well-understood for a decision gap $\varepsilon$ in trace distance: in the single-copy measurement setting with $d$-dimensional states, all three tasks can be solved using the same non-adaptive approach, which uses $Θ(d^{3/2}/\varepsilon^2)$ samples and is optimal in general, even without adaptivity. In this work, we consider decision gaps expressed in fidelity and study possible separations between these problems and how adaptivity can help. We prove that certification with respect to fidelity for a state $σ$ of rank $r$ does not benefit from adaptivity and requires $\widetildeΘ(r^{3/2}/\varepsilon)$ samples. For equivalence testing and independence testing, we provide adaptive algorithms using $\widetilde{O}(\min\{d^{3/2}/\varepsilon^2,d^{9/4}/\varepsilon\})$ and $\widetilde{O}(\min\{(d_Ad_C)^{3/2}/\varepsilon^2,d_A^{9/4}d_C^{3/4}/\varepsilon\})$ samples, for $d_A\geq d_C$, respectively. Our main technique is a framework that uses partial learning and a reduction to testing in $\ell_2$-distance, adapted from the distribution testing literature. We show that adaptivity matters for equivalence testing in fidelity by proving that $\widetildeΩ(1/\varepsilon^2)$ samples are necessary in the non-adaptive case even for qubits, showing a separation from certification.

quant-pharXiv:2609.08733Sep 9, 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

Near-optimal incoherent tomography of low-rank quantum channels

Kean Chen, Aadil Oufkir

We study tomography for quantum channels with input dimension $d_1$ , output dimension $d_2$ , and Kraus rank at most $r$ , to within diamond norm error $\varepsilon$ , using adaptive experiments that retain no quantum memory between channel queries. - For quantum channels whose non-zero Choi eigenvalues are bounded below by $Ω(d_1/r)$ , we establish optimal query upper and lower bounds $Θ(d_1d_2r^2/ε^2)$ . The upper bound is achieved by a nonadaptive algorithm that uses the estimator from [Surawy-Stepney et al., Quantum (2022)], together with a new diamond-norm analysis. The lower bound applies to arbitrary adaptive incoherent protocols and follows from a new local family of channels and a uniform one-query Fisher-information bound. - For general channels, we establish an upper bound $O(d_1d_2r^2\log(2d_1)/ε^2)$ , nearly matching the above lower bound $Ω(d_1d_2r^2/\varepsilon^2)$ . To achieve this, we generalize the above nonadaptive algorithm by adapting the input state over $O(\log(2d_1))$ rounds with the Matrix Multiplicative Weight Update algorithm.We study tomography for quantum channels with input dimension $d_1$, output dimension $d_2$, and Kraus rank at most $r$, to within diamond norm error $\varepsilon$, using adaptive experiments that retain no quantum memory between channel queries. - For quantum channels whose non-zero Choi eigenvalues are bounded below by $Ω(d_1/r)$, we establish optimal query upper and lower bounds $Θ(d_1d_2r^2/ε^2)$. The upper bound is achieved by a nonadaptive algorithm that uses the estimator from [Surawy-Stepney et al., Quantum (2022)], together with a new diamond-norm analysis. The lower bound applies to arbitrary adaptive incoherent protocols and follows from a new local family of channels and a uniform one-query Fisher-information bound. - For general channels, we establish an upper bound $O(d_1d_2r^2\log(2d_1)/ε^2)$, nearly matching the above lower bound $Ω(d_1d_2r^2/\varepsilon^2)$. To achieve this, we generalize the above nonadaptive algorithm by adapting the input state over $O(\log(2d_1))$ rounds with the Matrix Multiplicative Weight Update algorithm.

quant-pharXiv:2609.23752Sep 22, 20260 citations

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

d

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

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.

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

Θ(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)

, where

d_{\mathrm{in}}

and

d_{\mathrm{out}}

are the channel input and output dimensions, respectively, and

\varepsilon

is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires

Ω(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)

queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound

O(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)

. Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case

d_{\mathrm{in}}=1

. By contrast, coherent protocols with quantum memory achieve query complexity

Θ(d_{\mathrm{in}}^2 d_{\mathrm{out}}^2/\varepsilon^2)

. Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.

We study the problems of quantum state certification, equivalence testing and independence testing. In certification, given samples of an unknown quantum state

ρ

and the description of a state

σ

, the goal is to test whether

ρ=σ

, or whether

ρ

and

σ

are far in a given distance measure. In equivalence testing,

σ

is also unknown and only accessible via samples. Independence testing decides whether

ρ_{AC}=ρ_A\otimesρ_C

, or is far from being a product. The sample complexities of these problems are now well-understood for a decision gap

\varepsilon

in trace distance: in the single-copy measurement setting with

d

-dimensional states, all three tasks can be solved using the same non-adaptive approach, which uses

Θ(d^{3/2}/\varepsilon^2)

samples and is optimal in general, even without adaptivity. In this work, we consider decision gaps expressed in fidelity and study possible separations between these problems and how adaptivity can help. We prove that certification with respect to fidelity for a state

σ

of rank

r

does not benefit from adaptivity and requires

\widetildeΘ(r^{3/2}/\varepsilon)

samples. For equivalence testing and independence testing, we provide adaptive algorithms using

\widetilde{O}(\min\{d^{3/2}/\varepsilon^2,d^{9/4}/\varepsilon\})

and

\widetilde{O}(\min\{(d_Ad_C)^{3/2}/\varepsilon^2,d_A^{9/4}d_C^{3/4}/\varepsilon\})

samples, for

d_A\geq d_C

, respectively. Our main technique is a framework that uses partial learning and a reduction to testing in

\ell_2

-distance, adapted from the distribution testing literature. We show that adaptivity matters for equivalence testing in fidelity by proving that

\widetildeΩ(1/\varepsilon^2)

samples are necessary in the non-adaptive case even for qubits, showing a separation from certification.

\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 tomography for quantum channels with input dimension

d_1

, output dimension

d_2

, and Kraus rank at most

r

, to within diamond norm error

\varepsilon

, using adaptive experiments that retain no quantum memory between channel queries. - For quantum channels whose non-zero Choi eigenvalues are bounded below by

Ω(d_1/r)

, we establish optimal query upper and lower bounds

Θ(d_1d_2r^2/ε^2)

. The upper bound is achieved by a nonadaptive algorithm that uses the estimator from [Surawy-Stepney et al., Quantum (2022)], together with a new diamond-norm analysis. The lower bound applies to arbitrary adaptive incoherent protocols and follows from a new local family of channels and a uniform one-query Fisher-information bound. - For general channels, we establish an upper bound

O(d_1d_2r^2\log(2d_1)/ε^2)

, nearly matching the above lower bound

Ω(d_1d_2r^2/\varepsilon^2)

. To achieve this, we generalize the above nonadaptive algorithm by adapting the input state over

O(\log(2d_1))

rounds with the Matrix Multiplicative Weight Update algorithm.