⚛️ quantum physics

Optimal Separations Between Randomized and Quantum Query Complexity under Permutation Symmetry

This paper establishes that permutation symmetry significantly limits quantum speedups, proving tight quadratic separations for general permutation-invariant functions and nearly tight polynomial separations for graph and hypergraph properties, thereby improving upon previous cubic and higher-order bounds.

Original author: Yunqi Huang, Lvzhou Li, Zekun Ye, Shenggen Zheng

Published 2026-11-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original author: Yunqi Huang, Lvzhou Li, Zekun Ye, Shenggen Zheng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computing, there is a fundamental question that drives much of modern research: how much faster can a machine be if it uses the strange rules of quantum physics instead of the standard rules of classical physics? To answer this, scientists often use a simplified game called query complexity. Imagine you are trying to solve a puzzle, but you cannot see the whole picture at once. You can only peek at one piece of the puzzle at a time. The cost of solving the puzzle is simply the number of peeks you need to take. A classical computer, which follows the rules of everyday logic, might need to look at thousands of pieces to be sure of the answer. A quantum computer, which can exist in multiple states at once, might find the answer by looking at only a handful. For some very specific, highly structured puzzles, quantum computers have been proven to be exponentially faster, needing almost no peeks compared to the millions a classical machine would require. However, for most general problems, the advantage is much smaller, usually just a polynomial improvement, meaning the quantum machine is faster, but not by a factor of millions.

The big mystery has been how much structure a problem needs to give a quantum computer a massive advantage. If a problem is completely random and unstructured, classical and quantum computers perform similarly. But if the problem has a hidden pattern, quantum machines can exploit it. A specific type of symmetry, where the answer to the problem does not change no matter how you shuffle the order of the pieces, represents a middle ground. It is not entirely random, but it is not highly structured either. For years, researchers wondered if this kind of "shuffling symmetry" was enough to allow quantum computers to pull far ahead of their classical counterparts. The prevailing belief, based on previous work, was that while quantum computers could win, the gap between them and classical machines was limited to a cubic relationship, where the classical machine's effort was roughly the cube of the quantum machine's effort.

A team of researchers has now settled this question with a definitive proof that changes the landscape of what is possible. They demonstrated that for problems with this specific shuffling symmetry, the gap is actually much smaller than previously thought. They proved that a classical computer only needs to look at a number of pieces that is the square of what a quantum computer needs. In other words, if a quantum algorithm solves the problem by peeking at ten pieces, a classical algorithm can solve it by peeking at roughly one hundred. This is a significant improvement over the old belief that the classical computer would need to look at a thousand pieces. The researchers did not just prove this for simple strings of data; they extended their findings to complex shapes like graphs and hypergraphs, which are networks of connections. For these network problems, they showed that the classical effort grows as the power of the quantum effort, where the power depends on the size of the connections in the network. For standard graphs, the classical effort is the fourth power of the quantum effort, a tight bound that improves on the previous sixth-power estimate.

To reach this conclusion, the team developed a new way of simulating quantum behavior using classical methods. They realized that because the problem looks the same no matter how the pieces are shuffled, a classical computer does not need to check every single piece to get a good idea of the whole picture. Instead, it can take a small, random sample of the pieces. The researchers devised a sophisticated mathematical technique to show that this small sample contains enough information to mimic the quantum computer's behavior with high accuracy. They treated the quantum computer's complex internal state as a collection of partial clues and showed that by restricting their view to a random sample of the input, they could approximate the quantum result with a very small error. They then used a clever recursive method to handle the tiny remaining errors, effectively turning a complex quantum calculation into a series of simple classical steps based on that small sample. This approach allowed them to prove that the classical machine could catch up to the quantum machine much faster than anyone had previously calculated.

The team also went further to show that their new limits are nearly the best possible. They constructed specific examples of problems on these networks where the classical computer is forced to work almost as hard as their new upper bound allows. By encoding difficult mathematical problems into the structure of these networks, they created scenarios where the quantum computer could find the answer with very few peeks, while the classical computer needed a number of peeks that was almost exactly the square or the power predicted by their new formulas. This confirms that the gap they found is not just a theoretical possibility but a real, tight boundary. The work effectively closes the door on the idea that shuffling symmetry alone could allow for the massive, exponential speedups seen in other specialized quantum problems. It tells us that for this broad and important class of problems, the quantum advantage is real, but it is strictly bounded by a quadratic or polynomial relationship, not an exponential one. This provides a clearer map for the future of quantum computing, showing exactly where the technology will shine and where classical methods will remain competitive.

Technical Summary: Optimal Separations Between Randomized and Quantum Query Complexity under Permutation Symmetry

1. Problem Statement

The paper investigates the limits of quantum speedups for problems exhibiting permutation symmetry. Specifically, it addresses the relationship between randomized query complexity ( $R_\varepsilon(f)$ ) and quantum query complexity ( $Q_\varepsilon(f)$ ) for two classes of problems:

Permutation-invariant functions: Functions $f: D \subseteq A^N \to \{0,1\}$ where permuting the input positions preserves both the domain and the function value.
Graph and hypergraph properties: Boolean functions defined on graphs or $k$ -uniform hypergraphs where relabeling vertices preserves the promise and the answer.

