Quantum-Classical Equivalence for AND-Functions

This paper resolves a major open problem in quantum communication complexity by proving that for any Boolean function $f$, the bounded-error quantum and classical deterministic communication complexities of the AND-function $f \circ \mathrm{AND}_2$ are polynomially related, a result established by characterizing both complexities via the logarithm of $f$'s De Morgan sparsity.

The Gist

Imagine you are trying to solve a massive puzzle, but the pieces are split between two people, Alice and Bob. They can't see each other's pieces; they can only talk to each other by sending messages. The goal is to figure out the answer to a specific question (like "Do our pieces fit together?") while sending as few messages as possible.

This field of study is called Communication Complexity. For decades, scientists have been asking a big question: Does using quantum mechanics (the weird rules of the very small) give Alice and Bob a superpower? Specifically, can they solve certain problems using exponentially fewer messages if they use quantum physics compared to using normal, classical physics?

For some tricky, partial puzzles, the answer is "Yes, quantum wins big." But for the most common type of puzzle—where the answer is always defined for every possible input (called "total Boolean functions")—everyone suspects the answer is "No." They think quantum and classical methods are roughly the same speed, just with a few extra steps for one or the other.

The Specific Puzzle: The "AND" Game

The authors of this paper focused on a specific, very common type of puzzle called an And-function.

• Imagine Alice has a list of numbers ($x_1, x_2, ...$) and Bob has a matching list ($y_1, y_2, ...$).
• They first check if their numbers match in pairs (e.g., is $x_1$ AND $y_1$ both true? Is $x_2$ AND $y_2$ both true?).
• Then, they feed all those "AND" results into a final rule (a function $f$) to get the final answer.

This setup is famous because it includes real-world problems like checking if two sets of data are completely different (Set Disjointness).

The Big Discovery

Before this paper, we knew that for some of these "AND" puzzles, quantum and classical methods were equally efficient. But for all of them? That was a mystery.

The authors solved it. They proved that for every single "AND" puzzle, no matter how complex the final rule ($f$) is, the quantum method and the classical method are polynomially related.

What does that mean in plain English?
It means quantum computers might be faster, but they aren't exponentially faster. If a classical computer needs to send 1,000 messages, a quantum computer might only need 10 or 100, but it won't drop down to just 1. They are in the same "neighborhood" of difficulty. The gap between them is small, not a canyon.

How Did They Do It? (The "Sparsity" Analogy)

To prove this, the authors had to look at the "DNA" of the puzzle. They used a concept called Sparsity.

Think of a complex rule (the function $f$) as a giant recipe book.

• High Sparsity: The recipe book is huge, with millions of different ingredients and steps. It's very complex.
• Low Sparsity: The recipe is simple, with only a few ingredients.

The authors discovered a hidden link:

1. Complexity of the Recipe: If the recipe (the function) is very complex (high sparsity), then the "AND" puzzle is hard to solve.
2. The Quantum Barrier: They proved that if the recipe is complex, even a quantum computer cannot cheat its way to a solution. The quantum computer is forced to send a lot of messages, roughly proportional to the complexity of the recipe.

They used a clever mathematical trick called a "Restriction-and-Averaging" method. Imagine you have a giant, messy room (the complex puzzle).

1. Restriction: You lock away most of the room, leaving only a few specific items visible.
2. Averaging: You look at the room from many different angles and take an average.

They showed that if you try to use a "cheap" quantum strategy (sending very few messages), this restriction-and-averaging trick would break the strategy. It would force the quantum computer to admit that it actually needs to know more about the room than it thought. This proved that the quantum computer must send more messages than previously hoped for the hardest puzzles.

The "Log-Equivalence" Conjecture

There is a famous guess in the math world called the Log-Equivalence Conjecture. It basically says: "For normal puzzles, the difficulty of the quantum version and the classical version are just different versions of the same thing."

This paper confirms that this guess is true for the entire family of "AND" puzzles. It's a huge step forward in understanding the limits of quantum speed.

Summary

• The Problem: Can quantum computers solve "AND" puzzles exponentially faster than classical computers?
• The Answer: No.
• The Proof: The authors showed that the difficulty of these puzzles is tied to how "complex" the underlying rule is. Because of this complexity, quantum computers are forced to work almost as hard as classical computers.
• The Result: Quantum and classical communication for these problems are "polynomially related," meaning the gap between them is small and manageable, not a magical, exponential leap.

In short, for this specific and important class of problems, nature doesn't give quantum mechanics a "get out of jail free" card. It's a powerful tool, but it's not magic.

Technical Summary

Technical Summary: Quantum–Classical Equivalence for And-Functions

Problem Statement
A central open problem in quantum communication complexity is determining whether quantum protocols can achieve exponential efficiency advantages over classical protocols for computing total Boolean functions. While exponential separations are known for partial functions, relations, and sampling problems, the prevailing conjecture (the Log-Equivalence Conjecture, or LEC) posits that for total Boolean functions, bounded-error quantum communication complexity ($Q_{cc}$) and randomized communication complexity ($R_{cc}$) are polynomially related.

