Discrete-Query Quantum Algorithm for NAND Trees

by Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo

Theory of Computing, Volume 5(5), pp. 119-123, 2009

Bibliography with links to cited articles

[1]   A. Ambainis, A. M. Childs, B. W. Reichardt, R. Špalek, and S. Zhang: Any AND-OR formula of size N can be evaluated in time N12+o(1) on a quantum computer. In Proc. 48th IEEE FOCS, pp. 363–372. IEEE Comp. Soc. Press, 2007. [doi:10.1109/FOCS.2007.57, arXiv:quant-ph/0703015, arXiv:0704.3628].

[2]   H. Barnum and M. 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, arXiv:quant-ph/0201007].

[3]   D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders: Efficient quantum algorithms for simulating sparse Hamiltonians. Comm. Math. Phys., 270(2):359–371, 2007. [doi:10.1007/s00220-006-0150-x, arXiv:quant-ph/0508139].

[4]   A. M. Childs: Quantum information processing in continuous time. PhD thesis, Massachusetts Institute of Technology, 2004.

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

[6]   E. Farhi, J. Goldstone, and S. Gutmann: A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing, 4(1):169–190, 2008. [doi:10.4086/toc.2008.v004a008].

[7]   E. Farhi and S. Gutmann: Quantum computation and decision trees. Phys. Rev. A, 58:915–928, 1998. [doi:10.1103/PhysRevA.58.915, arXiv:quant-ph/9706062].

[8]   C. Mochon: Hamiltonian oracles. Phys. Rev. A, 75(4):042313, 2007. [doi:10.1103/PhysRevA.75.042313, arXiv:quant-ph/0602032].

[9]   M. Saks and A. Wigderson: Probabilistic Boolean decision trees and the complexity of evaluating game trees. In Proc. 27th FOCS, pp. 29–38. IEEE Comp. Soc. Press, 1986.

[10]   M. 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].

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