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:2302.14066 · Annual Symposium on Foundations of Computer Science

Query-optimal estimation of unitary channels in diamond distance

Jeongwan Haah, Robin Kothari, Ryan O’Donnell, Ewin Tang

Published Nov 6, 2023• 23 citations
arXivHTMLPDF

Abstract

We consider process tomography for unitary quantum channels. Given access to an unknown unitary channel acting on a d-dimensional qudit, we aim to output a classical description of a unitary that is $\varepsilon$-close to the unknown unitary in diamond norm. We design an algorithm achieving error $\varepsilon$ using $O\left(\mathrm{~d}^{2} / \varepsilon\right)$ applications of the unknown channel and only one qudit. This improves over prior results, which use $O\left(\mathrm{~d}^{3} / \varepsilon^{2}\right)$ [via standard process tomography] or $O\left(\mathrm{~d}^{2.5} / \varepsilon\right)$ [Yang, Renner, and Chiribella, PRL 2020] applications. To show this result, we introduce a simple technique to “bootstrap” an algorithm that can produce constant-error estimates to one that can produce $\varepsilon$-error estimates with the Heisenberg scaling. Finally, we prove a complementary lower bound showing that estimation requires $\Omega\left(\mathrm{d}^{2} / \varepsilon\right)$ applications, even with access to the inverse or controlled versions of the unknown unitary. This shows that our algorithm has both optimal query complexity and optimal space complexity.

DOI
10.1109/focs57990.2023.00028

Related papers

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

Entong He, Zihao Li, Yuxiang Yang

In the study of quantum process tomography, it has remained open how to learn a unitary channel in diamond distance with strictly parallel queries as efficiently as with sequential queries. Sequential queries allow one to exploit adaptivity to refine the estimate and adjust the learning strategy accordingly, whereas such adjustments are impossible for parallel queries. From the perspective of higher-order quantum operations, any parallel learning strategy can be simulated by a sequential one, whereas the converse does not hold in general, suggesting that sequential learning strategies are potentially more powerful. Contrary to this intuition, we present a new protocol for learning an unknown $d$-dimensional unitary channel to within $\varepsilon$ in diamond distance using $\mathcal{O}(d^2/\varepsilon)$ parallel queries, matching the lower bound presented in [Haah, Kothari, O'Donnell, and Tang, FOCS '23]. Our protocol thus closes the gap between parallel and sequential strategies for unitary channel tomography. As applications, it achieves optimal query complexity for boundary-regime quantum channel tomography and improves the query efficiency of the best-known protocol for tomography of fermionic linear optics.

quant-pharXiv:2609.38145•Sep 30, 2026•0 citations

Optimal Diamond Distance Estimation for Unitary Channels

Jinge Bao, Qisheng Wang

The diamond distance between two quantum channels determines the optimal probability of distinguishing them from a single use. We give a quantum algorithm that estimates the diamond distance between two unknown $d$-dimensional unitary channels to within additive error $\varepsilon$, using $O(\sqrt{d}/\varepsilon)$ queries to the unitary channels and their inverses. The query complexity is optimal, as it matches the lower bound due to Jeon and Oh (npj Quantum Inf. 2026).

quant-pharXiv:2610.40623•Oct 30, 2026•0 citations

Optimal 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

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

Optimal classical shadow estimation of unitary channels at Heisenberg limit

Entong He, Zihao Li, Noam Scully +2 more

Full tomography of an unknown quantum evolution is resource-intensive and often unnecessary when the goal is only to predict selected properties. This motivates the study of classical shadow estimation of unitary channels (CSEU), a task in which one queries an unknown $d$-dimensional unitary $U$ and stores classical data that can later be used to predict expectation values $\mathrm{tr}[O UρU^\dagger]$ for arbitrary input states $ρ$ and observables $O$. Here we propose a parallel and non-adaptive CSEU protocol that uses $\mathcal{O}(\min\{d\varepsilon^{-2},d^{3/2}\varepsilon^{-1}\})$ queries to $U$ when the observables have constant effective size. This achieves Heisenberg scaling with respect to the additive error $\varepsilon$ and is query-optimal, as we prove a matching lower bound $Ω(\min\{d\varepsilon^{-2},d^{3/2}\varepsilon^{-1}\})$ for the query complexity, which remains valid even when stronger access to the unknown unitary is available. Our CSEU protocol is a versatile primitive with applications to several quantum learning tasks. In particular, it yields a near-optimal algorithm for learning an arbitrary Hamiltonian from its real-time evolution in the high-precision regime and recovers the best-known bounds for several tasks in a unified way.

