Strict Hierarchy for Quantum Channel Certification to Unitary

Chen, Kean; Wang, Qisheng; Zhang, Zhicheng

doi:10.4230/LIPIcs.ICALP.2026.59

Strict Hierarchy for Quantum Channel Certification to Unitary

Kean Chen

Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, USA Qisheng Wang

School of Computer Science, Shanghai Jiao Tong University, Shanghai, China Zhicheng Zhang

School of Information and Communication Technology, Griffith University, Brisbane, QLD, Australia

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)

$\Theta(d/\varepsilon^{2})$ queries suffice for incoherent access model, matching the lower bound due to Fawzi, Flammarion, Garivier, and Oufkir (COLT 2023).
(ii)

$\Theta(d/\varepsilon)$ queries suffice for coherent access model, matching the lower bound due to Regev and Schiff (ICALP 2008).
(iii)

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

Keywords and phrases:

Quantum algorithms, quantum channels, quantum certification, query complexity, entanglement fidelity

Category:

Track A: Algorithms, Complexity and Games

Funding:

Qisheng Wang: Supported by startup funding from Shanghai Jiao Tong University.

Zhicheng Zhang: Supported in part by the Australian Research Council under Grant DP250102952.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Quantum computation theory ; Theory of computation

\rightarrow

Algorithm design techniques

Related Version:

Full Version: https://arxiv.org/abs/2604.26900 [8]

Acknowledgements:

Part of the work of Zhicheng Zhang was done when the author was with the Centre for Quantum Software and Information, University of Technology Sydney, Australia.

DOI:

10.4230/LIPIcs.ICALP.2026.59

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

A fundamental task in quantum computing and quantum information is to certify whether a quantum device implements a desired operation. The certification of quantum objects plays an important role in quantum property testing [23], including the certification of quantum states [25, 3, 12, 11], quantum Hamiltonians [14, 21], and quantum channels [13, 30, 18].

In this paper, we consider quantum channel certification. In principle, one can learn a full classical description of an unknown quantum channel via channel tomography [15, 27, 26, 31, 30, 36, 22, 9]. However, full tomography requires far more resources than the certification task and is generally inefficient. A more natural and widely studied goal is to decide only whether the device meets a given specification or is far from it.

1.1 Quantum channel certification to unitary

More formally, we study the problem of quantum channel certification to unitary [13].¹¹1The work [13] additionally considers the certification in the trace norm, a different closeness measure of quantum channels. Given a known unitary channel $\mathcal{U}(\rho)=U\rho U^{\dagger}$ and query access to an unknown quantum channel $\mathcal{E}$ , the goal is to decide between

\textup{Case 1}\colon\mathcal{E}=\mathcal{U}\qquad\text{and}\qquad\textup{Case% 2}\colon\|\mathcal{E}-\mathcal{U}\|_{\diamond}\geq\varepsilon,

with success probability $\geq 2/3$ , while minimizing the number of queries to $\mathcal{E}$ . Here, we consider the certification in the diamond norm $\left\lVert\cdot\right\rVert_{\diamond}$ , which captures the strongest black-box notion of closeness to a target operation.

1.2 Access models and a strict complexity hierarchy

A key lesson from recent work [3, 16, 5, 2, 17, 1, 10, 12, 6, 13, 7, 32, 33] in quantum learning and testing is that is that the access model for the unknown object matters: quantum memory, (in)coherent controls, and variants of oracle queries can yield provably different complexity results. In this paper, we consider three standard access models with increasing power: incoherent access, coherent access, and source-code access.

1.

Incoherent access (cf. [10]) corresponds to quantum algorithms without quantum memory. More precisely, after each query to $\mathcal{E}$ , the algorithm must perform a measurement; only classical information may be retained and used in subsequent queries. Formally, an incoherent algorithm using $T$ queries to $\mathcal{E}$ has the following behavior: When using the $i$ -th query to $\mathcal{E}$ for $1\leq i\leq T$ , the algorithm prepares a quantum state $\rho_{i}$ according to the classical information $C_{1},C_{2},\dots,C_{i-1}$ obtained previously, and applies $\mathcal{E}$ to $\rho_{i}$ , followed by a measurement with outcome $C_{i}$ .
2.

Coherent access, contrast to incoherent access, corresponds to quantum algorithms with quantum memory. The algorithm can perform an arbitrary joint quantum computation across multiple queries to $\mathcal{E}$ .
3.

Source-code access (cf. [19]) corresponds to coherent access and, additionally, access to the “source code” for implementing the target channel $\mathcal{E}$ . Here, the “source code” describes a quantum circuit $W$ that implements the unknown oracle (in our case, the channel $\mathcal{E}$ ). More precisely, the algorithm can query the unitary operator $W$ (and its inverse $W^{\dagger}$ ) such that $\operatorname{tr}_{\mathsf{B}}\left\lparen W(\rho_{\mathsf{A}}\otimes\lvert 0% \rangle\!\langle 0\rvert_{\mathsf{B}})W^{\dagger}\right\rparen=\mathcal{E}(% \rho_{\mathsf{A}})$ for any input state $\rho_{\mathsf{A}}$ , where $\mathsf{A}$ is the main system and $\mathsf{B}$ is the environment.

The main result of this paper is a strict complexity hierarchy of complexities for quantum channel certification to unitary across the above three models, showing a strict increase in power from incoherent to coherent to source-code access.

Table 1: Query complexity of certifying

\mathcal{E}=\mathcal{U}

versus

\|\mathcal{E}-\mathcal{U}\|_{\diamond}\geq\varepsilon

under three access models.

Access Model	Query Complexity	Upper Bounds	Lower Bounds
Incoherent Access	$\Theta(d/\varepsilon^{2})$	Theorem 3	[13]
Coherent Access	$\Theta(d/\varepsilon)$	Theorem 6	[29]
Source-Code Access	$\Theta(\sqrt{d}/\varepsilon)$	Theorem 9	[18]

1.3 Main results

In this paper, we provide efficient algorithms for quantum channel certification to unitary in each of the three access models mentioned above. Combining with the existing lower bounds in [13, 29, 18], we completely characterize the query complexity of this problem.

Theorem 1 (Informal, Theorems 3, 6, and 9 restated).

Let $\mathcal{E}$ be an unknown $d$ -dimensional quantum channel and $\mathcal{U}$ be a known $d$ -dimensional unitary channel. The optimal number of queries needed to certify $\mathcal{E}=\mathcal{U}$ versus $\|\mathcal{E}-\mathcal{U}\|_{\diamond}\geq\varepsilon$ is:

1.

$\Theta(d/\varepsilon^{2})$ in the incoherent access model;
2.

$\Theta(d/\varepsilon)$ in the coherent access model;
3.

$\Theta(\sqrt{d}/\varepsilon)$ in the source-code access model.

All three bounds in Theorem 1 are tight. For incoherent access, the lower bound is due to Fawzi, Flammarion, Garivier, and Oufkir [13], and our upper bound improves their $O\lparen d/\varepsilon^{4}\rparen$ . For coherent access, the lower bound follows from the proof and the hard instance in work of Regev and Schiff [29]. For source-code access, our upper bound matches the lower bound recently established by Jeon and Oh [18]. Together, these results exhibit a strict complexity hierarchy for the same certification task under increasingly powerful access to the unknown channel.

