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