Universal computation by quantum walk

B. A. Chase and A. J. Landahl, Universal quantum walks and adiabatic algorithms by 1D Hamiltonians , arXiv:0802.1207

Original

1973

Earlier work this paper cites.

P. Benioff, The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines , J. Stat. Phys. 22

1980

Earlier work this paper cites.

R. P. Feynman, Quantum mechanical computers , Optics News 11

1985

Earlier work this paper cites.

N. Margolus, Parallel quantum computation , in Complexity, Entropy, and the Physics of Information , edited by W. H. Zurek (Addison-Wesley, 1990), pp. 273–287

1990

Earlier work this paper cites.

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer , SIAM J. Comput. 26

1997

Earlier work this paper cites.

E. Farhi and S. Gutmann, Quantum computation and decision trees , Phys. Rev. A 58

1998

Earlier work this paper cites.

P. O. Boykin, T. Mor, M. Pulver, V. Roychowdhury, and F. Vatan, On universal and fault-tolerant quantum computing , Inform. Process. Lett. 75

2000

Earlier work this paper cites.

J. Watrous, Quantum simulations of classical random walks and undirected graph connectivity , J. Comput. System Sci. 62

2001

Earlier work this paper cites.

R. Wong, Asymptotic Expansions of Integrals (SIAM, 2001)

2001

Earlier work this paper cites.

A. Y. Kitaev, A. H. Shen, and M. N. Vyalyi, Classical and Quantum Computation (AMS, 2002)

2002

Earlier work this paper cites.

A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, Exponential algorithmic speedup by quantum walk , in Proc. 35th ACM Symposium on Theory of Computing (2003), pp. 59–68, quant-ph/0209131

2003

Earlier work this paper cites.

N. Shenvi, J. Kempe, and K. B. Whaley, A quantum random walk search algorithm , Phys. Rev. A 67

2003

Cited alongside, same era.

J. Kempe and O. Regev, 3-local Hamiltonian is QMA-complete , Quantum Information and Computation 3

2003

Cited alongside, same era.

D. Aharonov and A. Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge , in Proc. 35th ACM Symposium on Theory of Computing (2003), pp. 20–29, quant-ph/0301023

2003

Cited alongside, same era.

A. Ambainis, Quantum walk algorithm for element distinctness , SIAM J. Comput. 37

2004

Cited alongside, same era.

D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, Adiabatic quantum computation is equivalent to standard quantum computation , in Proc. 45th IEEE Symposium on Foundations of Computer Science (2004), pp. 42–51, quant-ph/0405098

2004

H. Buhrman and R. Špalek, Quantum verification of matrix products , in Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (2006), pp. 880–889, quant-ph/0409035

2006

Later among the works it cites.

J. Kempe, A. Kitaev, and O. Regev, The complexity of the local Hamiltonian problem , SIAM Journal on Computing 35

2006

Later among the works it cites.

A. M. Childs, L. J. Schulman, and U. V. Vazirani, Quantum algorithms for hidden nonlinear structures , in Proc. 48th IEEE Symposium on Foundations of Computer Science (2007), pp. 395–404, arXiv:0705.2784

Original

2007

Later among the works it cites.

A. Ambainis, A. M. Childs, B. W. Reichardt, R. Špalek, and S. Zhang, Any AND-OR formula of size N N can be evaluated in time N 1 / 2 + o ⁡ ( 1 ) N^{1/2+o(1)} on a quantum computer , in Proc. 48th IEEE Symposium on Foundations of Computer Science (2007), pp. 363–372, quant-ph/0703015, arXiv:0704.3628

Original

2007

Later among the works it cites.