Unbounded quantum advantage in communication complexity measured by distinguishability

Abstract

Communication complexity is a fundamental aspect of information science, concerned with the amount of communication required to solve a problem distributed among multiple parties. The standard quantification of one-way communication complexity relies on the minimal dimension of the communicated systems. In this paper, we measure the communication complexity of a task by the minimal distinguishability required to accomplish it, while leaving the dimension of the communicated systems unconstrained. Distinguishability is defined as the maximum probability of correctly guessing the sender's input from the message, quantifying the message's distinctiveness relative to the sender's input. This measure becomes especially relevant when maintaining the confidentiality of the sender's input is essential. After establishing the generic framework, we focus on three relevant families of communication complexity tasks -- the random access codes, equality problems defined by graphs and the pair-distinguishability tasks. We derive general lower bounds on the minimal classical distinguishability as a function of the success metric of these tasks. We demonstrate that quantum communication outperforms classical communication, presenting explicit protocols and utilizing semi-definite programming methods. In particular, we demonstrate unbounded quantum advantage for random access codes and Hadamard graph-based equality problems. Specifically, we show that the classical-to-quantum ratio of minimal distinguishability required to achieve the same success metric escalates polynomially and exponentially with the complexity of these tasks, reaching arbitrarily large values.

arXiv comment14 pages. Published version

References in corpus (25)

• Quantum Cryptography
• Quantum fingerprinting
• Non-locality and Communication Complexity
• Benchmarking an 11-qubit quantum computer
• Observation of Entangled States of a Fully Controlled 20-Qubit System
• Preparation contextuality powers parity-oblivious multiplexing
• Dimension witnesses and quantum state discrimination
• 16-qubit IBM universal quantum computer can be fully entangled
• State independent contextuality advances one-way communication
• Smooth Max-Information as One-Shot Generalization for Mutual Information
• Quantum communication complexity advantage implies violation of a Bell inequality
• Necessary and sufficient condition for quantum state-independent contextuality
• Connections Between Mutually Unbiased Bases and Quantum Random Access Codes
• Quantum contextuality provides communication complexity advantage
• Preparation contextuality as an essential feature underlying quantum communication advantage
• Necessary and sufficient conditions for state-independent measurement contextual scenarios
• Extrema of discrete Wigner functions and applications
• Characterising and bounding the set of quantum behaviours in contextuality scenarios
• Informationally restricted quantum correlations
• Informationally restricted correlations: a general framework for classical and quantum systems
• Measurement incompatibility and quantum advantage in communication
• Quantum prescriptions are more ontologically distinct than they are operationally distinguishable
• Device independent witness of arbitrary dimensional quantum systems employing binary outcome measurements
• Random access codes and non-local resources
• Alternative robust ways of witnessing nonclassicality in the simplest scenario

Cited by in corpus (7)

• Quantum thermodynamic advantage in work extraction from steerable quantum correlations
• Single-shot Distinguishability and Anti-distinguishability of Quantum Measurements
• Limitation of maximally entangled probes for single-shot distinguishability of unitaries
• Limits of Classical correlations and Quantum advantages under (Anti-)Distinguishability constraints in Multipartite Communication
• Single-shot antidistinguishability of unitary operations
• Complexity order of multiple resource algorithms
• Quantum description of reality is epistemically incomplete