⚛️ quantum physics

Quantum Advantage of Permutation-Invariant Functions in Communication Complexity

This paper establishes that while symmetry constraints limit quantum advantage for permutation-invariant functions with fixed alphabets to a quadratic separation, growing alphabets and graph symmetries enable exponential separations between quantum and randomized communication complexities even without prior entanglement or shared randomness.

Original authors: Yunqi Huang, Zekun Ye

Published 2026-10-01

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Yunqi Huang, Zekun Ye

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 authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computing, there is a fundamental question about how much information two people need to exchange to solve a problem together. Imagine two friends, Alice and Bob, who are far apart. Each holds a piece of a puzzle, and they must work together to find the answer without showing each other their entire pieces. In the classical world, where information is just bits of data, they often have to send a lot of messages back and forth. But in the quantum world, where information can exist in strange, overlapping states, they might solve the same puzzle with just a whisper. Scientists have long wondered: what makes a problem easy for quantum computers but hard for classical ones? Is it the size of the puzzle, or is it the shape of the rules?

This question becomes even more interesting when the rules of the puzzle have a special kind of symmetry. In many real-world scenarios, the order in which things appear doesn't matter, only the counts. If Alice and Bob are comparing two lists of items, and the lists are just shuffled versions of each other, the answer should be the same regardless of the shuffle. This is called permutation invariance. For years, researchers have studied how this symmetry affects the advantage quantum computers have over classical ones. A recent study by Yunqi Huang and Zekun Ye dives deep into this specific type of problem, exploring exactly how much faster a quantum computer can be when the rules are symmetric, and discovering that the answer depends entirely on how big the alphabet of symbols is.

The researchers focused on a scenario where Alice and Bob each have a long string of symbols, and they need to determine a property of the combined string. The catch is that the problem must remain the same even if they both shuffle their strings in the exact same way. The team proved that if the set of possible symbols is fixed and small—like a standard alphabet of letters or a fixed set of numbers—the quantum advantage is limited. In these cases, a classical computer can simulate the quantum one, but it might need to send a number of messages that is roughly the square of what the quantum computer sends. This is a significant speedup for the quantum side, but it is not exponential. The classical computer can still catch up, provided it is allowed to send a few extra bits of information related to the length of the strings. The study shows that for these fixed alphabets, the quantum advantage is real but bounded; it cannot grow infinitely large.

However, the story changes dramatically when the alphabet is allowed to grow. If the number of possible symbols increases as the strings get longer, the rules of the game shift. The researchers constructed specific examples where the alphabet size matches the length of the string. In this setting, they found problems where a quantum computer could solve the task with a number of messages that grows very slowly, like the logarithm of the string length. In contrast, a classical computer would need to send a number of messages that grows almost as fast as the string itself. This represents an exponential gap, a massive difference where the quantum computer leaves the classical one far behind. The key to this separation was not just the size of the alphabet, but how the information was hidden within the structure of the data. By encoding the problem into the relative positions of symbols or the specific arrangement of a rigid tree-like structure, the researchers showed that the classical computer is forced to do a tremendous amount of work to find the hidden pattern, while the quantum computer can navigate the structure with ease.

The team also explored a middle ground involving graphs, which are networks of points and lines. They showed that if the problem is about comparing two graphs that are just relabeled versions of each other, the quantum advantage can again become exponential. In one version, the graphs are rigid trees with a fixed shape, and the difficulty comes from how the two copies are aligned. In another version, the graphs can be any connected shape, allowing for even more information to be stored in the structure itself. In both cases, the quantum computer requires only a tiny amount of communication, while the classical computer struggles with a workload that grows polynomially with the size of the graph. These findings clarify the boundaries of quantum power: symmetry does not always guarantee a massive advantage, but when combined with a growing alphabet or complex graph structures, it can unlock a level of efficiency that classical physics simply cannot match.

