Communication tasks with infinite quantum-classical separation

Christopher Perry; Rahul Jain; Jonathan Oppenheim

Source-linked AI summary

Communication tasks with infinite quantum-classical separation

Christopher Perry, Rahul Jain, Jonathan Oppenheim

arXiv:1407.8217v4Jul 30, 2014quant-ph

TL;DR

The paper asks whether quantum resources can produce an unbounded advantage over classical communication in an exclusion task. It constructs a quantum strategy and compares it with classical and entanglement-assisted protocols. The quantum strategy reveals information tending to zero, while classical information cost is nearly n bits and entanglement-assisted classical communication can be constant.

Problem
The paper studies how much information and communication are required for Alice and Bob to solve the exclusion game with zero error.
Source: §2 · p. 7, Appendix C · p. 12
Method
The paper analyzes one-way classical and quantum protocols, constructs a PBR-inspired quantum strategy, and studies classical communication with shared entanglement and bounded abort probability.
Source: §2 · p. 7, Appendix B · p. 10, Appendix D · p. 15
Results
Quantum information cost tends to zero, classical information cost is at least n −o(n), and entanglement-assisted classical communication uses log2 k bits for constant k.
Source: Appendix B · p. 10, Appendix C · p. 12, Appendix E · p. 16
Takeaways & Limitations
The exclusion game exhibits an infinite separation between quantum and classical information costs and a constant-versus-linear communication separation when entanglement is available.
Source: Appendix D · p. 15, Appendix E · p. 16

Abstract

from arXiv · show

Quantum resources can be more powerful than classical resources - a quantum computer can solve certain problems exponentially faster than a classical computer, and computing a function of two people's inputs can be done with exponentially less communication with quantum messages than with classical ones. Here we consider a task between two players, Alice and Bob where quantum resources are infinitely more powerful than classical ones. Alice is given a string of length n, and Bob's task is to exclude certain combinations of bits that Alice might have. If Alice must send classical messages, then she must reveal nearly n bits of information to Bob, but if she is allowed to send quantum bits, the amount of information she must reveal goes to zero with increasing n. Next, we consider a version of the task where the parties can only send classical messages but may have access to entanglement. When assisted by entanglement, Alice only needs to send a constant number of bits, while without entanglement, the number of bits Alice must send grows linearly with n. The task is related to the PBR theorem which arises in the context of the foundations of quantum theory.

1. Information Theory

This section defines classical and quantum entropy and mutual-information quantities used to measure information in communication protocols.

Information Theory

Internal information cost quantifies information revealed about each party’s input through the protocol’s messages and public randomness.It is built from conditional mutual information terms.Source: §1 · p. 6
Shannon entropy is bounded by log2 |X|, with equality when X is uniformly distributed over its support.This provides the basic information scale for a classical random variable.Source: §1 · p. 6
Classical mutual information measures dependence between random variables using Shannon entropy and conditional entropy.The conditional form measures remaining uncertainty after conditioning on another variable.Source: §1 · p. 6
Quantum mutual information uses von Neumann entropy for composite quantum systems, including conditional versions.The quantum definitions replace Shannon entropy with von Neumann entropy.Source: §1 · p. 6

2. Classical Communication Protocols

This section defines one-way zero-error classical and quantum communication protocols and the information-cost measures used to analyze them.

Classical Communication Protocols

One-way protocols restrict communication to a message from Alice to Bob, with classical and quantum messages denoted MC and MQ.The exclusion game requires Bob to evaluate the task with zero error after receiving the message.Source: §2 · p. 7
Classical and quantum communication complexity are the minimum worst-case message lengths among protocols that solve the task with zero error.Classical cost is measured in bits, whereas quantum cost is measured in qubits.Source: §2 · p. 7
Internal information cost is the sum of each party’s conditional information revealed by the protocol, reducing to I(X : π(X) |Y) for one-way communication.The one-way reduction applies when communication is only from Alice to Bob.Source: §2 · p. 7
For independent uniform inputs, classical one-way information cost equals H(X) − H(X|MC), linking revealed information to residual uncertainty.The derivation uses independence of X and Y and uniformity of X.Source: §2 · pp. 7–8
A one-way quantum protocol’s information cost is bounded by twice the von Neumann entropy of Alice’s quantum message.The bound follows from the Araki–Lieb inequality.Source: §2 · p. 8

a. Protocols with abort

This section formalizes one-way protocols in which Alice may abort with bounded probability while Bob must solve the task without error whenever she does not abort.

a. Protocols with abort

A δ-abort protocol limits Alice’s abort probability to at most δ and requires zero-error evaluation when she continues.The maximum-abort model constrains this probability on every input pair.Source: a. Protocols with abort · p. 8
The classical δ-abort communication complexity is the cost of the cheapest shared-randomness protocol satisfying those abort and zero-error conditions.The definition also distinguishes worst-case and distribution-dependent abort constraints.Source: a. Protocols with abort · p. 8
The entanglement-assisted δ-abort complexity permits shared entangled states while restricting communication to classical messages from Alice to Bob.Bob must still calculate the task with zero error whenever Alice does not abort.Source: a. Protocols with abort · p. 8

Appendix B: Proof of Theorem 1

The appendix constructs a quantum exclusion-game protocol from a prepared state and measurement, proving perfect success while the information Alice reveals tends to zero as n grows.

Appendix B: Proof of Theorem 1