$\blacktriangleright$ Remark 2.

In [18, Theorem 3], they considered a similar and related problem of unitary channel certification to identity, where the task is to determine whether $\mathcal{U}=\mathcal{I}$ or $\lVert\mathcal{U}-\mathcal{I}\rVert_{\diamond}\geq\varepsilon$ for an unknown unitary channel $\mathcal{U}$ , given query access to $\mathcal{U}$ and $\mathcal{U}^{-1}$ . They provided a quantum algorithm for this problem with query complexity $\Theta\lparen\sqrt{d}/\varepsilon\rparen$ . In comparison, our result in the source-code access model implies their upper bound, as our problem “quantum channel certification to unitary” is more general: the unknown channel $\mathcal{E}$ is not guaranteed to be unitary.

1.4 Techniques

We begin with our optimal approach for incoherent access, based on which we further obtain our approaches for coherent and source-code accesses.

1.4.1 Incoherent access

We leverage the Choi–Jamiołkowski isomorphism: applying $(\mathcal{U}^{-1}\circ\mathcal{E})\otimes\mathcal{I}$ to the maximally entangled state $\lvert\Phi\rangle$ and measuring the projector onto $\lvert\Phi\rangle$ yields a Bernoulli random variable $X$ with expectation $\mathbf{E}[X]=\mathrm{F}_{\textup{ent}}\lparen\mathcal{E},\mathcal{U}\rparen$ , where $\mathrm{F}_{\textup{ent}}\lparen\mathcal{E},\mathcal{U}\rparen$ is the entanglement fidelity [24] (or channel fidelity [28]) between $\mathcal{E}$ and $\mathcal{U}$ .²²2For general quantum channels, the entanglement fidelity is defined as $\mathrm{F}_{\textup{ent}}\lparen\mathcal{E},\mathcal{F}\rparen\coloneqq\mathrm% {F}((\mathcal{E}\otimes\mathcal{I})(\lvert\Phi\rangle\!\langle\Phi\rvert),(% \mathcal{F}\otimes\mathcal{I})(\lvert\Phi\rangle\!\langle\Phi\rvert))$ , in which $\mathrm{F}$ denotes the (squared) fidelity between quantum states. To this end, we present a quantitative link between the entanglement fidelity and the diamond norm (in Lemma 4):

\mathrm{F}_{\textup{ent}}\lparen\mathcal{E},\mathcal{U}\rparen\leq\sqrt{% \mathrm{F}_{\textup{ent}}\lparen\mathcal{E},\mathcal{U}\rparen}\leq 1-\frac{1}% {8d}\lVert\mathcal{E}-\mathcal{U}\rVert_{\diamond}^{2}.

Further analysis shows that (i) $\mathbf{E}[X]=1$ when $\mathcal{E}=\mathcal{U}$ while (ii) $\mathbf{E}[X]\leq 1-\Theta\lparen{\varepsilon^{2}}/{d}\rparen$ when $\lVert\mathcal{E}-\mathcal{U}\rVert_{\diamond}\geq\varepsilon$ . To distinguish the two cases, it suffices to use $O\lparen d/\varepsilon^{2}\rparen$ samples of $X$ , which gives the upper bound.

In comparison, the previous work [13] considers the certification task in the incoherent access and ancilla-free setting. They obtained upper bounds $O(d/\varepsilon^{2})$ and $O(d/\varepsilon^{4})$ for trace norm and diamond norm certifications, respectively. They also showed that the upper bound $O(d/\varepsilon^{2})$ for trace norm certification is optimal by establishing a matching lower bound $\Omega(d/\varepsilon^{2})$ , which holds even for ancilla-assisted algorithms. We note that in our paper, we consider the incoherent access model but allowing ancilla qubits, i.e., the input to the unknown channel can be an entangled state on the main system and an ancilla system.

1.4.2 Coherent access

Inspired by [15], our approach for coherent access is obtained by bootstrapping the $\varepsilon$ dependence in the incoherent approach. First, we note that certifying $\mathcal{E}$ to $\mathcal{U}$ can be reduced to certifying $\mathcal{U}^{-1}\circ\mathcal{E}$ and $\mathcal{I}$ . Then, instead of measuring immediately after each use of $\mathcal{U}^{-1}\circ\mathcal{E}$ , we observe that repeatedly applying $\mathcal{U}^{-1}\circ\mathcal{E}$ can enlarge the promised gap linearly when the number of repetitions is small. Specifically, as given by Lemma 7, the $n$ -fold composition of $\mathcal{U}^{-1}\circ\mathcal{E}$ , satisfies

\left\lVert\left\lparen\mathcal{U}^{-1}\circ\mathcal{E}\right\rparen^{n}-% \mathcal{I}\right\rVert_{\diamond}\geq\frac{1}{2}n\left\lVert\left\lparen% \mathcal{U}^{-1}\circ\mathcal{E}\right\rparen-\mathcal{I}\right\rVert_{% \diamond},

as long as $n\leq\lparen 2\lVert\lparen\mathcal{U}^{-1}\circ\mathcal{E}\rparen-\mathcal{I}% \rVert_{\diamond}\rparen^{-1}$ . Based on this, we can amplify the difference between $\mathcal{U}^{-1}\circ\mathcal{E}$ and $\mathcal{I}$ , say $\eta$ , to $\Theta(1)$ using only $O(1/\eta)$ queries, and then we can call the incoherent certification algorithm with constant precision. However, since we do not know the value of $\eta$ , we use a step-wise amplification strategy from low precision to high precision with a logarithmic number of total steps. Through a careful error analysis, we can conclude that the overall complexity is $O(d/\varepsilon)$ .

1.4.3 Source-code access

Our approach for source-code access is also obtained by adapting the incoherent approach. Recall that in the incoherent approach, a random variable $X$ obtained using one query to $\mathcal{E}$ satisfies (i) $\mathbf{E}[X]=1$ when $\mathcal{E}=\mathcal{U}$ while (ii) $\mathbf{E}[X]\leq 1-\Theta\lparen{\varepsilon^{2}}/{d}\rparen$ when $\lVert\mathcal{E}-\mathcal{U}\rVert_{\diamond}\geq\varepsilon$ . Given source-code access, we view this process as a quantum circuit $V$ from the perspective of amplitudes, which is of the form

V\lvert 0\rangle=\sqrt{\mathbf{E}[X]}\lvert\phi_{0}\rangle+\sqrt{1-\mathbf{E}[% X]}\lvert\phi_{1}\rangle,

with $\lvert\phi_{0}\rangle\perp\lvert\phi_{1}\rangle$ . To distinguish the two cases, we focus on the amplitude $\sqrt{1-\mathbf{E}[X]}$ of $\lvert\phi_{1}\rangle$ , which is $0$ if $\mathcal{E}=\mathcal{U}$ and $\Theta\lparen\varepsilon/\sqrt{d}\rparen$ if $\lVert\mathcal{E}-\mathcal{U}\rVert_{\diamond}\geq\varepsilon$ . This special case can be determined with query complexity $O\lparen\sqrt{d}/\varepsilon\rparen$ by quantum amplitude estimation [4] if given source-code access.

