arXiv:2609.40001

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

Manaki Arihara, Satoshi Yoshida, Philip Taranto, Mio Murao

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations

Abstract

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.

Comments: 42 pages, 3 figures

Related papers

Random Stinespring superchannel: converting channel queries into dilation isometry queries

Filippo Girardi, Francesco Anna Mele, Haimeng Zhao +2 more

quant-pharXiv:2512.20599Dec 24, 20250 citations

Quantum channel tomography and estimation by local test

Kean Chen, Nengkun Yu, Zhicheng Zhang

quant-pharXiv:2512.13614Dec 16, 20250 citations

Optimal Distributed Similarity Estimation of Quantum Channels

Congcong Zheng, Kun Wang, Xutao Yu +2 more

quant-pharXiv:2512.10465Dec 12, 20250 citations

Approximation Does Not Help in Quantum Unitary Time-Reversal

Kean Chen, Nengkun Yu, Zhicheng Zhang

arXiv:2507.05736ACM Symposium on Theory of Computing (STOC)Jun 9, 20260 citations

Optimal Quantum Junta Testing without Inverse Queries

Jinge Bao, Minbo Gao, Penghui Yao

quant-pharXiv:2609.37926Sep 30, 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:2609.40001

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

Manaki Arihara, Satoshi Yoshida, Philip Taranto, Mio Murao

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations

arXiv HTML PDF

Abstract

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

Comments: 42 pages, 3 figures

Related papers

Random Stinespring superchannel: converting channel queries into dilation isometry queries

Filippo Girardi, Francesco Anna Mele, Haimeng Zhao +2 more

The recently introduced random purification channel, which converts $n$ copies of an arbitrary mixed quantum state into $n$ copies of the same uniformly random purification, has emerged as a powerful tool in quantum information theory. Motivated by this development, we introduce a channel-level analogue, which we call the random Stinespring superchannel. This consists in a procedure to transform $n$ parallel queries of an arbitrary quantum channel into $n$ parallel queries of the same uniformly random Stinespring isometry, via universal encoding and decoding operations that are efficiently implementable. When the channel is promised to have Choi rank at most $r$ , the procedure can be tailored to yield a Stinespring environment of dimension $r$ . We present two applications of the random Stinespring superchannel, one in quantum Shannon theory and one in quantum learning theory. In quantum Shannon theory, we prove a channel-level analogue of Uhlmann's theorem for quantum divergences. In quantum learning theory, our construction shows that tomography of quantum channels reduces to tomography of isometries. This yields a simple channel learning algorithm, based on existing isometry learning protocols, that matches the performance of the two recently proposed channel tomography algorithms. Complementarily, whereas the optimality of these algorithms had previously been established only up to a logarithmic factor in the dimension, we close this gap by removing this logarithmic factor from the lower bound. Taken together, our results fully establish the optimality of these recently introduced channel learning algorithms, showing that the optimal query complexity of learning a quantum channel with input dimension $d_A$ , output dimension $d_B$ , and Choi rank $r$ is $Θ(d_A d_B r)$ .The recently introduced random purification channel, which converts $n$ copies of an arbitrary mixed quantum state into $n$ copies of the same uniformly random purification, has emerged as a powerful tool in quantum information theory. Motivated by this development, we introduce a channel-level analogue, which we call the random Stinespring superchannel. This consists in a procedure to transform $n$ parallel queries of an arbitrary quantum channel into $n$ parallel queries of the same uniformly random Stinespring isometry, via universal encoding and decoding operations that are efficiently implementable. When the channel is promised to have Choi rank at most $r$, the procedure can be tailored to yield a Stinespring environment of dimension $r$. We present two applications of the random Stinespring superchannel, one in quantum Shannon theory and one in quantum learning theory. In quantum Shannon theory, we prove a channel-level analogue of Uhlmann's theorem for quantum divergences. In quantum learning theory, our construction shows that tomography of quantum channels reduces to tomography of isometries. This yields a simple channel learning algorithm, based on existing isometry learning protocols, that matches the performance of the two recently proposed channel tomography algorithms. Complementarily, whereas the optimality of these algorithms had previously been established only up to a logarithmic factor in the dimension, we close this gap by removing this logarithmic factor from the lower bound. Taken together, our results fully establish the optimality of these recently introduced channel learning algorithms, showing that the optimal query complexity of learning a quantum channel with input dimension $d_A$, output dimension $d_B$, and Choi rank $r$ is $Θ(d_A d_B r)$.

quant-pharXiv:2512.20599Dec 24, 20250 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$ .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.13614Dec 16, 20250 citations

Optimal Distributed Similarity Estimation of Quantum Channels

Congcong Zheng, Kun Wang, Xutao Yu +2 more

