dorsal/arxiv
View SchemaA Quantum Algorithm for the Hamiltonian NAND Tree
| Authors | E. Farhi, J. Goldstone, S. Gutmann |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0702144 |
| URL | https://arxiv.org/abs/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.
{
"annotation_id": "2dd3be3e-1640-4ca0-bc23-df6753efb5de",
"date_created": "2026-03-02T18:02:34.313000Z",
"date_modified": "2026-03-02T18:02:34.313000Z",
"file_hash": "7a8e8aacd1927a87217014540ab3f7f9e922bc71a2f63e6d5d42b21720193c8a",
"private": false,
"record": {
"abstract": "We give a quantum algorithm for the binary NAND tree problem in the\nHamiltonian oracle model. The algorithm uses a continuous time quantum walk\nwith a run time proportional to sqrt N. We also show a lower bound of sqrt N\nfor the NAND tree problem in the Hamiltonian oracle model.",
"arxiv_id": "quant-ph/0702144",
"authors": [
"E. Farhi",
"J. Goldstone",
"S. Gutmann"
],
"categories": [
"quant-ph"
],
"title": "A Quantum Algorithm for the Hamiltonian NAND Tree",
"url": "https://arxiv.org/abs/quant-ph/0702144"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "465c8c5e-b7d2-4093-a058-791c6cc71698",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}