A Quantum Algorithm for the Hamiltonian NAND Tree

2007/02/14 by Farhi, E., Goldstone, J., Gutmann, S. · 7 citations
#FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.quant-ph/0702144

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.

Cited by

• Direct Equivalence between Dynamics of Quantum Walks and Coupled Classical Oscillators
• Many-Body Effects in a Molecular Quantum NAND Tree
• Quantum walks on finite and bounded infinite graphs
• Matrix Inversion by Quantum Walk
• Lecture Notes on Quantum Algorithms
• Quantum state transfer and periodicity in discrete-time quantum walks under non--Markovian dephasing noise
• Quantum Search with a Generalized Laplacian

Related

• Quantum computation and decision trees
• A quantum dot implementation of the quantum NAND algorithm
• Noisy Tree Data Structures and Quantum Applications
• Every NAND formula of size N can be evaluated in time N^1/2+o(1) on a quantum computer
• Quantum Algorithms