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
Google Scholar
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–421
Article
MathSciNet
Google Scholar
Ambainis A (2003) Quantum walks and their algorithmic applications. Int J Quantum Inform 1:507–518
Article
MATH
Google Scholar
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
Google Scholar
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
Google Scholar
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–1473
Article
MathSciNet
MATH
Google Scholar
Berry DW, Ahokas G, Cleve R, Sanders BC (2007) Efficient quantum algorithms for simulating sparse Hamiltonians. Commun Math Phys 270:359
Article
MathSciNet
MATH
Google Scholar
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
Google Scholar
Boyer M, Brassard G, Høyer P, Tapp A (1998) Tight bounds on quantum searching. Fortschritte der Physik 56(5–5):493–505
Article
Google Scholar
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
Google Scholar
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
Google Scholar
Brassard G, Høyer P, Tapp A (1997) Cryptology column — quantum algorithm for the collision problem. ACM SIGACT News 28:14–19
Article
Google Scholar
Brouwer AE (1989) Distance-regular graphs. Springer, New York
Book
MATH
Google Scholar
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
Google Scholar
Cleve R, Ekert A, Macchiavello C, Mosca M (1998) Quantum algorithms revisited. Proc Roy Soc Lond A 454:339–354
Article
MathSciNet
MATH
Google Scholar
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
Google Scholar
Das A, Chakrabarti BK (2008) Quantum annealing and analog quantum computation. Rev Mod Phys 80:1061
Article
MathSciNet
MATH
Google Scholar
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–117
Article
MathSciNet
MATH
Google Scholar
Deutsch D, Jozsa R (1992) Rapid solutions of problems by quantum computation. Proc Roy Soc Lond, A 439:553–558
Article
MathSciNet
MATH
Google Scholar
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–488
Article
MathSciNet
Google Scholar
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–768
Article
MathSciNet
MATH
Google Scholar
Grigoriev D (1997) Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines. Theor Comput Sci 180:217–228
Article
MathSciNet
MATH
Google Scholar
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
Google Scholar
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–62
Chapter
Google Scholar
Hirvensalo M (2001) Quantum computing. Series: Natural Computing Series. Springer
Google Scholar
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
Google Scholar
Karchmer M, Wigderson A (1993) On span programs. In: Proceedings of the 8th IEEE structures in complexity conference. IEEE Press, Piscataway, pp 102–111
Google Scholar
Kaye P, Laflamme R, Mosca M (2007) An introduction to quantum computation. Oxford University Press, Oxford, UK
Google Scholar
Kempe J (2003) Quantum random walks - an introductory overview. Contemp Phys 44(4):307–327
Article
MathSciNet
Google Scholar
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, RI
MATH
Google Scholar
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 Raton
Book
Google Scholar
Mermin ND (2007) Quantum computer science: an introduction. Cambridge University Press, Cambridge
Book
MATH
Google Scholar
Mosca M (2001) Counting by quantum eigenvalue estimation. Theor Comput Sci 264:139–153
Article
MathSciNet
MATH
Google Scholar
Mosca M (2008) Abelian hidden subgroup problem. In: Kao M-Y (ed) Encyclopedia of algorithms. Springer, Berlin
Google Scholar
Mosca M (2009) Quantum algorithms. In: Meyers R (ed) Encyclopedia of complexity and systems science. Springer
Google Scholar
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, UK
MATH
Google Scholar
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
Google Scholar
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
Google Scholar
Shor P (1997) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput 26:1484–1509
Article
MathSciNet
MATH
Google Scholar
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
Google Scholar
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–494
MathSciNet
MATH
Google Scholar
Welsh D (1993) Complexity: knots, colourings and countings. Cambridge University Press, Cambridge, UK
Google Scholar
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