dorsal/arxiv
View SchemaHamiltonian Oracles
| Authors | Carlos Mochon |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0602032 |
| URL | https://arxiv.org/abs/quant-ph/0602032 |
| DOI | 10.1103/PhysRevA.75.042313 |
| Journal | Phys. Rev. A 75, 042313 (2007) |
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.
{
"annotation_id": "aa660b96-c7d2-4f19-8664-fc89e5327a13",
"date_created": "2026-03-02T18:02:23.623000Z",
"date_modified": "2026-03-02T18:02:23.623000Z",
"file_hash": "09ce55ae5d1a9839a70580c775486c0785cef29381766a35d68da13c23735911",
"private": false,
"record": {
"abstract": "Hamiltonian oracles are the continuum limit of the standard unitary quantum\noracles. In this limit, the problem of finding the optimal query algorithm can\nbe mapped into the problem of finding shortest paths on a manifold. The study\nof these shortest paths leads to lower bounds of the original unitary oracle\nproblem. A number of example Hamiltonian oracles are studied in this paper,\nincluding oracle interrogation and the problem of computing the XOR of the\nhidden bits. Both of these problems are related to the study of geodesics on\nspheres with non-round metrics. For the case of two hidden bits a complete\ndescription of the geodesics is given. For n hidden bits a simple lower bound\nis proven that shows the problems require a query time proportional to n, even\nin the continuum limit. Finally, the problem of continuous Grover search is\nreexamined leading to a modest improvement to the protocol of Farhi and\nGutmann.",
"arxiv_id": "quant-ph/0602032",
"authors": [
"Carlos Mochon"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.75.042313",
"journal_ref": "Phys. Rev. A 75, 042313 (2007)",
"title": "Hamiltonian Oracles",
"url": "https://arxiv.org/abs/quant-ph/0602032"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "85d8065c-6b48-4b5a-aefb-c2081e3dde97",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}