arXiv:2507.05736 · ACM Symposium on Theory of Computing (STOC)

Approximation Does Not Help in Quantum Unitary Time-Reversal

Kean Chen, Nengkun Yu, Zhicheng Zhang

Published Jun 9, 2026• 0 citations

Abstract

Access to the time-reverse $U^{-1}$ of an unknown quantum unitary process $U$ is widely assumed in quantum learning, metrology, and many-body physics. The fundamental task of unitary time-reversal dictates implementing $U^{-1}$ to within diamond-norm error $ε$ using black-box queries to the $d$-dimensional unitary $U$. Although the query complexity of this task has been extensively studied, existing lower bounds either hold only for the exact case (i.e., $ε=0$) or are suboptimal in $d$. This raises a central question: does approximation help reduce the query complexity of unitary time-reversal? We settle this question in the negative by establishing a robust and tight lower bound $Ω((1-ε)d^2)$ with explicit dependence on the error $ε$. This implies that unitary time-reversal retains optimal exponential hardness (in the number of qubits) even when constant error is allowed. Our bound applies to adaptive and coherent algorithms with unbounded ancillas and holds even when $ε$ is an average-case distance error.

DOI: 10.1145/3798129.3800847

Related papers

Query-optimal estimation of unitary channels in diamond distance

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

arXiv:2302.14066Annual Symposium on Foundations of Computer ScienceNov 6, 202323 citations

Optimal Quantum Junta Testing without Inverse Queries

Jinge Bao, Minbo Gao, Penghui Yao

quant-pharXiv:2609.37926Sep 30, 20260 citations

On the query complexity of unitary channel certification

Sangwoo Jeon, Changhun Oh

arXiv:2507.17254npj Quantum InformationDec 29, 20250 citations

Quantum memory advantage for quantum process tomography

Carlos Bravo-Prieto, Weiyuan Gong, Antonio Anna Mele

quant-pharXiv:2607.13476Jul 16, 20260 citations

An exponential query advantage from access to Stinespring dilation unitaries in quantum channel learning

Manaki Arihara, Satoshi Yoshida, Philip Taranto +1 more

quant-pharXiv:2609.40001Oct 1, 20260 citations

Optimal classical shadow estimation of unitary channels at Heisenberg limit

Entong He, Zihao Li, Noam Scully +2 more

quant-pharXiv:2606.13638Jun 12, 20260 citations

arXiv:2507.05736 · ACM Symposium on Theory of Computing (STOC)

Approximation Does Not Help in Quantum Unitary Time-Reversal

Kean Chen, Nengkun Yu, Zhicheng Zhang

Published Jun 9, 2026• 0 citations

arXiv HTML PDF

Abstract

Access to the time-reverse

U^{-1}

of an unknown quantum unitary process

U

is widely assumed in quantum learning, metrology, and many-body physics. The fundamental task of unitary time-reversal dictates implementing

U^{-1}

to within diamond-norm error

ε

using black-box queries to the

d

-dimensional unitary

U

. Although the query complexity of this task has been extensively studied, existing lower bounds either hold only for the exact case (i.e.,

ε=0

) or are suboptimal in

d

. This raises a central question: does approximation help reduce the query complexity of unitary time-reversal? We settle this question in the negative by establishing a robust and tight lower bound

Ω((1-ε)d^2)

with explicit dependence on the error

ε

. This implies that unitary time-reversal retains optimal exponential hardness (in the number of qubits) even when constant error is allowed. Our bound applies to adaptive and coherent algorithms with unbounded ancillas and holds even when

ε

is an average-case distance error.

DOI: 10.1145/3798129.3800847

Related papers

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.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.14066Annual Symposium on Foundations of Computer ScienceNov 6, 202323 citations

Optimal Quantum Junta Testing without Inverse Queries

Jinge Bao, Minbo Gao, Penghui Yao

