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

Lecture notes in computer science

Adversary Lower Bounds for Nonadaptive Quantum Algorithms

Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui Yao

Published Jan 1, 2008• 0 citations
Publisher
DOI
10.1007/978-3-540-69937-8_20

Related papers

Adversary lower bounds for nonadaptive quantum algorithms

Pascal Koiran, Jürgen Landes, Natacha Portier +1 more

arXiv:0804.1440•Journal of Computer and System Sciences•Oct 17, 2009•8 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

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

Harumichi Nishimura, Tomoyuki Yamakami

arXiv:quant-ph/0312003•Lecture notes in computer science•Jan 1, 2004•8 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.

quant-pharXiv:2610.41694•Nov 2, 2026•0 citations

Optimal Quantum Adversary Lower Bounds for Ordered Search

Andrew M. Childs, Troy Lee

arXiv:0708.3396•Lecture notes in computer science•Jan 1, 2008•20 citations

Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements

Ashwin Nayak, Xingyu Zhou

We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most $t$ samples. For sufficiently small $\varepsilon$, estimating an unknown state on $\mathbb{C}^d$ of rank at most $r$ to trace norm error $\varepsilon$ with constant success probability requires, and is achievable with, $$Θ\left(\frac{dr}{\varepsilon^2}\mathop{\mathrm{max}}\left\{1,\frac{r}{\sqrt{t}}\right\}\right)$$ samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most $t$ samples improve the complexity of algorithms making single-sample measurements by at most a factor $\sqrt{t}$. Further, measuring order $r^2$ samples jointly is necessary and sufficient to attain the unrestricted collective rate. For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on $t$ samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.

quant-pharXiv:2609.10514•Sep 10, 2026•6 citations
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.
We study the randomized classical query complexity of cyclic Forrelation, a cyclic analogue of kkk-Forrelation [AA15, STOC'15; BS21, STOC'21]. Given kkk Boolean functions f1,…,fk:F2n→{−1,1}f_1,\ldots,f_k:\mathbb{F}_2^n\to\{-1,1\}f1​,…,fk​:F2n​→{−1,1}, the goal is to estimate Tk=N−1Tr⁡(Df1H⊗n⋯DfkH⊗n),T_k=N^{-1}\operatorname{Tr}(D_{f_1}H^{\otimes n}\cdots D_{f_k}H^{\otimes n}),Tk​=N−1Tr(Df1​​H⊗n⋯Dfk​​H⊗n), where Dfi=diag⁡(fi(x):x∈F2n)D_{f_i}=\operatorname{diag}(f_i(x):x\in\mathbb{F}_2^n)Dfi​​=diag(fi​(x):x∈F2n​), HHH is the Hadamard gate, and N=2nN=2^nN=2n. This normalized-trace problem can be solved with kkk quantum queries in the DQC1 model. Its classical query complexity was left open in [JLS+26, FOCS'26], which conjectured a lower bound of Ω~(N1−2/k)\widetildeΩ(N^{1-2/k})Ω(N1−2/k). We establish a nearly complete characterization of the nonadaptive classical query complexity of cyclic Forrelation. For even k≥4k\ge 4k≥4, we prove a tight bound of Θk(N1−2/k)Θ_k(N^{1-2/k})Θk​(N1−2/k) for constant additive error. For odd k≥5k\ge 5k≥5, we obtain a lower bound of Ωk(N1−2/(k−1))Ω_k(N^{1-2/(k-1)})Ωk​(N1−2/(k−1)) and an upper bound of Ok(N1−2/k)O_k(N^{1-2/k})Ok​(N1−2/k). Surprisingly, k=3k=3k=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 kkk-cycle, leading to the exponent 1−1/⌊k/2⌋1-1/\lfloor k/2\rfloor1−1/⌊k/2⌋, rather than the previously conjectured 1−2/k1-2/k1−2/k, which was motivated by a Fourier-growth heuristic. Finally, allowing adaptivity, we prove a lower bound of Ω(N1/4)Ω(N^{1/4})Ω(N1/4) for every k≥4k\ge4k≥4. Although formally close to kkk-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 determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most ttt samples. For sufficiently small ε\varepsilonε, estimating an unknown state on Cd\mathbb{C}^dCd of rank at most rrr to trace norm error ε\varepsilonε with constant success probability requires, and is achievable with, Θ(drε2max{1,rt})Θ\left(\frac{dr}{\varepsilon^2}\mathop{\mathrm{max}}\left\{1,\frac{r}{\sqrt{t}}\right\}\right)Θ(ε2dr​max{1,t​r​}) samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most ttt samples improve the complexity of algorithms making single-sample measurements by at most a factor t\sqrt{t}t​. Further, measuring order r2r^2r2 samples jointly is necessary and sufficient to attain the unrestricted collective rate. For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on ttt samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.