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

On Exact Quantum Query Complexity

Ashley Montanaro, Richard Jozsa, Graeme Mitchison

arXiv:1111.0475AlgorithmicaAug 29, 201334 citations

Quantum Approximate Counting with Nonadaptive Grover Iterations

Venkateswaran, Ramgopal, Ryan O’Donnell

Approximate Counting refers to the problem where we are given query access to a function $f : [N] \to \{0,1\}$ , and we wish to estimate $K = #\{x : f(x) = 1\}$ to within a factor of $1+ε$ (with high probability), while minimizing the number of queries. In the quantum setting, Approximate Counting can be done with $O\left(\min\left(\sqrt{N/ε}, \sqrt{N/K}/ε\right)\right)$ queries. It has recently been shown that this can be achieved by a simple algorithm that only uses "Grover iterations"; however the algorithm performs these iterations adaptively. Motivated by concerns of computational simplicity, we consider algorithms that use Grover iterations with limited adaptivity. We show that algorithms using only nonadaptive Grover iterations can achieve $O\left(\sqrt{N/ε}\right)$ query complexity, which is tight.Approximate Counting refers to the problem where we are given query access to a function $f : [N] \to \{0,1\}$, and we wish to estimate $K = #\{x : f(x) = 1\}$ to within a factor of $1+ε$ (with high probability), while minimizing the number of queries. In the quantum setting, Approximate Counting can be done with $O\left(\min\left(\sqrt{N/ε}, \sqrt{N/K}/ε\right)\right)$ queries. It has recently been shown that this can be achieved by a simple algorithm that only uses "Grover iterations"; however the algorithm performs these iterations adaptively. Motivated by concerns of computational simplicity, we consider algorithms that use Grover iterations with limited adaptivity. We show that algorithms using only nonadaptive Grover iterations can achieve $O\left(\sqrt{N/ε}\right)$ query complexity, which is tight.

arXiv:2010.04370Leibniz international proceedings in informaticsOct 9, 20204 citations

Unbounded-error quantum query complexity

Ashley Montanaro, Harumichi Nishimura, Rudy Raymond

arXiv:0712.1446Theoretical Computer ScienceMay 3, 20119 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

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.

Approximate Counting refers to the problem where we are given query access to a function

f : [N] \to \{0,1\}

, and we wish to estimate $K = #\{x : f(x) = 1\}$ to within a factor of

1+ε

(with high probability), while minimizing the number of queries. In the quantum setting, Approximate Counting can be done with

O\left(\min\left(\sqrt{N/ε}, \sqrt{N/K}/ε\right)\right)

queries. It has recently been shown that this can be achieved by a simple algorithm that only uses "Grover iterations"; however the algorithm performs these iterations adaptively. Motivated by concerns of computational simplicity, we consider algorithms that use Grover iterations with limited adaptivity. We show that algorithms using only nonadaptive Grover iterations can achieve

O\left(\sqrt{N/ε}\right)

query complexity, which is tight.

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.