One of the most important contributions of this work is what it rules out. The researchers demonstrated that you cannot simply remove the dependence on the length of the input strings from the classical simulation. Even with the most advanced quantum tricks, a classical computer cannot solve these symmetric problems with a number of messages that depends only on the quantum cost. It must also account for the size of the input. Furthermore, they showed that the quadratic relationship between classical and quantum costs for fixed alphabets is tight; you cannot improve the exponent to make the classical cost even lower without breaking the laws of communication complexity. The study also confirmed that the logarithmic factors in the equations are necessary, meaning that the classical computer cannot be made arbitrarily efficient by tweaking the constants.

The methods used to reach these conclusions were rigorous and mathematical, relying on a blend of probability theory, polynomial approximation, and graph theory. The researchers did not just guess; they built specific communication protocols to prove their upper bounds and constructed counterexamples to prove their lower bounds. They showed that for fixed alphabets, the best a classical computer can do is a quadratic simulation, and for growing alphabets, the separation is exponential. They also provided a detailed characterization of the quantum cost using a specific measure of how different the possible inputs are, showing that this measure predicts the communication cost with high precision. The work extends previous findings that were limited to binary inputs, generalizing them to any fixed set of symbols and revealing the critical role that the size of the symbol set plays in determining the quantum advantage.

Ultimately, this research provides a clearer map of the landscape of quantum communication. It tells us that while quantum computers offer a powerful edge in symmetric problems, that edge is not infinite. It is constrained by the nature of the symbols being used. If the symbols are fixed, the advantage is strong but manageable. If the symbols grow with the problem, the advantage becomes overwhelming. This distinction helps scientists understand where to look for the next breakthroughs in quantum computing and where to expect classical algorithms to remain competitive. The findings suggest that the path to exponential quantum speedups in communication lies not just in the quantum mechanics of the particles, but in the combinatorial structure of the data itself. By understanding these structural limits, researchers can better design algorithms that leverage the full potential of quantum mechanics without overestimating its capabilities in every scenario.

Technical Summary: Quantum Advantage of Permutation-Invariant Functions in Communication Complexity

Problem Statement
This paper investigates how symmetry constraints, specifically invariance under simultaneous coordinate permutations, influence the quantum advantage in two-party communication complexity. The authors study partial functions $f: [q]^n \times [q]^n \to \{-1, +1, *\}$ that satisfy $f(\pi x, \pi y) = f(x, y)$ for all permutations $\pi \in S_n$ . In this setting, the function's value depends on the "joint type" (the counts of pairs $(x_i, y_i)$ ), which neither party knows locally; Alice knows the row sums (her histogram) and Bob knows the column sums. The central question is whether the relationship between classical randomized complexity ( $R_{pub}$ ) and quantum complexity ( $Q$ or $Q^*$ with entanglement) remains polynomially related under these symmetry constraints, and how this relationship depends on the alphabet size $q$ and input length $n$ .

Methodology
The authors employ a combination of combinatorial analysis, polynomial approximation methods, and symmetry-preserving encodings:

Separation Parameter ( $h_f$ ): The core of the analysis is a new combinatorial parameter, $h(T, U)$ , which measures the "distance" between two joint types $T$ and $U$ with identical margins. This parameter is defined via a maximization over cut events (bipartitions of the alphabet) of the Hellinger distance between the distributions of symbol pairs.
Classical Upper Bound (Batch Recovery): To simulate quantum protocols classically, the authors design a protocol where parties exchange marginal histograms and then estimate the joint type. They use public-coin random linear maps to recover the "disagreement set" (positions where local encodings differ) in a single batch. This allows them to estimate counts with sufficient accuracy to distinguish types, leading to a communication cost dependent on $h_f^{-2}$ .
Quantum Lower Bound (Geometric Reduction): The quantum lower bound relies on reducing the multidimensional problem of distinguishing joint types to a one-dimensional problem on an integer interval.
- They decompose the difference between two types into a sum of "alternating cycles" in the bipartite symbol graph.
- Using a maximum-weight spanning tree, they identify a specific cycle move where the counts on the edges are sufficiently large to support a polynomial approximation argument.
- They apply a uniform polynomial approximation lemma (combining multislice contraction and factorization-norm methods) to show that any quantum protocol distinguishing these types requires a number of qubits proportional to $h_f^{-1}$ .
Symmetry-Preserving Encodings: To demonstrate limitations of the fixed-alphabet results, the authors construct encodings that map hard communication problems (like XOR lifts of Forrelation) into permutation-invariant or graph-invariant settings. These encodings preserve the communication complexity while fixing local structures (e.g., local histograms or graph isomorphism types).

