Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication

Abstract

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.

arXiv comment5 pages, 2 figures. Published version

References in corpus (11)

• Quantum correlations with no causal order
• Non-locality and Communication Complexity
• Quantum computations without definite causal structure
• Insecurity of Quantum Secure Computations
• Experimental Superposition of Orders of Quantum Gates
• Computational advantage from quantum-controlled ordering of gates
• Perfect discrimination of no-signalling channels via quantum superposition of causal structures
• Witnessing causal nonseparability
• Quantum superposition of the order of parties as a communication resource
• Complete Insecurity of Quantum Protocols for Classical Two-Party Computation
• Quantum Private Comparison: A Review

Cited by in corpus (142)

• High-dimensional quantum communication: benefits, progress, and future challenges
• Experimental Verification of an Indefinite Causal Order
• Enhanced communication with the assistance of indefinite causal order
• Indefinite Causal Order in a Quantum Switch
• Quantum Metrology with Indefinite Causal Order
• Experimental Quantum Switching for Exponentially Superior Quantum Communication Complexity
• Bell's Theorem for Temporal Order
• Indefinite causal order enables perfect quantum communication with zero capacity channels
• Quantum Switch for the Quantum Internet: Noiseless Communications through Noisy Channels
• Experimental Quantum Communication Enhancement by Superposing Trajectories
• Communication through coherent control of quantum channels
• Computational advantage from quantum superposition of multiple temporal orders of photonic gates
• Communication through quantum-controlled noise
• Time-delocalized quantum subsystems and operations: on the existence of processes with indefinite causal structure in quantum mechanics
• Strict hierarchy between parallel, sequential, and indefinite-causal-order strategies for channel discrimination
• Resource theories of communication
• Communication Enhancement Through Quantum Coherent Control of $N$ Channels in an Indefinite Causal-order Scenario
• Sending classical information via three noisy channels in superposition of causal orders
• Quantum circuits with classical versus quantum control of causal order
• A purification postulate for quantum mechanics with indefinite causal order
• Multipartite Causal Correlations: Polytopes and Inequalities
• Cyclic Quantum Causal Models
• Experimentally feasible computational advantage from quantum superposition of gate orders
• Quantum Temporal Superposition: the case of QFT
• Two-way communication with a single quantum particle
• Experiments on quantum causality
• On the definition and characterisation of multipartite causal (non)separability
• Experimental entanglement of temporal order
• High-dimensional quantum communication complexity beyond strategies based on Bell's theorem
• Experimental Aspects of Indefinite Causal Order in Quantum Mechanics
• Experimental two-way communication with one photon
• Dynamics of quantum causal structures
• Unitary channel discrimination beyond group structures: Advantages of sequential and indefinite-causal-order strategies
• Classical Communications with Indefinite Causal Order for $N$ completely depolarizing channels
• Beyond Shannon Limits: Quantum Communications through Quantum Paths
• Quantification of quantum dynamics with input-output games
• Observer-dependent locality of quantum events
• Causal order as a resource for quantum communication
• Thermodynamics of quantum switch information capacity activation
• Semi-device-independent certification of indefinite causal order
• Semi-device-independent certification of indefinite causal order in a photonic quantum switch
• Coherence Equality and Communication in a Quantum Superposition
• Privacy-preserving quantum federated learning via gradient hiding
• Resource theory of superposition: State transformations
• Thermality, causality and the quantum-controlled Unruh-deWitt detector
• Higher-order Process Matrix Tomography of a passively-stable Quantum SWITCH
• Consequences of preserving reversibility in quantum superchannels
• Evading noise in multiparameter quantum metrology with indefinite causal order
• Quantum superpositions of "common-cause" and "direct-cause" causal structures
• Computational tameness of classical non-causal models
• Deterministic Generation of Multipartite Entanglement via Causal Activation in the Quantum Internet
• Causal and compositional structure of unitary transformations
• Reassessing the advantage of indefinite causal orders for quantum metrology
• Experimental superposition of time directions
• Reassessing thermodynamic advantage from indefinite causal order
• Process Products Need Qualification
• Simulating indefinite causal order with Rindler observers
• Experimental demonstration of input-output indefiniteness in a single quantum device
• Reassessing the computational advantage of quantum-controlled ordering of gates
• Quantum Causal Models
• Quantum steering beyond instrumental causal networks
• Quantum superpositions of causal orders as an operational resource
• Quantum communication through devices with indefinite input-output direction
• Comparing the quantum switch and its simulations with energetically-constrained operations
• Experimental Validation of Enhanced Information Capacity by Quantum Switch in Accordance with Thermodynamic Laws
• Embedding cyclic information-theoretic structures in acyclic spacetimes: no-go results for indefinite causality
• Experimentally demonstrating indefinite causal order algorithms to solve the generalized Deutsch's problem
• Activating information backflow with the assistance of quantum SWITCH
• Causal games of work extraction with indefinite causal order
• Maxwell's two-demon engine under pure dephasing noise
• Semi-Device-Independent Certification of Causal Nonseparability with Trusted Quantum Inputs
• Fundamental limits for realising quantum processes in spacetime
• Correlation Measure Equivalence in Dynamic Causal Structures of Quantum Gravity
• Quantum switch in the gravity of Earth
• Two-qubit causal structures and the geometry of positive qubit-maps
• Classical communication through quantum causal structures
• Quantum coherence in networks
• Quantum communication using a quantum switch of quantum switches
• Improvement in quantum communication using quantum switch
• Breaking the limits of purification: Postselection enhances heat-bath algorithmic cooling
• Quantum enhancement to information acquisition speed
• Composition rules for quantum processes: a no-go theorem
• Circulating Genuine Multiparty Entanglement in Quantum Network
• Memory in quantum processes with indefinite time direction and causal order
• Quantum networks boosted by entanglement with a control system
• Theory of Quantum Gravity Information Processing
• Activation of thermal states by coherently controlled thermalization processes
• Quantum superposition of causal structures as a universal resource for local implementation of nonlocal quantum operations
• Unextendible entangled bases and more nonlocality with less entanglement
• Practical computational advantage from the quantum switch on a generalized family of promise problems
• The SWITCH test for discriminating quantum evolutions
• A no-go theorem for superpositions of causal orders
• Quantum chicken-egg dilemmas: Delayed-choice causal order and the reality of causal non-separability
• Quantum sketching protocols for Hamming distance and beyond
• Quantifying Superpositions Between Quantum Evolutions
• Quantum from principles without assuming definite causal structure
• Interference as an information-theoretic game
• Using Quantum Switches to Mitigate Noise in Grover's Search Algorithm
• A Diagrammatic Approach to Information Transmission in Generalised Switches
• The quantum switch is uniquely defined by its action on unitary operations
• Quantum Supermaps are Characterized by Locality
• Experimental implementation of arbitrary entangled operations
• Network-Device-Independent Certification of Causal Nonseparability
• The Multi-round Process Matrix
• Addressable quantum gates
• Indefinite causal key distribution
• Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
• Revisiting dynamics of quantum causal structures -- when can causal order evolve?
• Parameter estimation via indefinite causal structures
• Tsirelson bounds for quantum correlations with indefinite causal order
• Coherent control of the causal order of entanglement distillation
• Universal quantum computation via quantum controlled classical operations
• Emergent non-Markovianity and dynamical quantification of the quantum switch
• Toward an Experimental Device-Independent Verification of Indefinite Causal Order
• Coherence, superposition, and Löwdin symmetric orthogonalization
• Network mechanism for generating genuinely correlative Gaussian states
• Background Independence and Quantum Causal Structure
• Information Carried by a Single Particle in Quantum Multiple-Access Channels
• Multifold behavior of the information transmission by the quantum 3-switch
• Expressibility, entangling power and quantum average causal effect for causally indefinite circuits
• Self-testing in a constrained prepare-measure scenario sans assuming quantum dimension
• Non-commutativity as a Universal Characterization for Enhanced Quantum Metrology
• Quantum switch as a thermodynamic resource in the context of passive states
• Causality in Higher Order Process Theories
• Optimal quantum precision in noise estimation: Is entanglement necessary?
• A de Finetti theorem for quantum causal structures
• Causal nonseparability and its implications for spatiotemporal relations
• Remote Creation of Quantum Coherence via Indefinite Causal Order
• Sequential device-independent certification of indefinite causal order
• Enhancement of non-Stabilizerness within Indefinite Causal Order
• Breaking absolute separability with quantum switch
• To share and not share a singlet: control qubit and nonclassicality in teleportation
• Entropic uncertainty under indefinite causal order and input-output direction
• Information Exchange in Causally Nonseparable Processes
• Causal influence versus signalling for interacting quantum channels
• Optimal Thermalization under Indefinite Causal Order with Identical and Asymmetric Baths
• Phase-sensitive superposition of quantum states
• Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
• No quantum advantage for violating fixed-order inequalities?
• Features of preparable entangled states in Gaussian quantum networks
• A Profunctorial Semantics for Quantum Supermaps
• Quantum probabilities for the causal ordering of events