Quantum communication complexity
Quantum communication complexity studies the amount of quantum information that spatially separated parties must exchange to compute a function whose input is distributed among them. It is the quantum analogue of communication complexity, in which local computation is treated as free while communication constitutes the measured resource. The subject provides a mathematical framework for separating the effects of communication, prior correlation, computational error, and interaction in distributed information processing.
A standard problem assigns an input (x\in X) to Alice and an input (y\in Y) to Bob. Their objective is to determine a value (f(x,y)), where
[ f:X\times Y\rightarrow Z, ]
by exchanging quantum systems according to an agreed protocol. The communication cost is the total number of transmitted qubits, usually evaluated in the worst case over all valid input pairs. Depending on the model, the parties may begin with shared entanglement, may use private or shared randomness, and may be permitted a bounded probability of error.
The theory is concerned primarily with asymptotic relations between input length and communication cost. Local computation is not charged because the model isolates the informational constraints created by partitioning the input. Consequently, a protocol can involve arbitrarily complicated unitary transformations or measurements without affecting its stated communication complexity.
Historical development
The classical communication model was formulated by Andrew Yao in 1979. His model converted distributed computation into the study of protocols represented by decision trees, combinatorial rectangles, and probability distributions over transcripts. Yao introduced the quantum version in 1993, defining protocols in which communicated messages are quantum states and proving an early separation between quantum and deterministic classical communication.
A second foundational development concerned prior entanglement. In 1997, Richard Cleve and Harry Buhrman showed that shared entangled states could reduce the communication required for certain distributed tasks even when the entanglement itself conveyed no signal before the protocol began. This result established entanglement-assisted communication complexity as a distinct model rather than merely a reformulation of quantum message transmission.
During the late 1990s, You Watanabe analyzed interactive quantum protocols in the bounded-error setting and related their state transformations to classical transcript methods. Her work formed part of the period in which the field’s basic distinctions among qubit communication, prior entanglement, and allowable error were standardized.
Subsequent lower-bound theory was developed through methods connecting communication protocols to approximation theory. Alexander Razborov established strong bounds for symmetric predicates by representing their acceptance probabilities through low-degree polynomial approximations. Hartmut Klauck developed discrepancy-based and rectangle-based arguments for several quantum models. These results clarified that quantum communication can produce large improvements for particular problems without eliminating the underlying information requirements of distributed computation.
Formal models
A quantum communication protocol consists of an initial state, a sequence of local operations, transmitted message registers, and a final measurement. Alice’s operations may depend on (x), while Bob’s operations may depend on (y). At each communication round, one party transfers a register to the other. The protocol terminates when a designated party measures part of the resulting state and produces an output.
For a function (f), the notation (Q_\varepsilon(f)) commonly denotes the minimum number of communicated qubits among protocols that compute (f) with error at most (\varepsilon) on every input. The constant-error quantity (Q(f)) generally refers to a fixed value such as (\varepsilon=1/3), because standard error-reduction constructions change the cost by a controlled multiplicative factor.
The exact quantum communication complexity, denoted (Q_E(f)), requires the output to equal (f(x,y)) with probability one. Exact protocols are more restrictive than bounded-error protocols and may have substantially different complexity. A protocol with one-sided error must be exact on one output class while allowing bounded error on the other. These variants correspond to different approximation properties of the function’s communication matrix.
Entanglement-assisted communication
In an entanglement-assisted model, Alice and Bob initially share a state
[ \lvert\psi\rangle\in\mathcal H_A\otimes\mathcal H_B ]
that is independent of their inputs. They may perform input-dependent local operations on their respective subsystems, but the no-communication theorem prevents the shared state from transmitting information by itself. Communication becomes possible only when a message register is sent.
Prior entanglement changes the relationship between classical and quantum messages. Through superdense coding, one transmitted qubit can carry two classical bits when an appropriate entangled pair has already been shared. Conversely, quantum teleportation converts the transmission of one unknown qubit into two classical bits of communication together with one shared entangled pair. These transformations imply constant-factor relations between several entanglement-assisted models, although they do not make all models equivalent when interaction patterns or message types are restricted.
One-way and interactive protocols
A one-way protocol permits a single message from Alice to Bob, after which Bob produces the output. Its cost reflects how efficiently Alice’s input can be encoded into a quantum state that supports the measurements associated with Bob’s possible inputs. This setting is closely connected to quantum random access codes, which encode classical data into quantum states while preserving the ability to recover selected information.
Interactive protocols allow messages in both directions. Interaction can reduce communication because each message may depend on information extracted from earlier messages. The global state after (r) rounds has the schematic form
[ \lvert\psi_{x,y}^{(r)}\rangle
U_r^{(x,y)}\cdots U_2^{(x,y)}U_1^{(x,y)} \lvert\psi_0\rangle, ]
where each unitary is local to the party acting during that round, apart from the relabeling of a transmitted register. The dependence on both inputs arises indirectly through the protocol history rather than through any party’s direct access to the other party’s input.
Representative problems
The equality function asks whether two (n)-bit strings are identical. Classical randomized protocols with shared randomness solve equality using constant communication at constant error, so the problem does not yield an exponential advantage under every comparison of models. In the one-way setting without shared randomness, however, quantum fingerprinting produces a short quantum state representing each input. A referee can compare two such states using a measurement related to the swap test, giving exponentially shorter fingerprints than deterministic classical descriptions.
The set-disjointness function assigns a bit string to each party and asks whether there is an index at which both strings contain a (1). Its bounded-error randomized classical complexity is (\Theta(n)). Quantum protocols evaluate the function using (O(\sqrt n)) qubits up to model-dependent logarithmic factors, through distributed forms of Grover's algorithm. Matching lower bounds show that the quadratic reduction reflects the correct asymptotic scale rather than a limitation of a particular protocol.
The inner-product function returns
[ \operatorname{IP}_n(x,y)
\left(\sum_{i=1}^{n}x_i y_i\right)\bmod 2. ]
Its communication matrix has strong spectral and discrepancy properties, which force linear communication in standard bounded-error quantum models. The function therefore serves as a canonical example in which quantum messages do not produce a sublinear protocol despite the availability of interference and entanglement.
Partial functions and promise problems can display larger separations than total functions. A partial function is defined only on a specified subset of (X\times Y), allowing a protocol to exploit structural promises about valid inputs. Several exponential quantum advantages occur in this setting. For total functions, known relationships among rank, approximation, and information measures impose stronger constraints on the possible separations.
Lower-bound methods
A lower bound proves that every protocol in a specified model must communicate at least a given number of qubits. Because a (q)-qubit message can inhabit a (2^q)-dimensional space, dimension counting supplies elementary bounds in restricted settings. General interactive protocols require methods that account for how local operations and communication alter correlations between the parties.
Rank and factorization
For a Boolean function (f), its communication matrix (M_f) has rows indexed by (x), columns indexed by (y), and entries determined by (f(x,y)). Exact protocols impose algebraic restrictions on matrices describing their acceptance probabilities. Matrix rank and related factorization parameters therefore yield lower bounds on exact or low-error communication.
In quantum models, positive semidefinite factorizations arise naturally because measurement probabilities have the form
[ \Pr[\text{accept}\mid x,y]
\operatorname{Tr}(A_xB_y) ]
for suitable positive semidefinite operators in certain protocol formulations. The minimum dimension of such a factorization is related to positive semidefinite rank, which also appears in optimization and the study of extended formulations.
Polynomial methods
The acceptance probability of a low-communication quantum protocol can often be approximated by a polynomial of controlled degree in parameters describing the input relation. For symmetric predicates, averaging over permutations reduces the analysis to a univariate polynomial. Results from approximation theory, including bounds on how rapidly a low-degree polynomial can change, then constrain the protocol’s success probability.
This method is particularly effective for disjointness and related predicates. The protocol’s quantum dynamics are not simulated step by step. Instead, the low communication cost is converted into a low-complexity algebraic representation, and the target function is shown not to admit such a representation below a particular degree.
Discrepancy and corruption bounds
The discrepancy method measures how closely a function’s output distribution can be balanced over product subsets of the input space. Low discrepancy indicates that large combinatorial rectangles provide little information about the function value. Quantum protocols are not themselves partitions into classical rectangles, but their acceptance matrices satisfy norm inequalities that preserve a connection to discrepancy.
Corruption-style arguments examine distributions under which any sufficiently large rectangle contains a controlled fraction of incorrectly labeled inputs. Quantum analogues replace direct rectangle counting with operator norms or generalized factorization norms. These methods yield lower bounds for functions whose hardness is visible through global distributional structure.
Information complexity
Quantum information complexity measures how much information about one party’s input becomes available to the other during a protocol. It distinguishes communicated qubits from the information actually revealed by them, since an interactive message may be highly correlated with registers already held by the recipient.
The quantum conditional mutual information,
[ I(X:M\mid Y), ]
quantifies the information about Alice’s classical input (X) contained in a message register (M), conditioned on Bob’s input (Y). Summing suitable directional contributions across rounds produces an information cost. Because communication bounds information transfer, information-complexity lower bounds imply communication lower bounds. The framework also supports direct-sum and direct-product results concerning the resources required to solve many independent instances.
Relation to classical complexity
Every classical randomized protocol can be embedded in a quantum protocol by representing classical messages in orthogonal basis states. It follows that quantum communication complexity is no greater than the corresponding classical complexity when the models have equivalent access to randomness and prior correlations.
The reverse simulation generally incurs overhead. Teleportation converts a qubit protocol with prior entanglement into a classical communication protocol that retains access to that entanglement, but it does not produce an ordinary randomized classical protocol because the shared entangled state remains a nonclassical resource. Classical simulation without entanglement can require substantially more communication.
Quantum advantages therefore depend on the comparison being made. A separation may concern exact communication rather than bounded-error communication. It may arise only in the one-way model, or it may rely on a promise restricting the valid inputs. Statements of quantum advantage are consequently properties of explicitly specified pairs of models rather than of quantum communication in isolation.
Connections to other fields
Quantum communication complexity provides lower-bound techniques for quantum query complexity, streaming algorithms, and distributed data processing. A streaming algorithm can sometimes be converted into a communication protocol by partitioning the input stream between two parties. A communication lower bound then limits the memory available to the streaming computation.
The field is also connected to nonlocal games. In a nonlocal game, separated players respond to questions without communicating after the game begins, although they may share entanglement beforehand. Communication complexity instead permits explicit messages and measures their total size. Transformations between these models relate communication bounds to violations of Bell inequalities and to the geometry of quantum correlations.