A Quantum Algorithm for the Hamiltonian NAND Tree
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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
16 pages, 15 figures, v2 with run time improved to sqrt N by slight sharpening of estimates in section 3