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.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.23752Sep 22, 20260 citations

An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation

Harumichi Nishimura, Tomoyuki Yamakami

arXiv:quant-ph/0312003Lecture notes in computer scienceJan 1, 20048 citations

Exponential quantum-classical query separations for cyclic Forrelation

Yuxin Zhang, Changpeng Shao

We study the randomized classical query complexity of cyclic Forrelation, a cyclic analogue of $k$ -Forrelation [AA15, STOC'15; BS21, STOC'21]. Given $k$ Boolean functions $f_1,\ldots,f_k:\mathbb{F}_2^n\to\{-1,1\}$ , the goal is to estimate $T_k=N^{-1}\operatorname{Tr}(D_{f_1}H^{\otimes n}\cdots D_{f_k}H^{\otimes n}),$ where $D_{f_i}=\operatorname{diag}(f_i(x):x\in\mathbb{F}_2^n)$ , $H$ is the Hadamard gate, and $N=2^n$ . This normalized-trace problem can be solved with $k$ quantum queries in the DQC1 model. Its classical query complexity was left open in [JLS+26, FOCS'26], which conjectured a lower bound of $\widetildeΩ(N^{1-2/k})$ . We establish a nearly complete characterization of the nonadaptive classical query complexity of cyclic Forrelation. For even $k\ge 4$ , we prove a tight bound of $Θ_k(N^{1-2/k})$ for constant additive error. For odd $k\ge 5$ , we obtain a lower bound of $Ω_k(N^{1-2/(k-1)})$ and an upper bound of $O_k(N^{1-2/k})$ . Surprisingly, $k=3$ admits a polylogarithmic-query nonadaptive classical algorithm, disproving the conjecture in this case. These results suggest an unexpected parity-dependent structure: the nonadaptive complexity may be governed by the independence number of the $k$ -cycle, leading to the exponent $1-1/\lfloor k/2\rfloor$ , rather than the previously conjectured $1-2/k$ , which was motivated by a Fourier-growth heuristic. Finally, allowing adaptivity, we prove a lower bound of $Ω(N^{1/4})$ for every $k\ge4$ . Although formally close to $k$ -Forrelation, the cyclic structure leads to rather different classical behavior and requires different techniques. Our lower bounds are based on hidden-shift collision constructions, and our upper bounds follow from randomized sampling together with cycle-specific conditional-moment estimates. Our results provide a systematic understanding of its query advantages over classical computation.We study the randomized classical query complexity of cyclic Forrelation, a cyclic analogue of $k$-Forrelation [AA15, STOC'15; BS21, STOC'21]. Given $k$ Boolean functions $f_1,\ldots,f_k:\mathbb{F}_2^n\to\{-1,1\}$, the goal is to estimate $T_k=N^{-1}\operatorname{Tr}(D_{f_1}H^{\otimes n}\cdots D_{f_k}H^{\otimes n}),$ where $D_{f_i}=\operatorname{diag}(f_i(x):x\in\mathbb{F}_2^n)$, $H$ is the Hadamard gate, and $N=2^n$. This normalized-trace problem can be solved with $k$ quantum queries in the DQC1 model. Its classical query complexity was left open in [JLS+26, FOCS'26], which conjectured a lower bound of $\widetildeΩ(N^{1-2/k})$. We establish a nearly complete characterization of the nonadaptive classical query complexity of cyclic Forrelation. For even $k\ge 4$, we prove a tight bound of $Θ_k(N^{1-2/k})$ for constant additive error. For odd $k\ge 5$, we obtain a lower bound of $Ω_k(N^{1-2/(k-1)})$ and an upper bound of $O_k(N^{1-2/k})$. Surprisingly, $k=3$ admits a polylogarithmic-query nonadaptive classical algorithm, disproving the conjecture in this case. These results suggest an unexpected parity-dependent structure: the nonadaptive complexity may be governed by the independence number of the $k$-cycle, leading to the exponent $1-1/\lfloor k/2\rfloor$, rather than the previously conjectured $1-2/k$, which was motivated by a Fourier-growth heuristic. Finally, allowing adaptivity, we prove a lower bound of $Ω(N^{1/4})$ for every $k\ge4$. Although formally close to $k$-Forrelation, the cyclic structure leads to rather different classical behavior and requires different techniques. Our lower bounds are based on hidden-shift collision constructions, and our upper bounds follow from randomized sampling together with cycle-specific conditional-moment estimates. Our results provide a systematic understanding of its query advantages over classical computation.

quant-pharXiv:2610.41694Nov 2, 2026

Optimal Quantum Adversary Lower Bounds for Ordered Search

Andrew M. Childs, Troy Lee

arXiv:0708.3396Lecture notes in computer scienceJan 1, 200817 citations

Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound

Aleksandrs Belovs

Computational ComplexityApr 16, 201525 citations

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.

We study the randomized classical query complexity of cyclic Forrelation, a cyclic analogue of

k

-Forrelation [AA15, STOC'15; BS21, STOC'21]. Given

k

Boolean functions

f_1,\ldots,f_k:\mathbb{F}_2^n\to\{-1,1\}

, the goal is to estimate

T_k=N^{-1}\operatorname{Tr}(D_{f_1}H^{\otimes n}\cdots D_{f_k}H^{\otimes n}),

where

D_{f_i}=\operatorname{diag}(f_i(x):x\in\mathbb{F}_2^n)

H

is the Hadamard gate, and

N=2^n

. This normalized-trace problem can be solved with

k

quantum queries in the DQC1 model. Its classical query complexity was left open in [JLS+26, FOCS'26], which conjectured a lower bound of

\widetildeΩ(N^{1-2/k})

. We establish a nearly complete characterization of the nonadaptive classical query complexity of cyclic Forrelation. For even

k\ge 4

, we prove a tight bound of

Θ_k(N^{1-2/k})

for constant additive error. For odd

k\ge 5

, we obtain a lower bound of

Ω_k(N^{1-2/(k-1)})

and an upper bound of

O_k(N^{1-2/k})

. Surprisingly,

k=3

admits a polylogarithmic-query nonadaptive classical algorithm, disproving the conjecture in this case. These results suggest an unexpected parity-dependent structure: the nonadaptive complexity may be governed by the independence number of the

k

-cycle, leading to the exponent

1-1/\lfloor k/2\rfloor

, rather than the previously conjectured

1-2/k

, which was motivated by a Fourier-growth heuristic. Finally, allowing adaptivity, we prove a lower bound of

Ω(N^{1/4})

for every

k\ge4

. Although formally close to

k

-Forrelation, the cyclic structure leads to rather different classical behavior and requires different techniques. Our lower bounds are based on hidden-shift collision constructions, and our upper bounds follow from randomized sampling together with cycle-specific conditional-moment estimates. Our results provide a systematic understanding of its query advantages over classical computation.