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 n1∕2+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].