Quantum–Classical Equivalence for and -Functions
Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett · 2026
Read Quantum–Classical Equivalence for and -Functions by Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-03249.txt.
Introduction
Bhattacharya, Byramji, Chattopadhyay, Dahiya, and Lovett settle a long-open problem in communication complexity. The question is whether quantum protocols can be vastly cheaper than classical ones for total Boolean functions. The shared guess is that they cannot. Razborov proved this in 2002 for AND-functions whose outer function is symmetric. The general case stayed open for over two decades.
An AND-function applies an outer Boolean function to the pairwise ANDs of two inputs. The team shows that for every outer function, quantum and classical costs of the composed function are linked by a polynomial, up to log factors. Both costs are pinned, up to polynomial loss, by the log of the De Morgan sparsity of the outer function. The proof builds on fresh work about non-sparse Boolean functions, which the team extends. The result closes the conjecture for all AND-functions, not just the symmetric ones Razborov handled.
Catalog record
| CREATOR | Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.03249
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantum–Classical Equivalence for and -Functions Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett Abstract A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for and \and -functions of the form F ( x , y ) = f ( x 1 ∧ y 1 , … , x n ∧ y n ) , F(x,y)=f(x_{1}\land y_{1},\ldots,x_{n}\land y_{n}), when the outer function f f is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all and \and -functions has remained open and has been posed by several authors. In this work, we settle this problem in a strong way. We show that for every Boolean function f f , the bounded-error quantum and classical deterministic communication complexities of the function f ∘ and 2 f\circ\and_{2} are polynomially related, up to polylogarithmic factors in n n . We prove this by showing that both are characterized—up to polynomial loss—by the logarithm of the De Morgan sparsity of f f . Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett [ 8 ] on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general and \and -functions. 1 Introduction Understanding when/if the laws of quantum mechanics can be exploited to provide significant computational advantage is a major research theme. Two classical results show that indeed quantum algorithms can have surprising power. Shor’s polynomial time algorithm on quantum computers for integer factoring beats all known classical factoring algorithms by an exponential speed-up. Grover search in the quantum query model beats all possible classical algorithms by a quadratic factor. The first result on exponential speed-up is conditional on the hardness of factoring by classical computers. The second result is provable advantage but only quadratic and we know no better is possible in that query model. In this work, we’re concerned with provable exponential advantage for quantum models when the task is to compute a total Boolean function. It is well known that both the factoring problem and the search problem for a marked item that Grover’s algorithm solves, can readily be re-phrased in terms of total Boolean functions. Communication complexity, introduced by Yao [ 41 ] , studies the amount of communication required to compute a function whose input is distributed among multiple parties. Since its inception, communication complexity has become a central tool in theoretical computer science, with applications ranging from streaming algorithms and time–space tradeoffs to data structure lower bounds and circuit complexity. See the textbooks [ 22 , 28 ] for excellent introductions to the area and its applications. In the most standard setting—the two-party model—two players, Alice and Bob, wish to compute a Boolean function F:X\times Y\to\{0,1\} , where Alice receives x\in X and Bob receives y\in Y . They exchange messages according to a pre-agreed protocol in order to compute F(x,y) , with the goal of minimizing the total number of bits communicated in the worst case. Several variants of communication complexity arise depending on the type of interaction allowed and whether the protocol is permitted to err with small probability. In this work, we focus on three such models: two classical models and one quantum model. In the classical deterministic model, the deterministic communication complexity of F , denoted \textrm{D}^{cc}(F) , is the minimum number of bits that must be exchanged by a protocol that computes F(x,y) correctly on all inputs. In the public-coin randomized model, Alice and Bob have access to shared public randomness and are required to compute F(x,y) with error probability at most 1/3 on every input; the corresponding complexity measure is the randomized communication complexity , denoted \textrm{R}^{cc}(F) . The quantum variant of communication complexity, also introduced by Yao [ 42 ] , allows the messages exchanged between the parties to be quantum states (qubits). At the end of the protocol, one of the parties performs a measurement on its quantum state to produce the output. In addition, the parties may share an arbitrary entangled state prior to the start of the protocol, at no communication cost [ 10 ] . The number of qubits exchanged by the best such protocol that computes F(x,y) with error probability at most 1/3 , for the worst input, is called the bounded-error quantum communication complexity of F , and is denoted \textrm{Q}^{cc}(F) . A central question in quantum computation is to understand when quantum models enable efficient solutions to problems that are believed to be hard for classical models. In the context of communication complexity, this question asks when quantum protocols can be super-polynomially more efficient than classical (randomized) protocols, and has been a major driving force behind research in the area. Exponential quantum advantages were discovered early on for structured problems arising from partial functions, sampling problems and relations, see [ 29 , 4 , 2 , 12 , 32 ] . This understanding has been refined over a number of papers, see [ 14 , 13 , 15 ] , with latest work exhibiting exponential quantum advantage over such promised problems even when the quantum protocol is extremely restricted and no restrictions are imposed on competing classical protocols. In a very recent work, exponential quantum advantage was shown for a total search problem in TFNP by Goos et. al. [ 16 ] . However, as re-iterated by [ 16 ] , no such separation is known for total Boolean functions which remains the holy grail of the search for quantum advantage. The largest gap currently known between bounded-error quantum and randomized communication complexity for a total function is only polynomial: a cubic separation (up to polylogarithmic factors), obtained by lifting cubic separations between quantum and randomized query complexity [ 3 , 35 ] . These results have led to the prevailing belief that, in the absence of special structure—most notably for total Boolean functions—quantum and randomized communication complexities are always polynomially related. This belief was explicitly formulated by Shi and Zhu [ 40 ] as the Log-Equivalence Conjecture (LEC). Conjecture 1.1 (Log-Equivalence Conjecture (LEC) [ 40 ] ) . For every total Boolean function, the bounded-error quantum and randomized communication complexities are polynomially related in the two-party communication model. Despite intensive research efforts, the problem of proving or disproving the LEC remains wide open. In light of the lack of progress on general total functions, several authors [ 5 , 31 , 18 , 40 ] have proposed studying composed communication problems of the form F=f\circ g , where g:\{0,1\}^{b}\times\{0,1\}^{b}\to\{0,1\} is a small, preferably constant-size, gadget. Among such restricted classes, \and -functions of the form F(x,y)=f(x_{1}\land y_{1},\ldots,x_{n}\land y_{n}) have received particular attention. This is partly motivated by the fact that some of the most studied problems in communication complexity, such as Set Disjointness and Inner Product , are \and -functions. To the best of our knowledge, \and -functions, especially in the context of quantum communication complexity, were first systematically studied by Buhrman and de Wolf [ 5 ]