As quantum processors are deployed across different hardware platforms and remote cloud laboratories, a basic physical question is whether two black-box devices realize the same quantum process, without relying on a trusted classical description. We formulate the core primitive for this comparison task as \emph{distributed similarity estimation of quantum channels} (DSEC): given local access to two unknown channels, estimate the normalized inner product of their Choi states. We prove that the optimal query complexity of DSEC is $Θ(\max\{\sqrt{d}/\varepsilon,1/\varepsilon^2\})$ , where $d$ is the channel dimension and $\varepsilon$ is the additive error. This matching query complexity is nontrivial: channel learning permits input choices and interleaving known operations, which makes channel learning strictly harder than state learning. We first prove an information-theoretic lower bound with this scaling, which holds even in the \emph{strongest setting}, allowing adaptive strategies, multiple rounds of classical communication, and coherent access with arbitrary ancillas. We then give a matching upper bound in the \emph{weakest setting}, namely non-adaptive and ancilla-free incoherent access, via a randomized measurement algorithm achieving this bound. Finally, we show that our algorithm achieves a quadratic improvement over classical shadow baselines. Our results provide theoretically optimal and practical algorithms for quantum device benchmarking and distributed quantum learning.As quantum processors are deployed across different hardware platforms and remote cloud laboratories, a basic physical question is whether two black-box devices realize the same quantum process, without relying on a trusted classical description. We formulate the core primitive for this comparison task as \emph{distributed similarity estimation of quantum channels} (DSEC): given local access to two unknown channels, estimate the normalized inner product of their Choi states. We prove that the optimal query complexity of DSEC is $Θ(\max\{\sqrt{d}/\varepsilon,1/\varepsilon^2\})$, where $d$ is the channel dimension and $\varepsilon$ is the additive error. This matching query complexity is nontrivial: channel learning permits input choices and interleaving known operations, which makes channel learning strictly harder than state learning. We first prove an information-theoretic lower bound with this scaling, which holds even in the \emph{strongest setting}, allowing adaptive strategies, multiple rounds of classical communication, and coherent access with arbitrary ancillas. We then give a matching upper bound in the \emph{weakest setting}, namely non-adaptive and ancilla-free incoherent access, via a randomized measurement algorithm achieving this bound. Finally, we show that our algorithm achieves a quadratic improvement over classical shadow baselines. Our results provide theoretically optimal and practical algorithms for quantum device benchmarking and distributed quantum learning.

quant-pharXiv:2512.10465Dec 12, 20250 citations

Approximation Does Not Help in Quantum Unitary Time-Reversal

Kean Chen, Nengkun Yu, Zhicheng Zhang

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

arXiv:2507.05736ACM Symposium on Theory of Computing (STOC)Jun 9, 20260 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

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

\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

The recently introduced random purification channel, which converts

n

copies of an arbitrary mixed quantum state into

n

copies of the same uniformly random purification, has emerged as a powerful tool in quantum information theory. Motivated by this development, we introduce a channel-level analogue, which we call the random Stinespring superchannel. This consists in a procedure to transform

n

parallel queries of an arbitrary quantum channel into

n

parallel queries of the same uniformly random Stinespring isometry, via universal encoding and decoding operations that are efficiently implementable. When the channel is promised to have Choi rank at most

r

, the procedure can be tailored to yield a Stinespring environment of dimension

r

. We present two applications of the random Stinespring superchannel, one in quantum Shannon theory and one in quantum learning theory. In quantum Shannon theory, we prove a channel-level analogue of Uhlmann's theorem for quantum divergences. In quantum learning theory, our construction shows that tomography of quantum channels reduces to tomography of isometries. This yields a simple channel learning algorithm, based on existing isometry learning protocols, that matches the performance of the two recently proposed channel tomography algorithms. Complementarily, whereas the optimality of these algorithms had previously been established only up to a logarithmic factor in the dimension, we close this gap by removing this logarithmic factor from the lower bound. Taken together, our results fully establish the optimality of these recently introduced channel learning algorithms, showing that the optimal query complexity of learning a quantum channel with input dimension

d_A

, output dimension

d_B

, and Choi rank

r

Θ(d_A d_B r)

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

Θ(\max\{\sqrt{d}/\varepsilon,1/\varepsilon^2\})

, where

d

is the channel dimension and

\varepsilon

is the additive error. This matching query complexity is nontrivial: channel learning permits input choices and interleaving known operations, which makes channel learning strictly harder than state learning. We first prove an information-theoretic lower bound with this scaling, which holds even in the \emph{strongest setting}, allowing adaptive strategies, multiple rounds of classical communication, and coherent access with arbitrary ancillas. We then give a matching upper bound in the \emph{weakest setting}, namely non-adaptive and ancilla-free incoherent access, via a randomized measurement algorithm achieving this bound. Finally, we show that our algorithm achieves a quadratic improvement over classical shadow baselines. Our results provide theoretically optimal and practical algorithms for quantum device benchmarking and distributed quantum learning.

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.

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.

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.