Source-linked AI summary
Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication
Philippe Allard Guérin, Adrien Feix, Mateus Araújo, Časlav Brukner
TL;DR
The paper asks whether superposing communication direction can reduce communication complexity beyond causally ordered quantum protocols. It constructs the Exchange Evaluation game using the quantum switch and finds an exponential saving that persists with bounded error.
Problem
No information-processing task was known to obtain an exponential advantage from the quantum switch over causally ordered quantum or classical communication.
Method
The paper encodes Exchange Evaluation inputs into local n-qubit unitaries that commute or anticommute and evaluates them with the quantum switch.
Results
The quantum switch uses n qubits, whereas deterministic causally ordered communication requires Ω(2^n) qubits, and the Ω(2^n) lower bound persists with bounded error.
Takeaways & Limitations
Superposition of causal ordering yields an exponential communication saving for a non-promise tripartite task.
Abstract
from arXiv · showhide
In communication complexity, a number of distant parties have the task of calculating a distributed function of their inputs, while minimizing the amount of communication between them. It is known that with quantum resources, such as entanglement and quantum channels, one can obtain significant reductions in the communication complexity of some tasks. In this work, we study the role of the quantum superposition of the direction of communication as a resource for communication complexity. We present a tripartite communication task for which such a superposition allows for an exponential saving in communication, compared to one-way quantum (or classical) communication; the advantage also holds when we allow for protocols with bounded error probability.
A B C
The paper introduces the Exchange Evaluation game, showing that the quantum switch gives an exponential communication advantage over causally ordered protocols, including bounded-error settings. The task uses unitaries encoding distributed inputs so that their commutation behavior reveals the function value.
- A B C: The causally ordered tripartite problem is reduced to a bipartite task by identifying Bob and Charlie as one party.A lower bound for the resulting one-way bipartite task therefore bounds causally ordered tripartite communication.
- A B C: The Exchange Evaluation game encodes Alice’s and Bob’s inputs into local n-qubit unitaries that commute or anticommute.The quantum switch then uses this structure to evaluate the task deterministically with n communicated qubits.
- A B C: For deterministic one-way evaluation, the Exchange Evaluation game requires communication growing exponentially with n in the causally ordered case.The lower bound follows because distinct inputs must be perfectly distinguishable for suitable opposing inputs.
- A B C: 1/2(2^n + n − 1) = Ω(2^n) qubits are required causally with dense coding, versus n qubits using the quantum switch.This yields an exponential deterministic separation in communication complexity.
- A B C: The Exchange Evaluation game is not a promise game, unlike most previously known tasks with exponential quantum advantages.The authors identify secure distributed computation as one possible direction for future applications of the protocol.
VC-dimension bounds on the bounded error one-way
The paper uses VC-dimension to lower-bound bounded-error one-way quantum communication for Exchange Evaluation, showing that the cost remains exponential in n.
- VC-dimension is the size of the largest subset shattered by a Boolean function.A set S is shattered when every labeling of S can be realized by some input x.
- The bounded-error one-way quantum complexity Q1_ϵ(f) is related to VC-dimension through a lower bound involving binary entropy H(ϵ).The theorem applies when arbitrary prior shared entanglement is available.
- For Exchange Evaluation, the set S of pairs (y,g) with g = 0 and y ≠ 0 is shattered, giving VC(EEn) ≥ 2^n−1.
- Q1_ϵ(EEn) ≥ (1 − H(ϵ))2^n−2, so one-way communication scales exponentially with n even with bounded error.