quant-pharXiv:2606.13638•Jun 12, 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 consider process tomography for unitary quantum channels. Given access to an unknown unitary channel acting on a d-dimensional qudit, we aim to output a classical description of a unitary that is ε\varepsilonε-close to the unknown unitary in diamond norm. We design an algorithm achieving error ε\varepsilonε using O( d2/ε)O\left(\mathrm{~d}^{2} / \varepsilon\right)O( d2/ε) applications of the unknown channel and only one qudit. This improves over prior results, which use O( d3/ε2)O\left(\mathrm{~d}^{3} / \varepsilon^{2}\right)O( d3/ε2) [via standard process tomography] or O( d2.5/ε)O\left(\mathrm{~d}^{2.5} / \varepsilon\right)O( d2.5/ε) [Yang, Renner, and Chiribella, PRL 2020] applications. To show this result, we introduce a simple technique to “bootstrap” an algorithm that can produce constant-error estimates to one that can produce ε\varepsilonε-error estimates with the Heisenberg scaling. Finally, we prove a complementary lower bound showing that estimation requires Ω(d2/ε)\Omega\left(\mathrm{d}^{2} / \varepsilon\right)Ω(d2/ε) applications, even with access to the inverse or controlled versions of the unknown unitary. This shows that our algorithm has both optimal query complexity and optimal space complexity.
In the study of quantum process tomography, it has remained open how to learn a unitary channel in diamond distance with strictly parallel queries as efficiently as with sequential queries. Sequential queries allow one to exploit adaptivity to refine the estimate and adjust the learning strategy accordingly, whereas such adjustments are impossible for parallel queries. From the perspective of higher-order quantum operations, any parallel learning strategy can be simulated by a sequential one, whereas the converse does not hold in general, suggesting that sequential learning strategies are potentially more powerful. Contrary to this intuition, we present a new protocol for learning an unknown ddd-dimensional unitary channel to within ε\varepsilonε in diamond distance using O(d2/ε)\mathcal{O}(d^2/\varepsilon)O(d2/ε) parallel queries, matching the lower bound presented in [Haah, Kothari, O'Donnell, and Tang, FOCS '23]. Our protocol thus closes the gap between parallel and sequential strategies for unitary channel tomography. As applications, it achieves optimal query complexity for boundary-regime quantum channel tomography and improves the query efficiency of the best-known protocol for tomography of fermionic linear optics.
The diamond distance between two quantum channels determines the optimal probability of distinguishing them from a single use. We give a quantum algorithm that estimates the diamond distance between two unknown ddd-dimensional unitary channels to within additive error ε\varepsilonε, using O(d/ε)O(\sqrt{d}/\varepsilon)O(d​/ε) queries to the unitary channels and their inverses. The query complexity is optimal, as it matches the lower bound due to Jeon and Oh (npj Quantum Inf. 2026).
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 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ε.
Full tomography of an unknown quantum evolution is resource-intensive and often unnecessary when the goal is only to predict selected properties. This motivates the study of classical shadow estimation of unitary channels (CSEU), a task in which one queries an unknown ddd-dimensional unitary UUU and stores classical data that can later be used to predict expectation values tr[OUρU†]\mathrm{tr}[O UρU^\dagger]tr[OUρU†] for arbitrary input states ρρρ and observables OOO. Here we propose a parallel and non-adaptive CSEU protocol that uses O(min⁡{dε−2,d3/2ε−1})\mathcal{O}(\min\{d\varepsilon^{-2},d^{3/2}\varepsilon^{-1}\})O(min{dε−2,d3/2ε−1}) queries to UUU when the observables have constant effective size. This achieves Heisenberg scaling with respect to the additive error ε\varepsilonε and is query-optimal, as we prove a matching lower bound Ω(min⁡{dε−2,d3/2ε−1})Ω(\min\{d\varepsilon^{-2},d^{3/2}\varepsilon^{-1}\})Ω(min{dε−2,d3/2ε−1}) for the query complexity, which remains valid even when stronger access to the unknown unitary is available. Our CSEU protocol is a versatile primitive with applications to several quantum learning tasks. In particular, it yields a near-optimal algorithm for learning an arbitrary Hamiltonian from its real-time evolution in the high-precision regime and recovers the best-known bounds for several tasks in a unified way.
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.