Quantum versus Classical Communication Complexity of Total Functions

Quantum versus Classical Communication Complexity of Total Functions

Definitions and mathematical statement

For a total function $F:X\times Y\to\{0,1\}$ on finite sets, Alice receives $x$ and Bob $y$. Let $R^{\mathrm{cc}}_{1/3}(F)$ be the least worst-case number of communicated classical bits with public randomness and error at most $1/3$ on every input. Let $Q^{\mathrm{cc}}_{1/3}(F)$ be the analogous qubit cost allowing free prior entanglement, as fixed in the source. The conjecture is a universal polynomial bound \[ R^{\mathrm{cc}}_{1/3}(F)\le C\left(1+Q^{\mathrm{cc}}_{1/3}(F)\right)^c \] for constants independent of $F,X,Y$. Local computation is not charged. Totality excludes promise restrictions; a result for composed AND-functions or with extra input-size factors does not establish this unrestricted polynomial relation.

Formulation and concept references: [S1].

Short English statement

For every total two-party Boolean problem, is classical randomized communication at most polynomially more expensive than quantum communication with prior entanglement?

Research attempt

Status: UNRESOLVED. We establish basic protocol comparisons, prove a constant-cost randomized protocol for total equality, and contrast it with an exact deterministic lower bound. This rules out a tempting deterministic-rank shortcut but does not give the proposed polynomial simulation of general entangled quantum protocols.

Primary-source scope check.

Bhattacharya--Byramji--Chattopadhyay--Dahiya--Lovett [S1], consulted 1 October 2026, treats functions of the form $f(x_1\wedge y_1,\ldots,x_n\wedge y_n)$ and gives relations up to polylogarithmic factors in input length. Those qualifications matter: an arbitrary total communication matrix need not have this form, and the target bound may not contain an uncontrolled input-length factor. We therefore keep the unrestricted conjecture distinct from that result.

Elementary protocol inequalities.

Let $D(F)$ be deterministic communication cost under the same output convention. A deterministic protocol is a public-coin randomized protocol that ignores its coins, so $R^{\mathrm{cc}}_{1/3}(F)\le D(F)$. A classical bit can be sent as one of two orthogonal qubit states and measured perfectly, so any classical randomized protocol can be simulated quantumly at its communication cost. Shared classical randomness can be obtained by measuring shared entangled pairs. Hence \[ Q^{\mathrm{cc}}_{1/3}(F)\le R^{\mathrm{cc}}_{1/3}(F)\le D(F). \] There is also a trivial input-transmission bound $D(F)\le\lceil\log_2|X|\rceil+1$: Alice sends her input index, Bob evaluates the total function, and, if both outputs are required, returns one bit. The corresponding bound with $Y$ holds by exchanging roles. None bounds classical cost by a polynomial in quantum cost alone, because the input domains can be arbitrarily large.

Total equality has a constant-cost public-coin protocol.

For $x,y\in\{0,1\}^n$, let $\mathrm{EQ}_n(x,y)$ be one exactly when $x=y$. Publicly sample two independent uniformly random vectors $r_1,r_2\in\mathbb F_2^n$. Alice sends the two bits $r_i\cdot x$. Bob accepts precisely when they equal $r_i\cdot y$ for both $i$.

If $x=y$, acceptance is certain. If $x\ne y$, write $z=x-y\ne0$ in $\mathbb F_2^n$. For uniform $r$, the bit $r\cdot z$ is uniform: choose a coordinate where $z$ is one and pair each $r$ with the vector obtained by flipping that coordinate. These two vectors yield opposite dot products. Thus a false equality passes each test with probability $1/2$ and both independent tests with probability $1/4<1/3$. Communication is two bits when Bob alone outputs, or three if Bob returns the answer. The error guarantee holds separately for every input pair, as required.

This proof uses free public randomness. Transmitting the random vectors would cost order $n$ bits and would describe a different protocol resource accounting. It is also a total function: no promise on unequal strings was introduced.

Yet exact deterministic equality needs large communication.

Every leaf of a deterministic communication protocol corresponds to a combinatorial rectangle $A\times B$ of inputs, because each successive message restricts only one player's input given the previous transcript. An accepting leaf for equality can contain at most one diagonal pair $(x,x)$. If it contained distinct $(x,x)$ and $(y,y)$, its rectangle would also contain $(x,y)$, which should be rejected. There are $2^n$ diagonal pairs, so the protocol needs at least $2^n$ accepting leaves.

A binary protocol of worst-case cost $d$ has at most $2^d$ leaves after padding shorter transcripts if necessary. Hence $D(\mathrm{EQ}_n)\ge n$. This lower bound coexists with the constant randomized upper bound. It proves concretely that replacing bounded-error randomized complexity with deterministic complexity in the target would be an unjustified change.

The equality communication matrix is the $2^n\times2^n$ identity matrix and has full real rank. Thus large exact rank by itself also cannot force large bounded-error public-coin communication. A proposed proof using rank must control the appropriate approximation or protocol model, rather than applying an exact deterministic matrix bound to a randomized quantity.

Why unrestricted local computation does not give a simulation.

Both parties may perform arbitrarily much local computation, but they still lack the other input. Numerically describing a quantum message to classical precision can require information depending on Hilbert-space dimension, interaction history, and the desired accumulated error. The number of amplitudes is not bounded polynomially merely by naming the number of transmitted qubits. Free prior entanglement adds another resource that cannot be silently replaced by a small fixed classical shared state.

These observations identify gaps in a naive simulation argument; they are not a lower bound against every classical simulation. A valid proof must exploit totality to obtain a uniform communication bound, with constants independent of both input domains and without an extra input-size factor.

Verification and remaining gap.

The equality error was calculated exactly, and the rectangle argument checks every diagonal input rather than an average input distribution. Shared random bits and prior entanglement were kept distinct from charged communication. No quantum circuit simulation or new communication lower-bound experiment is claimed.

The unresolved step is the proposed universal polynomial relation for all total functions. The special protocol and exact lower bound above are established reference examples, not a separation between the two bounded-error measures. They expose a concrete invalid shortcut while leaving the actual entangled-quantum-to-public-classical simulation problem open in this attempt.

Sources

• S1 Bhattacharya et al., Quantum-Classical Equivalence for And-Functions, ECCC TR26-013 $2026$, Conjecture 1.1. https://eccc.weizmann.ac.il/report/2026/013/download. Formulation source. Consulted 24 September 2026: Introduction and Conjecture 1.1, including public coins and free prior entanglement.