1.5 Discussion

In this paper, we settle the query complexities for quantum channel certification to unitary under three access models with increasing power: $\Theta(d/\varepsilon^{2})$ for incoherent access, $\Theta(d/\varepsilon)$ for coherent access, and $\Theta(\sqrt{d}/\varepsilon)$ for source-code access. This establishes a strict complexity hierarchy across these access models. We conclude by listing several directions for future work.

$\blacksquare$

First, an immediate question is whether one can establish a strict hierarchy for other quantum learning and testing problems across these access models.
$\blacksquare$

Second, it would be interesting to identify problems for which the hierarchy collapses; i.e., where a stronger access model does not help in improving the complexity.
$\blacksquare$

Third, a broader direction is to investigate whether a larger strict hierarchy can be obtained by considering a richer set of access models in quantum computing.

1.6 Organization

Section 2 presents the incoherent approach with the analytic connection between entanglement fidelity and the diamond norm. Section 3 presents the coherent bootstrapping approach. Section 4 presents the approach for source-code access.

2 Incoherent access

2.1 The algorithm

Algorithm 1 Incoherent Certification: IncohCert

(\varepsilon,\delta,\mathcal{E},\mathcal{U})

.

Theorem 3.

Let $\mathcal{E}$ be an unknown $d$ -dimensional quantum channel and $\mathcal{U}$ be a known $d$ -dimensional unitary channel. Then, Algorithm 1 uses $n=\lceil 8d\ln(1/\delta)/\varepsilon^{2}\rceil$ queries to $\mathcal{E}$ and distinguishes the cases: (i) $\mathcal{E}=\mathcal{U}$ or (ii) $\|\mathcal{E}-\mathcal{U}\|_{\diamond}\geq\varepsilon$ , with probability at least $1-\delta$ . Moreover, for the case $\mathcal{E}=\mathcal{U}$ , the algorithm always outputs “ $\mathcal{E}=\mathcal{U}$ ” with probability $1$ .

Proof.

The algorithm is shown in Algorithm 1. If $\mathcal{E}=\mathcal{U}$ , then all $x_{i}$ must be $0$ , and Algorithm 1 outputs “ $\mathcal{E}=\mathcal{U}$ ” with probability $1$ .

Otherwise, we assume $\|\mathcal{E}-\mathcal{U}\|_{\diamond}\geq\varepsilon$ . By Lemma 4, this means

\mathrm{F}_{\textup{ent}}(\mathcal{E},\mathcal{U})\leq 1-\frac{1}{8d}\|% \mathcal{E}-\mathcal{U}\|_{\diamond}^{2}\leq 1-\frac{\varepsilon^{2}}{8d}.

Thus, for each $i$ , the probability of $x_{i}=0$ is

\operatorname{tr}\!\left(\lvert\Phi\rangle\!\langle\Phi\rvert\lparen(\mathcal{% U}^{-1}\circ\mathcal{E})\otimes\mathcal{I}\rparen(\lvert\Phi\rangle\!\langle% \Phi\rvert)\right)=\frac{1}{d^{2}}\operatorname{tr}(C_{\mathcal{U}}\cdot C_{% \mathcal{E}})=\mathrm{F}_{\mathrm{ent}}(\mathcal{E},\mathcal{U})\leq 1-\frac{% \varepsilon^{2}}{8d}.

Therefore, for $n\geq 8d\ln\lparen 1/\delta\rparen/\varepsilon^{2}$ , the probability that there is at least one $x_{i}=1$ is at least

1-\left\lparen 1-\frac{\varepsilon^{2}}{8d}\right\rparen^{n}\geq 1-\exp\left% \lparen-\frac{n\varepsilon^{2}}{8d}\right\rparen=1-\delta,

where we use the fact that $1-x\leq\exp\lparen-x\rparen$ for $x\in\lparen 0,1\rparen$ . $\hfill\blacktriangleleft$

2.2 Technical lemmas

Lemma 4.

Let $\mathcal{E}$ be a $d$ -dimensional quantum channel and $\mathcal{U}$ be a $d$ -dimensional unitary channel. Then,

\sqrt{\mathrm{F}_{\textup{ent}}\lparen\mathcal{E},\mathcal{U}\rparen}\leq 1-% \frac{1}{8d}\lVert\mathcal{E}-\mathcal{U}\rVert_{\diamond}^{2}.

Proof.

Let $\mathcal{F}\coloneqq\mathcal{U}^{-1}\circ\mathcal{E}$ . Then, by unitary invariance, we have $\|\mathcal{E}-\mathcal{U}\|_{\diamond}=\|\mathcal{F}-\mathcal{I}\|_{\diamond}$ and $\mathrm{F}_{\textup{ent}}(\mathcal{E},\mathcal{U})=\mathrm{F}_{\textup{ent}}(% \mathcal{F},\mathcal{I})$ . Therefore, we only have to show that

\sqrt{\mathrm{F}_{\textup{ent}}\lparen\mathcal{F},\mathcal{I}\rparen}\leq 1-% \frac{1}{8d}\lVert\mathcal{F}-\mathcal{I}\rVert_{\diamond}^{2}.

Let $\{A_{k}\}$ be a set of Kraus operators of $\mathcal{F}$ (no more than $d^{2}$ ). Let $V=\sum_{k}A_{k}\otimes\lvert k\rangle:\mathbb{C}^{d}\to\mathbb{C}^{d}\otimes% \mathcal{H}_{\mathrm{anc}}\cong\mathbb{C}^{d}\otimes\mathbb{C}^{d^{2}}$ be a Stinespring dilation isometry for $\mathcal{F}$ , i.e., $\mathcal{F}(\rho)=\operatorname{tr}_{\mathrm{anc}}(V\rho V^{\dagger})$ , where $\{\lvert k\rangle\}$ is the computational basis of $\mathcal{H}_{\mathrm{anc}}$ . Let $W_{\eta}\colon\lvert\psi\rangle\mapsto\lvert\psi\rangle\otimes\lvert\eta\rangle$ be a Stinespring dilation isometry for $\mathcal{I}$ for some unit vector $\lvert\eta\rangle\in\mathcal{H}_{\mathrm{anc}}$ . By the continuity of Stinespring’s representation [20],

\|\mathcal{F}-\mathcal{I}\|_{\diamond}\leq 2\inf_{\lvert\eta\rangle}\|V-W_{% \eta}\|,

(1)

where $\lvert\eta\rangle$ is taken over all unit vectors in $\mathcal{H}_{\mathrm{anc}}$ .

On the other hand,

	$\displaystyle\mathrm{F}_{\textup{ent}}\lparen\mathcal{F},\mathcal{I}\rparen$	$\displaystyle=\sum_{k}\langle\Phi\rvert(A_{k}\otimes I)\lvert\Phi\rangle\!% \langle\Phi\rvert(A_{k}^{\dagger}\otimes I)\lvert\Phi\rangle$
		$\displaystyle=\frac{1}{d^{2}}\sum_{k}\left\lvert\operatorname{tr}\lparen A_{k}% \rparen\right\rvert^{2},$

