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:2609.38145

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

Entong He, Zihao Li, Yuxiang Yang

quant-phSubmitted Sep 29, 2026• Announced Sep 30, 2026• 1 citation
arXivHTMLPDF

Abstract

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.

AI Summary

The paper asks whether strictly parallel queries can match the optimal sequential query complexity for learning an unknown $d$-dimensional unitary channel in diamond distance. Parallel access permits entangled inputs and a collective final measurement, but no oracle output can influence another oracle input. Existing parallel bounds incurred additional dimension factors or worse accuracy dependence. It constructs a protocol using $O(d^2/\varepsilon)$ parallel queries that outputs a classical unitary-channel estimate within diamond distance $\varepsilon$ with probability at least $2/3$. Specifically, it uses at most $Q=d(L-d)\leq 8\pi d^2/\varepsilon$ queries, where $L=\lceil8\pi d/\varepsilon\rceil-1$. This matches the known information-theoretic lower bound and sequential upper bound. The construction uses covariant estimation and representation-theoretic probe weights derived from a Slater determinant of the lowest $d$ discrete sine modes. Global-phase invariance allows coherence between sectors with different query counts to be replaced by classical randomization. Rather than converting average infidelity into diamond distance, the analysis directly bounds eigenphase escape probabilities: the expected number outside a prescribed arc is $O(d^3/(L\varepsilon)^3)$, sufficient when $L=\Theta(d/\varepsilon)$. Applications give optimal $O(rd_1d_2/\varepsilon)$ channel tomography in the boundary regime $rd_2=d_1$, using a parallel-tester dilation theorem, and $O(n^2/\varepsilon)$ queries for $n$-mode fermionic linear-optics tomography. The guarantees concern query complexity with unrestricted probe preparation and collective measurements; gate complexity and implementation costs are not bounded. General channel tomography outside the boundary regime is not resolved.

Little sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
30 pages. Comments are welcome

Related papers

Near-Optimal Parallel Unitary Process Tomography in Diamond Distance

Noam Scully, Sisi Zhou

Unitary process tomography is the act of learning how an unknown unitary gate acts on a quantum system. It is an essential procedure for realizing a functioning quantum computer. As quantum technologies develop, it is important to understand the computational resources needed to conduct unitary process tomography using a variety of types of circuits. In particular, when measuring error in diamond distance, it is known how to achieve optimal query complexity using a sequential circuit architecture, but it had not been known whether a parallel circuit architecture could achieve the same optimal query complexity. In this work, we prove that unitary process tomography with near-optimal query complexity is indeed possible using a parallel circuit by introducing an explicit, novel parallel procedure. This closes the gap between sequential and parallel circuits up to a logarithmic factor, showing that parallel and sequential strategies are nearly equally capable for this task.

quant-pharXiv:2609.36127•Sep 30, 2026•1 citation

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•Nature Physics•Dec 12, 2025•36 citations

Quantum channel tomography: optimal bounds in the near-boundary regime

Kean Chen, Aadil Oufkir

Quantum channel tomography (also known as quantum process tomography) is a fundamental task in quantum information and quantum computing, aiming to learn the full description of an unknown quantum channel from black-box queries. For channels with input dimension $d_1$, output dimension $d_2$, and Kraus rank at most $r$, [CGO+26] identifies the dilation rate $τ=rd_2/d_1\geq 1$ as a key parameter governing a Heisenberg-to-classical transition in query complexity. While the optimal bounds in the boundary regime ($τ=1$) and the away-from-boundary regime ($τ\geq 1+Ω(1)$) are now known, the precise behavior in the near-boundary regime ($1<τ<1+o(1)$) has remained unresolved. In this paper, we close this gap, thereby fully settling the query complexity of quantum channel tomography. Specifically, we show that the query complexity is - $Ω(rd_1d_2/\varepsilon^2)$ for diamond norm error $\varepsilon$, matching the upper bound by [MB26, CGO+26], - $Θ(d_1^2/\varepsilon+\min\{(τ-1)d_1^2,(τ-1)^2d_1^2d_2^2\}/\varepsilon^2)$ for Choi trace norm error $\varepsilon$. Our results reveal two qualitatively different forms of the Heisenberg-to-classical transition. For diamond norm tomography, the Heisenberg scaling disappears suddenly as soon as $τ$ leaves the boundary regime. In contrast, Choi trace norm tomography exhibits a gradual transition from Heisenberg to classical scaling as $τ$ moves from the boundary regime to the away-from-boundary regime.

quant-pharXiv:2611.03639•Nov 3, 2026•0 citations

Query-optimal estimation of unitary channels in diamond distance

Jeongwan Haah, Robin Kothari, Ryan O’Donnell +1 more

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.

