A Quantum Algorithm for the Hamiltonian NAND Tree

By Edward Farhi, Jeffrey Goldstone, Sam Gutmann. Theory of Computing, 2007

299 citations recorded by the source corpus.

We give a quantum algorithm for the binary NAND tree problem in the Hamil- tonian oracle model. The algorithm uses a continuous time quantum walk with a running time proportional to p N. We also show a lower bound of W( p N) for the NAND tree problem in the Hamiltonian oracle model.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/6acaf5610ab9080932a70908daf6aecfcce2b91e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Search via quantum walk (2006, background): “In a break-through, Farhi, Goldstone, and Gutmann [20] designed an O( √ n) continuous-time quantum walk algorithm for balanced formulae.”
Quantum walks: a comprehensive review (2012, methodology): “Moreover, Farhi et al. [146] have produced a O( √ N ) quantum algorithm for solving the NAND tree problem (which consists of evaluating the root node of a perfectly bifurcating tree whose N leaves are either ‘0’ or ‘1’ and the value of any other node is the NAND of corresponding children leaves) and”
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters (2015, methodology): “For example, it was used to convert the algorithm for evaluating a balanced binary NAND tree with n leaves [13] to the discrete-query model [10].”
Exponential improvement in precision for simulating sparse Hamiltonians (2013, background): “[19] E. Farhi and S. Gutmann.”
Universal Computation by Multiparticle Quantum Walk (2012, methodology): “Notable previous applications of such scattering include the quantum algorithm for the Hamiltonian NAND tree [8] and the single-particle universality construction [5].”
Machine learning \& artificial intelligence in the quantum domain (2017, methodology): “, 2014), algorithms for quadratic and super-polynomial improvements in NANDand boolean-tree evaluations, which are important in evaluation of optimal strategies in two-player games 130 (Childs et al., 2009; Zhan et al., 2012; Farhi et al., 2008).”
On the Relationship Between Continuous- and Discrete-Time Quantum Walk (2008, methodology): “Finally, I discuss limitations of the method for simulating Hamiltonians with negative matrix elements, and present two problems that motivate attempting to circumvent these limitations.”