where $\lvert\Phi\rangle$ denotes the maximally entangled state. Suppose that $\lvert\eta\rangle=\sum_{k}c_{k}\lvert k\rangle$ with $\sum_{k}\lvert c_{k}\rvert^{2}=1$ . By the Cauchy–Schwarz inequality,

\left|\operatorname{tr}\lparen W_{\eta}^{\dagger}V\rparen\right|=\left|\sum_{k% }c_{k}^{*}\operatorname{tr}\lparen A_{k}\rparen\right|\leq\sqrt{\sum_{k}\left% \lvert\operatorname{tr}\lparen A_{k}\rparen\right\rvert^{2}}=d\sqrt{\mathrm{F}% _{\textup{ent}}\lparen\mathcal{F},\mathcal{I}\rparen},

which also means that there is a unit vector $\lvert\eta_{\star}\rangle$ such that

\operatorname{tr}\left\lparen W_{\eta_{\star}}^{\dagger}V\right\rparen=d\sqrt{% \mathrm{F}_{\textup{ent}}\lparen\mathcal{F},\mathcal{I}\rparen}.

(2)

Using $\lVert A\rVert\leq\sqrt{\operatorname{tr}\lparen A^{\dagger}A\rparen}$ , we have

$\displaystyle\lVert V-W_{\eta_{\star}}\rVert$	$\displaystyle\leq\sqrt{\operatorname{tr}\left\lparen\left\lparen V-W_{\eta_{% \star}}\right\rparen^{\dagger}\left\lparen V-W_{\eta_{\star}}\right\rparen% \right\rparen}$
	$\displaystyle=\sqrt{\operatorname{tr}\left\lparen V^{\dagger}V\right\rparen+% \operatorname{tr}\left\lparen W_{\eta_{\star}}^{\dagger}W_{\eta_{\star}}\right% \rparen-2\operatorname{Re}\left\lparen\operatorname{tr}\left\lparen W_{\eta_{% \star}}^{\dagger}V\right\rparen\right\rparen}$
	$\displaystyle=\sqrt{2d-2\operatorname{tr}\left\lparen W_{\eta_{\star}}^{% \dagger}V\right\rparen}$	(3)
	$\displaystyle=\sqrt{2d-2d\sqrt{\mathrm{F}_{\textup{ent}}\lparen\mathcal{F},% \mathcal{I}\rparen}},$	(4)

where Equation 3 uses the fact that $\operatorname{tr}\lparen V^{\dagger}V\rparen=\operatorname{tr}\lparen W_{\eta_% {\star}}^{\dagger}W_{\eta_{\star}}\rparen=d$ and $\operatorname{tr}\lparen W_{\eta_{\star}}^{\dagger}V\rparen$ is a real number, and Equation 4 is due to Equation 2. Combining Equations 1 and 4, we have

\lVert\mathcal{F}-\mathcal{I}\rVert_{\diamond}\leq 2\sqrt{2d-2d\sqrt{\mathrm{F% }_{\textup{ent}}\lparen\mathcal{F},\mathcal{I}\rparen}},

which gives

\sqrt{\mathrm{F}_{\textup{ent}}\lparen\mathcal{F},\mathcal{I}\rparen}\leq 1-% \frac{1}{8d}\lVert\mathcal{F}-\mathcal{I}\rVert_{\diamond}^{2}.\

$\hfill\blacktriangleleft$

2.3 Lower bound

The upper bound in Theorem 3 matches the lower bound for quantum channel certification to identity in [13]. Here, note that quantum channel certification to identity is a special case of quantum channel certification to unitary.

Lemma 5 ([13, Theorem 1]).

Let $\mathcal{E}$ be an unknown $d$ -dimensional unitary quantum channel and $\varepsilon\in\lparen 0,1\rparen$ . Then, any incoherent algorithm requires $\Omega\lparen d/\varepsilon^{2}\rparen$ to $\mathcal{E}$ to distinguish the cases: (i) $\mathcal{E}=\mathcal{I}$ or (ii) $\lVert\mathcal{E}-\mathcal{I}\rVert_{\diamond}\geq\varepsilon$ , with probability $\geq 2/3$ .

3 Coherent access

3.1 The algorithm

Algorithm 2 Coherent certification: CohCert

(\varepsilon,\delta,\mathcal{E},\mathcal{U})

.

Theorem 6.

Let $\mathcal{E}$ be an unknown $d$ -dimensional quantum channel and $\mathcal{U}$ be a known $d$ -dimensional unitary channel. Then, Algorithm 2 uses $n=O(d\log(1/\delta)/\varepsilon)$ queries to $\mathcal{E}$ and distinguishes the cases: (i) $\mathcal{E}=\mathcal{U}$ or (ii) $\|\mathcal{E}-\mathcal{U}\|_{\diamond}\geq\varepsilon$ , with probability at least $1-\delta$ .

Proof.

The algorithm is shown in Algorithm 2.

The case $\mathcal{E}=\mathcal{U}$ .

In the $j$ -th iteration in Algorithm 2, the probability of $b_{j}=\mathsf{reject}$ is $0$ due to Theorem 3. Therefore, the probability of Algorithm 2 outputting $\mathsf{reject}$ is $0$ .

The case $\|\mathcal{E}-\mathcal{U}\|_{\diamond}\geq\varepsilon$ .

Let $\eta\coloneqq\|\mathcal{E}-\mathcal{U}\|_{\diamond}=\|\mathcal{U}^{-1}\circ% \mathcal{E}-\mathcal{I}\|_{\diamond}$ .

If $\eta\in(1/2,2]$ , then in the $0$ -th iteration, $b_{0}=\mathsf{accept}$ with probability at most $\delta_{0}\leq\delta$ , due to Theorem 3. This means Algorithm 2 outputs $\mathsf{accept}$ with probability at most $\delta$ .

Otherwise, assume $\eta\in(2^{-a},2^{-a+1}]$ for an integer $a\geq 2$ , and we know that $a\leq\log(1/\varepsilon)+1$ . Note that $T\geq a$ and we consider the $(a-2)$ -th iteration. We can see that $p_{a-2}=2^{a-2}\leq\frac{1}{2\eta}$ . Using Lemma 7, we have

\left\|(\mathcal{U}^{-1}\circ\mathcal{E})^{p_{a-2}}-\mathcal{I}\right\|_{% \diamond}>\frac{1}{2}p_{a-2}\eta=2^{a-3}\eta>\frac{1}{8}.

Then, by Theorem 3, the probability that $b_{a-2}=\mathsf{accept}$ is at most $\delta_{a-2}\leq\delta$ . This means Algorithm 2 outputs $\mathsf{accept}$ with probability at most $\delta$ .

Complexity analysis.

The complexity of Algorithm 2 is thus

	$\displaystyle\sum_{j=0}^{T}p_{j}\cdot O\lparen d\log\lparen 1/\delta_{j}\rparen\rparen$	$\displaystyle=\sum_{j=0}^{T}2^{j}\cdot O\lparen d\left\lparen\log\lparen 1/% \delta\rparen+T+1-j\right\rparen\rparen$
		$\displaystyle=O\lparen 2^{T}d\log\lparen 1/\delta\rparen\rparen+O\lparen d% \cdot 2^{T+2}\rparen$
		$\displaystyle=O\lparen d\log\lparen 1/\delta\rparen/\varepsilon\rparen.\$

