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

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2409.12566

Quantum Channel Testing in Average-Case Distance

Rosenthal, Gregory, Hugo Aaronson, Sathyawageeswar Subramanian, Animesh Datta, Tom Gur

Published Sep 19, 2024• 2 citations
arXivHTMLPDF

Abstract

We study the complexity of testing properties of quantum channels. First, we show that testing identity to any channel $\mathcal N: \mathbb C^{d_{\mathrm{in}} \times d_{\mathrm{in}}} \to \mathbb C^{d_{\mathrm{out}} \times d_{\mathrm{out}}}$ in diamond norm distance requires $Ω(\sqrt{d_{\mathrm{in}}} / \varepsilon)$ queries, even in the strongest algorithmic model that admits ancillae, coherence, and adaptivity. This is due to the worst-case nature of the distance induced by the diamond norm. Motivated by this limitation and other theoretical and practical applications, we introduce an average-case analogue of the diamond norm, which we call the average-case imitation diamond (ACID) norm. In the weakest algorithmic model without ancillae, coherence, or adaptivity, we prove that testing identity to certain types of channels in ACID distance can be done with complexity independent of the dimensions of the channel, while for other types of channels the complexity depends on both the input and output dimensions. Building on previous work, we also show that identity to any fixed channel can be tested with $\tilde O(d_{\mathrm{in}} d_{\mathrm{out}}^{3/2} / \varepsilon^2)$ queries in ACID distance and $\tilde O(d_{\mathrm{in}}^2 d_{\mathrm{out}}^{3/2} / \varepsilon^2)$ queries in diamond distance in this model. Finally, we prove tight bounds on the complexity of channel tomography in ACID distance.

DOI
10.48550/arxiv.2409.12566

Related papers

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

quant-pharXiv:2512.13614•Dec 16, 2025•0 citations

On the query complexity of unitary channel certification

Sangwoo Jeon, Changhun Oh

Certifying the correct functioning of a unitary channel is a critical step toward reliable quantum information processing. In this work, we investigate the query complexity of the unitary channel certification task: testing whether a given d -dimensional unitary channel is identical to or ε -far in diamond distance from a target unitary operation. We show that incoherent algorithms—those without quantum memory—require Ω( d / ε 2 ) queries, matching the known upper bound. In addition, for general quantum algorithms, we prove a lower bound of \(\Omega (\sqrt{d}/\varepsilon )\) and present a matching quantum algorithm based on quantum singular value transformation, establishing a tight query complexity of \(\Theta (\sqrt{d}/\varepsilon )\) . On the other hand, notably, we prove that for almost all unitary channels drawn from a natural average-case ensemble, certification can be accomplished with only \({\mathcal{O}}(1/{\varepsilon }^{2})\) queries. This demonstrates an exponential query complexity gap between worst- and average-case scenarios in certification, implying that certification is significantly easier for most unitary channels encountered in practice. Together, our results offer both theoretical insights and practical tools for verifying quantum processes.

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

Improved Lower Bounds for Learning Quantum Channels in Diamond Distance

Aadil Oufkir, Filippo Girardi

We prove that learning an unknown quantum channel with input dimension $d_A$, output dimension $d_B$, and Choi rank $r$ to diamond distance $\varepsilon$ requires $ Ω\!\left( \frac{d_A d_B r}{\varepsilon \log(d_B r / \varepsilon)} \right)$ channel queries when $d_A= rd_B$, and $Ω\!\left( \frac{d_A d_B r}{\varepsilon^2 \log(d_B r / \varepsilon)} \right)$ channel queries when $d_A\le rd_B/2$. These lower bounds improve upon the best previous $Ω(d_A d_B r)$ bound by introducing explicit, near-optimal $\varepsilon$-dependence. Moreover, when $d_A\le rd_B/2$, the lower bound is optimal up to a logarithmic factor. The proof constructs ensembles of channels that are well separated in diamond norm yet admit Stinespring isometries that are close in operator norm.

quant-pharXiv:2601.04180•Jan 8, 2026•0 citations

