Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources

Abstract

Quantum systems are known to offer advantages over their classical counterpart in communication complexity protocols, where the aim is to minimize the amount of information exchange between distant parties to compute global functions of their distributed inputs. In this work, we establish that any one-way communication protocol implemented using a prime-dimensional quantum system -- restricted to stabilizer-state encodings and Clifford-operation decodings -- can be exactly simulated by transmitting a classical system of the same dimension, given access to shared randomness between the sender and receiver. In direct analogy with the Gottesman-Knill theorem, which attributes quantum computational speedup to non-stabilizer resources, commonly known as the magic resources, our result identifies the same non-stabilizer resources as the essential ingredient for the quantum advantage in one-way communication complexity. Furthermore, we present explicit tasks where even a 'minimal magic resource' suffices to achieve a provable quantum advantage, highlighting its efficient use in communication protocols.

Accepted in Physical Review A. Close to the published version

References in corpus (37)

• Quantum Teleportation is a Universal Computational Primitive
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Quantum Computing with Very Noisy Devices
• Non-locality and Communication Complexity
• Contextuality supplies the magic for quantum computation
• A new proof for the existence of mutually unbiased bases
• The Resource Theory of Stabilizer Computation
• Substituting Quantum Entanglement for Communication
• Quantum advantage with shallow circuits
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Negative Quasi-Probability as a Resource for Quantum Computation
• Hudson's Theorem for finite-dimensional quantum systems
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Violation of Bell's inequality: criterion for quantum communication complexity advantage
• Preparation contextuality powers parity-oblivious multiplexing
• Magic state distillation in all prime dimensions using quantum Reed-Muller codes
• Quantum Random Access Codes using Single $d$-level Systems
• Efficiently computable bounds for magic state distillation
• No-hypersignaling principle
• Classical information storage in an $n$-level quantum system
• Quantum contextuality provides communication complexity advantage
• Efficient classical simulation of Clifford circuits with nonstabilizer input states
• Quantum random access codes and incompatibility of measurements
• Communication tasks with infinite quantum-classical separation
• A single $T$-gate makes distribution learning hard
• Limited preparation contextuality in quantum theory and its relation to the Cirel'son bound
• Magic-induced computational separation in entanglement theory
• Does violation of a Bell inequality always imply quantum advantage in a communication complexity problem?
• Constraints on magic state protocols from the statistical mechanics of Wigner negativity
• Magic Resource Can Enhance the Quantum Capacity of Channels
• Simple Communication Complexity Separation from Quantum State Antidistinguishability
• Quantum Advantages in (n,d)->1 Random Access Codes
• Classical analogue of quantum superdense coding and communication advantage of a single quantum system
• Prepare-and-Magic: Semi-Device Independent Magic Certification in the Prepare-and-Measure Scenario
• Scalable & Noise-Robust Communication Advantage of Multipartite Quantum Entanglement
• Stronger Nonlocality in GHZ States: A Step Beyond the Conventional GHZ Paradox