The central question is: What is the largest possible separation between $R(f)$ and $Q(f)$ for these symmetric problems? While unstructured search provides a quadratic separation ( $R = \Theta(Q^2)$ ), previous results suggested that for symmetric problems, the separation might be larger (e.g., cubic or higher). This work aims to tighten these upper bounds and establish matching lower bounds.

2. Methodology

The authors employ a combination of compressed oracle techniques, residual expansions, and structural encoding to derive their results.

Upper Bounds (Simulation):
The core technique involves simulating a quantum algorithm using a classical randomized algorithm that queries only a small random sample of the input.

Compressed Oracle & Sampling: Building on Zhandry's compressed oracle and Carolan's compressed permutation oracle, the authors replace a full random permutation with a "compressed" version stored in a coherent database. They then restrict the range of this database to a small random sample $S$ of size $s = O(T^2)$ (where $T$ is the quantum query count).
Exact Norm Formula: A key technical innovation is an exact norm formula for the error introduced when restricting the database range to a sample. This allows them to bound the state error introduced by sampling.
Residual Expansion: To handle cases where the quantum algorithm has a small success bias (not just constant error), the authors construct a "residual identity." This expresses the difference between the ideal quantum expectation and the sampled classical expectation as a constant multiple ( $\lambda = 1/8$ ) of another algorithm's signed output expectation. By iterating this identity, they generate a geometric series of postprocessing functions, allowing the simulation to preserve arbitrarily small biases without increasing the sample size.
Hypergraph Compilation: For graph and hypergraph properties, the method is extended by compiling hyperedge queries. A single hyperedge query on $k$ vertices is compiled into $2k$ auxiliary permutation queries. Sampling $O(T^2)$ vertices allows the simulation of the entire induced subgraph with $O(T^{2k})$ queries.

Lower Bounds (Separation):
To prove the tightness of the upper bounds, the authors construct explicit families of promise problems on hypergraphs.

Encoding: They encode an arbitrary $m$ -bit promise problem into an uncolored, connected, simple $k$ -uniform hypergraph on $N = \Theta(m^{1/k})$ vertices.
Structural Recovery: The encoding uses "data vertices" (storing source bits) and "address vertices" (forming a rigid tree structure). The hypergraph's structure allows an algorithm to coherently recover the address of any data vertex using amplitude amplification, despite arbitrary vertex relabeling.
Source Problem: They apply this encoding to the $\ell$ -Forrelation problem (Bansal and Sinha), choosing the order $\ell$ to increase slowly with the input size. This source problem has polylogarithmic quantum complexity but nearly linear randomized complexity.

3. Key Contributions and Results

Theorem 1.1 (Permutation-Invariant Functions):
For any permutation-invariant function over an arbitrary finite alphabet and error $\epsilon \in [1/6, 1/2)$ :
$R_\epsilon(f) = O(Q_\epsilon(f)^2)$
This improves the previous cubic bound ( $O(Q^3)$ ) by Chailloux (2019). The bound is tight, matching the quadratic separation of unstructured search.

Theorem 1.2 (Graph and Hypergraph Properties):
For $k$ -uniform hypergraph properties (with $k \ge 2$ fixed) and $\epsilon \in [1/6, 1/2)$ :
$R_\epsilon(f) = O_k(Q_\epsilon(f)^{2k})$

For graphs ( $k=2$ ), this improves the previous sextic bound ( $O(Q^6)$ ) to a quartic bound ( $O(Q^4)$ ).
For general $k$ , this improves the previous $O(Q^{3k})$ bound to $O(Q^{2k})$ .

Theorem 1.3 (Tightness of Bounds):
The authors construct explicit families of $k$ -uniform hypergraph properties $\{F_N\}$ such that:
$R_{1/3}(F_N) \ge N^{k-o(1)} \quad \text{and} \quad Q_{1/3}(F_N) \le N^{1/2+o(1)}$
Since $Q \approx N^{1/2}$ , this implies $R \approx Q^{2k-o(1)}$ , demonstrating that the upper bounds in Theorem 1.2 are nearly tight.

4. Significance and Claims

The paper claims to resolve the question of the optimal separation between randomized and quantum query complexity for symmetric problems:

Optimality for Strings: It establishes that permutation invariance does not allow for separations larger than quadratic, settling the conjecture that $R(f) = O(Q(f)^2)$ for these functions.
Optimality for Graphs/Hypergraphs: It demonstrates that the symmetry inherent in graph and hypergraph properties (vertex relabeling) limits the quantum advantage to a factor of $2k$ in the exponent, rather than the previously suspected $3k$ or higher.
Methodological Advance: The paper introduces a robust framework for simulating quantum algorithms on symmetric inputs using small samples and residual expansions, which preserves success probabilities even when the bias is arbitrarily small. This technique is applicable to a broader class of symmetric problems beyond the specific cases analyzed.

The authors emphasize that their results are tight for permutation-invariant functions and nearly tight for graph and hypergraph properties, with the gap being only a sub-polynomial factor ( $N^{o(1)}$ ) in the lower bound construction. The work relies on the "unstructured" nature of permutation symmetry to limit quantum speedups, contrasting with problems like Simon's or period-finding where specific algebraic structures enable exponential separations.

Technical Summary: Optimal Separations Between Randomized and Quantum Query Complexity under Permutation Symmetry

1. Problem Statement

2. Methodology

3. Key Contributions and Results

4. Significance and Claims

More like this