A Quantum Algorithm for the Hamiltonian NAND Tree

by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann

Theory of Computing, Volume 4(8), pp. 169-190, 2008

Bibliography with links to cited articles

[1]   Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, and Shengyu Zhang: Any AND-OR formula of size N can be evaluated in time n12+o(1) on a quantum computer. In Proc. 48th FOCS, pp. 363–372. IEEE Computer Society, 2007. [doi:10.1109/FOCS.2007.57].

[2]   Howard Barnum and Michael Saks: A lower bound on the quantum query complexity of read-once functions. J. Comput. System Sci., 69(2):244–258, 2004. [doi:10.1016/j.jcss.2004.02.002].

[3]   Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani: Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510–1523, 1997. [doi:10.1137/S0097539796300933].

[4]   Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yeung: Discrete-query quantum algorithm for NAND trees, 2007. [arXiv:quant-ph/0702160].

[5]   Richard Cleve, Dmitry Gavinsky, and David L. Yeung: Quantum algorithms for evaluating MIN-MAX trees, 2007. [arXiv:0710.5794].

[6]   Edward Farhi and Sam Gutmann: An analog analogue of a digital quantum computation. Phys. Rev. A, 57:2403, 1998. [doi:10.1103/PhysRevA.57.2403].

[7]   Edward Farhi and Sam Gutmann: Quantum computation and decision trees. Phys. Rev. A, 58:915, 1998. [doi:10.1103/PhysRevA.58.915].

[8]   Carlos Mochon: Hamiltonian oracles. Phys. Rev. A, 75:042313, 2007. [doi:10.1103/PhysRevA.75.042313].

[9]   Ben W. Reichardt and Robert Špalek: Span-program-based quantum algorithm for evaluating formulas. In Proc. 40th STOC, pp. 103–112. ACM, 2008. [doi:10.1145/1374376.1374394].

[10]   Michael Saks and Avi Wigderson: Probabilistic boolean trees and the complexity of evaluating game trees. In Proc. 27th FOCS, pp. 29–38. IEEE Computer Society, 1986.

[11]   Miklos Santha: On the Monte Carlo Boolean decision tree complexity of read-once formulae. Random Structures Algorithms, 6(1):75–87, 1995. [doi:10.1002/rsa.3240060108].

[12]   Marc Snir: Lower bounds on probabilistic decision trees. Theoret. Comput. Sci., 38:69–82, 1985. [doi:10.1016/0304-3975(85)90210-5].