Exponential separation of quantum communication and classical information
From MaRDI portal
Abstract: We exhibit a Boolean function for which the quantum communication complexity is exponentially larger than the classical information complexity. An exponential separation in the other direction was already known from the work of Kerenidis et. al. [SICOMP 44, pp. 1550-1572], hence our work implies that these two complexity measures are incomparable. As classical information complexity is an upper bound on quantum information complexity, which in turn is equal to amortized quantum communication complexity, our work implies that a tight direct sum result for distributional quantum communication complexity cannot hold. The function we use to present such a separation is the Symmetric k-ary Pointer Jumping function introduced by Rao and Sinha [ECCC TR15-057], whose classical communication complexity is exponentially larger than its classical information complexity. In this paper, we show that the quantum communication complexity of this function is polynomially equivalent to its classical communication complexity. The high-level idea behind our proof is arguably the simplest so far for such an exponential separation between information and communication, driven by a sequence of round-elimination arguments, allowing us to simplify further the approach of Rao and Sinha. As another application of the techniques that we develop, we give a simple proof for an optimal trade-off between Alice's and Bob's communication while computing the related Greater-Than function on n bits: say Bob communicates at most b bits, then Alice must send n/exp(O(b)) bits to Bob. This holds even when allowing pre-shared entanglement. We also present a classical protocol achieving this bound.
Recommendations
- Exponential separation of quantum and classical communication complexity
- Exponential separation of quantum and classical one-way communication complexity
- Exponential Separation of Quantum and Classical One-Way Communication Complexity
- A new exponential separation between quantum and classical one-way communication complexity
- Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
- Exponential separations for one-way quantum communication complexity, with applications to cryptography
- Entanglement-Assisted Communication of Classical and Quantum Information
- Classical communication costs in quantum information processing
- QUANTUM INFORMATION SPLITTING OF TWO-QUBIT STATE WITH MINIMAL CLASSICAL COMMUNICATION AND MEASUREMENT COMPLEXITY
- Bounded-error quantum state identification and exponential separations in communication complexity
Cited in
(9)- Quantum versus randomized communication complexity, with efficient players
- Exponential separation of quantum and classical communication complexity
- QUANTUM INFORMATION SPLITTING OF TWO-QUBIT STATE WITH MINIMAL CLASSICAL COMMUNICATION AND MEASUREMENT COMPLEXITY
- scientific article; zbMATH DE number 7204275 (Why is no real title available?)
- Exponential Separation of Information and Communication for Boolean Functions
- A hierarchy of constant communication complexity
- Quantum and classical communication complexity of permutation-invariant functions
- Randomized communication and implicit graph representations
- Sample efficient identity testing and independence testing of quantum states
This page was built for publication: Exponential separation of quantum communication and classical information
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4977978)