This question has been particularly studied for composed functions of the form $F(x, y) = f(x_1 \land y_1, \dots, x_n \land y_n)$, known as And-functions. While Razborov (2002) resolved the case where the outer function $f$ is symmetric, proving that $Q_{cc}$ and deterministic communication complexity ($D_{cc}$) are polynomially related, the general case for arbitrary Boolean functions $f$ remained open. Furthermore, prior to this work, it was not even established whether $R_{cc}$ and $D_{cc}$ are polynomially related for general And-functions.

Methodology
The authors resolve this problem by establishing a structural characterization of And-functions based on the De Morgan sparsity of the outer function $f$. The sparsity of $f$, denoted $\text{spar}(f)$, is the number of non-zero coefficients in its unique multilinear polynomial representation over the reals.

The proof strategy proceeds in three main stages:

1. Structural Characterization via Restriction Trees:
   The authors extend recent structural results (Chattopadhyay, Dahiya, and Lovett, 2026) to show that any Boolean function $f$ with large sparsity $s$ admits a semi-adaptive max-degree restriction tree. Unlike fully adaptive trees where variable choices depend on previous outcomes, this structure relies on a fixed set of "core variables" $V$. For every assignment of values in $\{0, *\}$ to $V$, the remaining variables can be fixed such that the restricted function retains full degree on the surviving free variables. The depth of this tree is shown to be $\Omega(\log s / \log n)$.

2. Lifting to the Communication Setting:
   The authors lift these restrictions from the domain of $f$ to the two-party communication setting of $f \circ \text{And}_2$. They define a lifting procedure where restrictions on the inner variables $z_i = x_i \land y_i$ are mapped to restrictions on the input pairs $(x_i, y_i)$. Crucially, this lifting introduces "masked variables" (where $x_i$ is free but $y_i$ is fixed to 0, rendering the AND gate 0 regardless of $x_i$).
   The key insight is that under these lifted restrictions, the function $f \circ \text{And}_2$ retains its "hardness" (specifically, its degree) while the structure of the inputs simplifies the analysis of communication protocols.

3. Lower Bounds via Approximate $\gamma_2$ Norm:
   The core technical contribution is proving that large sparsity of $f$ implies a large approximate $\gamma_2$ norm ($\tilde{\gamma}_2$) for the communication matrix of $f \circ \text{And}_2$. The approximate $\gamma_2$ norm is a known lower bound for bounded-error quantum communication complexity.
   The proof employs a restriction-and-averaging argument:

   • They sample a random restriction from the lifted tree and average over the masked variables.
   • This process preserves the high degree of the target function $f \circ \text{And}_2$.
   • Simultaneously, they show that any small-weight rectangle decomposition (which would imply a small $\tilde{\gamma}_2$ norm) is simplified by this process into a low-degree polynomial.
   • This creates a contradiction: a low-degree polynomial cannot approximate a high-degree function. Thus, the approximate $\gamma_2$ norm must be large.

Key Contributions and Results

• Main Theorem (Theorem 1.3): For every total Boolean function $f: \{0,1\}^n \to \{0,1\}$, the logarithm of the approximate $\gamma_2$ norm of $f \circ \text{And}_2$ is lower-bounded by the sparsity of $f$:
  $$\log \tilde{\gamma}_2(f \circ \text{And}_2) = \Omega\left( \left( \frac{\log \text{spar}(f)}{\log n} \right)^{1/3} \right)$$
  (Ignoring polylogarithmic factors in $n$).

• Quantum-Classical Equivalence (Theorem 1.2): By combining the above lower bound with known upper bounds on deterministic complexity in terms of sparsity (Knop et al., 2021), the authors prove that for all And-functions, deterministic, randomized, and bounded-error quantum communication complexities are polynomially related:
  $$D_{cc}(f \circ \text{And}_2) = O\left( Q_{cc}(f \circ \text{And}_2)^7 \cdot (\log n)^2 \right)$$
  $$D_{cc}(f \circ \text{And}_2) = O\left( R_{cc}(f \circ \text{And}_2)^5 \cdot (\log n)^2 \right)$$

• Resolution of the Log-Approximate-Rank Conjecture (LARC) for And-Functions: The authors show that for And-functions, the logarithm of the approximate rank (and the approximate $\gamma_2$ norm) characterizes the randomized communication complexity up to polylogarithmic factors. This stands in contrast to recent work showing LARC is false for general functions (specifically Xor-functions), highlighting that And-functions possess a specific structural regularity.

Significance
The paper settles the long-standing open problem regarding the equivalence of quantum and classical communication complexities for general And-functions. It confirms the intuition, originally suspected by Buhrman and de Wolf (2001), that diverse complexity measures (communication-theoretic, algebraic, and analytic) coincide for this class of functions.

The work is significant because:

1. It extends Razborov's seminal result from symmetric outer functions to all Boolean outer functions.
2. It establishes the first polynomial equivalence between randomized and deterministic communication complexity for general And-functions.
3. It provides a unified framework linking the sparsity of a Boolean function to the communication complexity of its lifted version, utilizing a novel "semi-adaptive" restriction tree structure that bridges the gap between the fully adaptive techniques of previous works and the non-adaptive requirements of analytic lower bounds.

The authors note that while the Log-Equivalence Conjecture remains open for general total Boolean functions, this result represents a major step toward a complete understanding of the conjecture by resolving the And-function case, which includes fundamental problems like Set Disjointness and Inner Product.