$\hfill\blacktriangleleft$

3.2 Technical lemmas

Lemma 7.

If $\lVert\mathcal{E}-\mathcal{I}\rVert_{\diamond}=\varepsilon$ , then for any integer $1\leq n\leq\frac{1}{2\varepsilon}$ , we have

\|\mathcal{E}^{n}-\mathcal{I}\|_{\diamond}\geq\frac{1}{2}n\varepsilon.

Proof.

Let $\mathcal{E}=\mathcal{I}+\Delta$ , where $\|\Delta\|_{\diamond}=\varepsilon$ . Then we have

\mathcal{E}^{n}-\mathcal{I}=(\mathcal{I}+\Delta)^{n}-\mathcal{I}=n\Delta+\sum_% {i=2}^{n}\binom{n}{i}\Delta^{i}.

Therefore,

$\displaystyle\\|\mathcal{E}^{n}-\mathcal{I}\\|_{\diamond}$	$\displaystyle\geq n\\|\Delta\\|_{\diamond}-\sum_{i=2}^{n}\binom{n}{i}\\|\Delta^{i% }\\|_{\diamond}$
	$\displaystyle\geq n\varepsilon-\sum_{i=2}^{n}\binom{n}{i}\varepsilon^{i}$	(5)
	$\displaystyle=n\varepsilon-\left((1+\varepsilon)^{n}-1-n\varepsilon\right)$
	$\displaystyle\geq n\varepsilon-\left(e^{n\varepsilon}-1-n\varepsilon\right)$
	$\displaystyle\geq n\varepsilon-e^{n\varepsilon}\frac{(n\varepsilon)^{2}}{2}$	(6)
	$\displaystyle\geq n\varepsilon-\frac{e^{1/2}}{4}n\varepsilon$	(7)
	$\displaystyle\geq\frac{1}{2}n\varepsilon$

where Equation 5 uses the sub-multiplicativity $\|\Delta^{k}\|_{\diamond}\leq\|\Delta\|_{\diamond}^{k}$ (see [35, Proposition 3.48(1)]), Equation 6 uses the Taylor expansion

e^{n\varepsilon}-1-n\varepsilon=\sum_{i=2}^{\infty}\frac{(n\varepsilon)^{i}}{i% !}\leq\frac{(n\varepsilon)^{2}}{2}\sum_{i=0}^{\infty}\frac{(n\varepsilon)^{i}}% {i!}=\frac{(n\varepsilon)^{2}}{2}e^{n\varepsilon},

and Equation 7 uses $n\varepsilon\leq 1/2$ . $\hfill\blacktriangleleft$

3.3 Lower bound

In the following we present a query lower bound of $\Omega(d/\varepsilon)$ for quantum channel certification to identity, a special case of certification to unitary. The proof follows from a simple reduction to Regev-Schiff’s $p$ -faulty Grover problem [29].

Lemma 8.

Let $\mathcal{E}$ be an unknown $d$ -dimensional quantum channel. Suppose $\varepsilon\in(0,1)$ . Then it requires $\Omega(d/\varepsilon)$ queries to $\mathcal{E}$ to distinguish the cases: (i) $\mathcal{E}=\mathcal{I}$ or (ii) $\|\mathcal{E}-\mathcal{I}\|_{\diamond}\geq\varepsilon$ , with probability $\geq 2/3$ .

Proof.

Let us consider the following hard instance from [29]. For each $k\in\{0,1,\dots,d-1\}$ , define the $p$ -faulty Grover oracle and its corresponding quantum channel:

	$\displaystyle O_{k}$	$\displaystyle=I-2\lvert k\rangle\!\langle k\rvert,$
	$\displaystyle\mathcal{E}_{k}(\rho)$	$\displaystyle=p\rho+(1-p)O_{k}\rho O_{k}^{\dagger},$

where $p=1-\frac{\varepsilon}{2}>\frac{1}{2}$ .

Consider the task of distinguishing between the following two cases:

1.

$\mathcal{E}=\mathcal{I}$ .
2.

$\mathcal{E}=\mathcal{E}_{k}$ for some $k\in\left\{0,1,\ldots,d-1\right\}$ . In this case, pick any $j\neq k$ . Define

$\lvert\psi\rangle=\frac{\lvert k\rangle+\lvert j\rangle}{\sqrt{2}},\qquad% \lvert\psi_{\perp}\rangle=\frac{-\lvert k\rangle+\lvert j\rangle}{\sqrt{2}}.$

It is easy to see that $O_{k}\lvert\psi\rangle=\lvert\psi_{\perp}\rangle$ and $\left<\psi\vphantom{\psi_{\perp}}\middle|\psi_{\perp}\vphantom{\psi}\right>=0$ , which mean

$\mathcal{E}_{k}(\lvert\psi\rangle\!\langle\psi\rvert)\;=\;p\,\lvert\psi\rangle% \!\langle\psi\rvert+(1-p)\,\lvert\psi_{\perp}\rangle\!\langle\psi_{\perp}\rvert.$

Then, we can calculate that

$\left\lVert\mathcal{E}_{k}-\mathcal{I}\right\rVert_{\diamond}\geq\left\lVert% \mathcal{E}_{k}(\lvert\psi\rangle\!\langle\psi\rvert)-\lvert\psi\rangle\!% \langle\psi\rvert\right\rVert_{1}=2(1-p)=\varepsilon.$

Any quantum algorithm for quantum channel certification to identity (see Lemma 8) can also distinguish the above two cases. Since the $p$ -faulty Grover problem has query lower bound $\Omega\!\left(\frac{pd}{1-p}\right)$ [29], it follows that $\Omega(d/\varepsilon)$ queries are required for quantum channel certification by $p=1-\frac{\varepsilon}{2}$ . $\hfill\blacktriangleleft$

4 Source-code access

4.1 The algorithm

Theorem 9.

Let $W$ be the source code (quantum unitary circuit) that implements an unknown $d$ -dimensional quantum channel $\mathcal{E}$ . Let $\mathcal{U}$ be a known $d$ -dimensional unitary channel. Then, Algorithm 3 uses $n=O\lparen\sqrt{d}\log\lparen 1/\delta\rparen/\varepsilon\rparen$ queries to controlled- $W$ and controlled- $W^{\dagger}$ , and distinguishes the cases: (i) $\mathcal{E}=\mathcal{U}$ or (ii) $\|\mathcal{E}-\mathcal{U}\|_{\diamond}\geq\varepsilon$ , with probability at least $1-\delta$ .

To prove Theorem 9, we need the quantum amplitude estimation [4]. Here, for convenience, we use the version adapted from [34].

Theorem 10 ([34, Theorem III.4]).

Let $U$ be a unitary operator such that

U\lvert 0\rangle_{\mathsf{A}}\lvert 0\rangle_{\mathsf{B}}=\sqrt{1-p}\lvert 0% \rangle_{\mathsf{A}}\lvert\phi_{0}\rangle_{\mathsf{B}}+\sqrt{p}\lvert\perp% \rangle_{\mathsf{A}}\lvert\phi_{1}\rangle_{\mathsf{B}},

