Skip to content
Preprint

Optimal Separations Between Randomized and Quantum Query Complexity under Permutation Symmetry

Nov 2026 · 0 citations · 19 references
Physics

TL;DR

It is proved that every such function over an arbitrary finite alphabet $A$ satisfies R_\varepsilon(f)=O(Q_\varepsilon(f)^2)$, and bounds for graph and hypergraph properties are established, which are tight for permutation-invariant functions and nearly tight for graph and hypergraph properties.

Abstract

A function $f:\cD\subseteq A^N\to\{0,1\}$ is \emph{permutation-invariant} if every permutation of its input positions preserves both its domain and its value. We study how this symmetry limits quantum speedups. For $1/6\leq\varepsilon<1/2$, we prove that every such function over an arbitrary finite alphabet $A$ satisfies $R_\varepsilon(f)=O(Q_\varepsilon(f)^2)$, where $R_\varepsilon$ and $Q_\varepsilon$ denote randomized and quantum query complexities with error at most $\varepsilon$. This improves the previous cubic bound (ITCS 2019). We further establish bounds for graph and hypergraph properties, for which vertex relabeling preserves both the promise and the answer. For the same range of $\varepsilon$, we obtain $R_\varepsilon(f)=O(Q_\varepsilon(f)^4)$ for graph properties in the adjacency-matrix model and $R_\varepsilon(f)=O_k(Q_\varepsilon(f)^{2k})$ for $k$-uniform hypergraph properties with fixed $k\geq2$, where the implicit constant depends only on $k$. These improve the previous bounds $R_{1/3}(f)=O(Q_{1/3}(f)^6)$ and $R_{1/3}(f)=O_k(Q_{1/3}(f)^{3k})$, respectively (SICOMP 2024) These bounds are tight for permutation-invariant functions and nearly tight for graph and hypergraph properties. Unstructured search gives a matching quadratic separation with $R_{1/3}(f)=\Theta\!\left(Q_{1/3}(f)^2\right)$. For every fixed $k\geq 2$, we construct explicit families of invariant promise problems on $k$-uniform hypergraphs satisfying $R_{1/3}(f)\geq Q_{1/3}(f)^{2k-o(1)}$.

View source

Similar papers

Preprint Oct 2026

Optimal query complexity for fractional quantum evolution

The argument reduces any $N$-query circuit to the approximation of $e^{it\theta}$ by a trigonometric polynomial with degree bounded by $O(N)$ by a trigonometric polynomial with degree bounded by $O(N)$ together with Remez inequality to establish a matching lower bound for arbitrary query algorithms.

A. Liu, Adam Wesołowski, Jayne Thompson et al. · 0 citations
Preprint Sep 2026

The quantum query complexity of the semigroup product problem

It is proved that for monoids with a stable partial order in which the identity is the minimum element, the bounded-error quantum query complexity is at most $\sqrt{n+1}((\beta+2)\log(n+2))^{O(\log(\beta+2))}$.

Troy Lee, M. Santha · 0 citations
Preprint Sep 2026

Optimal Quantum Junta Testing

We determine the quantum query complexity of testing $k$-juntas for Boolean functions, unitaries, and quantum channels. Let $n$ denote the number of input bits or qubits and $\varepsilon$ the distance parameter. For all sufficiently large $k$, $n \ge 2k$, and $2^{-k/16} \le \varepsilon \le 1/16$, we establish the follo...

Jing Bao, Minbo Gao, Peng-Hui Yao · 1 citation
Preprint Oct 2026

Quantum Submodular Maximization

We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint $k$ on an $n$-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected...

Yong-Gang Jiang, Xiao-Ming Sun, Peng-Hui Yao et al. · 0 citations
Sep 2026

Improved Quantum Random Self-Reduction for Linear Problems

We study quantum random self-reductions for linear problems over finite fields. Let $M\in\mathbb{F}^{n\times n}$ be an arbitrary matrix, and let $\mathcal{O}$ be an oracle that agrees with the linear map $x\mapsto Mx$ on an $\varepsilon$-fraction of inputs $x\sim\mathbb{F}^n$. Given coherent access to $\mathcal{O}$ and...

Vahid R. Asadi, Shuichi Hirahara, Nobutaka Shimizu · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.