Richard Cleve

Discrete-query quantum algorithm for NAND trees. (arXiv:quant-ph/0702160v2 UPDATED)

2019 · arXiv (Cornell University)

Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for evaluating NAND trees that runs in time O(sqrt(N log N)) in the Hamiltonian query model. In this note, we point out that their algorithm can …