where $p\in[0,1]$ , $\lvert 0\rangle_{\mathsf{A}}\perp\lvert\perp\rangle_{\mathsf{A}}$ , and $\lvert\phi_{0}\rangle$ and $\lvert\phi_{1}\rangle$ are normalized pure states. Then, there is a quantum query algorithm $\textup{{SqrtAmplEst}}\lparen\varepsilon,\delta,U\rparen$ that estimates $\sqrt{p}$ to within additive error $\varepsilon$ with success probability $\geq 1-\delta$ using $O\lparen\log\lparen 1/\delta\rparen/\varepsilon\rparen$ queries to controlled- $U$ and controlled- $U^{\dagger}$ .

Algorithm 3 Source-Code Certification: SourceCodeCert

(\varepsilon,\delta,\mathcal{E},\mathcal{U})

.

Proof of Theorem 9.

The construction of $V$ follows Lines 3 and 4 in Algorithm 1, and we have

\left\lVert\langle 0\rvert_{\mathsf{AC}}V_{\mathsf{ABC}}\lvert 0\rangle_{% \mathsf{ABC}}\right\rVert^{2}=\operatorname{tr}\!\left(\lvert\Phi\rangle\!% \langle\Phi\rvert\lparen(\mathcal{U}^{-1}\circ\mathcal{E})\otimes\mathcal{I}% \rparen(\lvert\Phi\rangle\!\langle\Phi\rvert)\right)=\mathrm{F}_{\textup{ent}}% (\mathcal{E},\mathcal{U}).

Therefore, by Theorem 10, $p$ is an estimate of $\sqrt{1-\mathrm{F}_{\textup{ent}}(\mathcal{E},\mathcal{U})}$ such that

\Pr\left[\left\lvert p-\sqrt{1-\mathrm{F}_{\textup{ent}}(\mathcal{E},\mathcal{% U})}\right\rvert\leq\frac{\varepsilon}{16\sqrt{d}}\right]\geq 1-\delta.

Then, we follow the argument in the proof of Theorem 3. If $\mathcal{E}=\mathcal{U}$ , then $\mathrm{F}_{\textup{ent}}(\mathcal{E},\mathcal{U})=1$ , and thus $p<\frac{\varepsilon}{4\sqrt{d}}$ with probability $\geq 1-\delta$ , in which case Algorithm 3 outputs “ $\mathcal{E}=\mathcal{U}$ ” with probability $\geq 1-\delta$ . Otherwise, if $\|\mathcal{E}-\mathcal{U}\|_{\diamond}\geq\varepsilon$ , then by Lemma 4,

\sqrt{1-\mathrm{F}_{\textup{ent}}(\mathcal{E},\mathcal{U})}\geq\sqrt{\frac{1}{% 8d}\|\mathcal{E}-\mathcal{U}\|_{\diamond}^{2}}\geq\frac{\varepsilon}{\sqrt{8d}},

and thus $p>\frac{\varepsilon}{4\sqrt{d}}$ with probability $\geq 1-\delta$ , in which case outputs $\mathsf{reject}$ with probability $\geq 1-\delta$ .

To complete the proof, the query complexity is $O\lparen\sqrt{d}\log\lparen 1/\delta\rparen/{\varepsilon}\rparen$ due to the use of Theorem 10. $\hfill\blacktriangleleft$

4.2 Lower bound

The upper bound in Theorem 9 matches the lower bound for quantum channel certification to identity in [18]. Here, note that quantum channel certification to identity is a special case of quantum channel certification to unitary.

Lemma 11 ([18, Theorem 2]).

Let $\mathcal{E}$ be an unknown $d$ -dimensional unitary quantum channel and $\varepsilon\in\lparen 0,1/2\rparen$ . Then, it requires $\Omega\lparen\sqrt{d}/\varepsilon\rparen$ to $\mathcal{E}$ and $\mathcal{E}^{-1}$ to distinguish the cases: (i) $\mathcal{E}=\mathcal{I}$ or (ii) $\lVert\mathcal{E}-\mathcal{I}\rVert_{\diamond}\geq\varepsilon$ , with probability $\geq 2/3$ .

References

