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

arXiv:2611.08919

Optimal Separations Between Randomized and Quantum Query Complexity under Permutation Symmetry

Yunqi Huang, Lvzhou Li, Zekun Ye, 鄭盛根

Published Nov 6, 2026• 0 citations
arXivHTMLPDF

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)=Θ\!\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)}$.

DOI
10.48550/arxiv.2611.08919

Related papers

Symmetries, Graph Properties, and Quantum Speedups

Shalev Ben-David, Andrew M. Childs, Andras Gilyen +3 more

Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs-where graph symmetry is manifested differently-we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013).

arXiv:2006.12760•Annual Symposium on Foundations of Computer Science•Nov 1, 2020•32 citations

Quantum Advantage of Permutation-Invariant Functions in Communication Complexity

Yunqi Huang, Zekun Ye

We study how symmetry affects quantum advantage in two-party communication complexity. For any partial function $f$ on length-$n$ strings over a fixed alphabet of size $q$, invariant under simultaneous coordinate permutations, we prove $R^{\mathrm{pub}}(f)=O_q(t\log(2+n/t))$, where $t=\min\{n,Q^{\ast}(f)^2\}$, $R^{\mathrm{pub}}$ denotes public-coin randomized communication complexity, and $Q^{\ast}$ denotes entanglement-assisted quantum communication complexity. This bound is tight for set disjointness and extends the binary-alphabet result of Guan et al. with a smaller logarithmic overhead. The exponent of the logarithmic factor cannot be reduced by any fixed positive amount: for every fixed $\varepsilon\in(0,1)$, there are binary permutation-invariant partial functions with quantum communication complexity $O_\varepsilon(\log\log n)$ and randomized communication complexity $Ω_\varepsilon((\log n)^{1-\varepsilon})$. We also characterize quantum communication complexity by a combinatorial parameter up to a logarithmic factor. Growing alphabets and graph symmetries admit exponential separations. For every fixed $\varepsilon\in(0,1)$, we exhibit permutation-invariant partial functions on length-$n$ strings over an $n$-symbol alphabet with quantum communication complexity $O_\varepsilon(\log n)$ and randomized communication complexity $Ω_\varepsilon(n^{1-\varepsilon})$. For graph-invariant partial functions on $v$-vertex graphs, we obtain $O_\varepsilon(\log v)$ quantum versus $Ω_\varepsilon(v^{2-\varepsilon})$ randomized communication complexity. All separation protocols require no prior entanglement.

quant-pharXiv:2609.40116•Oct 1, 2026•0 citations

Symmetries, Graph Properties, and Quantum Speedups

Shalev Ben-David, Andrew M. Childs, András Gilyén +3 more

Abstract. Aaronson and Ambainis [ Theory Comput., 10 (2014), pp. 133–166] and Chailloux [ Proceedings of the 10 th Innovations in Theoretical Computer Science Conference, 2018, pp. 19:1–19:7] showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent superpolynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow superpolynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs—where graph symmetry is manifested differently—we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu [ Lecture Notes in Comput. Sci. 6845, Springer, 2011, pp. 365–376] and Montanaro and de Wolf [ Theory Comput., 7 (2016)].

SIAM Journal on Computing•Dec 13, 2024•8 citations

Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity

Andris Ambainis, Jānis Iraids, Martins Kokainis

We study how large the certificate complexity ${C}(f)$ of a total Boolean function can be relative to its randomized and quantum query complexities. We construct a total Boolean function $f$ whose randomized query complexity with one-sided error satisfies ${R}_1(f) = Θ(\sqrt{{C}(f)})$. This separation is optimal even when two-sided error is allowed. From this construction, we obtain another total Boolean function $F$ with bounded-error quantum query complexity ${Q}(F) = \widetilde O({C}(F)^{1/4})$, attaining the general quartic bound up to polylogarithmic factors. For the same function, both exact and zero-error quantum query complexities are $\widetilde O(\sqrt{{C}(F)})$. We also prove matching lower bounds for these two measures on $F$.

quant-pharXiv:2609.11664•Sep 11, 2026•1 citation

Can graph properties have exponential quantum speedup?

Andrew M. Childs, Daochen Wang

Quantum computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity $R$ of any graph property $\mathcal{P}$ has $R(\mathcal{P}) = O(Q(\mathcal{P})^{6})$, where $Q$ is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove $R(\mathcal{P}) = O(Q(\mathcal{P})^{3l})$ for any $l$-uniform hypergraph property $\mathcal{P}$ in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.

arXiv:2001.10520•Jan 28, 2020•6 citations

Random Garbage Creates Exponential Quantum Query Separations

Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray

