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.

REFERENCES

• 1: http://www.idquantique.com/.
• 2: S. Aaronson and A. Ambainis. Quantum search of spatial regions. Theory of Computing, 1:47--79, 2005.
• 3: Harold Abelson, Lower Bounds on Information Transfer in Distributed Computations, Journal of the ACM (JACM), v.27 n.2, p.384-392, April 1980 [doi>10.1145/322186.322200]
• 4: P. Aliferis, D. Gottesman, and J. Preskill. Quantum accuracy threshold for concatenated distance-3 codes. Quantum Information and Computation, 6:97--165, 2006.
• 5: Andris Ambainis, A new protocol and lower bounds for quantum coin flipping, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.134-142, July 2001, Hersonissos, Greece [doi>10.1145/380752.380788]
• 6: A. Ambainis , M. Mosca , A. Tapp , R. de Wolf, Private quantum channels, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.547, November 12-14, 2000
• 7: P. K. Aravind. Bell's theorem without inequalities and only two distant observers. Foundations of Physics Letters, 15:397--405, 2002.
• 8: Howard Barnum , Claude Crépeau , Daniel Gottesman , Adam Smith , Alain Tapp, Authentication of Quantum Messages, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.449-458, November 16-19, 2002
• 9: J. S. Bell. On the Einstein-Podolsky-Rosen paradox. Physics, 1:195--200, 1964.
• 10: Michael Ben-Or , Claude Crepeau , Daniel Gottesman , Avinatan Hassidim , Adam Smith, Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.249-260, October 21-24, 2006 [doi>10.1109/FOCS.2006.68]
• 11: C. H. Bennett and G. Brassard. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, pages 175--179, 1984.
• 12: C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Physical Review Letters, 70:1895--1899, 1993.
• 13: Guido Berlin , Gilles Brassard , Felix Bussieres , Nicolas Godbout, Loss-Tolerant Quantum Coin Flipping, Proceedings of the Second International Conference on Quantum, Nano and Micro Technologies (ICQNM 2008), p.1-9, February 10-15, 2008 [doi>10.1109/ICQNM.2008.17]
• 14: G. Brassard. Quantum communication complexity. Foundations of Physics, 33:1593--1616, 2003.
• 15: G. Brassard, A. Broadbent, J. Fitzsimons, S. Gambs, and A. Tapp. Anonymous quantum communication. In Proceedings of 13th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2007), pages 460--473, 2007.
• 16: G. Brassard, A. Broadbent, and A. Tapp. Quantum pseudo-telepathy. Foundations of Physics, 35:1877--1907, 2005.
• 17: G. Brassard, R. Cleve, and A. Tapp. Cost of exactly simulating quantum entanglement with classical communication. Physical Review Letters, 83:1874--1878, 1999.
• 18: H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Physical Review Letters, 87:167902 {4 pages}, 2001.
• 19: Harry Buhrman , Richard Cleve , Avi Wigderson, Quantum vs. classical communication and computation, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.63-68, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276713]
• 20: H. Buhrman and H. Röhrig. Distributed quantum computing. In Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science 2003 (MFCS 2003), pages 1--20, 2003.
• 21: H. Buhrman, P. Høyer W. van Dam, and A. Tapp. Multiparty quantum communication complexity. Physical Review A, 60:2737--2741, 1999.
• 22: F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt. Proposed experiment to test local hidden-variable theories. Physical Review Letters, 23:880--884, 1969.
• 23: R. Cleve and H. Buhrman. Substituting quantum entanglement for communication. Physical Review A, 56:1201--1204, 1997.
• 24: Richard Cleve , William Slofstra , Falk Unger , Sarvagya Upadhyay, Perfect Parallel Repetition Theorem for Quantum XOR Proof Systems, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.109-114, June 13-March 16, 2007 [doi>10.1109/CCC.2007.24]
• 25: Richard Cleve , Wim van Dam , Michael Nielsen , Alain Tapp, Quantum Entanglement and the Communication Complexity of the Inner Product Function, Selected papers from the First NASA International Conference on Quantum Computing and Quantum Communications, p.61-74, February 17-20, 1998
• 26: Henk C.A. van Tilborg, Encyclopedia of Cryptography and Security, Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 27: A. Einstein, B. Podolsky, and N. Rosen. Can quantum-mechanical description of physical reality be considered complete? Physical Review, 47:777--780, 1935.
• 28: Dmitry Gavinsky , Pavel Pudlák, Exponential Separation of Quantum and Classical Non-interactive Multi-party Communication Complexity, Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, p.332-339, June 22-26, 2008 [doi>10.1109/CCC.2008.27]
• 29: D. Gottesman and I. Chuang. Quantum digital signatures. Available as http://arxiv.org/abs/quant-ph/0105032, 2001.
• 30: D. M. Greenberger, M. A. Horne, and A. Zeilinger. Going beyond Bell's theorem. In Bell's Theorem, Quantum Theory and Conceptions of the Universe, pages 69--72, 1988.
• 31: Gus Gutoski , John Watrous, Toward a general theory of quantum games, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250873]
• 32: A. Holevo. Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii, 9:3--11, 1973. English translation in Problems of Information Transmission, 9:177--183, 1973.
• 33: Phillip Kaye , Raymond Laflamme , Michele Mosca, An Introduction to Quantum Computing, Oxford University Press, Inc., New York, NY, 2007
• 34: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 35: A. K. Lenstra and H.W. Lenstra, Jr., editors. The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics. Springer, 1993.
• 36: A. K. Lenstra , H. W. Lenstra, Jr. , M. S. Manasse , J. M. Pollard, The number field sieve, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.564-572, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100295]
• 37: D. Leung, B. Toner, and J.Watrous. Coherent state exchange in multi-prover quantum interactive proof systems. Available as http://arxiv.org/abs/0804.4118, 2008.
• 38: S. Massar, D. Bacon, N. J. Cerf, and R. Cleve. Classical simulation of quantum entanglement without local hidden variables. Physical Review A, 63:052305 {8 pages}, 2001.
• 39: T. Maudlin. Bell's inequality, information transmission, and prism models. In Proceedings of the Biennial Meeting of the Philosophy of Science Association, volume one: contributed papers, pages 404--417, 1992.
• 40: N. D. Mermin. Quantum mysteries revisited. American Journal of Physics, 58(8):731--734, 1990.
• 41: N. David Mermin, Quantum Computer Science: An Introduction, Cambridge University Press, New York, NY, 2007
• 42: C. Mochon. Quantum weak coin flipping with arbitrarily small bias. Available as http://arxiv.org/abs/0711.4114, 2007.
• 43: Ilan Newman, Private vs. common random bits in communication complexity, Information Processing Letters, v.39 n.2, p.67-71, July 31, 1991 [doi>10.1016/0020-0190(91)90157-D]
• 44: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 45: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 46: Ran Raz, Exponential separation of quantum and classical communication complexity, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.358-367, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301343]
• 47: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 48: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 49: A. Steane and W. van Dam. Physicists triumph at guess my number. Physics Today, 53:35--39, 2000.
• 50: B. F. Toner and D. Bacon. Communication cost of simulating Bell correlations. Physical Review Letters, 91:187904 {4 pages}, 2003.
• 51: J. Watrous, Succinct quantum proofs for properties of finite groups, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.537, November 12-14, 2000
• 52: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]
• 53: A. C.-C. Yao. Quantum circuit complexity. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science (STOC 1993), pages 222--227, 1993.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Physics

General Terms:
Design

Keywords:
communication complexity, pseudo-telepathy, quantum games, simulation of entanglement