Discrete-query quantum algorithm for NAND trees

Abstract

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 be converted into an algorithm using O(N^{1/2 + epsilon}) queries in the conventional quantum query model, for any fixed epsilon > 0.

2 pages. v2: updated name of one author

References in corpus (1)

• Hamiltonian Oracles

Cited by in corpus (20)

• Simulating Hamiltonian dynamics with a truncated Taylor series
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Exponential improvement in precision for simulating sparse Hamiltonians
• Quantum query complexity of state conversion
• Disordered Quantum Walks in one lattice dimension
• Universal quantum computation by discontinuous quantum walk
• Asymptotic behavior of quantum walks with spatio-temporal coin fluctuations
• Machine learning \& artificial intelligence in the quantum domain
• Green's function approach for quantum graphs: an overview
• Quantum Walks on Trees with Disorder: Decay, Diffusion, and Localization
• Bose-Hubbard model for universal quantum walk-based computation
• The quantum query complexity of read-many formulas
• Quantum Slide and NAND Tree on a Photonic Chip
• Single-qubit unitary gates by graph scattering
• Search by Lackadaisical Quantum Walk with Symmetry Breaking
• Multi-target quantum walk search on Johnson graph
• A strong direct product theorem for quantum query complexity
• Making the cut: two methods for breaking down a quantum algorithm
• Space-Efficient Quantum Error Reduction without log Factors
• Quantum algorithms and approximating polynomials for composed functions with shared inputs