nach oben

Erschienen in:

2012 | OriginalPaper | Buchkapitel

Algorithms for Quantum Computers

verfasst von : Jamie Smith, Michele Mosca

Erschienen in: Handbook of Natural Computing

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This chapter surveys the field of quantum computer algorithms. It gives a taste of both the breadth and the depth of the known algorithms for quantum computers, focusing on some of the more recent results. It begins with a brief review of quantum Fourier transform-based algorithms, followed by quantum searching and some of its early generalizations. It continues with a more in-depth description of two more recent developments: algorithms developed in the quantum walk paradigm, followed by tensor network evaluation algorithms (which include approximating the Tutte polynomial).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Bell's Inequalities — Foundations and Quantum Communication

Nächstes Kapitel Physical Implementation of Large-Scale Quantum Computation

Aaronson S, Shi Y (2004) Quantum lower bounds for the collision and the element distinctness problems. J ACM 51(4):595–605. doi: http://doi.acm.org/10.1145/1008731.1008735

Aharonov D, Ambainis A, Kempe J, Vazirani U (2001) Quantum walks on graphs. In: STOC’01: proceedings of the 33rd annual ACM symposium on theory of computing. ACM Press, New York, pp 50–59. doi: http://doi.acm.org/10.1145/380752.380758

Aharonov D, Arad I (2006) The BQP-hardness of approximating the Jones polynomial. http://arxiv.org/abs/quant-ph/0605181

Aharonov D, Arad I, Eban E, Landau Z (2007) Polynomial quantum algorithms for additive approximations of the Potts model and other points of the Tutte plane. http://arxiv.org/abs/quant-ph/0702008

Aharonov D, Jones V, Landau Z (2008) A polynomial quantum algorithm for approximating the Jones polynomial. Algorithmica 55(3):395–421MathSciNetCrossRef

Ambainis A (2003) Quantum walks and their algorithmic applications. Int J Quantum Inform 1:507–518MATHCrossRef

Ambainis A (2004) Quantum walk algorithm for element distinctness. In: Proceedings of the 45th annual IEEE symposium on foundations of computer science, pp 22–31. doi: 10.1109/FOCS.2004.54

Ambainis A, Bach E, Nayak A, Vishwanath A, Watrous J (2001) One-dimensional quantum walks. In: STOC’ 01: proceedings of the 33rd annual ACM symposium on theory of computing. ACM Press, New York, pp 37–49. doi: http://doi.acm.org/10.1145/380752.380757

Ambainis A, Childs A, Reichardt B, Spalek R, Zhang S (2007) Any and-or formula of size n can be evaluated in time n ^{1 ∕ 2+o(1)} on a quantum computer. In: Proceedings of the 48th annual IEEE symposium on foundations of computer science, pp 363–372. doi: 10.1109/FOCS.2007.57

Arad I, Landau Z (2008) Quantum computation and the evaluation of tensor networks. http://arxiv.org/abs/0805.0040

Beaudin L, Ellis-Monaghan J, Pangborn G, Shrock R (2008) A little statistical mechanics for the graph theorist. http://arxiv.org/abs/0804.2468

Bernstein BK, Vazirani U (1997) Quantum complexity theory. SIAM J Comput 26:1411–1473MathSciNetMATHCrossRef

Berry DW, Ahokas G, Cleve R, Sanders BC (2007) Efficient quantum algorithms for simulating sparse Hamiltonians. Commun Math Phys 270:359MathSciNetMATHCrossRef

Boixo S, Knill E, Somma R (2009) Quantum state preparation by phase randomization. http://arxiv.org/abs/0903.1652

Boneh D, Lipton R (1995) Quantum cryptanalysis of hidden linear functions (extended abstract). In: Proceedings of the 15th annual international cryptology conference on advances in cryptology. Lecture notes in computer science, vol. 963. Springer, London, UK, pp 424–437

Boyer M, Brassard G, Høyer P, Tapp A (1998) Tight bounds on quantum searching. Fortschritte der Physik 56(5–5):493–505CrossRef

Brassard G, Høyer P (1997) An exact quantum polynomial-time algorithm for Simon's problem. In: Proceedings of the fifth Israeli symposium on theory of computing and systems (ISTCS’97). IEEE Press, Piscataway, pp 12–23

