Fetching the paper…
Reading the bibliography…
This article surveys the state of the art in quantum computer algorithms, including both black-box and non-black-box results.
C. W. Helstrom, Quantum detection and estimation theory
1976
Earlier work this paper cites.
Y. Manin, “Classical computing, quantum computing, and Shor’s factoring algorithm”, Séminaire Bourbaki
1980
Earlier work this paper cites.
P. Benioff, “Quantum Mechanical Models of Turing Machines That Dissipate No Energy”, Phys. Rev. Lett
1982
Earlier work this paper cites.
R. Feynman, “Simulating Physics with Computers,” International Journal of Theoretical Physics
1982
Earlier work this paper cites.
A.S. Holevo, Probabilistic and statistical aspects of quantum theory
1982
Earlier work this paper cites.
S. Wiesner, “Conjugate coding”, Sigact News
1983
Earlier work this paper cites.
C. H. Bennett, G. Brassard, “Quantum cryptography: Public-key distribution and coin tossing”, Proceedings of IEEE International Conference on Computers, Systems and Signal Processing
1984
Earlier work this paper cites.
D. Deutsch, “Quantum theory, the Church-Turing principle and the universal quantum computer,” Proceedings of the Royal Society of London A
1985
Earlier work this paper cites.
C. Bennett, “Notes on the History of Reversible Computation by Charles Bennett”, IBM J. Research and Development, Vol. 32, No. 1, 16-23 (1988)
1988
Earlier work this paper cites.
F. Jaeger, D. L. Vertigan, D. J. A. Welsh, “On the Computational Complexity of the Jones and Tutte Polynomials”, Mathematical Proceedings of the Cambridge Philosophical Society
1990
Earlier work this paper cites.
A. Berthiaume, G. Brassard, “The quantum challenge to structural complexity theory”, Proc. 7th Conf. Structure Complexity Theory
1992
Earlier work this paper cites.
D. Deutsch, R. Jozsa, “Rapid solutions of problems by quantum computation”, Proceedings of the Royal Society of London, Series A
1992
Earlier work this paper cites.
D. J. A. Welsh, “Complexity: knots, colourings and counting”, Cambridge University Press (1993)
1993
Earlier work this paper cites.
A. Berthiaume, G. Brassard, “Oracle quantum computing”, J. Modern Opt
1994
Earlier work this paper cites.
P. Hausladen and W. K. Wootters, “A pretty good measurement for distinguishing quantum. states”, J. Mod. Opt
1994
Earlier work this paper cites.
Peter Shor, “Algorithms for Quantum Computation: Discrete Logarithms and Factoring,” Proceedings of the 35th Annual Symposium on Foundations of Computer Science
1994
Earlier work this paper cites.
D. Simon, “On the power of quantum computation”, Proceedings of the 35th IEEE Symposium on the Foundations of Computer Science (FOCS)
1994
Earlier work this paper cites.
D. Boneh, R. Lipton, “Quantum Cryptanalysis of Hidden Linear Functions (Extended Abstract)”, Proceedings of 15th Annual International Cryptology Conference (CRYPTO’95)
1995
Earlier work this paper cites.
A. Kitaev,“Quantum measurements and the Abelian Stabilizer Problem”, quant-ph/9511026 (1995)
1995
Earlier work this paper cites.
R. Motwani and P. Raghavan, Randomized Algorithms
1995
Earlier work this paper cites.
B. Schumacher, “Quantum coding”, Phys. Rev. A
1995
Earlier work this paper cites.
L. Grover, “A fast quantum mechanical algorithm for database search” Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC 1996)
1996
Earlier work this paper cites.
A. Kitaev,“Quantum measurements and the Abelian Stabilizer Problem”, Electronic Colloquium on Computational Complexity (ECCC)
1996
Earlier work this paper cites.
S. Lloyd, “Universal Quantum Simulators”, Science
1996
Earlier work this paper cites.
A. Menezes, P. van Oorschot, and S. Vanstone, “Handbook of Applied Cryptography”, CRC Press, 1996
1996
Earlier work this paper cites.
R. Beals, “Quantum computation of Fourier transforms over symmetric groups”, Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing (STOC)
1997
Earlier work this paper cites.
C. Bennett, E. Bernstein, G. Brassard, U. Vazirani, Strengths and Weaknesses of Quantum Computing
1997
Earlier work this paper cites.
E. Bernstein, U. Vazirani, “Quantum Complexity Theory”, SIAM Journal on Computing Volume
1997
Earlier work this paper cites.
G. Brassard, P. Høyer, “An exact quantum polynomial-time algorithm for Simon’s problem”, Proc. of Fifth Israeli Symposium on Theory of Computing and Systems (ISTCS’97)
1997
Earlier work this paper cites.
G. Brassard, P. Høyer, Alain Tapp, “Cryptology Column —Quantum Algorithm for the Collision Problem”, ACM SIGACT News
1997
Earlier work this paper cites.
D. Grigoriev, “Testing Shift-Equivalence of Polynomials by Deterministic, Probabilistic and Quantum Machines”, Theor. Comput. Sci
1997
Earlier work this paper cites.
A. Kitaev, “Quantum computations: algorithms and error correction”, Russ. Math. Surv., 1997, 52 (6), 1191-1249
1997
Earlier work this paper cites.
P. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer” SIAM J. Computing
1997
Earlier work this paper cites.
D. Simon, “On the Power of Quantum Computation”, SIAM J. Computing
1997
Earlier work this paper cites.
U. Vazirani, Berkeley Lecture Notes. Fall 1997. Lecture 8. http://www.cs.berkeley.edu/ ~ \tilde{\hskip 5.69054pt} vazirani/qc.html
1997
Earlier work this paper cites.
Michel Boyer, Gilles Brassard, Peter Høyer, Alain Tapp, “Tight bounds on quantum searching,” Fortschritte der Physik
1998
Earlier work this paper cites.
Gilles Brassard, Peter Høyer, Alain Tapp, “Quantum Counting”, Proceedings of the ICALP’98 Lecture notes in Computer Science
1998
Earlier work this paper cites.
Richard Cleve, Artur Ekert, Chiara Macchiavello, Michele Mosca, “Quantum Algorithms Revisited,” Proceedings of the Royal Society of London A
1998
Earlier work this paper cites.
J.M. Ettinger. “On noncommutative hidden subgroups”. Lecture at AQIP’98
1998
Earlier work this paper cites.
E. Farhi, S. Gutmann, “Quantum Computation and Decision Trees”, Phys. Rev. A
1998
Earlier work this paper cites.
M. Freedman, “P/NP, and the quantum field computer”, Proceedings of the National Academy of Sciences
1998
Earlier work this paper cites.
L. Grover, “A framework for fast quantum mechanical algorithms”, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (STOC)
1998
Earlier work this paper cites.
R. Jozsa, “Quantum Algorithms and the Fourier Transform”, Proceedings of the Royal Society of London A
1998
Earlier work this paper cites.
M. Mosca, A. Ekert, “The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer”, Proceedings 1st NASA International Conference on Quantum Computing & Quantum Communications
1998
Earlier work this paper cites.
U. Vazirani, “On the power of quantum computation”, Philosophical Transactions of the Royal Society of London, Series A
1998
Earlier work this paper cites.
Ch. Zalka, “Efficient Simulation of Quantum Systems by Quantum Computers” Proc. Roy. Soc. Lond. A
1998
Earlier work this paper cites.
D. Abrams, S. Lloyd, “Quantum Algorithm Providing Exponential Speed Increase for Finding Eigenvalues and Eigenvectors”, Phys. Rev. Lett
1999
Earlier work this paper cites.
P. Høyer, “Conjugated operators in quantum algorithms”, Physical Review A
1999
Earlier work this paper cites.
M. Mosca, “Quantum Computer Algorithms”, D.Phil. thesis, Oxford (1999)
1999
Earlier work this paper cites.
A. Nayak, F. Wu, “The Quantum Query Complexity of Approximating the Median and Related Statistics”, Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing (STOC)
1999
Earlier work this paper cites.
M. Püschel , M. Rötteler , T. Beth, “Fast Quantum Fourier Transforms for a Class of Non-Abelian Groups”, Proceedings of the 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes
1999
Earlier work this paper cites.
B. Terhal, PhD thesis, Amsterdam (1999)
1999
Earlier work this paper cites.
Gilles Brassard, Peter Høyer, Michele Mosca, Alain Tapp. “Quantum Amplitude Amplification and Estimation,” to appear in Quantum Computation and Quantum Information Science, AMS Contemporary Math Series
2000
Earlier work this paper cites.
R. Cleve, “An introduction to quantum complexity theory”, Collected Papers on Quantum Computation and Quantum Information Theory
2000
Earlier work this paper cites.
R. Cleve, “The Query Complexity of Order-Finding”, IEEE Conference on Computational Complexity
2000
Cited alongside, same era.
M. Ettinger, P. Høyer. “On quantum algorithms for noncommutative hidden subgroups”, Adv. in Appl. Math., 25(3):239–251, 2000
2000
Cited alongside, same era.
E. Farhi, J. Goldstone, S. Gutmann and M. Sipser, “Quantum Computation by Adiabatic Evolution”, quant-ph/0001106, (2000)
2000
Cited alongside, same era.
L. Hales, S. Hallgren, “An Improved Quantum Fourier Transform Algorithm and Applications”, FOCS 2000: 515-525
2000
Cited alongside, same era.
S. Hallgren, A. Russell, and A. Ta-Shma, “Normal subgroup reconstruction and quantum computation using group representations”, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing
2000
Cited alongside, same era.
M. Szegedy, “Quantum Speed-Up of Markov Chain Based Algorithms”, Proceedings of the 45th IEEE Symposium on the Foundations of Computer Science (FOCS), 32-41 (2004)
2004
Later among the works it cites.
D. Aharonov, O. Regev, “Lattice Problems in NP intersect coNP”, Journal of the ACM
2005
Later among the works it cites.
D. Bacon, A. Childs, W. van Dam, “From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups”, Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005)
2005
Later among the works it cites.
M. Bordewich, M Freedman, L Lovasz, D. J. A. Welsh, “Approximate Counting and Quantum Computation”, Combinatorics, Probability and Computing
2005
Later among the works it cites.
H. Buhrman, C. Dürr, M. Heiligman, P. Høyer, F. Magniez, M. Santha, R. de Wolf, “Quantum Algorithms for Element Distinctness”, SIAM J. Comput
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
T. Hogg, “Quantum search heuristics”, Phys. Rev. A
2000
Cited alongside, same era.
Michael Nielsen, Isaac Chuang “Quantum Computation and Quantum Information”, Cambridge University Press (2000)
2000
Cited alongside, same era.
D. Aharonov, A. Ambainis, J. Kempe, U. Vazirani “Quantum Walks On Graphs”, Proceedings of ACM Symposium on Theory of Computation (STOC’01)
2001
Cited alongside, same era.
A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, J. Watrous, “One-dimensional quantum walks”, Proceedings of the 33rd ACM Symposium on Theory of Computing
2001
Cited alongside, same era.
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. deWolf, “Quantum lower bounds by polynomials”, Journal of the ACM
2001
Cited alongside, same era.
K. Cheung, M. Mosca, “Decomposing Finite Abelian Groups”, Vol. 1, No.2, Quantum Information and Computation
2001
Cited alongside, same era.
W. van Dam, M. Mosca, U. Vazirani, “How Powerful is Adiabatic Quantum Computation?”, Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS’01)
2001
Cited alongside, same era.
2005
Later among the works it cites.
S. Fenner, Y. Zhang, “Quantum Algorithms for a Set of Group Theoretic Problems”, Proceedings of the Ninth IC-EATCS Italian Conference on Theoretical Computer Science
2005
Later among the works it cites.
K. Friedl, G. Ivanyos, M. Santha, “Efficient testing of groups”, Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing (STOC)
2005
Later among the works it cites.
S. Hallgren, “Fast quantum algorithms for computing the unit group and class group of a number field”, Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005)
2005
Later among the works it cites.
S. Hallgren, M. Roetteler, P. Sen, “Limitations of Quantum Coset States for Graph Isomorphism”, eprint arXiv:quant-ph/0511148
2005
Later among the works it cites.
P. Kaye, “Optimized quantum implementation of elliptic curve arithmetic over binary fields”, Quantum Information and Computation
2005
Later among the works it cites.
J. Kempe and A. Shalev, “The hidden subgroup problem and permutation group theory”, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (SODA’05)
2005
Later among the works it cites.
G. Kuperberg, “A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem”, SIAM J. Comput
2005
Later among the works it cites.
J. Radhakrishnan, M. Roetteler, P. Sen, “On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group”, In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP)
2005
Later among the works it cites.
A. Schmidt, U. Vollmer, “Polynomial time quantum algorithm for the computation of the unit group of a number field”, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing
2005
Later among the works it cites.
A. Sokal “The multivariate Tutte polynomial (alias Potts model) for graphs and matroids”, Surveys in Combinatorics
2005
Later among the works it cites.
D. Aharonov, V. Jones, Z. Landau, “A polynomial quantum algorithm for approximating the Jones polynomial”, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing (STOC)
2006
Later among the works it cites.
A. Ambainis, R. Spalek, “Quantum Algorithms for Matching and Network Flows”, Proceedings of STACS’06, Lecture Notes in Computer Science
2006
Later among the works it cites.
D. Bacon, I. Chuang, A. Harrow, “Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms”, Phys. Rev. Lett
2006
Later among the works it cites.
C. Bennett, A. Harrow, S. Lloyd “Universal quantum data compression via gentle tomography”, Phys. Rev. A
2006
Later among the works it cites.
H. Buhrman, B. Špalek, “Quantum verification of matrix products”, Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
2006
Later among the works it cites.
T. Byrnes, Y. Yamamoto “Simulating lattice gauge theories on a quantum computer”, Phys. Rev. A
2006
Later among the works it cites.
R. Jozsa, “An Introduction to Measurement Based Quantum Computation”, NATO Science Series, III: Computer and Systems Sciences. Quantum Information Processing - From Theory to Experiment
2006
Later among the works it cites.
P. Kaye, R. Laflamme, M. Mosca “An Introduction to Quantum Computation”. Oxford University Press, (2006)
2006
Later among the works it cites.
S. Lomonaco, L. Kauffman, “Topological Quantum Computing and the Jones Polynomial”, Proc. SPIE
2006
Later among the works it cites.
C. Moore, D. Rockmore, A. Russell, “Generic Quantum Fourier Transforms”, ACM Trans. Algorithms
2006
Later among the works it cites.
2006
Later among the works it cites.
D. Aharonov, D. Gottesman, S. Irani, J. Kempe, “The power of quantum systems on a line”, Proc. 48th IEEE Symposium on the Foundations of Computer Science (FOCS)
2007
Later among the works it cites.
D. Aharonov, A. Ta-Shma, “Adiabatic Quantum State Generation”, SIAM J. Comput
2007
Later among the works it cites.
G. Alagic, C. Moore, A. Russell, “Quantum algorithms for Simon’s problem over general groups”, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms (SODA)
2007
Later among the works it cites.
A. Ambainis, A.Childs, B. Reichardt, R. Spalek, S. Zhang, “Any AND-OR Formula of Size N can be Evaluated in time N 1 / 2 + o ( 1 ) N^{1/2+o(1)} on a Quantum Computer” 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07)
2007
Later among the works it cites.
D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders, “Efficient quantum algorithms for simulating sparse Hamiltonians”, Communications in Mathematical Physics
2007
Later among the works it cites.
A. Childs, W. van Dam, “Quantum algorithm for a generalized hidden shift problem”, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
2007
Later among the works it cites.
A. Childs, A. Landahl, P. Parrilo, “Improved quantum algorithms for the ordered search problem via semidefinite programming”, Phys. Rev. A
2007
Later among the works it cites.
W. van Dam, G. M. D’Ariano, A. Ekert, C. Macchiavello, and M. Mosca,“General optimized schemes for phase estimation”, Physical Review Letters
2007
Later among the works it cites.
W. van Dam, G. M. D’Ariano, A. Ekert, C. Macchiavello, and M. Mosca, ”Optimal phase estimation in quantum networks”, Journal of Physics A: Math. Theor. 40 (2007) 7971-7984
2007
Later among the works it cites.
S. Dörn, T. Thierauf, “The Quantum Query Complexity of Algebraic Properties”, Proceedings of the 16th International Symposium on Fundamentals of Computation Theory (FCT)
2007
Later among the works it cites.
S. Hallgren, “Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem”, J. ACM 54(1): (2007)
2007
Later among the works it cites.
G. Ivanyos, L. Sanselme, M. Santha, An efficient quantum algorithm for the Hidden Subgroup Problem in extraspecial groups
2007
Later among the works it cites.
S. Jansen, M. Ruskai, R. Seiler, “Bounds for the adiabatic approximation with applications to quantum computation”, J. Math. Phys. 48, 102111 (2007)
2007
Later among the works it cites.
J. Kempe, “Approaches to Quantum Error Correction”, in Quantum Decoherence, Poincare Seminar 2005, Progress in Mathematical Physics series
2007
Later among the works it cites.
F. Magniez and A. Nayak, “Quantum complexity of testing group commutativity”, Algorithmica, 48(3):221-232, 2007
2007
Later among the works it cites.
F. Magniez, A. Nayak, J. Roland and M. Santha, “Search via quantum walk”, 39th ACM Symposium on Theory of Computing (STOC)
2007
Later among the works it cites.
F. Magniez, M. Santha and M. Szegedy, “Quantum algorithms for the triangle problem”, SIAM Journal of Computing
2007
Later among the works it cites.
C. Moore, A. Russell and P. Sniady, “On the impossibility of a quantum sieve algorithm for graph isomorphism: unconditional results” Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (STOC)
2007
Later among the works it cites.
R. Cleve, D. Gavinsky and D. Yeung, “Quantum Algorithms for Evaluating Min-Max Trees”, to appear in the Proceedings of TQC 2008, LNCS
2008
Closest in time.
W. van Dam, I. Shparlinski, “Classical and Quantum Algorithms for Exponential Congruences”, To appear in the proceedings of TQC 2008, LNCS
2008
Closest in time.
Y. Inui, F. Le Gall, “Quantum Property Testing of Group Solvability”, To appear in Proceedings of LATIN’08 (2008)
2008
Closest in time.
G. Ivanyos, L. Sanselme and M. Santha, “An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups”, to appear in the Proceedings of LATIN 2008
2008
Closest in time.
2008
Closest in time.
A. Papageorgiou, and J. F. Traub, “Quantum Algorithms and Complexity for Continuous Problems”, (2008)
2008
Closest in time.
B. Reichardt and R. Spalek, “Span-program-based quantum algorithm for evaluating formulas”, To appear in Proceedings of the fortieth annual ACM symposium on Theory of computing (STOC 2008)
2008
Closest in time.
M. Santha, “Quantum walk based search algorithms”, to appear in Proceedings of TAMC 2008
2008
Closest in time.
J. Watrous, “Quantum computational complexity”, same volume
2008
Closest in time.
P. Wocjan and J. Yard, “The Jones polynomial: quantum algorithms and applications in quantum complexity theory”, Quantum Information and Computation
2008
Closest in time.