We prove an exponential separation between standard (XOR) quantum queries and forward-erasing queries for a Boolean property of injective functions, answering a question of Aaronson~\cite{Aaronson2021Open}. We also obtain an exponential separation for a Boolean promise problem on permutations, where forward in-place queries are unitary but inverse queries are not supplied. Our construction follows Aaronson's suggestion of appending fixed random garbage to a Simon function. Let $X=\{0,1\}^n$ and $N=2^n$. We use the injection $f_{h,r}(x)=(h(x),x,r_x)$, where $h:X\to X$ is promised to be either a permutation or a Simon function, and $r:X\to X$ is an arbitrary tag table that is reused on every query. The resulting problem is solvable with at most $n+2$ standard queries, but requires $Θ(\sqrt N)$ forward-erasing queries, matching classical collision sampling. Embedding these instances into permutations, with the copy of $x$ replaced by a single bit that keeps the embedding injective, gives a promise problem on permutations of $L=4N^2$ elements that requires $O(\log L)$ standard queries versus $Θ(L^{1/4})$ forward in-place queries. The lower bounds use the recording method. We replace each query by a nearby contraction that records cells of a purified tag table. After $T$ queries, tracing out the purified tag table yields a sum of positive-semidefinite contributions, each depending on $h$ at no more than $T$ addresses. A query-by-query hybrid bounds the trace-norm difference between the actual and auxiliary final operators by $O(T/\sqrt N)$. Random permutations and random Simon functions have the same restriction distribution on such a set unless it contains a hidden Simon pair, an event of probability $O(T^2/N)$. Consequently, the actual final states in the two cases remain close unless $T=Ω(\sqrt N)$, giving the required lower bounds.