Optimal learning of quantum channels in diamond distance

Antonio Anna Mele, Lennart Bittel

Quantum process tomography, the task of estimating an unknown quantum channel, is a central problem in quantum information theory. A long-standing open question is how many uses of an unknown channel are required to learn it in diamond distance, the standard metric for distinguishing quantum processes. While quantum state tomography is well understood, for general channels the problem remained open beyond the unitary case. Here we establish the query complexity of channel tomography with optimal dependence on the dimension parameters, at any fixed constant accuracy. We design an algorithm showing that any channel with input/output dimensions $d_{\mathrm{in}},d_{\mathrm{out}}$ and Kraus rank at most $k$ can be learned to accuracy $\varepsilon$ using $O(d_{\mathrm{in}}d_{\mathrm{out}}k/\varepsilon^{2})$ channel uses. Conversely, we prove that $Ω(d_{\mathrm{in}}d_{\mathrm{out}}k)$ uses are necessary at constant accuracy and that, for non-minimal Kraus rank, a separate $Ω(1/\varepsilon^{2})$ contribution is unavoidable. Since channels subsume states, unitaries, isometries, and measurements as special cases, our protocol provides a unified framework for these tomography tasks, yielding new guarantees for isometry and measurement tomography while recovering known optimal scalings for state and unitary tomography. Our algorithm follows the natural strategy of performing optimal tomography on the Choi state. The main technical contribution is to show that this suffices to control the induced diamond-distance error, avoiding the dimension loss incurred by a naive conversion from Choi-state trace distance to channel diamond distance. The protocol uses the channel non-adaptively to prepare Choi-state copies, purifies them in parallel, and performs optimal pure-state tomography on the resulting purifications. Hence, we reduce channel tomography to pure-state tomography.

quant-pharXiv:2512.10214•Dec 12, 2025•0 citations

Unitary Channel Testing Under a Depolarizing Noise Assumption

Hirak Ghosh, Andrew Jackson, Animesh Datta

We present fast algorithms $\unicode{x2013}$ under the depolarizing noise assumption, often made in fault-tolerant quantum computations $\unicode{x2013}$ to test its strength. Our optimal algorithms answer the following question: is the quantum channel implemented by a given black box identical to a target unitary or $\varepsilon$-far from it in the diamond distance, assuming that the deviation is a depolarizing channel with unknown parameter? Our algorithm has a query complexity of $Θ(1/\varepsilon).$ The query complexity of the relaxed problem of testing whether the black-box channel is $\varepsilon_1$-close to a target unitary or $\varepsilon_2$-far in the diamond distance is $Θ\bigl(\varepsilon_2/(\varepsilon_2 - \varepsilon_1)^2\bigr).$ In both cases, we provide matching lower bounds that hold even for adaptive, ancilla-assisted protocols with multi-outcome incoherent measurements.

quant-pharXiv:2606.10730•Jun 10, 2026•0 citations

Quantum channel tomography: optimal bounds and a Heisenberg-to-classical phase transition

Kean Chen, Filippo Girardi, Aadil Oufkir +2 more

How many black-box queries to a quantum channel are needed to learn its full classical description? This question lies at the heart of quantum channel tomography (also known as quantum process tomography), a fundamental task in the characterization and validation of quantum hardware. Despite extensive prior work, the optimal query complexity for quantum channel tomography is far from fully understood. In this paper, we study tomography of an unknown quantum channel with input dimension $d_1$, output dimension $d_2$, and Kraus rank at most $r$, to within error $\varepsilon$. We identify the dilation rate $τ= r d_2 / d_1$ (which always satisfies $τ\geq 1$ due to the trace preservation of quantum channels) as a key parameter, and establish that the optimal query complexity of channel tomography exhibits distinct scaling laws across three regimes of $τ$. - In the boundary regime ($τ= 1$): we show that the query complexity is $Θ(r d_1 d_2/\varepsilon)$ for Choi trace norm error $\varepsilon$, and is upper bounded by $O(\min\{r d_1^{1.5} d_2/\varepsilon, r d_1 d_2/\varepsilon^2\})$ and lower bounded by $Ω(r d_1 d_2/\varepsilon)$ for diamond norm error $\varepsilon$. - In the away-from-boundary regime ($τ\geq 1+Ω(1)$): we show that the query complexity is $Θ(r d_1 d_2/\varepsilon^2)$ for both Choi trace norm and diamond norm errors $\varepsilon$. Our results uncover a sharp Heisenberg-to-classical phase transition in the query complexity of quantum channel tomography: at $τ=1$, the optimal query complexity exhibits Heisenberg scaling $1/\varepsilon$, whereas for $τ\geq 1+Ω(1)$, it exhibits classical scaling $1/\varepsilon^2$. In addition, we show that in the near-boundary regime ($1< τ< 1+o(1)$), the query complexity exhibits a mixture of Heisenberg and classical scaling behaviors.

quant-pharXiv:2604.17369•Apr 21, 2026•0 citations
We study the complexity of testing properties of quantum channels. First, we show that testing identity to any channel N:Cdin×din→Cdout×dout\mathcal N: \mathbb C^{d_{\mathrm{in}} \times d_{\mathrm{in}}} \to \mathbb C^{d_{\mathrm{out}} \times d_{\mathrm{out}}}N:Cdin​×din​→Cdout​×dout​ in diamond norm distance requires Ω(din/ε)Ω(\sqrt{d_{\mathrm{in}}} / \varepsilon)Ω(din​​/ε) queries, even in the strongest algorithmic model that admits ancillae, coherence, and adaptivity. This is due to the worst-case nature of the distance induced by the diamond norm. Motivated by this limitation and other theoretical and practical applications, we introduce an average-case analogue of the diamond norm, which we call the average-case imitation diamond (ACID) norm. In the weakest algorithmic model without ancillae, coherence, or adaptivity, we prove that testing identity to certain types of channels in ACID distance can be done with complexity independent of the dimensions of the channel, while for other types of channels the complexity depends on both the input and output dimensions. Building on previous work, we also show that identity to any fixed channel can be tested with O~(dindout3/2/ε2)\tilde O(d_{\mathrm{in}} d_{\mathrm{out}}^{3/2} / \varepsilon^2)O~(din​dout3/2​/ε2) queries in ACID distance and O~(din2dout3/2/ε2)\tilde O(d_{\mathrm{in}}^2 d_{\mathrm{out}}^{3/2} / \varepsilon^2)O~(din2​dout3/2​/ε2) queries in diamond distance in this model. Finally, we prove tight bounds on the complexity of channel tomography in ACID distance.
We study the estimation of an unknown quantum channel E\mathcal{E}E with input dimension d1d_1d1​, output dimension d2d_2d2​ and Kraus rank at most rrr. We establish a connection between the query complexities in two models: (i) access to E\mathcal{E}E, and (ii) access to a random dilation of E\mathcal{E}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 nnn queries to E\mathcal{E}E yet faithfully simulates the tester with nnn queries to a random dilation. As application, we show that: - O(rd1d2/ε2)O(rd_1d_2/\varepsilon^2)O(rd1​d2​/ε2) queries to E\mathcal{E}E suffice for channel tomography to within diamond norm error ε\varepsilonε. Moreover, when rd2=d1rd_2=d_1rd2​=d1​, we show that the Heisenberg scaling O(1/ε)O(1/\varepsilon)O(1/ε) can be achieved, even if E\mathcal{E}E is not a unitary channel: - O(min⁡{d12.5/ε,d12/ε2})O(\min\{d_1^{2.5}/\varepsilon,d_1^2/\varepsilon^2\})O(min{d12.5​/ε,d12​/ε2}) queries to E\mathcal{E}E suffice for channel tomography to within diamond norm error ε\varepsilonε, and O(d12/ε)O(d_1^2/\varepsilon)O(d12​/ε) queries suffice for the case of Choi state trace norm error ε\varepsilonε. - O(min⁡{d11.5/ε,d1/ε2})O(\min\{d_1^{1.5}/\varepsilon,d_1/\varepsilon^2\})O(min{d11.5​/ε,d1​/ε2}) queries to E\mathcal{E}E suffice for tomography of the mixed state E(∣0⟩⟨0∣)\mathcal{E}(|0\rangle\langle 0|)E(∣0⟩⟨0∣) to within trace norm error ε\varepsilonε.
Certifying the correct functioning of a unitary channel is a critical step toward reliable quantum information processing. In this work, we investigate the query complexity of the unitary channel certification task: testing whether a given d -dimensional unitary channel is identical to or ε -far in diamond distance from a target unitary operation. We show that incoherent algorithms—those without quantum memory—require Ω( d / ε 2 ) queries, matching the known upper bound. In addition, for general quantum algorithms, we prove a lower bound of Ω(d/ε)\Omega (\sqrt{d}/\varepsilon )Ω(d​/ε) and present a matching quantum algorithm based on quantum singular value transformation, establishing a tight query complexity of Θ(d/ε)\Theta (\sqrt{d}/\varepsilon )Θ(d​/ε) . On the other hand, notably, we prove that for almost all unitary channels drawn from a natural average-case ensemble, certification can be accomplished with only O(1/ε2){\mathcal{O}}(1/{\varepsilon }^{2})O(1/ε2) queries. This demonstrates an exponential query complexity gap between worst- and average-case scenarios in certification, implying that certification is significantly easier for most unitary channels encountered in practice. Together, our results offer both theoretical insights and practical tools for verifying quantum processes.
We prove that learning an unknown quantum channel with input dimension dAd_AdA​, output dimension dBd_BdB​, and Choi rank rrr to diamond distance ε\varepsilonε requires $ Ω\!\left( \frac{d_A d_B r}{\varepsilon \log(d_B r / \varepsilon)} \right)$ channel queries when dA=rdBd_A= rd_BdA​=rdB​, and Ω ⁣(dAdBrε2log⁡(dBr/ε))Ω\!\left( \frac{d_A d_B r}{\varepsilon^2 \log(d_B r / \varepsilon)} \right)Ω(ε2log(dB​r/ε)dA​dB​r​) channel queries when dA≤rdB/2d_A\le rd_B/2dA​≤rdB​/2. These lower bounds improve upon the best previous Ω(dAdBr)Ω(d_A d_B r)Ω(dA​dB​r) bound by introducing explicit, near-optimal ε\varepsilonε-dependence. Moreover, when dA≤rdB/2d_A\le rd_B/2dA​≤rdB​/2, the lower bound is optimal up to a logarithmic factor. The proof constructs ensembles of channels that are well separated in diamond norm yet admit Stinespring isometries that are close in operator norm.
Quantum process tomography, the task of estimating an unknown quantum channel, is a central problem in quantum information theory. A long-standing open question is how many uses of an unknown channel are required to learn it in diamond distance, the standard metric for distinguishing quantum processes. While quantum state tomography is well understood, for general channels the problem remained open beyond the unitary case. Here we establish the query complexity of channel tomography with optimal dependence on the dimension parameters, at any fixed constant accuracy. We design an algorithm showing that any channel with input/output dimensions din,doutd_{\mathrm{in}},d_{\mathrm{out}}din​,dout​ and Kraus rank at most kkk can be learned to accuracy ε\varepsilonε using O(dindoutk/ε2)O(d_{\mathrm{in}}d_{\mathrm{out}}k/\varepsilon^{2})O(din​dout​k/ε2) channel uses. Conversely, we prove that Ω(dindoutk)Ω(d_{\mathrm{in}}d_{\mathrm{out}}k)Ω(din​dout​k) uses are necessary at constant accuracy and that, for non-minimal Kraus rank, a separate Ω(1/ε2)Ω(1/\varepsilon^{2})Ω(1/ε2) contribution is unavoidable. Since channels subsume states, unitaries, isometries, and measurements as special cases, our protocol provides a unified framework for these tomography tasks, yielding new guarantees for isometry and measurement tomography while recovering known optimal scalings for state and unitary tomography. Our algorithm follows the natural strategy of performing optimal tomography on the Choi state. The main technical contribution is to show that this suffices to control the induced diamond-distance error, avoiding the dimension loss incurred by a naive conversion from Choi-state trace distance to channel diamond distance. The protocol uses the channel non-adaptively to prepare Choi-state copies, purifies them in parallel, and performs optimal pure-state tomography on the resulting purifications. Hence, we reduce channel tomography to pure-state tomography.
We present fast algorithms $\unicode{x2013}$ under the depolarizing noise assumption, often made in fault-tolerant quantum computations $\unicode{x2013}$ to test its strength. Our optimal algorithms answer the following question: is the quantum channel implemented by a given black box identical to a target unitary or ε\varepsilonε-far from it in the diamond distance, assuming that the deviation is a depolarizing channel with unknown parameter? Our algorithm has a query complexity of Θ(1/ε).Θ(1/\varepsilon).Θ(1/ε). The query complexity of the relaxed problem of testing whether the black-box channel is ε1\varepsilon_1ε1​-close to a target unitary or ε2\varepsilon_2ε2​-far in the diamond distance is Θ(ε2/(ε2−ε1)2).Θ\bigl(\varepsilon_2/(\varepsilon_2 - \varepsilon_1)^2\bigr).Θ(ε2​/(ε2​−ε1​)2). In both cases, we provide matching lower bounds that hold even for adaptive, ancilla-assisted protocols with multi-outcome incoherent measurements.
How many black-box queries to a quantum channel are needed to learn its full classical description? This question lies at the heart of quantum channel tomography (also known as quantum process tomography), a fundamental task in the characterization and validation of quantum hardware. Despite extensive prior work, the optimal query complexity for quantum channel tomography is far from fully understood. In this paper, we study tomography of an unknown quantum channel with input dimension d1d_1d1​, output dimension d2d_2d2​, and Kraus rank at most rrr, to within error ε\varepsilonε. We identify the dilation rate τ=rd2/d1τ= r d_2 / d_1τ=rd2​/d1​ (which always satisfies τ≥1τ\geq 1τ≥1 due to the trace preservation of quantum channels) as a key parameter, and establish that the optimal query complexity of channel tomography exhibits distinct scaling laws across three regimes of τττ. - In the boundary regime (τ=1τ= 1τ=1): we show that the query complexity is Θ(rd1d2/ε)Θ(r d_1 d_2/\varepsilon)Θ(rd1​d2​/ε) for Choi trace norm error ε\varepsilonε, and is upper bounded by O(min⁡{rd11.5d2/ε,rd1d2/ε2})O(\min\{r d_1^{1.5} d_2/\varepsilon, r d_1 d_2/\varepsilon^2\})O(min{rd11.5​d2​/ε,rd1​d2​/ε2}) and lower bounded by Ω(rd1d2/ε)Ω(r d_1 d_2/\varepsilon)Ω(rd1​d2​/ε) for diamond norm error ε\varepsilonε. - In the away-from-boundary regime (τ≥1+Ω(1)τ\geq 1+Ω(1)τ≥1+Ω(1)): we show that the query complexity is Θ(rd1d2/ε2)Θ(r d_1 d_2/\varepsilon^2)Θ(rd1​d2​/ε2) for both Choi trace norm and diamond norm errors ε\varepsilonε. Our results uncover a sharp Heisenberg-to-classical phase transition in the query complexity of quantum channel tomography: at τ=1τ=1τ=1, the optimal query complexity exhibits Heisenberg scaling 1/ε1/\varepsilon1/ε, whereas for τ≥1+Ω(1)τ\geq 1+Ω(1)τ≥1+Ω(1), it exhibits classical scaling 1/ε21/\varepsilon^21/ε2. In addition, we show that in the near-boundary regime (1<τ<1+o(1)1< τ< 1+o(1)1<τ<1+o(1)), the query complexity exhibits a mixture of Heisenberg and classical scaling behaviors.