Brassard G, Høyer P, Mosca M, Tapp A (2002) Quantum amplitude amplification and estimation. Quantum Computation & Information, AMS Contemporary Math Series 305:53–74

Brassard G, Høyer P, Tapp A (1997) Cryptology column — quantum algorithm for the collision problem. ACM SIGACT News 28:14–19CrossRef

Brouwer AE (1989) Distance-regular graphs. Springer, New YorkMATHCrossRef

Childs A (2008) CO781 Topics in quantum information: quantum algorithms. Lecture notes on quantum algorithms. http://www.math.uwaterloo.ca/~amchilds/teaching/w08/co781.html

Childs AM, Cleve R, Deotto E, Farhi E, Gutmann S, Spielman DA (2003) Exponential algorithmic speedup by a quantum walk. In: STOC ’03: proceedings of the 35th annual ACM symposium on theory of computing. ACM Press, New York, pp 59–68. doi: http://doi.acm.org/10.1145/780542.780552

Childs A, van Dam W (2010) Quantum algorithms for algebraic problems. Rev Mod Phys 82(1):1–52

Cleve R, Ekert A, Macchiavello C, Mosca M (1998) Quantum algorithms revisited. Proc Roy Soc Lond A 454:339–354MathSciNetMATHCrossRef

D'Ariano GM, van Dam W, Ekert E, Macchiavello C, Mosca M (2007) General optimized schemes for phase estimation. Phys Rev Lett 98(9):090,501

Das A, Chakrabarti BK (2008) Quantum annealing and analog quantum computation. Rev Mod Phys 80:1061MathSciNetMATHCrossRef

De las Cuevas G, Dür W, Van den Nest M, Briegel HJ (2008) Completeness of classical spin models and universal quantum computation. http://arxiv.org/abs/0812.2368

Deutsch D (1985) Quantum theory, the Church-Turing principle and the universal quantum computer. Proc Roy Soc Lond A 400:97–117MathSciNetMATHCrossRef

Deutsch D, Jozsa R (1992) Rapid solutions of problems by quantum computation. Proc Roy Soc Lond, A 439:553–558MathSciNetMATHCrossRef

Farhi E, Goldstone J, Gutmann S (2007) A quantum algorithm for the Hamiltonian NAND tree. http://arxiv.org/abs/quant-ph/0702144

Feynman R (1982) Simulating physics with computers. Int J Theor Phys 21(6,7):467–488MathSciNetCrossRef

Freedman MH, Kitaev A, Larsen MJ, Wang Z (2001) Topological quantum computation. http://arxiv.org/abs/quant-ph/0101025

Freedman MH, Kitaev A, Wang Z (2000) Simulation of topological field theories by quantum computers. http://arxiv.org/abs/quant-ph/0001071

Geraci J (2008) A BQP-complete problem related to the Ising model partition function via a new connection between quantum circuits and graphs. http://arxiv.org/abs/0801.4833

Geraci J, Lidar DA (2008) On the exact evaluation of certain instances of the Potts partition function by quantum computers. Commun Math Phys 279(3):735–768MathSciNetMATHCrossRef

Grigoriev D (1997) Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines. Theor Comput Sci 180:217–228MathSciNetMATHCrossRef

Grover L (1996) A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th annual ACM symposium on the theory of computing (STOC, 96). ACM Press, New York, pp 212–219

