Abstract
Quantum computing combines the framework of quantum mechanics with that of computer science. In this paper we give a short introduction to quantum computing and survey the results in the area of distributed quantum computing and its applications to physics.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aaronson, S., Ambainis, A.: Quantum search of spatial regions (2003); quant-ph/0303041
Abelson, H.: Lower bounds on information transfer in distributed computations. J. Assoc. Comput. Mach. 27(2), 384–392 (1980); Earlier version in FOCS 1978
Aharonov, D., Ta-Shma, A., Vazirani, U., Yao, A.: Quantum bit escrow. In: Proceedings of STOC 2000, pp. 705–714 (2000)
Ambainis, A.: A new protocol and lower bounds for quantum coin flip**. In: Proceedings of 33rd ACM STOC, pp. 134–142 (2001)
Ambainis, A.: Lower bound for a class of weak quantum coin flip** protocols (2002); quant-ph/0204063
Ambainis, A., Buhrman, H., Dodis, Y., Röhrig, H.: Multiparty quantum coin flip** (2003) (submitted)
Ambainis, A., Schulman, L., Ta-Shma, A., Vazirani, U., Wigderson, A.: The quantum communication complexity of sampling. In: 39th IEEE Symposium on Foundations of Computer Science, pp. 342–351 (1998)
Ambainis, A., Shi, Y.: Distributed construction of quantum fingerprints. quant-ph/0305022 (2003)
Aspect, A., Dalibard, J., Roger, G.: Experimental test of Bell’s inequalities using time-varying analyzers. Phys. Rev. Lett. 49(25), 1804 (1982)
Bell, J.S.: On the Einstein-Podolsky-Rosen paradox. Physics 1 (1964)
Bennett, C., Brassard, G., Crépeau, C., Jozsa, R., Peres, A., Wootters, W.: Tele-porting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Physiscal Review Letters 70, 1895–1899 (1993)
Bennett, C., Wiesner, S.: Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states. Physiscal Review Letters 69, 2881–2884 (1992)
Bennett, C.H., Brassard, G.: Quantum cryptography: Public key distribution and coin tossing. In: Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, pp. 175–179 (1984)
Brassard, G., Cleve, R., Tapp, A.: The cost of exactly simulating quantum entanglement with classical communication. Physical Review Letters 83(9), 1874–1877 (1999)
Buhrman, H., Cleve, R., van Dam, W.: Quantum entanglement and communication complexity. SIAM Journal on Computing 30(8), 1829–1841 (2001); quant-ph/9705033
Buhrman, H., Cleve, R., Watrous, J., de Wolf, R.: Quantum fingerprinting. Physical Review Letters 87(16) (September 26 2001)
Buhrman, H., Cleve, R., Wigderson, A.: Quantum vs. classical communication and computation. In: 30th Annual ACM Symposium on Theory of Computing (1998); quant-ph/9702040
Buhrman, H., de Wolf, R.: Communication complexity lower bounds by polynomials. In: 16th IEEE Annual Conference on Computational Complexity (CCC 2001), pp. 120–130 (2001); cs.CC/9910010
Buhrman, H., Höyer, P., Massar, S., Röhrig, H.: Combinatorics and quantum nonlocality. Accepted for publication in Physical Review Letters (2002)
Buhrman, H., Höyer, P., Massar, S., Röhrig, H.: Resistance of quantum nonlo-cality to imperfections (2003) (manuscript)
Buhrman, H., van Dam, W., Höyer, P., Tapp, A.: Multiparty quantum communication complexity. Physical Review A 60(4), 2737–2741 (1999)
Cleve, R., Buhrman, H.: Substituting quantum entanglement for communication complexity. Physical Review A 56(2), 1201–1204 (1997)
Cleve, R., van Dam, W., Nielsen, M., Tapp, A.: Quantum entanglement and the communication complexity of the inner product function. In: Proceedings of the 1st NASA International Conference on Quantum Computing and Quantum Communications. Springer, Heidelberg (1998)
Dieks, D.: Communication by EPR devices. Phys. Lett. A 92(6), 271–272 (1982)
Einstein, A., Podolsky, B., Rosen, N.: Can quantum-mechanical description of physical reality be considered complete? Phys. Rev. 47, 777 (1935)
Feige, U.: Noncryptographic selection protocols. In: Proceedings of 40th IEEE FOCS, pp. 142–152 (1999)
Frankl, P., Rödl, V.: Forbidden intersections. Trans. Amer. Math. Soc. 300(1), 259–286 (1987)
Goldenberg, L., Vaidman, L., Wiesner, S.: Quantum gambling. Physical Review Letters 88, 3356–3359 (1999)
Grover, L.: A fast quantum mechenical algorithm for database search. In: 28th ACM Symposium on Theory of Computing, pp. 212–218 (1996)
Holevo, A.S.: Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii 9(3), 3–11 (1973); English translation in Problems of Information Transmission, 9, 177–183 (1973)
Høyer, P., de Wolf, R.: Improved quantum communication complexity bounds for disjointness and equality. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol. 2285, pp. 299–310. Springer, Heidelberg (2002); quant-ph/0109068
Hromkovič, J.: Communication Complexity and Parallel Computing. EATCS series: Texts in Theoretical Computer Science. Springer, Heidelberg (1997)
Deutsch, D., Josza, R.: Rapid solutions of problems by quantum computation. Proc. Roy. Soc. London Se. A 439, 553–558 (1992)
Kalyanasundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM J. Discrete Mathematics 5(4), 545–557 (1992)
Kitaev, A.Y.: Quantum coin-flip**. Talk at QIP 2003 (slides and video at MSRI) (December 2002)
Kremer, I.: Quantum communication. Master’s thesis, Computer Science Department, The Hebrew University (1995)
Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)
Lo, H.K., Chau, H.F.: Why quantum bit commitment and ideal quantum coin tossing are impossible. Physica D 120, 177–187 (1998)
Lo, H.-K., Chau, H.F.: Unconditional security of quantum key distribution over arbitrarily long distances March 3 (1998); quant-ph/9803006
Massar, S.: Nonlocality, closing the detection loophole, and communication complexity. Physical Review A 65, 032121 (2002)
Mayers, D.: Unconditional security in quantum cryptography February 10 (1998); quant-ph/9802025
Mayers, D.: Unconditionally secure quantum bit commitment is impossible. Physical Review Letters 78, 3414–3417 (1997)
Mayers, D., Salvail, L., Chiba-Kohno, Y.: Unconditionally secure quantum coin tossing April 22 (1999); quant-ph/9904078
Mehlhorn, K., Schmidt, E.M.: Las Vegas is better than determinism in VLSI and distributed computing (extended abstract). In: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, San Francisco, California, pp. 330–337, May 5-7 (1982)
Newman, I.: Private vs. common random bits in communication complexity. Information Processing Letters 39(2), 67–71 (1991)
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
Nisan, N., Wigderson, A.: On rank vs. communication complexity. Combinatorica 15, 557–566 (1995); Earlier version in FOCS 1994
Raz, R.: Exponential separation of quantum and classical communication complexity. In: Proceedings of 31th STOC, pp. 358-367 (1999)
Razborov, A.A.: Quantum communication complexity of symmetric predicates. Izv. Math. 67(1), 145–159 (2003)
Saks, M.: A robust noncryptographic protocol for collective coin flip**. SIAM J. Discrete Math. 2(2), 240–244 (1989)
Spekkens, R., Rudolph, T.: A quantum protocol for cheat-sensitive weak coin flip** (2002); quant-ph/0202118
Wootters, W.K., Zurek, W.H.: A single quantum cannot be cloned. Nature 299(5886), 802–803 (1982)
Yao, A.C.-C.: Some complexity questions related to distributive computing. In: Proceedings of 11th STOC, pp. 209–213 (1979)
Yao, A.C.-C.: Quantum circuit complexity. In: Proceedings of 34th FOCS, pp. 352–360 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Buhrman, H., Röhrig, H. (2003). Distributed Quantum Computing. In: Rovan, B., Vojtáš, P. (eds) Mathematical Foundations of Computer Science 2003. MFCS 2003. Lecture Notes in Computer Science, vol 2747. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45138-9_1
Download citation
DOI: https://doi.org/10.1007/978-3-540-45138-9_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40671-6
Online ISBN: 978-3-540-45138-9
eBook Packages: Springer Book Archive