Communication tasks with infinite quantum-classical separation

Abstract

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.

V4: Added affiliation V3: Slight changes to match journal version. V2: Slight modification in entanglement assisted setting - Alice must now abort rather than Bob. Improved proofs in appendices

References in corpus (3)

• On the reality of the quantum state
• Conclusive Exclusion of Quantum States
• Quantum state targeting

Cited by in corpus (25)

• Is the quantum state real? An extended review of $\psi$-ontology theorems
• Operational interpretation of weight-based resource quantifiers in convex quantum resource theories of states
• Using quantum theory to reduce the complexity of input-output processes
• Extreme Quantum Advantage for Rare-Event Sampling
• Imperfect 1-out-of-2 quantum oblivious transfer: bounds, a protocol, and its experimental implementation
• Noncontextuality Inequalities from Antidistinguishability
• Simple Communication Complexity Separation from Quantum State Antidistinguishability
• Simple Information Processing Tasks with Unbounded Quantum Advantage
• Doubly infinite separation of quantum information and communication
• Tight bounds for antidistinguishability and circulant sets of pure quantum states
• Unambiguous quantum state elimination for qubit sequences
• Classical analogue of quantum superdense coding and communication advantage of a single quantum system
• Experimental demonstration of optimal unambiguous two-out-of-four quantum state elimination
• Not-Post-Peierls compatibility under noisy channels
• Single-shot Distinguishability and Anti-distinguishability of Quantum Measurements
• Maximal Elements of Quantum Communication
• Reality, Causality, and Quantum Theory
• Identifying the value of a random variable unambiguously: Quantum versus classical approaches
• Limitation of maximally entangled probes for single-shot distinguishability of unitaries
• POVMs are equivalent to projections for perfect state exclusion of three pure states in three dimensions
• Failure of epistemic models to explain the antidistinguishability of quantum mixed preparations
• How contextuality and antidistinguishability are related
• Partial particle and wave information and weak duality games
• Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources
• Quantum advantage in a unified scenario and secure detection of resources