A Quantum Algorithm for the Hamiltonian NAND Tree
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.
16 pages, 15 figures, v2 with run time improved to sqrt N by slight sharpening of estimates in section 3
References in corpus (2)
Cited by in corpus (47)
- Universal computation by multi-particle quantum walk
- On the relationship between continuous- and discrete-time quantum walk
- Hamiltonian simulation with nearly optimal dependence on all parameters
- Negative weights make adversaries stronger
- Hamiltonian Simulation Using Linear Combinations of Unitary Operations
- Quantum algorithms for hidden nonlinear structures
- Laplacian versus Adjacency Matrix in Quantum Walk Search
- Asymptotic behavior of quantum walks with spatio-temporal coin fluctuations
- Quantum Walks
- Black-box Hamiltonian simulation and unitary implementation
- Span-program-based quantum algorithm for evaluating formulas
- Coined Quantum Walks on Weighted Graphs
- A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
- Superdiffusive quantum stochastic walk definable of arbitrary directed graph
- Efficient simulation of sparse Markovian quantum dynamics
- Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer
- Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure
- Decoherent quantum walks driven by a generic coin operation
- Solutions of a two-particle interacting quantum walk
- Mixing Times in Quantum Walks on Two-Dimensional Grids
- The QWalk Simulator of Quantum Walks
- Quantum Query Algorithms are Completely Bounded Forms
- Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk
- Quantum walks on embedded hypercubes
- The quantum query complexity of read-many formulas
- Path-integral solution of the one-dimensional Dirac quantum cellular automaton
- Conditional Quantum Walk and Iterated Quantum Games
- Local Hamiltonians in Quantum Computation
- Quantum field theory from a quantum cellular automaton in one spatial dimension and a no-go theorem in higher dimensions
- Limitations on the simulation of non-sparse Hamiltonians
- Quantum Slide and NAND Tree on a Photonic Chip
- Discrete time Dirac quantum walk in 3+1 dimensions
- Quantum Adversary (Upper) Bound
- The walker speaks its graph: global and nearly-local probing of the tunnelling amplitude in continuous-time quantum walks
- On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids
- Span-program-based quantum algorithm for evaluating unbalanced formulas
- How to Compile Some NAND Formula Evaluators
- Path-sum solution of the Weyl Quantum Walk in 3+1 dimensions
- NAND-Trees, Average Choice Complexity, and Effective Resistance
- Java Application that Outputs Quantum Circuit for Some NAND Formula Evaluators
- Adversary lower bounds in the Hamiltonian oracle model
- Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size
- Quantum Algorithms for Evaluating MIN-MAX Trees
- Unitary-circuit semantics for measurement-based computations
- Momentum switches
- Implementing Quantum Gates Using Length-3 Dynamic Quantum Walks
- Randomized Algorithms and Lower Bounds for Quantum Simulation