Grover L (1998) A framework for fast quantum mechanical algorithms. In: Proceedings of the 13th annual ACM symposium on theory of computing (STOC' 98). ACM Press, New York, pp 53–62CrossRef

Hirvensalo M (2001) Quantum computing. Series: Natural Computing Series. Springer

Hübener R, Van den Nest M, Dür W, Briegel HJ (2008) Classical spin systems and the quantum stabilizer formalism: general mappings and applications. http://arxiv.org/abs/0812.2127

Jordan S (2008) Quantum computation beyond the circuit model. PhD thesis, MIT University, Cambridge

Karchmer M, Wigderson A (1993) On span programs. In: Proceedings of the 8th IEEE structures in complexity conference. IEEE Press, Piscataway, pp 102–111

Kaye P, Laflamme R, Mosca M (2007) An introduction to quantum computation. Oxford University Press, Oxford, UK

Kempe J (2003) Quantum random walks - an introductory overview. Contemp Phys 44(4):307–327MathSciNetCrossRef

Kitaev AY (1995) Quantum measurements and the Abelian stabilizer problem. http://arxiv.org/abs/quant-ph/9511026

Kitaev A, Shen A, Vyalvi M (2002) Classical and quantum computation. American Mathematical Society, Providence, RIMATH

Magniez F, Nayak A, Roland J, Santha M (2007) Search via quantum walk. In: STOC ’07: proceedings of the 39th annual ACM symposium on theory of computing. ACM, New York, pp 575–584. doi: http://doi.acm.org/10.1145/1250790.1250874

Menezes A, van Oorschot P, Vanstone S (1996) Handbook of applied cryptography. CRC Press, Boca RatonCrossRef

Mermin ND (2007) Quantum computer science: an introduction. Cambridge University Press, CambridgeMATHCrossRef

Mosca M (2001) Counting by quantum eigenvalue estimation. Theor Comput Sci 264:139–153MathSciNetMATHCrossRef

Mosca M (2008) Abelian hidden subgroup problem. In: Kao M-Y (ed) Encyclopedia of algorithms. Springer, Berlin

Mosca M (2009) Quantum algorithms. In: Meyers R (ed) Encyclopedia of complexity and systems science. Springer

Nayak A, Vishwanath A (2000) Quantum walk on the line. http://arxiv.org/abs/quant-ph/0010117

Nielsen M, Chuang I (2000) Quantum computation and quantum information. Cambridge University Press, Cambridge, UKMATH

Reichardt BW, Spalek R (2008) Span-program-based quantum algorithm for evaluating formulas. In: STOC ’08: proceedings of the 40th annual ACM symposium on theory of computing. ACM Press, New York, pp 103–112. doi: http://doi.acm.org/10.1145/1374376.1374394

Santha M (2008) Quantum walk based search algorithms. In: Agrawal M, Du D-Z, Duan Z, Li A (eds) Theory and applications of models of computation. Lecture notes in computer science, vol 4978. Springer, Berlin, Heidelberg, pp 31–46. doi: 10.1007/978-3-540-79228-4_3

Shor P (1994) Algorithms for quantum computation: Discrete logarithms and factoring. In: Proceedings of the 35th annual symposium on foundations of computer science. IEEE Computer Society, Washington, DC, pp 124–134

Shor P (1997) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput 26:1484–1509MathSciNetMATHCrossRef

Simon D (1994) On the power of quantum computation. In: Proceedings of the 35th IEEE symposium on the foundations of computer science (FOCS). IEEE Computer Society, Washington, DC, pp 116–123

Szegedy M (2004) Quantum speed-up of Markov chain based algorithms. In: Proceedings of the 45th annual IEEE symposium on foundations of computer science (FOCS). IEEE Computer Society, Washington, DC, pp 32–41. doi: http://dx.doi.org/10.1109/FOCS.2004.53

Tulsi T, Grover L, Patel A (2006) A new algorithm for fixed point quantum search. Quant Inform Comput 6(6):483–494MathSciNetMATH

Welsh D (1993) Complexity: knots, colourings and countings. Cambridge University Press, Cambridge, UK

Wiebe N, Berry DW, Høyer P, Sanders BC (2008) Higher order decompositions of ordered operator exponentials. http://arxiv.org/abs/0812.0562

Wocjan P, Yard J (2006) The Jones polynomial: quantum algorithms and applications in quantum complexity theory. http://arxiv.org/abs/quant-ph/0603069

Titel: Algorithms for Quantum Computers
verfasst von: Jamie Smith
Michele Mosca
Verlag: Springer Berlin Heidelberg
Buch: Handbook of Natural Computing
Print ISBN: 978-3-540-92909-3

Electronic ISBN: 978-3-540-92910-9

Copyright-Jahr: 2012
DOI: https://doi.org/10.1007/978-3-540-92910-9_43

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner