A Quantum Algorithm for the Hamiltonian NAND Tree

Abstract

We give a quantum algorithm for the binary NAND tree problem in the Hamiltonian oracle model. The algorithm uses a continuous time quantum walk with a run time proportional to sqrt N. We also show a lower bound of sqrt N for the NAND tree problem in the Hamiltonian oracle model.

16 pages, 15 figures, v2 with run time improved to sqrt N by slight sharpening of estimates in section 3

Cited by in corpus (6)

• Quantum algorithms for hidden nonlinear structures
• A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
• Decoherent quantum walks driven by a generic coin operation
• Local Hamiltonians in Quantum Computation
• How to Compile Some NAND Formula Evaluators
• Java Application that Outputs Quantum Circuit for Some NAND Formula Evaluators