We study the query complexity of testing quantum juntas. Given an unknown $n$ -qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most $k$ qubits or is $\varepsilon$ -far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to $U$ , but not to $U^\dagger$ or controlled- $U$ . We give tight bounds for both unitary and channel junta testing. For sufficiently large $k$ , $n \ge 2k$ , and a broad range of $\varepsilon$ , both problems have query complexity $Θ\left(k/(\varepsilon^2\log k)\right)$ . Our upper bounds are achieved by simple nonadaptive testers using product inputs and single-qubit measurements. For junta channels, this closes the gap by Bao and Yao (COLT 23, TPAMI 2025) between an $\widetilde{O}(k)$ upper bound and a $\widetildeΩ(\sqrt{k})$ lower bound at constant $\varepsilon$ , establishing the optimal $Θ(k/\log k)$ query complexity. At the heart of both bounds is a strong connection between quantum junta testing and classical support-size testing. For the upper bounds, we reduce quantum junta testing to a generalized support-size problem for distributions over random subsets, and develop a new tester with improved sample complexity. For the lower bounds, we proceed in the reverse direction, reducing classical support-size testing to quantum junta testing through a phase-masked hard ensemble and showing that forward quantum queries can be exactly classicalized on average. Together, these reductions identify support-size testing as the classical core of quantum junta testing and yield matching lower bounds. At constant $\varepsilon$ , they also give a separation between $Θ(k/\log k)$ forward queries and $\widetilde{O}(\sqrt{k})$ queries with inverse access.We study the query complexity of testing quantum juntas. Given an unknown $n$-qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most $k$ qubits or is $\varepsilon$-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to $U$, but not to $U^\dagger$ or controlled-$U$. We give tight bounds for both unitary and channel junta testing. For sufficiently large $k$, $n \ge 2k$, and a broad range of $\varepsilon$, both problems have query complexity $Θ\left(k/(\varepsilon^2\log k)\right)$. Our upper bounds are achieved by simple nonadaptive testers using product inputs and single-qubit measurements. For junta channels, this closes the gap by Bao and Yao (COLT 23, TPAMI 2025) between an $\widetilde{O}(k)$ upper bound and a $\widetildeΩ(\sqrt{k})$ lower bound at constant $\varepsilon$, establishing the optimal $Θ(k/\log k)$ query complexity. At the heart of both bounds is a strong connection between quantum junta testing and classical support-size testing. For the upper bounds, we reduce quantum junta testing to a generalized support-size problem for distributions over random subsets, and develop a new tester with improved sample complexity. For the lower bounds, we proceed in the reverse direction, reducing classical support-size testing to quantum junta testing through a phase-masked hard ensemble and showing that forward quantum queries can be exactly classicalized on average. Together, these reductions identify support-size testing as the classical core of quantum junta testing and yield matching lower bounds. At constant $\varepsilon$, they also give a separation between $Θ(k/\log k)$ forward queries and $\widetilde{O}(\sqrt{k})$ queries with inverse access.

quant-pharXiv:2609.37926Sep 30, 20260 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.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.17254npj Quantum InformationDec 29, 20250 citations

Quantum memory advantage for quantum process tomography

Carlos Bravo-Prieto, Weiyuan Gong, Antonio Anna Mele

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

quant-pharXiv:2607.13476Jul 16, 20260 citations

An exponential query advantage from access to Stinespring dilation unitaries in quantum channel learning

Manaki Arihara, Satoshi Yoshida, Philip Taranto +1 more

We present a learning task for quantum channels that exhibits an exponential separation in query complexity (in terms of the number of qubits) between two access models: i) black-box channel access and ii) access to a Stinespring dilation unitary of the channel along with its inverse. We consider the task of learning how close the unknown channel is to the set of unitary channels. This is characterized by the \textit{optimal average gate fidelity (OAGF)}, defined as the average gate fidelity maximized over all unitary channels. For constant Kraus rank and a dilation environment of dimension $\operatorname{polylog}(d)$ , we provide an algorithm that estimates the OAGF to fixed additive accuracy using $\operatorname{polylog}(d)$ queries to the Stinespring dilation unitary and its inverse. In contradistinction, under the black-box access model, this estimation requires at least $Ω(\sqrt{d})$ queries, even for channels of constant Kraus rank and constant additive accuracy. As a corollary, we rule out a universal simulator that uses only $\operatorname{poly}(\log d,q)$ queries to the unknown channel to approximate the output of arbitrary $q$ -query algorithms with access to a randomly-sampled Stinespring dilation unitary and its inverse, even to sufficiently small constant error. These results demonstrate that access to the system-environment joint evolution and its inverse can provide an exponential advantage in estimating an intrinsic property of a quantum channel.We present a learning task for quantum channels that exhibits an exponential separation in query complexity (in terms of the number of qubits) between two access models: i) black-box channel access and ii) access to a Stinespring dilation unitary of the channel along with its inverse. We consider the task of learning how close the unknown channel is to the set of unitary channels. This is characterized by the \textit{optimal average gate fidelity (OAGF)}, defined as the average gate fidelity maximized over all unitary channels. For constant Kraus rank and a dilation environment of dimension $\operatorname{polylog}(d)$, we provide an algorithm that estimates the OAGF to fixed additive accuracy using $\operatorname{polylog}(d)$ queries to the Stinespring dilation unitary and its inverse. In contradistinction, under the black-box access model, this estimation requires at least $Ω(\sqrt{d})$ queries, even for channels of constant Kraus rank and constant additive accuracy. As a corollary, we rule out a universal simulator that uses only $\operatorname{poly}(\log d,q)$ queries to the unknown channel to approximate the output of arbitrary $q$-query algorithms with access to a randomly-sampled Stinespring dilation unitary and its inverse, even to sufficiently small constant error. These results demonstrate that access to the system-environment joint evolution and its inverse can provide an exponential advantage in estimating an intrinsic property of a quantum channel.