arXiv:2302.14066•Annual Symposium on Foundations of Computer Science•Nov 6, 2023•79 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 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•9 citations
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 paper asks whether strictly parallel queries can match the optimal sequential query complexity for learning an unknown ddd-dimensional unitary channel in diamond distance. Parallel access permits entangled inputs and a collective final measurement, but no oracle output can influence another oracle input. Existing parallel bounds incurred additional dimension factors or worse accuracy dependence.
It constructs a protocol using O(d2/ε)O(d^2/\varepsilon)O(d2/ε) parallel queries that outputs a classical unitary-channel estimate within diamond distance ε\varepsilonε with probability at least 2/32/32/3. Specifically, it uses at most Q=d(L−d)≤8πd2/εQ=d(L-d)\leq 8\pi d^2/\varepsilonQ=d(L−d)≤8πd2/ε queries, where L=⌈8πd/ε⌉−1L=\lceil8\pi d/\varepsilon\rceil-1L=⌈8πd/ε⌉−1. This matches the known information-theoretic lower bound and sequential upper bound.
The construction uses covariant estimation and representation-theoretic probe weights derived from a Slater determinant of the lowest ddd discrete sine modes. Global-phase invariance allows coherence between sectors with different query counts to be replaced by classical randomization. Rather than converting average infidelity into diamond distance, the analysis directly bounds eigenphase escape probabilities: the expected number outside a prescribed arc is O(d3/(Lε)3)O(d^3/(L\varepsilon)^3)O(d3/(Lε)3), sufficient when L=Θ(d/ε)L=\Theta(d/\varepsilon)L=Θ(d/ε).
Applications give optimal O(rd1d2/ε)O(rd_1d_2/\varepsilon)O(rd1​d2​/ε) channel tomography in the boundary regime rd2=d1rd_2=d_1rd2​=d1​, using a parallel-tester dilation theorem, and O(n2/ε)O(n^2/\varepsilon)O(n2/ε) queries for nnn-mode fermionic linear-optics tomography. The guarantees concern query complexity with unrestricted probe preparation and collective measurements; gate complexity and implementation costs are not bounded. General channel tomography outside the boundary regime is not resolved.
Unitary process tomography is the act of learning how an unknown unitary gate acts on a quantum system. It is an essential procedure for realizing a functioning quantum computer. As quantum technologies develop, it is important to understand the computational resources needed to conduct unitary process tomography using a variety of types of circuits. In particular, when measuring error in diamond distance, it is known how to achieve optimal query complexity using a sequential circuit architecture, but it had not been known whether a parallel circuit architecture could achieve the same optimal query complexity. In this work, we prove that unitary process tomography with near-optimal query complexity is indeed possible using a parallel circuit by introducing an explicit, novel parallel procedure. This closes the gap between sequential and parallel circuits up to a logarithmic factor, showing that parallel and sequential strategies are nearly equally capable for this task.
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.
Quantum channel tomography (also known as quantum process tomography) is a fundamental task in quantum information and quantum computing, aiming to learn the full description of an unknown quantum channel from black-box queries. For channels with input dimension d1d_1d1​, output dimension d2d_2d2​, and Kraus rank at most rrr, [CGO+26] identifies the dilation rate τ=rd2/d1≥1τ=rd_2/d_1\geq 1τ=rd2​/d1​≥1 as a key parameter governing a Heisenberg-to-classical transition in query complexity. While the optimal bounds in the boundary regime (τ=1τ=1τ=1) and the away-from-boundary regime (τ≥1+Ω(1)τ\geq 1+Ω(1)τ≥1+Ω(1)) are now known, the precise behavior in the near-boundary regime (1<τ<1+o(1)1<τ<1+o(1)1<τ<1+o(1)) has remained unresolved. In this paper, we close this gap, thereby fully settling the query complexity of quantum channel tomography. Specifically, we show that the query complexity is - Ω(rd1d2/ε2)Ω(rd_1d_2/\varepsilon^2)Ω(rd1​d2​/ε2) for diamond norm error ε\varepsilonε, matching the upper bound by [MB26, CGO+26], - Θ(d12/ε+min⁡{(τ−1)d12,(τ−1)2d12d22}/ε2)Θ(d_1^2/\varepsilon+\min\{(τ-1)d_1^2,(τ-1)^2d_1^2d_2^2\}/\varepsilon^2)Θ(d12​/ε+min{(τ−1)d12​,(τ−1)2d12​d22​}/ε2) for Choi trace norm error ε\varepsilonε. Our results reveal two qualitatively different forms of the Heisenberg-to-classical transition. For diamond norm tomography, the Heisenberg scaling disappears suddenly as soon as τττ leaves the boundary regime. In contrast, Choi trace norm tomography exhibits a gradual transition from Heisenberg to classical scaling as τττ moves from the boundary regime to the away-from-boundary regime.
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.
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).
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.