- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Reviews of Modern Physics

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Quantum algorithms for algebraic problems

Andrew M. Childs* and Wim van Dam†

Andrew M. Childs*

  • Department of Combinatorics and Optimization and Institute for Quantum Computing, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

Wim van Dam†

  • Departments of Computer Science and Physics, University of California, Santa Barbara, California 93106, USA

  • *amchilds@uwaterloo.ca
  • †vandam@cs.ucsb.edu
PDF

Rev. Mod. Phys. 82, 1 – Published 15 January, 2010

DOI: https://doi.org/10.1103/RevModPhys.82.1

Abstract

Quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup over classical computation and, in particular, on problems with an algebraic flavor.

View figure in article

Article Text

References (232)

  1. Aaronson, S., and A. Ambainis, 2005, Theory Comput. 1, 47, preliminary version in FOCS 2003.
  2. Adleman, L. M., J. DeMarrais, and M.-D. A. Huang, 1997, SIAM J. Comput. 26, 1524.
  3. Adleman, L. M., and M.-D. Huang, 2001, J. Symb. Comput. 32, 171, preliminary version in ANTS-II 1996.
  4. Agrawal, M., N. Kayal, and N. Saxena, 2004, Ann. Math. 160, 781.
  5. Aharonov, D., 2003, e-print arXiv:quant-ph/0301040.
  6. Aharonov, D., and I. Arad, 2006, e-print arXiv:quant-ph/0605181.
  7. Aharonov, D., I. Arad, E. Eban, and Z. Landau, 2007, e-print arXiv:quant-ph/0702008.
  8. Aharonov, D., and M. Ben-Or, 2008, SIAM J. Comput. 38, 1207, preliminary version in STOC 1997.
  9. Aharonov, D., V. Jones, and Z. Landau, 2009, Algorithmica 55, 395, preliminary version in STOC 2006.
  10. Aharonov, D., W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, 2007, SIAM J. Comput. 37, 166, preliminary version in FOCS 2004.
  11. Ajtai, M., 1996, ACM Symposium on Theory of Computing (ACM, New York), pp. 99–108.
  12. Ajtai, M., 1998, ACM Symposium on Theory of Computing (ACM, New York), pp. 10–19.
  13. Ajtai, M., and C. Dwork, 1997, ACM Symposium on Theory of Computing (ACM, New York), pp. 284–293.
  14. Ajtai, M., R. Kumar, and D. Sivakumar, 2001, ACM Symposium on Theory of Computing (ACM, New York), pp. 601–610.
  15. Alagic, G., C. Moore, and A. Russell, 2007, ACM-SIAM Symposium on Discrete Algorithms (SIAM, Philadelphia), pp. 1217–1224; e-print arXiv:quant-ph/0603251.
  16. Alexander, J. W., 1923, Proc. Natl. Acad. Sci. U.S.A. 9, 93.
  17. Ambainis, A., 2007, SIAM J. Comput. 37, 210, preliminary version in FOCS 2004.
  18. Ambainis, A., A. M. Childs, B. W. Reichardt, R. Špalek, and S. Zhang, 2007, IEEE Symposium on Foundations of Computer Science (IEEE, Los Alamitos, CA), pp. 363–372; e-print arXiv:quant-ph/0703015; e-print arXiv:0704.3628.
  19. Ambainis, A., J. Kempe, and A. Rivosh, 2005, ACM-SIAM Symposium on Discrete Algorithms (SIAM, Philadelphia), pp. 1099–1108; e-print arXiv:quant-ph/0402107.
  20. Ambainis, A., and R. Špalek, 2006, Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science Vol. 3884 (Springer, Berlin), pp. 172–183; e-print arXiv:quant-ph/0508205.
  21. Arad, I., and Z. Landau, 2008, e-print arXiv:0805.0040.
  22. Aspuru-Guzik, A., A. D. Dutoi, P. J. Love, and M. Head-Gordon, 2005, Science 309, 1704.
  23. Babai, L., G. Cooperman, L. Finkelstein, E. Luks, and Á. Seress, 1995, J. Comput. Syst. Sci. 50, 296, preliminary version in STOC 1991.
  24. Babai, L., D. Grigoriev, and D. Mount, 1982, ACM Symposium on Theory of Computing (ACM, New York), pp. 310–324.
  25. Babai, L., W. M. Kantor, and E. Luks, 1983, IEEE Symposium on Foundations of Computer Science (IEEE, Los Alamitos, CA), pp. 162–171.
  26. Babai, L., and E. Szemerédi, 1984, IEEE Symposium on Foundations of Computer Science (IEEE, Los Alamitos, CA), pp. 229–240.
  27. Bacon, D., 2008, Quantum Inf. Comput. 8, 438.
  28. Bacon, D., A. M. Childs, and W. van Dam, 2005, IEEE Symposium on Foundations of Computer Science (IEEE, Los Alamitos, CA), pp. 469–478; e-print arXiv:quant-ph/0504083.
  29. Bacon, D., A. M. Childs, and W. van Dam, 2006, Chicago J. Theor. Comput. Sci. 2006, 2.
  30. Barenco, A., A. Ekert, K.-A. Suominen, and P. Törmä, 1996, Phys. Rev. A 54, 139.
  31. Barnum, H., and E. Knill, 2002, J. Math. Phys. 43, 2097.
  32. Beals, R., 1997, ACM Symposium on Theory of Computing (ACM, New York), pp. 48–53.
  33. Beals, R., H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf, 2001, J. ACM 48, 778, preliminary version in FOCS 1998.
  34. Bennett, C. H., 1973, IBM J. Res. Dev. 17, 525.
  35. Bennett, C. H., E. Bernstein, G. Brassard, and U. Vazirani, 1997, SIAM J. Comput. 26, 1510.
  36. Berndt, B. C., R. J. Evans, and K. S. Williams, 1998, Gauss and Jacobi Sums (Wiley, New York).
  37. Bernstein, E., and U. Vazirani, 1993, ACM Symposium on Theory of Computing (ACM, New York), pp. 11–20.
  38. Bernstein, E., and U. Vazirani, 1997, SIAM J. Comput. 26, 1411, preliminary version in STOC 1993.
  39. Beth, T., 1987, Theor. Comput. Sci. 51, 331.
  40. Blum, A., A. Kalai, and H. Wasserman, 2003, J. ACM 50, 506, preliminary version in STOC 1999.
  41. Boneh, D., and R. Lipton, 1995, Advances in Cryptology, Lecture Notes in Computer Science Vol. 963 (Springer, Berlin), pp. 424–437.
  42. Bordewich, M., M. Freedman, L. Lovász, and D. Welsh, 2005, Combin. Probab. Comput. 14, 737.
  43. Born, M., and V. Fock, 1928, Z. Phys. 51, 165.
  44. Boykin, P. O., T. Mor, M. Pulver, V. Roychowdhury, and F. Vatan, 2000, Inf. Process. Lett. 75, 101.
  45. Brassard, G., P. Høyer, M. Mosca, and A. Tapp, 2002, in Quantum Computation and Information, edited by S. J. Lomonaco and H. E. Brandt, AMS Contemporary Mathematics Series Vol. 305 (AMS, Providence, RI), pp. 53–74; e-print arXiv:quant-ph/0005055.
  46. Brassard, G., P. Høyer, and A. Tapp, 1997, SIGACT News 28, 14.
  47. Buchmann, J., 1990, in Séminaire de Théorie des Nombres, Paris 1988–1989, Progress in Mathematics Vol. 91 (Birkhäuser, Boston), pp. 27–41.
  48. Buchmann, J., 2004, Introduction to Cryptography, 2nd ed., Undergraduate Texts in Mathematics (Springer-Verlag, New York).
  49. Buchmann, J. A., and H. C. Williams, 1989, in Advances in Cryptology, Lecture Notes in Computer Science Vol. 435 (Springer, Berlin), pp. 335–343.
  50. Buhler, J. P., H. W. Lenstra, Jr., and C. Pomerance, 1993, The Development of the Number Field Sieve, Lecture Notes in Mathematics Vol. 1554 (Springer, New York), pp. 50–94.
  51. Buhrman, H., and R. Špalek, 2006, ACM-SIAM Symposium on Discrete Algorithms (SIAM, Philadelphia), pp. 880–889; e-print arXiv:quant-ph/0409035.
  52. Cheung, D., D. Maslov, J. Mathew, and D. Pradhan, 2008, in Proceedings of the Third Workshop on Theory of Quantum Computation, Communication, and Cryptography, Lecture Notes in Computer Science Vol. 5106 (Springer, Berlin), pp. 96–104.
  53. Cheung, K. K. H., and M. Mosca, 2001, Quantum Inf. Comput. 1, 26.
  54. Childs, A. M., R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, 2003, ACM Symposium on Theory of Computing (ACM, New York), pp. 59–68; e-print arXiv:quant-ph/0209131.
  55. Childs, A. M., and J. Goldstone, 2004a, Phys. Rev. A 70, 042312.
  56. Childs, A. M., and J. Goldstone, 2004b, Phys. Rev. A 70, 022314.
  57. Childs, A. M., L. J. Schulman, and U. V. Vazirani, 2007, IEEE Symposium on Foundations of Computer Science (IEEE, Los Alamitos, CA), pp. 395–404; e-print arXiv:0705.2784.
  58. Childs, A. M., and P. Wocjan, 2007, Quantum Inf. Comput. 7, 504.
  59. Childs, A. M., and W. van Dam, 2007, ACM-SIAM Symposium on Discrete Algorithms (SIAM, Philadelphia), pp. 1225–1234; e-print arXiv:quant-ph/0507190.
  60. Clausen, M., 1989, Theor. Comput. Sci. 67, 55.
  61. Cleve, R., 1994, http://www.cpsc.ucalgary.ca/~cleve/pubs/fourier_transform.ps
  62. Cleve, R., 2004, Inf. Comput. 192, 162, preliminary version in CCC 2000.
  63. Cleve, R., A. Ekert, C. Macchiavello, and M. Mosca, 1998, Proc. R. Soc. London, Ser. A 454, 339.
  64. Cleve, R., and J. Watrous, 2000, IEEE Symposium on Foundations of Computer Science (IEEE, Los Alamitos, CA), pp. 526–536; e-print arXiv:quant-ph/0006004.
  65. Cohen, H., 1993, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics Vol. 138 (Springer, Berlin).
  66. Coppersmith, D., 1994, IBM Research Division Technical Report No. RC 19642 (unpublished); e-print arXiv:quant-ph/0201067.
  67. Damgård, I. B., 1990, Advances in Cryptology, Lecture Notes in Computer Science Vol. 403 (Springer-Verlag, New York), pp. 163–172.
  68. de Beaudrap, J. N., R. Cleve, and J. Watrous, 2002, Algorithmica 34, 449.
  69. Decker, T., J. Draisma, and P. Wocjan, 2009, Quantum Inf. Comput. 9, 215.
  70. den Boer, B., 1990, Advances in Cryptology, Lecture Notes in Computer Science Vol. 403 (Springer, Berlin), pp. 530–539.
  71. Deutsch, D., 1985, Proc. R. Soc. London, Ser. A 400, 97.
  72. Deutsch, D., 1989, Proc. R. Soc. London, Ser. A 425, 73.
  73. Deutsch, D., and R. Jozsa, 1992, Proc. R. Soc. London, Ser. A 439, 553.
  74. Diaconis, P., 1988, Group Representations in Probability and Statistics, IMS Lecture Notes—Monograph Series Vol. 11 (Institute of Mathematical Statistics, Hayward, CA).
  75. Diaconis, P., and D. Rockmore, 1990, J. Am. Math. Soc. 3, 297.
  76. Diffie, W., and M. E. Hellman, 1976, IEEE Trans. Inf. Theory 22, 644.
  77. DiVincenzo, D. P., 1995, Phys. Rev. A 51, 1015.
  78. Dürr, C., M. Heiligman, P. Høyer, and M. Mhalla, 2006, SIAM J. Comput. 35, 1310, preliminary version in STOC 2000.
  79. Ekert, A., and R. Jozsa, 1996, Rev. Mod. Phys. 68, 733.
  80. Ettinger, M., and P. Høyer, 1999, e-print arXiv:quant-ph/9901029.
  81. Ettinger, M., and P. Høyer, 2000, Adv. Appl. Math. 25, 239.
  82. Ettinger, M., P. Høyer, and E. Knill, 1999, e-print arXiv:quant-ph/9901034.
  83. Ettinger, M., P. Høyer, and E. Knill, 2004, Inf. Process. Lett. 91, 43.
  84. Farhi, E., J. Goldstone, and S. Gutmann, 2008, Theor. Comput. 4, 169.
  85. Farhi, E., J. Goldstone, S. Gutmann, and M. Sipser, 2000, e-print arXiv:quant-ph/0001106.
  86. Farhi, E., and S. Gutmann, 1998, Phys. Rev. A 58, 915.
  87. Fenner, S. A., and Y. Zhang, 2008, Proceedings of the Fifth Annual Conference on Theory and Applications of Models of Computation, Lecture Notes in Computer Science Vol. 4978 (Springer, Berlin), pp. 70–81, e-print arXiv:quant-ph/0610086.
  88. Feynman, R. P., 1982, Int. J. Theor. Phys. 21, 467.
  89. Filotti, I. S., and J. N. Mayer, 1980, ACM Symposium on Theory of Computing (ACM, New York), pp. 236–243.
  90. Fisher, D. S., 1992, Phys. Rev. Lett. 69, 534.
  91. Flaxman, A. D., and B. Przydatek, 2005, Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science Vol. 3404 (Springer, Berlin), pp. 305–314.
  92. Fortnow, L., and J. D. Rogers, 1998, J. Comput. Syst. Sci. 59, 240, preliminary version in CCC 1998.
  93. Freedman, M., M. Larsen, and Z. Wang, 2002, Commun. Math. Phys. 227, 605.
  94. Freedman, M. H., A. Kitaev, M. J. Larsen, and Z. Wang, 2003, Bull., New Ser., Am. Math. Soc. 40, 31.
  95. Freedman, M. H., A. Y. Kitaev, and Z. Wang, 2002, Commun. Math. Phys. 227, 587.
  96. Friedl, K., G. Ivanyos, F. Magniez, M. Santha, and P. Sen, 2003, ACM Symposium on Theory of Computing (ACM, New York), pp. 1–9, e-print arXiv:quant-ph/0211091.
  97. Gavinsky, D., 2004, Quantum Inf. Comput. 4, 229.
  98. Gordon, D. M., 1993, SIAM J. Discrete Math. 6, 124.
  99. Grigni, M., L. J. Schulman, M. Vazirani, and U. Vazirani, 2004, Combinatorica 24, 137, preliminary version in STOC 2001.
  100. Grover, L. K., 1997, Phys. Rev. Lett. 79, 325, preliminary version in STOC 1996.
  101. Hales, L., and S. Hallgren, 2000, IEEE Symposium on Foundations of Computer Science (IEEE, Los Alamitos, CA), pp. 515–525.
  102. Hales, L. R., 2002, Ph.D. thesis, University of California, Berkeley; e-print arXiv:quant-ph/0212002.
  103. Hallgren, S., 2005, ACM Symposium on Theory of Computing (ACM, New York), pp. 468–474.
  104. Hallgren, S., 2007, J. ACM 54, 4, preliminary version in STOC 2002.
  105. Hallgren, S., C. Moore, M. Rötteler, A. Russell, and P. Sen, 2006, ACM Symposium on Theory of Computing (ACM, New York), pp. 604–617; e-print arXiv:quant-ph/0511148; e-print arXiv:quant-ph/0511149.
  106. Hallgren, S., A. Russell, and A. Ta-Shma, 2003, SIAM J. Comput. 32, 916, preliminary version in STOC 2000.
  107. Hamermesh, M., 1989, Group Theory and Its Application to Physical Problems (Dover, New York).
  108. Hardy, G. H., and E. M. Wright, 1979, An Introduction to the Theory of Numbers, 5th ed. (Oxford University Press, Oxford).
  109. Harrow, A. W., B. Recht, and I. L. Chuang, 2002, J. Math. Phys. 43, 4445.
  110. Harrow, A. W., and A. Winter, 2006, e-print arXiv:quant-ph/0606131.
  111. Hausladen, P., and W. K. Wootters, 1994, J. Mod. Opt. 41, 2385.
  112. Hayashi, M., A. Kawachi, and H. Kobayashi, 2008, Quantum Inf. Comput. 8, 345.
  113. Hoffmann, C. M., 1982, Group-Theoretic Algorithms and Graph Isomorphism, Lecture Notes in Computer Science Vol. 136 (Springer-Verlag, Berlin).
  114. Holevo, A. S., 1973, J. Multivariate Anal. 3, 337.
  115. Høyer, P., 1997, e-print arXiv:quant-ph/9702028.
  116. Hulek, K., 2003, Elementary Algebraic Geometry, Student Mathematical Library Vol. 20 (AMS, Providence, RI).
  117. Impagliazzo, R., and A. Wigderson, 1997, ACM Symposium on Theory of Computing (ACM, New York), pp. 220–229.
  118. Ip, L., 2003, http://lawrenceip.com/papers/hspsdpabstract.html
  119. Ireland, K., and M. Rosen, 1990, A Classical Introduction to Modern Number Theory, Graduate Texts in Mathematics Vol. 84, 2nd ed. (Springer-Verlag, New York).
  120. Ivanyos, G., 2008, Quantum Inf. Comput. 8, 579.
  121. Ivanyos, G., F. Magniez, and M. Santha, 2003, Int. J. Found. Comput. Sci. 14, 723, preliminary version in SPAA 2001.
  122. Ivanyos, G., L. Sanselme, and M. Santha, 2007, Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science Vol. 4393 (Springer, Berlin), pp. 586–597; e-print arXiv:quant-ph/0701235.
  123. Ivanyos, G., L. Sanselme, and M. Santha, 2008, Latin American Symposium on Theoretical Informatics, Lecture Notes in Computer Science Vol. 4957 (Springer, Berlin), pp. 759–771; e-print arXiv:0707.1260.
  124. Jaeger, F., D. L. Vertigan, and D. J. A. Welsh, 1990, Math. Proc. Cambridge Philos. Soc. 108, 35.
  125. Jansen, S., M. B. Ruskai, and R. Seiler, 2007, J. Math. Phys. 48, 102111.
  126. Jones, V. F. R., 1985, Bull., New Ser., Am. Math. Soc. 12, 103.
  127. Jordan, S. P., and P. Wocjan, 2008, e-print arXiv:0807.4688.
  128. Jozsa, R., 2003, Ann. Phys. 306, 241.
  129. Kauffman, L. H., 1987, Topology 26, 395.
  130. Kawachi, A., T. Koshiba, H. Nishimura, and T. Yamakami, 2005, Advances in Cryptology, Lecture Notes in Computer Science Vol. 3494 (Springer, Berlin), pp. 268–284; e-print arXiv:quant-ph/0403069.
  131. Kaye, P., 2005, Quantum Inf. Comput. 5, 474.
  132. Kaye, P., R. Laflamme, and M. Mosca, 2007, An Introduction to Quantum Computing (Oxford University Press, Oxford).
  133. Kedlaya, K. S., 2006, Comput. Complexity 15, 1.
  134. Khot, S., 2005, J. ACM 52, 789, preliminary version in FOCS 2004.
  135. Kitaev, A. Y., 1995, e-print arXiv:quant-ph/9511026.
  136. Kitaev, A. Y., 1997, Russ. Math. Surveys 52, 1191.
  137. Kitaev, A. Y., A. H. Shen, and M. N. Vyalyi, 2002, Classical and Quantum Computation (AMS, Providence, RI).
  138. Knill, E., 1995, Los Alamos National Laboratory Technical Report No. LAUR-95–2225 (unpublished); e-print arXiv:quant-ph/9508006.
  139. Knill, E., and R. Laflamme, 1998, Phys. Rev. Lett. 81, 5672.
  140. Knill, E., R. Laflamme, and W. Zurek, 1996, Los Alamos National Laboratory Technical Report No. LAUR-96–2199 (unpublished); e-print arXiv:quant-ph/9610011.
  141. Knill, E., R. Laflamme, and W. Zurek, 1997, Proc. R. Soc. London, Ser. A 454, 365.
  142. Köbler, J., U. Schöning, and J. Torán, 1993, The Graph Isomorphism Problem: Its Structural Complexity (Springer, New York).
  143. Koblitz, N., 1998, Algebraic Aspects of Cryptography, Algorithms and Computation in Mathematics Vol. 3 (Springer-Verlag, New York).
  144. Koiran, P., V. Nesme, and N. Portier, 2007, Theor. Comput. Sci. 380, 115, preliminary version in ICALP 2005.
  145. Kuperberg, G., 2005, SIAM J. Comput. 35, 170.
  146. Lauder, A., and D. Wan, 2008, in Algorithmic Number Theory, edited by J. P. Buhler and P. Stevenhagen, MSRI Publications Vol. 44 (Cambridge University Press, Cambridge), pp. 579–612.
  147. Lenstra, A. K., H. W. Lenstra, Jr., and L. Lovász, 1982, Math. Ann. 261, 515.
  148. Lenstra, H. W., Jr., 1983, Math. Op. Res. 8, 538.
  149. Lenstra, H. W., Jr., 2002, Not. Am. Math. Soc. 49, 182.
  150. Lidl, R., and H. Niederreiter, 1997, Finite Fields, 2nd ed., Encyclopedia of Mathematics and Its Applications Vol. 20 (Cambridge University Press, Cambridge).
  151. Lloyd, S., 1996, Science 273, 1073.
  152. Lorenzini, D., 1996, An Invitation to Arithmetic Geometry, Graduate Studies in Mathematics Vol. 9 (AMS, Providence, RI).
  153. Luks, E. M., 1982, J. Comput. Syst. Sci. 25, 42.
  154. Magniez, F., and A. Nayak, 2007, Algorithmica 48, 221, preliminary version in ICALP 2005.
  155. Magniez, F., A. Nayak, J. Roland, and M. Santha, 2007, ACM Symposium on Theory of Computing (ACM, New York), pp. 575–584; e-print arXiv:quant-ph/0608026.
  156. Magniez, F., M. Santha, and M. Szegedy, 2007, SIAM J. Comput. 37, 413.
  157. Manin, Y., 1980, unpublished.
  158. Maslen, D. K., and D. N. Rockmore, 1995, ACM-SIAM Symposium on Discrete Algorithms (SIAM, Philadelphia), pp. 253–262.
  159. Maurer, U. M., and S. Wolf, 1999, SIAM J. Comput. 28, 1689.
  160. Menezes, A. J., P. C. van Oorschot, and S. A. Vanstone, 1996, Handbook of Applied Cryptography (CRC, Boca Raton, FL).
  161. Micciancio, D., 2001, SIAM J. Comput. 30, 2008, preliminary version in FOCS 1998.
  162. Micciancio, D., and S. Goldwasser, 2002, Complexity of Lattice Problems: A Cryptographic Perspective (Kluwer, Boston).
  163. Miller, G., 1980, ACM Symposium on Theory of Computing (ACM, New York), pp. 225–235.
  164. Miller, G. L., 1976, J. Comput. Syst. Sci. 13, 300, preliminary version in STOC 1975.
  165. Moore, C., D. Rockmore, and A. Russell, 2006, ACM Trans. Algorithms 2, 707, preliminary version in SODA 2004.
  166. Moore, C., D. N. Rockmore, A. Russell, and L. J. Schulman, 2007, SIAM J. Comput. 37, 938, preliminary version in SODA 2004.
  167. Moore, C., A. Russell, and L. J. Schulman, 2008, SIAM J. Comput. 37, 1842, preliminary version in FOCS 2005.
  168. Moore, C., A. Russell, and P. Sniady, 2007, ACM Symposium on Theory of Computing (ACM, New York), pp. 536–545; e-print arXiv:quant-ph/0612089.
  169. Moore, C., A. Russell, and U. Vazirani, 2007, e-print arXiv:quant-ph/0701115.
  170. Mosca, M., 1999, Ph.D. thesis, University of Oxford.
  171. Mosca, M., and A. Ekert, 1999, Proceedings of the First NASA International Conference on Quantum Computing and Quantum Communication, Lecture Notes in Computer Science Vol. 1509 (Springer-Verlag, Berlin).
  172. Mosca, M., and C. Zalka, 2004, Int. J. Quantum Inf. 2, 91.
  173. Nielsen, M. A., and I. L. Chuang, 2000, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge).
  174. Okamoto, T., K. Tanaka, and S. Uchiyama, 2000, in Advances in Cryptology, Lecture Notes in Computer Science Vol. 1880 (Springer, Berlin), pp. 147–165.
  175. Papadimitriou, C. H., 1994, Computational Complexity (Addison-Wesley, Reading, MA).
  176. Pérez-García, D., F. Verstraete, M. M. Wolf, and J. I. Cirac, 2007, Quantum Inf. Comput. 7, 401.
  177. Petrank, E., and M. Roth, 1997, IEEE Trans. Inf. Theory 43, 1602.
  178. Pila, J., 1990, Math. Comput. 55, 745.
  179. Pólya, G., 1945, How to Solve It: A New Aspect of Mathematical Method (Princeton University Press, Princeton, NJ).
  180. Pomerance, C., 1987, in Discrete Algorithms and Complexity, edited by D. S. Johnson, T. Nishizeki, A. Nozaki, and H. S. Wilf (Academic, Boston), pp. 119–143.
  181. Preskill, J., 1998a, Lecture notes for Ph229: Quantum information and computation, http://www.theory.caltech.edu/people/preskill/ph229.
  182. Preskill, J., 1998b, Proc. R. Soc. London, Ser. A 454, 385.
  183. Proos, J., and C. Zalka, 2003, Quantum Inf. Comput. 3, 317.
  184. Püschel, M., M. Rötteler, and T. Beth, 1999, International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Lecture Notes in Computer Science Vol. 1719 (Springer, Berlin), pp. 148–159; e-print arXiv:quant-ph/9807064.
  185. Rabin, M. O., 1980, J. Number Theory 12, 128.
  186. Radhakrishnan, J., M. Rötteler, and P. Sen, 2009, Algorithmica 55, 490.
  187. Regev, O., 2004a, J. ACM 51, 899, preliminary version in STOC 2003.
  188. Regev, O., 2004b, SIAM J. Comput. 33, 738, preliminary version in FOCS 2002.
  189. Regev, O., 2004c, e-print arXiv:quant-ph/0406151.
  190. Reichardt, B. W., 2004, ACM Symposium on Theory of Computing (ACM, New York), pp. 502–510.
  191. Reichardt, B. W., and R. Špalek, 2008, ACM Symposium on Theory of Computing (ACM, New York), pp. 103–112; e-print arXiv:0710.2630.
  192. Rivest, R., A. Shamir, and L. Adleman, 1978, Commun. ACM 21, 120.
  193. Rockmore, D., 1990, Adv. Appl. Math. 11, 164.
  194. Rudolph, T., and L. Grover, 2002, e-print arXiv:quant-ph/0210187.
  195. Russell, A., and I. E. Shparlinski, 2004, J. Complex. 20, 404.
  196. Schmidt, A., and U. Vollmer, 2005, ACM Symposium on Theory of Computing (ACM, New York), pp. 475–480.
  197. Schnorr, C. P., 1987, Theor. Comput. Sci. 53, 201.
  198. Schoof, R., 1985, Math. Comput. 44, 483.
  199. Sen, P., 2006, IEEE Conference on Computational Complexity (IEEE, Los Alamitos, CA), pp. 274–287; e-print arXiv:quant-ph/0512085.
  200. Serre, J.-P., 1977, Linear Representations of Finite Groups, Graduate Texts in Mathematics Vol. 42 (Springer, New York).
  201. Shenvi, N., J. Kempe, and K. B. Whaley, 2003, Phys. Rev. A 67, 052307.
  202. Shi, Y., 2003, Quantum Inf. Comput. 3, 84.
  203. Shor, P. W., 1996, IEEE Symposium on Foundations of Computer Science (IEEE, Los Alamitos, CA), pp. 56–65; e-print arXiv:quant-ph/9605011.
  204. Shor, P. W., 1997, SIAM J. Comput. 26, 1484, preliminary version in FOCS 1994.
  205. Shor, P. W., and S. P. Jordan, 2008, Quantum Inf. Comput. 8, 681.
  206. Shoup, V., 2005, A Computational Introduction to Number Theory and Algebra (Cambridge University Press, Cambridge).
  207. Simon, D. R., 1997, SIAM J. Comput. 26, 1474, preliminary version in FOCS 1994.
  208. Solovay, R., 2000, Lie groups and quantum circuits, http://www.msri.org/publications/ln/msri/2000/qcomputing/solovay/1/.
  209. Spielman, D. A., 1996, ACM Symposium on Theory of Computing (ACM, New York), pp. 576–584.
  210. Stigler, S. M., 1980, Trans. N. Y. Acad. Sci. 39, 147.
  211. Szegedy, M., 2004, IEEE Symposium on Foundations of Computer Science (IEEE, Los Alamitos, CA), pp. 32–41; e-print arXiv:quant-ph/0401053.
  212. Terras, A., 1999, Fourier Analysis On Finite Groups and Applications, London Mathematical Society Student Texts Vol. 43 (Cambridge University Press, Cambridge).
  213. Thiel, C., 1995, Ph.D. thesis, Universität des Saarlandes, Saarbrücken, Germany.
  214. van Emde Boas, P., 1981, University of Amsterdam Department of Mathematics Technical Report No. 8104.
  215. van Dam, W., 2002, Algorithmica 34, 413.
  216. van Dam, W., 2004, e-print arXiv:quant-ph/0405081.
  217. van Dam, W., G. M. D’Ariano, A. Ekert, C. Macchiavello, and M. Mosca, 2007, J. Phys. A 40, 7971.
  218. van Dam, W., S. Hallgren, and L. Ip, 2006, SIAM J. Comput. 36, 763.
  219. van Dam, W., M. Mosca, and U. Vazirani, 2001, IEEE Symposium on Foundations of Computer Science (IEEE, Los Alamitos, CA), pp. 279–287; e-print arXiv:quant-ph/0206003.
  220. van Dam, W., and G. Seroussi, 2002, e-print arXiv:quant-ph/0207131.
  221. van Dam, W., and U. Vazirani, 2003, http://www.cs.berkeley.edu/~vazirani/pubs/qao.ps
  222. Vollmer, U., 2000, Proceedings of the Fourth International Symposium on Algorithmic Number Theory, Lecture Notes in Computer Science Vol. 1838 (Springer, Berlin), pp. 581–594.
  223. von zur Gathen, J., M. Karpinski, and I. Shparlinski, 1997, Comput. Complexity 6, 64.
  224. Watrous, J., 2001a, ACM Symposium on Theory of Computing (ACM, New York), pp. 60–67.
  225. Watrous, J., 2001b, J. Comput. Syst. Sci. 62, 376.
  226. Watrous, J., 2009, in Encyclopedia of Complexity and Systems Science (Springer, New York); e-print arXiv:0804.3401.
  227. Wiesner, S., 1996, e-print arXiv:quant-ph/9603028.
  228. Witten, E., 1989, Commun. Math. Phys. 121, 351.
  229. Wocjan, P., and J. Yard, 2008, Quantum Inf. Comput. 8, 147.
  230. Yao, A. C.-C., 1993, IEEE Symposium on Foundations of Computer Science (IEEE, Los Alamitos, CA), pp. 352–361.
  231. Yuen, H. P., R. S. Kennedy, and M. Lax, 1975, IEEE Trans. Inf. Theory 21, 125.
  232. Zalka, C., 1998, Proc. R. Soc. London, Ser. A 454, 313.

Outline

Information

Rev. Mod. Phys. 82, 1– Published 15 January, 2010

    © 2010 American Physical Society

    Sign In to Your Journals Account

    Filter

    Filter

    Article Lookup

    Enter a citation