[1] Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi. Quantum algorithmic measurement. Nature Communications, 13(1):887, 2022. doi:10.1038/s41467-021-27922-0.
[2] Costin Bădescu and Ryan O’Donnell. Improved quantum data analysis. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1398–1411, 2021. doi:10.1145/3406325.3451109.
[3] Costin Bădescu, Ryan O’Donnell, and John Wright. Quantum state certification. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 503–514, 2019. doi:10.1145/3313276.3316344.
[4] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Samuel J. Lomonaco, Jr. and Howard E. Brandt, editors, Quantum Computation and Information, volume 305 of Contemporary Mathematics, pages 53–74. AMS, 2002. doi:10.1090/conm/305/05215.
[5] Sebastien Bubeck, Sitan Chen, and Jerry Li. Entanglement is necessary for optimal quantum property testing. In Proceedings of the IEEE 61st Annual Symposium on Foundations of Computer Science, pages 692–703. IEEE, 2020. doi:10.1109/FOCS46700.2020.00070.
[6] Kean Chen, Qisheng Wang, Peixun Long, and Mingsheng Ying. Unitarity estimation for quantum channels. IEEE Transactions on Information Theory, 69(8):5116–5134, 2023. doi:10.1109/TIT.2023.3263645.
[7] Kean Chen, Qisheng Wang, and Zhicheng Zhang. Local test for unitarily invariant properties of bipartite quantum states. IEEE Transactions on Information Theory, 2026. doi:10.1109/TIT.2026.3697790.
[8] Kean Chen, Qisheng Wang, and Zhicheng Zhang. Strict hierarchy for quantum channel certification to unitary. ArXiv e-prints, 2026. arXiv:2604.26900.
[9] Kean Chen, Nengkun Yu, and Zhicheng Zhang. Quantum channel tomography and estimation by local test. ArXiv e-prints, 2025. doi:10.48550/arXiv.2512.13614.
[10] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. Exponential separations between learning with and without quantum memory. In Proceedings of the IEEE 62nd Annual Symposium on Foundations of Computer Science, pages 574–585. IEEE, 2022. doi:10.1109/FOCS52979.2021.00063.
[11] Sitan Chen, Jerry Li, Brice Huang, and Allen Liu. Tight bounds for quantum state certification with incoherent measurements. In Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, pages 1205–1213, 2022. doi:10.1109/FOCS54457.2022.00118.
[12] Sitan Chen, Jerry Li, and Ryan O’Donnell. Toward instance-optimal state certification with incoherent measurements. In Conference on Learning Theory, pages 2541–2596. PMLR, 2022. URL: https://proceedings.mlr.press/v178/chen22b.html.
[13] Omar Fawzi, Nicolas Flammarion, Aurélien Garivier, and Aadil Oufkir. Quantum channel certification with incoherent measurements. In Proceedings of the 36th Conference on Learning Theory, pages 1822–1884, 2023. URL: https://proceedings.mlr.press/v195/fawzi23a.html.
[14] Minbo Gao, Zhengfeng Ji, Qisheng Wang, Wenjun Yu, and Qi Zhao. Quantum Hamiltonian certification. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1424–1467, 2026. doi:10.1137/1.9781611978971.53.
[15] Jeongwan Haah, Robin Kothari, Ryan O’Donnell, and Ewin Tang. Query-optimal estimation of unitary channels in diamond distance. In Proceedings of the IEEE 64th Annual Symposium on Foundations of Computer Science, pages 363–390. IEEE, 2023. doi:10.1109/FOCS57990.2023.00028.
[16] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16(10):1050–1057, 2020. doi:10.1038/s41567-020-0932-7.
[17] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Information-theoretic bounds on quantum advantage in machine learning. Physical Review Letters, 126(19):190505, 2021. doi:10.1103/PhysRevLett.126.190505.
[18] Sangwoo Jeon and Changhun Oh. On the query complexity of unitary channel certification. npj Quantum Information, 12:2, 2026. doi:10.1038/s41534-025-01135-5.
[19] Robin Kothari and Ryan O’Donnell. Mean estimation when you have the source code; or, quantum Monte Carlo methods. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1186–1215. SIAM, 2023. doi:10.1137/1.9781611977554.ch44.
[20] Dennis Kretschmann, Dirk Schlingemann, and Reinhard F. Werner. The information-disturbance tradeoff and the continuity of Stinespring’s representation. IEEE Transactions on Information Theory, 54(4):1708–1717, 2008. doi:10.1109/TIT.2008.917696.
[21] Junseo Lee and Myeongjin Shin. Optimal certification of constant-local Hamiltonians. ArXiv e-prints, 2025. doi:10.48550/arXiv.2512.09778.
[22] Antonio Anna Mele and Lennart Bittel. Optimal learning of quantum channels in diamond distance. ArXiv e-prints, 2025. doi:10.48550/arXiv.2512.10214.
[23] Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing. In Theory of Computing Library, number 7 in Graduate Surveys, pages 1–81. University of Chicago, 2016. doi:10.4086/toc.gs.2016.007.
[24] Michael A. Nielsen. A simple formula for the average gate fidelity of a quantum dynamical operation. Physics Letters A, 303(4):249–252, 2002. doi:10.1016/S0375-9601(02)01272-0.
[25] Ryan O’Donnell and John Wright. Quantum spectrum testing. Communications in Mathematical Physics, 387(1):1–75, 2021. doi:10.1007/s00220-021-04180-1.
[26] Aadil Oufkir. On Adaptivity in Classical and Quantum Learning. PhD thesis, Ecole normale supérieure de lyon-ENS LYON, 2023. URL: https://theses.hal.science/tel-04210763/.
[27] Aadil Oufkir. Sample-optimal quantum process tomography with non-adaptive incoherent measurements. In Proceedings of the 2023 IEEE International Symposium on Information Theory (ISIT), pages 1919–1924, June 2023. doi:10.1109/ISIT54713.2023.10206538.
[28] Maxim Raginsky. A fidelity measure for quantum channels. Physics Letters A, 290(1-2):11–18, 2001. doi:10.1016/S0375-9601(01)00640-5.
[29] Oded Regev and Liron Schiff. Impossibility of a quantum speed-up with a faulty oracle. In Proceedings of 35th International Colloquium on Automata, Languages and Programming, pages 773–781, 2008. doi:10.1007/978-3-540-70575-8_63.
[30] Gregory Rosenthal, Hugo Aaronson, Sathyawageeswar Subramanian, Animesh Datta, and Tom Gur. Quantum channel testing in average-case distance. ArXiv e-prints, 2024. doi:10.48550/arXiv.2409.12566.
[31] Trystan Surawy-Stepney, Jonas Kahn, Richard Kueng, and Madalin Guta. Projected least-squares quantum process tomography. Quantum, 6:844, 2022. doi:10.22331/q-2022-10-20-844.
[32] Ewin Tang and John Wright. Amplitude amplification and estimation require inverses. ArXiv e-prints, 2025. doi:10.48550/arXiv.2507.23787.
[33] Ewin Tang, John Wright, and Mark Zhandry. Conjugate queries can help. ArXiv e-prints, 2025. doi:10.48550/arXiv.2510.07622.
[34] Qisheng Wang. Optimal trace distance and fidelity estimations for pure quantum states. IEEE Transactions on Information Theory, 70(12):8791–8805, 2024. doi:10.1109/TIT.2024.3447915.
[35] John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. doi:10.1017/9781316848142.
[36] Satoshi Yoshida, Jisho Miyazaki, and Mio Murao. Quantum advantage in storage and retrieval of isometry channels. ArXiv e-prints, 2025. arXiv:2507.10784.

[bib.bib1] [1] Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi. Quantum algorithmic measurement. Nature Communications, 13(1):887, 2022. doi:10.1038/s41467-021-27922-0.

[bib.bib2] [2] Costin Bădescu and Ryan O’Donnell. Improved quantum data analysis. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1398–1411, 2021. doi:10.1145/3406325.3451109.

[bib.bib3] [3] Costin Bădescu, Ryan O’Donnell, and John Wright. Quantum state certification. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 503–514, 2019. doi:10.1145/3313276.3316344.

[bib.bib4] [4] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Samuel J. Lomonaco, Jr. and Howard E. Brandt, editors, Quantum Computation and Information, volume 305 of Contemporary Mathematics, pages 53–74. AMS, 2002. doi:10.1090/conm/305/05215.

[bib.bib5] [5] Sebastien Bubeck, Sitan Chen, and Jerry Li. Entanglement is necessary for optimal quantum property testing. In Proceedings of the IEEE 61st Annual Symposium on Foundations of Computer Science, pages 692–703. IEEE, 2020. doi:10.1109/FOCS46700.2020.00070.

[bib.bib6] [6] Kean Chen, Qisheng Wang, Peixun Long, and Mingsheng Ying. Unitarity estimation for quantum channels. IEEE Transactions on Information Theory, 69(8):5116–5134, 2023. doi:10.1109/TIT.2023.3263645.

[bib.bib7] [7] Kean Chen, Qisheng Wang, and Zhicheng Zhang. Local test for unitarily invariant properties of bipartite quantum states. IEEE Transactions on Information Theory, 2026. doi:10.1109/TIT.2026.3697790.

[bib.bib8] [8] Kean Chen, Qisheng Wang, and Zhicheng Zhang. Strict hierarchy for quantum channel certification to unitary. ArXiv e-prints, 2026. arXiv:2604.26900.

[bib.bib9] [9] Kean Chen, Nengkun Yu, and Zhicheng Zhang. Quantum channel tomography and estimation by local test. ArXiv e-prints, 2025. doi:10.48550/arXiv.2512.13614.

[bib.bib10] [10] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. Exponential separations between learning with and without quantum memory. In Proceedings of the IEEE 62nd Annual Symposium on Foundations of Computer Science, pages 574–585. IEEE, 2022. doi:10.1109/FOCS52979.2021.00063.

[bib.bib11] [11] Sitan Chen, Jerry Li, Brice Huang, and Allen Liu. Tight bounds for quantum state certification with incoherent measurements. In Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, pages 1205–1213, 2022. doi:10.1109/FOCS54457.2022.00118.