For the stated scaling of m, the quantum protocol satisfies ICµ(MQ) → 0 as n →∞ for every input distribution µ.The message entropy and information complexity both tend to zero in the large-n limit.Source: Appendix B · pp. 10–11
Alice receives x, prepares the state |Ψx(θm)⟩, and sends it to Bob, who selects systems indexed by y and applies a projective measurement.The protocol’s construction uses the systems specified by Bob’s input to produce the answer string.Source: Appendix B · p. 10
The quantum strategy always succeeds because Bob’s measurement outcome is orthogonal to the forbidden string specified by the inputs.The proof states that Bob therefore outputs a valid excluding string with certainty.Source: Appendix B · p. 10
The vanishing information cost is bounded through the entropy of Alice’s message and the small-angle scaling of θm.The proof analyzes θm using bounds and a Taylor expansion around θm = 0.Source: Appendix B · pp. 10–11

Appendix C: Proof of Theorem 2

Under the uniform input distribution, the theorem analyzes classical one-way strategies for the exclusion game and gives information-cost bounds for different scalings of m.

For uniformly distributed independent inputs, any winning one-way public-coin classical strategy must satisfy the theorem’s information-cost bounds.Source: Appendix C · p. 12
When √n = o(m) and m = o(n), the uniform internal information cost obeys IC_unif(MC) ≥ n − o(n).Source: Appendix C · p. 12
The theorem separately considers the linear regime m = αn for a constant α with 0 < α < 1.Source: Appendix C · p. 12

1. Proof of Part 1.

The proof lower-bounds classical information cost by minimizing the set of Alice’s inputs that Bob’s possible answers fail to exclude, using consistency among those answers.

Because Bob must answer correctly with certainty, his private randomness can be fixed, while public coins remain part of the classical message protocol.Source: §1 · p. 12
Each possible answer excludes 2^(n−m) strings, and the full excluded set is the union S(M_C) = ∪_y S_{z_y}.Source: §1 · pp. 12–13
The minimizing answer set has the form A_x = {z_y : z_y = M_y(a_x)}, for a suitably chosen string a_x whose answers differ from Alice’s on every y.Source: §1 · p. 12
The proof counts overlaps among answer masks through pairwise and higher-order intersection quantities such as k_ij, k_123, and r_ij.Source: §1 · pp. 12–13
Choosing mutually consistent answers minimizes excluded-string overlap effects, yielding A_x = {z_y : z_y = M_y(a_x)} for a suitable a_x.Source: §1 · p. 13
After taking a_x to be the all-zero string, the inputs Bob can exclude are precisely those containing at least m zeros, leaving γ_m as the remaining possibility count.Source: §1 · pp. 12–13

2. Proof of Part 2.

The proof of Part 2 invokes a binary-entropy lemma to evaluate the information-cost expression for the specified parameter regimes.

Lemma 5 supplies the asymptotic estimate used to analyze the theorem’s information-cost expression for the stated values of m.Source: §2 · p. 13
The binary entropy function H(q) is the quantity appearing in the lemma’s bound.Source: §2 · p. 13

a. Instance (a).

For m = n^(1−ϵ) with 0 < ϵ < 1, the theorem’s regime satisfies √n = o(m) and m = o(n), producing a near-linear information-cost lower bound.

Instance (a)

This parametrization lies simultaneously in the regimes √n = o(m) and m = o(n).Source: a. Instance (a) · p. 14
IC_unif(M_C) ≥ n − o(n) when m = n^(1−ϵ) for 0 < ϵ < 1.Source: a. Instance (a) · p. 14

b. Instance (b).

For m = αn with 0 < α < 1, the uniform classical information cost of the message is linear in n.

ICunif(MC) ∈ Ω(n) when m = αn with 0 < α < 1.Source: b. Instance (b) · p. 14

Appendix D: Proof of Theorem 3

With bounded abort probability, any one-way public-coin classical strategy still has linear communication cost when m scales as αn.

Any one-way public-coin classical strategy for the exclusion game has communication cost Ω(n), provided Alice aborts with probability at most δ > 0 on each input pair and Bob can produce z_y ≠ M_y(x) when she does not abort.Source: Appendix D · p. 15
Because Bob must answer correctly whenever Alice does not abort, Bob’s private randomness can be fixed and the strategy treated as deterministic.Source: Appendix D · p. 15
Under uniform independent inputs, bounding the conditional entropy after abort and non-abort events yields an Ω(n) information-cost lower bound.Source: Appendix D · p. 15

Appendix E: Proof of Theorem 4

The entanglement-assisted protocol uses constant classical communication while preserving perfect exclusion whenever Alice does not abort. Its construction steers Bob’s states through measurements on shared entanglement and chooses a constant number of replicated sets to bound the abort probability.

An entanglement-assisted strategy uses log2 k bits, with k depending on δ but not n, and succeeds perfectly whenever Alice does not abort.Source: Appendix E · p. 16
The steering construction requires log2 k bits of communication, and k can be chosen constant while maintaining abort probability at most δ.Source: Appendix E · pp. 16, 18, 19
The protocol’s steering measurements map Alice’s input bits to target states on Bob’s systems through outcomes labeled 0 or 1.Source: Appendix E · pp. 16, 18
Alice sends the index of a set whose measurements all yielded outcome 0; otherwise, she aborts and sends an abort symbol.Source: Appendix E · p. 18
When Alice does not abort, Bob obtains the n-state message state and applies the earlier exclusion protocol to produce a winning answer.Source: Appendix E · p. 18
With suitable k, Alice and Bob succeed using a constant amount of classical communication regardless of n.Source: Appendix E · p. 19