Can quantum mechanics help distributed computing?

Abstract

We present a brief survey of results where quantum information processing is useful to solve distributed computation tasks. We describe problems that are impossible to solve using classical resources but that become feasible with the help of quantum mechanics. We also give examples where the use of quantum information significantly reduces the need for communication. The main focus of the survey is on communication complexity but we also address other distributed tasks.

14 pages. Contains some new material

References in corpus (6)

• The Communication Cost of Simulating Bell Correlations
• Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority
• Quantum weak coin flipping with arbitrarily small bias
• Coherent state exchange in multi-prover quantum interactive proof systems
• Multi-partite Quantum Entanglement versus Randomization: Fair and Unbiased Leader Election in Networks
• Characterizing the combinatorics of distributed EPR pairs for multi-partite entanglement

Cited by in corpus (10)

• Local and Distributed Quantum Computation
• Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks
• The GHZ state in secret sharing and entanglement simulation
• Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model
• Correlations for computation and computation for correlations
• Quantum Advantage for the LOCAL Model in Distributed Computing
• What Can be Observed Locally? Round-based Models for Quantum Distributed Computing
• On the Power of Quantum Distributed Proofs
• Can Quantum Communication Speed Up Distributed Computation?
• A Fast Exact Quantum Algorithm for Solitude Verification