Key Contributions and Results

Quadratic Simulation for Fixed Alphabets:
For any fixed alphabet size $q$ , the authors prove that the public-coin randomized complexity is quadratically bounded by the entanglement-assisted quantum complexity, up to a logarithmic factor in the input length $n$ :
$R_{pub}(f) = O_q(Q^*(f)^2 \log n)$
This extends previous binary-alphabet results (Guan et al., [GHYY25]) to arbitrary fixed alphabets and improves the logarithmic overhead. The bound is tight for binary set disjointness.
Quantum Characterization:
The paper provides a nearly tight characterization of quantum complexity for these functions. They show that $Q^*(f)$ is bounded below and above (up to logarithmic factors) by the inverse of the separation parameter $h_f$ . Specifically, $Q(f) \leq O_q(Q^*(f) \log n)$ , implying that prior entanglement can be removed with only a logarithmic multiplicative overhead for fixed-alphabet permutation-invariant functions.
Necessity of Input-Length Dependence:
The authors demonstrate that the dependence on $\log n$ in the simulation bound is necessary. By encoding communication problems into the Hamming weights of binary strings, they construct functions where $Q(f) = O(\log \log n)$ but $R_{pub}(f) = \Omega((\log n)^{1-\epsilon})$ . This refutes the possibility of a simulation bound that is purely polynomial in $Q^*(f)$ without dependence on $n$ , even for binary alphabets.
Exponential Separations with Growing Alphabets and Graph Symmetries:
The paper establishes that the quadratic bound breaks down when the alphabet size grows with $n$ or when considering graph symmetries:
- Growing Alphabets: For an alphabet of size $n$ , there exist permutation-invariant functions with $Q(f) = O(\log n)$ and $R_{pub}(f) = \Omega(n^{1-\epsilon})$ .
- Graph Invariance: For graphs on $v$ vertices, there exist functions invariant under simultaneous vertex relabeling with $Q(f) = O(\log v)$ and $R_{pub}(f) = \Omega(v^{1-\epsilon})$ .
- Independent Relabeling: If the two parties can relabel their graphs independently, the separation becomes $Q(f) = O(\log v)$ vs. $R_{pub}(f) = \Omega(v^{2-\epsilon})$ .
  These results show that fixing local structures (like histograms or graph isomorphism types) does not eliminate the communication difficulty arising from relative alignment, allowing for exponential quantum advantages.
Obstructions to Improving Exponents:
The paper proves that the quadratic exponent in the fixed-alphabet simulation cannot be improved to $2-\eta$ for any $\eta > 0$ (due to Set Disjointness) and that the logarithmic factor in the quantum upper bound relative to $h_f^{-1}$ is necessary (due to Intersection Parity with fixed margins).

Significance
The paper clarifies the precise scope of quantum advantage in symmetric communication problems. It establishes that for fixed alphabets, symmetry restricts the quantum advantage to at most a quadratic speedup (up to logarithmic factors), extending and refining prior binary results. However, it demonstrates that this restriction is fragile: allowing the alphabet to grow or considering graph symmetries restores the potential for exponential quantum-classical separations. The work highlights that the "hardness" in these symmetric problems often resides in the relative alignment of inputs rather than the local structure, a feature that quantum protocols can exploit efficiently only when the local structure is not too constrained. The results also settle open questions regarding the necessity of input-length dependence in simulation bounds and the tightness of the quadratic exponent.

Technical Summary: Quantum Advantage of Permutation-Invariant Functions in Communication Complexity

More like this