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

Quantum memory advantage for quantum process tomography

Carlos Bravo-Prieto, Weiyuan Gong, Antonio Anna Mele

quant-phcs.DSmath-phSubmitted Jul 15, 2026• Announced Jul 16, 2026• 7 citations
arXivHTMLPDF

Abstract

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

Comments
11 + 15 pages, 1 figure

Related papers

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

Near-optimal incoherent tomography of low-rank quantum channels

Kean Chen, Aadil Oufkir

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

quant-pharXiv:2609.23752•Sep 22, 2026•1 citation

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•10 citations

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•1 citation

Sample-Optimal Quantum Process Tomography with non-adaptive Incoherent Measurements

Aadil Oufkir

How many copies of a quantum process are necessary and sufficient to construct an approximate classical description of it? We extend the result of Surawy-Stepney, Kahn, Kueng, and Guta (2022) to show that ${\tilde {\mathcal{O}}}\left( {{d^6}/{\varepsilon ^2}} \right)$ copies are sufficient to learn a d-dimensional quantum channel to within ε in the diamond norm. Moreover, we show that Ω(d6/ε2) copies are necessary for any strategy using incoherent non-adaptive measurements. This lower bound applies even for ancilla-assisted strategies.

arXiv:2301.12925•IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2023•13 citations
Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be Θ(din3dout3/ε2)Θ(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)Θ(din3​dout3​/ε2), where dind_{\mathrm{in}}din​ and doutd_{\mathrm{out}}dout​ are the channel input and output dimensions, respectively, and ε\varepsilonε is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires Ω(din3dout3/ε2)Ω(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)Ω(din3​dout3​/ε2) queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound O(din3dout3/ε2)O(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)O(din3​dout3​/ε2). Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case din=1d_{\mathrm{in}}=1din​=1. By contrast, coherent protocols with quantum memory achieve query complexity Θ(din2dout2/ε2)Θ(d_{\mathrm{in}}^2 d_{\mathrm{out}}^2/\varepsilon^2)Θ(din2​dout2​/ε2). Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.
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 study tomography for quantum channels with input dimension d1d_1d1​, output dimension d2d_2d2​, and Kraus rank at most rrr, to within diamond norm error ε\varepsilonε, using adaptive experiments that retain no quantum memory between channel queries. - For quantum channels whose non-zero Choi eigenvalues are bounded below by Ω(d1/r)Ω(d_1/r)Ω(d1​/r), we establish optimal query upper and lower bounds Θ(d1d2r2/ε2)Θ(d_1d_2r^2/ε^2)Θ(d1​d2​r2/ε2). The upper bound is achieved by a nonadaptive algorithm that uses the estimator from [Surawy-Stepney et al., Quantum (2022)], together with a new diamond-norm analysis. The lower bound applies to arbitrary adaptive incoherent protocols and follows from a new local family of channels and a uniform one-query Fisher-information bound. - For general channels, we establish an upper bound O(d1d2r2log⁡(2d1)/ε2)O(d_1d_2r^2\log(2d_1)/ε^2)O(d1​d2​r2log(2d1​)/ε2), nearly matching the above lower bound Ω(d1d2r2/ε2)Ω(d_1d_2r^2/\varepsilon^2)Ω(d1​d2​r2/ε2). To achieve this, we generalize the above nonadaptive algorithm by adapting the input state over O(log⁡(2d1))O(\log(2d_1))O(log(2d1​)) rounds with the Matrix Multiplicative Weight Update algorithm.
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.
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.
How many copies of a quantum process are necessary and sufficient to construct an approximate classical description of it? We extend the result of Surawy-Stepney, Kahn, Kueng, and Guta (2022) to show that O~(d6/ε2){\tilde {\mathcal{O}}}\left( {{d^6}/{\varepsilon ^2}} \right)O~(d6/ε2) copies are sufficient to learn a d-dimensional quantum channel to within ε in the diamond norm. Moreover, we show that Ω(d6/ε2) copies are necessary for any strategy using incoherent non-adaptive measurements. This lower bound applies even for ancilla-assisted strategies.