CoChat
Sign Up
Cited by 345Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyComplexity and Algorithms in Graphs

The DOI matches its Crossref record; 264 of the 266 references it cites were found in a registry or an index.

Quantum algorithms for algebraic problems

Open access
Childs, Andrew M., van Dam, Wim·2010·Reviews of Modern Physics
DOI 10.1103/revmodphys.82.1
Open this paper in CoChat — free accountOpen PDF

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.

Overview

Integrity signals

Registry

Crossref · 10.1103/revmodphys.82.1

Cites

264 of 264 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Citations

Cites

Research works printed but not linked: 69

  1. 10.4086/toc.2005.v001a004 · DOI
  2. Ajtai, M., 1996, ACM Symposium on Theory of Computing
  3. Ajtai, M., 1998, ACM Symposium on Theory of Computing
  4. Ajtai, M., 1997, ACM Symposium on Theory of Computing
  5. Ajtai, M., 2001, ACM Symposium on Theory of Computing
  6. Ambainis, A., 2007, IEEE Symposium on Foundations of Computer Science
  7. Ambainis, A., 2005, ACM-SIAM Symposium on Discrete Algorithms
  8. Ambainis, A., 2006, Symposium on Theoretical Aspects of Computer Science
  9. Babai, L., 1982, ACM Symposium on Theory of Computing
  10. Babai, L., 1983, IEEE Symposium on Foundations of Computer Science
  11. Babai, L., 1984, IEEE Symposium on Foundations of Computer Science
  12. Bacon, D., 2008, Quantum Inf. Comput., 8, 438
  13. Bacon, D., 2005, IEEE Symposium on Foundations of Computer Science
  14. Bacon, D., 2006, Chicago J. Theor. Comput. Sci., 2006, 2
  15. Beals, R., 1997, ACM Symposium on Theory of Computing
  16. Bernstein, E., 1993, ACM Symposium on Theory of Computing
  17. Boneh, D., 1995, Advances in Cryptology
  18. Buchmann, J. A., 1989, Advances in Cryptology
  19. Buhrman, H., 2006, ACM-SIAM Symposium on Discrete Algorithms
  20. Cheung, D., 2008, Proceedings of the Third Workshop on Theory of Quantum Computation, Communication, and Cryptography
  21. Cheung, K. K. H., 2001, Quantum Inf. Comput., 1, 26
  22. Childs, A. M., 2003, ACM Symposium on Theory of Computing
  23. Childs, A. M., 2007, IEEE Symposium on Foundations of Computer Science
  24. Childs, A. M., 2007, Quantum Inf. Comput., 7, 504
  25. Childs, A. M., 2007, ACM-SIAM Symposium on Discrete Algorithms
  26. Cleve, R., 2000, IEEE Symposium on Foundations of Computer Science
  27. Damgård, I. B., 1990, Advances in Cryptology
  28. Decker, T., 2009, Quantum Inf. Comput., 9, 215
  29. den Boer, B., 1990, Advances in Cryptology
  30. 10.4086/toc.2008.v004a008 · DOI
  31. Fenner, S. A., 2008, Proceedings of the Fifth Annual Conference on Theory and Applications of Models of Computation
  32. Filotti, I. S., 1980, ACM Symposium on Theory of Computing
  33. Flaxman, A. D., 2005, Symposium on Theoretical Aspects of Computer Science
  34. Friedl, K., 2003, ACM Symposium on Theory of Computing
  35. Gavinsky, D., 2004, Quantum Inf. Comput., 4, 229
  36. Hales, L., 2000, IEEE Symposium on Foundations of Computer Science
  37. Hallgren, S., 2005, ACM Symposium on Theory of Computing
  38. Hallgren, S., 2006, ACM Symposium on Theory of Computing
  39. Hayashi, M., 2008, Quantum Inf. Comput., 8, 345
  40. Impagliazzo, R., 1997, ACM Symposium on Theory of Computing
  41. Ivanyos, G., 2008, Quantum Inf. Comput., 8, 579
  42. Ivanyos, G., 2007, Symposium on Theoretical Aspects of Computer Science
  43. Ivanyos, G., 2008, Latin American Symposium on Theoretical Informatics
  44. Kawachi, A., 2005, Advances in Cryptology
  45. Kaye, P., 2005, Quantum Inf. Comput., 5, 474
  46. Lenstra, H. W., Jr., 2002, Not. Am. Math. Soc., 49, 182
  47. Lidl, R., 1997, Finite Fields
  48. Magniez, F., 2007, ACM Symposium on Theory of Computing
  49. Maslen, D. K., 1995, ACM-SIAM Symposium on Discrete Algorithms
  50. Miller, G., 1980, ACM Symposium on Theory of Computing
  51. Moore, C., 2007, ACM Symposium on Theory of Computing
  52. Mosca, M., 1999, Proceedings of the First NASA International Conference on Quantum Computing and Quantum Communication
  53. Okamoto, T., 2000, Advances in Cryptology
  54. Pérez-García, D., 2007, Quantum Inf. Comput., 7, 401
  55. Proos, J., 2003, Quantum Inf. Comput., 3, 317
  56. Püschel, M., 1999, International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes
  57. Reichardt, B. W., 2004, ACM Symposium on Theory of Computing
  58. Reichardt, B. W., 2008, ACM Symposium on Theory of Computing
  59. Schmidt, A., 2005, ACM Symposium on Theory of Computing
  60. Shi, Y., 2003, Quantum Inf. Comput., 3, 84
  61. Shor, P. W., 1996, IEEE Symposium on Foundations of Computer Science
  62. Shor, P. W., 2008, Quantum Inf. Comput., 8, 681
  63. Spielman, D. A., 1996, ACM Symposium on Theory of Computing
  64. Szegedy, M., 2004, IEEE Symposium on Foundations of Computer Science
  65. van Dam, W., 2001, IEEE Symposium on Foundations of Computer Science
  66. Vollmer, U., 2000, Proceedings of the Fourth International Symposium on Algorithmic Number Theory
  67. Watrous, J., 2001, ACM Symposium on Theory of Computing
  68. Wocjan, P., 2008, Quantum Inf. Comput., 8, 147
  69. Yao, A. C.-C., 1993, IEEE Symposium on Foundations of Computer Science

Cited by

Sorted by citations

See all 345

Related

See all

Metadata

Authors
Childs, A. M., & van Dam, W.
Affiliations
University of Waterloo (CA)
ORCID
Childs, Andrew M.
Venue
Reviews of Modern Physics
Publisher
American Physical Society (APS)
Published
2010-01-15
Volume
82
Issue
1
Pages
1-52
ISSN
  • 0034-6861 (ISSN-L)
  • 1539-0756
DOI
10.1103/revmodphys.82.1
OpenAlex
W1972883454
Cited by
344
References
266
Citations by year
2026: 14 · 2025: 20 · 2024: 23 · 2023: 53 · 2022: 23 · 2021: 13 · 2020: 18 · 2019: 16 · 2018: 19 · 2017: 17 · 2016: 15 · 2015: 16 · 2014: 24 · 2013: 24 · 2012: 22
FWCI
23.31
Type
journal article
Language
en
Open access
Licence
link.aps.org/licenses/aps-default-license (vor)
Locations
  • Reviews of Modern Physics (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
Keywords
quantum algorithms, algebraic problems, integer factorization, Shor's algorithm, quantum computing

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review