2006/02/28 by Carlos Mochon · 3 citations
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #quant-ph
paper · pdf · doi:10.1103/physreva.75.042313
published as Phys. Rev. A 75, 042313 (2007) · 16 pages, REVTeX 4 (minor corrections in v2)
openalex publication_date 2007/04/13 · arxiv created 2007/04/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 nonround 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.