Discrete-query quantum algorithm for NAND trees

DOI10.4086/TOC.2009.V005A005MaRDI QIDQ3002804zbMATH OpenOpenAlexFDO

Authors Andrew M. Childs, Richard Cleve, David Yonge-Mallo, Stephen P. Jordan

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/quant-ph/0702160

zbMATH Keywords

quantum computationquantum walkquantum query complexityformula evaluationHamiltonian simulation

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Eulerian and Hamiltonian graphs (05C45)

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.

Recommendations

• scientific article; zbMATH DE number 5899272
• Challenges of adiabatic quantum evaluation of NAND trees
• Faster quantum algorithm for evaluating game trees
• Quantum Algorithms for Evaluating Min-Max Trees
• Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer

Cited in

(9)

• Challenges of adiabatic quantum evaluation of NAND trees
• scientific article; zbMATH DE number 5899272 (Why is no real title available?)
• Quantum algorithm design: techniques and applications
• Asymptotic behavior of quantum walks with spatio-temporal coin fluctuations
• A strong direct product theorem for quantum query complexity
• Intricacies of quantum computational paths
• Green's function approach for quantum graphs: an overview
• Multi-target quantum walk search on Johnson graph
• Disordered quantum walks in one lattice dimension

This page was built for publication: Discrete-query quantum algorithm for NAND trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3002804)