quant-pharXiv:2609.40001Oct 1, 20260 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.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.13638Jun 12, 20260 citations

Access to the time-reverse

U^{-1}

of an unknown quantum unitary process

U

is widely assumed in quantum learning, metrology, and many-body physics. The fundamental task of unitary time-reversal dictates implementing

U^{-1}

to within diamond-norm error

ε

using black-box queries to the

d

-dimensional unitary

U

. Although the query complexity of this task has been extensively studied, existing lower bounds either hold only for the exact case (i.e.,

ε=0

) or are suboptimal in

d

. This raises a central question: does approximation help reduce the query complexity of unitary time-reversal? We settle this question in the negative by establishing a robust and tight lower bound

Ω((1-ε)d^2)

with explicit dependence on the error

ε

ε

is an average-case distance error.

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.

We study the query complexity of testing quantum juntas. Given an unknown

n

-qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most

k

qubits or is

\varepsilon

-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to

U

, but not to

U^\dagger

or controlled-

U

. We give tight bounds for both unitary and channel junta testing. For sufficiently large

k

n \ge 2k

, and a broad range of

\varepsilon

, both problems have query complexity

Θ\left(k/(\varepsilon^2\log k)\right)

. Our upper bounds are achieved by simple nonadaptive testers using product inputs and single-qubit measurements. For junta channels, this closes the gap by Bao and Yao (COLT 23, TPAMI 2025) between an

\widetilde{O}(k)

upper bound and a

\widetildeΩ(\sqrt{k})

lower bound at constant

\varepsilon

, establishing the optimal

Θ(k/\log k)

query complexity. At the heart of both bounds is a strong connection between quantum junta testing and classical support-size testing. For the upper bounds, we reduce quantum junta testing to a generalized support-size problem for distributions over random subsets, and develop a new tester with improved sample complexity. For the lower bounds, we proceed in the reverse direction, reducing classical support-size testing to quantum junta testing through a phase-masked hard ensemble and showing that forward quantum queries can be exactly classicalized on average. Together, these reductions identify support-size testing as the classical core of quantum junta testing and yield matching lower bounds. At constant

\varepsilon

, they also give a separation between

Θ(k/\log k)

forward queries and

\widetilde{O}(\sqrt{k})

queries with inverse access.

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

Θ(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.

\operatorname{polylog}(d)

, we provide an algorithm that estimates the OAGF to fixed additive accuracy using

\operatorname{polylog}(d)

queries to the Stinespring dilation unitary and its inverse. In contradistinction, under the black-box access model, this estimation requires at least

Ω(\sqrt{d})

queries, even for channels of constant Kraus rank and constant additive accuracy. As a corollary, we rule out a universal simulator that uses only

\operatorname{poly}(\log d,q)

queries to the unknown channel to approximate the output of arbitrary

q

-query algorithms with access to a randomly-sampled Stinespring dilation unitary and its inverse, even to sufficiently small constant error. These results demonstrate that access to the system-environment joint evolution and its inverse can provide an exponential advantage in estimating an intrinsic property of a quantum channel.

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.