[bib.bib12] [12] Sitan Chen, Jerry Li, and Ryan O’Donnell. Toward instance-optimal state certification with incoherent measurements. In Conference on Learning Theory, pages 2541–2596. PMLR, 2022. URL: https://proceedings.mlr.press/v178/chen22b.html.

[bib.bib13] [13] Omar Fawzi, Nicolas Flammarion, Aurélien Garivier, and Aadil Oufkir. Quantum channel certification with incoherent measurements. In Proceedings of the 36th Conference on Learning Theory, pages 1822–1884, 2023. URL: https://proceedings.mlr.press/v195/fawzi23a.html.

[bib.bib14] [14] Minbo Gao, Zhengfeng Ji, Qisheng Wang, Wenjun Yu, and Qi Zhao. Quantum Hamiltonian certification. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1424–1467, 2026. doi:10.1137/1.9781611978971.53.

[bib.bib15] [15] Jeongwan Haah, Robin Kothari, Ryan O’Donnell, and Ewin Tang. Query-optimal estimation of unitary channels in diamond distance. In Proceedings of the IEEE 64th Annual Symposium on Foundations of Computer Science, pages 363–390. IEEE, 2023. doi:10.1109/FOCS57990.2023.00028.

[bib.bib16] [16] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16(10):1050–1057, 2020. doi:10.1038/s41567-020-0932-7.

[bib.bib17] [17] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Information-theoretic bounds on quantum advantage in machine learning. Physical Review Letters, 126(19):190505, 2021. doi:10.1103/PhysRevLett.126.190505.

[bib.bib18] [18] Sangwoo Jeon and Changhun Oh. On the query complexity of unitary channel certification. npj Quantum Information, 12:2, 2026. doi:10.1038/s41534-025-01135-5.

[bib.bib19] [19] Robin Kothari and Ryan O’Donnell. Mean estimation when you have the source code; or, quantum Monte Carlo methods. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1186–1215. SIAM, 2023. doi:10.1137/1.9781611977554.ch44.

[bib.bib20] [20] Dennis Kretschmann, Dirk Schlingemann, and Reinhard F. Werner. The information-disturbance tradeoff and the continuity of Stinespring’s representation. IEEE Transactions on Information Theory, 54(4):1708–1717, 2008. doi:10.1109/TIT.2008.917696.

[bib.bib21] [21] Junseo Lee and Myeongjin Shin. Optimal certification of constant-local Hamiltonians. ArXiv e-prints, 2025. doi:10.48550/arXiv.2512.09778.

[bib.bib22] [22] Antonio Anna Mele and Lennart Bittel. Optimal learning of quantum channels in diamond distance. ArXiv e-prints, 2025. doi:10.48550/arXiv.2512.10214.

[bib.bib23] [23] Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing. In Theory of Computing Library, number 7 in Graduate Surveys, pages 1–81. University of Chicago, 2016. doi:10.4086/toc.gs.2016.007.

[bib.bib24] [24] Michael A. Nielsen. A simple formula for the average gate fidelity of a quantum dynamical operation. Physics Letters A, 303(4):249–252, 2002. doi:10.1016/S0375-9601(02)01272-0.

[bib.bib25] [25] Ryan O’Donnell and John Wright. Quantum spectrum testing. Communications in Mathematical Physics, 387(1):1–75, 2021. doi:10.1007/s00220-021-04180-1.

[bib.bib26] [26] Aadil Oufkir. On Adaptivity in Classical and Quantum Learning. PhD thesis, Ecole normale supérieure de lyon-ENS LYON, 2023. URL: https://theses.hal.science/tel-04210763/.

[bib.bib27] [27] Aadil Oufkir. Sample-optimal quantum process tomography with non-adaptive incoherent measurements. In Proceedings of the 2023 IEEE International Symposium on Information Theory (ISIT), pages 1919–1924, June 2023. doi:10.1109/ISIT54713.2023.10206538.

[bib.bib28] [28] Maxim Raginsky. A fidelity measure for quantum channels. Physics Letters A, 290(1-2):11–18, 2001. doi:10.1016/S0375-9601(01)00640-5.

[bib.bib29] [29] Oded Regev and Liron Schiff. Impossibility of a quantum speed-up with a faulty oracle. In Proceedings of 35th International Colloquium on Automata, Languages and Programming, pages 773–781, 2008. doi:10.1007/978-3-540-70575-8_63.

[bib.bib30] [30] Gregory Rosenthal, Hugo Aaronson, Sathyawageeswar Subramanian, Animesh Datta, and Tom Gur. Quantum channel testing in average-case distance. ArXiv e-prints, 2024. doi:10.48550/arXiv.2409.12566.

[bib.bib31] [31] Trystan Surawy-Stepney, Jonas Kahn, Richard Kueng, and Madalin Guta. Projected least-squares quantum process tomography. Quantum, 6:844, 2022. doi:10.22331/q-2022-10-20-844.

[bib.bib32] [32] Ewin Tang and John Wright. Amplitude amplification and estimation require inverses. ArXiv e-prints, 2025. doi:10.48550/arXiv.2507.23787.

[bib.bib33] [33] Ewin Tang, John Wright, and Mark Zhandry. Conjugate queries can help. ArXiv e-prints, 2025. doi:10.48550/arXiv.2510.07622.

[bib.bib34] [34] Qisheng Wang. Optimal trace distance and fidelity estimations for pure quantum states. IEEE Transactions on Information Theory, 70(12):8791–8805, 2024. doi:10.1109/TIT.2024.3447915.

[bib.bib35] [35] John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. doi:10.1017/9781316848142.

[bib.bib36] [36] Satoshi Yoshida, Jisho Miyazaki, and Mio Murao. Quantum advantage in storage and retrieval of isometry channels. ArXiv e-prints, 2025. arXiv:2507.10784.

Strict Hierarchy for Quantum Channel Certification to Unitary

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Quantum channel certification to unitary

1.2 Access models and a strict complexity hierarchy

1.3 Main results

Theorem 1 (Informal, Theorems 3, 6, and 9 restated).

▶ Remark 2.

1.4 Techniques

1.4.1 Incoherent access

1.4.2 Coherent access

1.4.3 Source-code access

1.5 Discussion

1.6 Organization

2 Incoherent access

2.1 The algorithm

Theorem 3.

Proof.

2.2 Technical lemmas

Lemma 4.

Proof.

2.3 Lower bound

Lemma 5 ([13, Theorem 1]).

3 Coherent access

3.1 The algorithm

Theorem 6.

Proof.

The case 𝓔=𝓤.

The case ‖𝓔−𝓤‖⋄≥𝜺.

Complexity analysis.

3.2 Technical lemmas

Lemma 7.

Proof.

3.3 Lower bound

Lemma 8.

Proof.

4 Source-code access

4.1 The algorithm

Theorem 9.

Theorem 10 ([34, Theorem III.4]).

Proof of Theorem 9.

4.2 Lower bound

Lemma 11 ([18, Theorem 2]).

References

$\blacktriangleright$ Remark 2.

The case $\mathcal{E}=\mathcal{U}$ .

The case $\|\mathcal{E}-\mathcal{U}\|_{\diamond}\geq\varepsilon$ .