Hamiltonian Oracles
arXiv:quant-ph/0602032 · doi:10.1103/PhysRevA.75.042313
Abstract
Hamiltonian oracles are the continuum limit of the standard unitary quantum oracles. In this limit, the problem of finding the optimal query algorithm can be mapped into the problem of finding shortest paths on a manifold. The study of these shortest paths leads to lower bounds of the original unitary oracle problem. A number of example Hamiltonian oracles are studied in this paper, including oracle interrogation and the problem of computing the XOR of the hidden bits. Both of these problems are related to the study of geodesics on spheres with non-round metrics. For the case of two hidden bits a complete description of the geodesics is given. For n hidden bits a simple lower bound is proven that shows the problems require a query time proportional to n, even in the continuum limit. Finally, the problem of continuous Grover search is reexamined leading to a modest improvement to the protocol of Farhi and Gutmann.
16 pages, REVTeX 4 (minor corrections in v2)
References in corpus (11)
- Quantum Computation and Decision Trees
- Time Optimal Control in Spin Systems
- Spatial search by quantum walk
- Quantum Computation as Geometry
- Quantum information and precision measurement
- Spatial search and the Dirac equation
- Quantum channels showing superadditivity in capacity
- Measuring Energy, Estimating Hamiltonians, and the Time-Energy Uncertainty Relation
- A family of generalized `pretty good' measurements and the minimal-error pure-state discrimination problems for which they are optimal
- Quantum circuit implementation of the Hamiltonian versions of Grover's algorithm
- Distinguishing n Hamiltonians on C^n by a single measurement
Cited by in corpus (23)
- On the relationship between continuous- and discrete-time quantum walk
- Exponential improvement in precision for simulating sparse Hamiltonians
- Grover Search with Lackadaisical Quantum Walks
- Exploring adiabatic quantum trajectories via optimal control
- Discrete-query quantum algorithm for NAND trees
- Efficient discrete-time simulations of continuous-time quantum query algorithms
- Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
- Quantum Search with Multiple Walk Steps per Oracle Query
- Approximating Fractional Time Quantum Evolution
- Quantum Walk Search on Johnson Graphs
- Faster Quantum Walk Search on a Weighted Graph
- Using post-measurement information in state discrimination
- Quantum Walk Search with Time-Reversal Symmetry Breaking
- Quantum Computing by Cooling
- Irreconcilable Difference Between Quantum Walks and Adiabatic Quantum Computing
- Engineering the Success of Quantum Walk Search Using Weighted Graphs
- Quantum algorithms for formula evaluation
- Unstructured Search by Random and Quantum Walk
- Optimal Quantum Walk Search on Kronecker Graphs with Dominant or Fixed Regular Initiators
- Scoring Anomalous Vertices Through Quantum Walks
- Adversary lower bounds in the Hamiltonian oracle model
- A time-dependent Tsirelson's bound from limits on the rate of information gain in quantum systems
- A universal adiabatic quantum query algorithm