cs.CCCross-listedarXiv:2609.03628•Sep 4, 2026•0 citations
A function f:\cD⊆AN→{0,1}f:\cD\subseteq A^N\to\{0,1\}f:\cD⊆AN→{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≤ε<1/21/6\leq\varepsilon<1/21/6≤ε<1/2, we prove that every such function over an arbitrary finite alphabet AAA satisfies Rε(f)=O(Qε(f)2)R_\varepsilon(f)=O(Q_\varepsilon(f)^2)Rε​(f)=O(Qε​(f)2), where RεR_\varepsilonRε​ and QεQ_\varepsilonQε​ 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ε(f)=O(Qε(f)4)R_\varepsilon(f)=O(Q_\varepsilon(f)^4)Rε​(f)=O(Qε​(f)4) for graph properties in the adjacency-matrix model and Rε(f)=Ok(Qε(f)2k)R_\varepsilon(f)=O_k(Q_\varepsilon(f)^{2k})Rε​(f)=Ok​(Qε​(f)2k) for kkk-uniform hypergraph properties with fixed k≥2k\geq2k≥2, where the implicit constant depends only on kkk. These improve the previous bounds R1/3(f)=O(Q1/3(f)6)R_{1/3}(f)=O(Q_{1/3}(f)^6)R1/3​(f)=O(Q1/3​(f)6) and R1/3(f)=Ok(Q1/3(f)3k)R_{1/3}(f)=O_k(Q_{1/3}(f)^{3k})R1/3​(f)=Ok​(Q1/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 R1/3(f)=Θ ⁣(Q1/3(f)2)R_{1/3}(f)=Θ\!\left(Q_{1/3}(f)^2\right)R1/3​(f)=Θ(Q1/3​(f)2). For every fixed k≥2k\geq 2k≥2, we construct explicit families of invariant promise problems on kkk-uniform hypergraphs satisfying R1/3(f)≥Q1/3(f)2k−o(1)R_{1/3}(f)\geq Q_{1/3}(f)^{2k-o(1)}R1/3​(f)≥Q1/3​(f)2k−o(1).
Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs-where graph symmetry is manifested differently-we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013).
We study how symmetry affects quantum advantage in two-party communication complexity. For any partial function fff on length-nnn strings over a fixed alphabet of size qqq, invariant under simultaneous coordinate permutations, we prove Rpub(f)=Oq(tlog⁡(2+n/t))R^{\mathrm{pub}}(f)=O_q(t\log(2+n/t))Rpub(f)=Oq​(tlog(2+n/t)), where t=min⁡{n,Q∗(f)2}t=\min\{n,Q^{\ast}(f)^2\}t=min{n,Q∗(f)2}, RpubR^{\mathrm{pub}}Rpub denotes public-coin randomized communication complexity, and Q∗Q^{\ast}Q∗ denotes entanglement-assisted quantum communication complexity. This bound is tight for set disjointness and extends the binary-alphabet result of Guan et al. with a smaller logarithmic overhead. The exponent of the logarithmic factor cannot be reduced by any fixed positive amount: for every fixed ε∈(0,1)\varepsilon\in(0,1)ε∈(0,1), there are binary permutation-invariant partial functions with quantum communication complexity Oε(log⁡log⁡n)O_\varepsilon(\log\log n)Oε​(loglogn) and randomized communication complexity Ωε((log⁡n)1−ε)Ω_\varepsilon((\log n)^{1-\varepsilon})Ωε​((logn)1−ε). We also characterize quantum communication complexity by a combinatorial parameter up to a logarithmic factor. Growing alphabets and graph symmetries admit exponential separations. For every fixed ε∈(0,1)\varepsilon\in(0,1)ε∈(0,1), we exhibit permutation-invariant partial functions on length-nnn strings over an nnn-symbol alphabet with quantum communication complexity Oε(log⁡n)O_\varepsilon(\log n)Oε​(logn) and randomized communication complexity Ωε(n1−ε)Ω_\varepsilon(n^{1-\varepsilon})Ωε​(n1−ε). For graph-invariant partial functions on vvv-vertex graphs, we obtain Oε(log⁡v)O_\varepsilon(\log v)Oε​(logv) quantum versus Ωε(v2−ε)Ω_\varepsilon(v^{2-\varepsilon})Ωε​(v2−ε) randomized communication complexity. All separation protocols require no prior entanglement.
Abstract. Aaronson and Ambainis [ Theory Comput., 10 (2014), pp. 133–166] and Chailloux [ Proceedings of the 10 th Innovations in Theoretical Computer Science Conference, 2018, pp. 19:1–19:7] showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent superpolynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow superpolynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs—where graph symmetry is manifested differently—we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu [ Lecture Notes in Comput. Sci. 6845, Springer, 2011, pp. 365–376] and Montanaro and de Wolf [ Theory Comput., 7 (2016)].
We study how large the certificate complexity C(f){C}(f)C(f) of a total Boolean function can be relative to its randomized and quantum query complexities. We construct a total Boolean function fff whose randomized query complexity with one-sided error satisfies R1(f)=Θ(C(f)){R}_1(f) = Θ(\sqrt{{C}(f)})R1​(f)=Θ(C(f)​). This separation is optimal even when two-sided error is allowed. From this construction, we obtain another total Boolean function FFF with bounded-error quantum query complexity Q(F)=O~(C(F)1/4){Q}(F) = \widetilde O({C}(F)^{1/4})Q(F)=O(C(F)1/4), attaining the general quartic bound up to polylogarithmic factors. For the same function, both exact and zero-error quantum query complexities are O~(C(F))\widetilde O(\sqrt{{C}(F)})O(C(F)​). We also prove matching lower bounds for these two measures on FFF.
Quantum computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity RRR of any graph property P\mathcal{P}P has R(P)=O(Q(P)6)R(\mathcal{P}) = O(Q(\mathcal{P})^{6})R(P)=O(Q(P)6), where QQQ is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove R(P)=O(Q(P)3l)R(\mathcal{P}) = O(Q(\mathcal{P})^{3l})R(P)=O(Q(P)3l) for any lll-uniform hypergraph property P\mathcal{P}P in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.
We prove an exponential separation between standard (XOR) quantum queries and forward-erasing queries for a Boolean property of injective functions, answering a question of Aaronson~\cite{Aaronson2021Open}. We also obtain an exponential separation for a Boolean promise problem on permutations, where forward in-place queries are unitary but inverse queries are not supplied. Our construction follows Aaronson's suggestion of appending fixed random garbage to a Simon function. Let X={0,1}nX=\{0,1\}^nX={0,1}n and N=2nN=2^nN=2n. We use the injection fh,r(x)=(h(x),x,rx)f_{h,r}(x)=(h(x),x,r_x)fh,r​(x)=(h(x),x,rx​), where h:X→Xh:X\to Xh:X→X is promised to be either a permutation or a Simon function, and r:X→Xr:X\to Xr:X→X is an arbitrary tag table that is reused on every query. The resulting problem is solvable with at most n+2n+2n+2 standard queries, but requires Θ(N)Θ(\sqrt N)Θ(N​) forward-erasing queries, matching classical collision sampling. Embedding these instances into permutations, with the copy of xxx replaced by a single bit that keeps the embedding injective, gives a promise problem on permutations of L=4N2L=4N^2L=4N2 elements that requires O(log⁡L)O(\log L)O(logL) standard queries versus Θ(L1/4)Θ(L^{1/4})Θ(L1/4) forward in-place queries. The lower bounds use the recording method. We replace each query by a nearby contraction that records cells of a purified tag table. After TTT queries, tracing out the purified tag table yields a sum of positive-semidefinite contributions, each depending on hhh at no more than TTT addresses. A query-by-query hybrid bounds the trace-norm difference between the actual and auxiliary final operators by O(T/N)O(T/\sqrt N)O(T/N​). Random permutations and random Simon functions have the same restriction distribution on such a set unless it contains a hidden Simon pair, an event of probability O(T2/N)O(T^2/N)O(T2/N). Consequently, the actual final states in the two cases remain close unless T=Ω(N)T=Ω(\sqrt N)T=Ω(N​), giving the required lower bounds.