dorsal/arxiv
View SchemaNested quantum search and NP-complete problems
| Authors | N. J. Cerf, L. K. Grover, C. P. Williams |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9806078 |
| URL | https://arxiv.org/abs/quant-ph/9806078 |
| DOI | 10.1103/PhysRevA.61.032303 |
| Journal | Phys.Rev. A61 (2000) 032303 |
Abstract
A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order $\sqrt{d}$, where $d$ is the dimension of the search space, whereas any classical algorithm necessarily scales as $O(d)$. It is shown here that an improved quantum search algorithm can be devised that exploits the structure of a tree search problem by nesting this standard search algorithm. The number of iterations required to find the solution of an average instance of a constraint satisfaction problem scales as $\sqrt{d^\alpha}$, with a constant $\alpha<1$ depending on the nesting depth and the problem considered. When applying a single nesting level to a problem with constraints of size 2 such as the graph coloring problem, this constant $\alpha$ is estimated to be around 0.62 for average instances of maximum difficulty. This corresponds to a square-root speedup over a classical nested search algorithm, of which our presented algorithm is the quantum counterpart.
{
"annotation_id": "8e2d343b-c694-4f6b-83ed-ad1de0c0a602",
"date_created": "2026-03-02T18:02:45.030000Z",
"date_modified": "2026-03-02T18:02:45.030000Z",
"file_hash": "31b7fb13d0d07d47c84bc1c3187a064a07aab95cd3d9c5a2ab1c33b1660a68e6",
"private": false,
"record": {
"abstract": "A quantum algorithm is known that solves an unstructured search problem in a\nnumber of iterations of order $\\sqrt{d}$, where $d$ is the dimension of the\nsearch space, whereas any classical algorithm necessarily scales as $O(d)$. It\nis shown here that an improved quantum search algorithm can be devised that\nexploits the structure of a tree search problem by nesting this standard search\nalgorithm. The number of iterations required to find the solution of an average\ninstance of a constraint satisfaction problem scales as $\\sqrt{d^\\alpha}$, with\na constant $\\alpha\u003c1$ depending on the nesting depth and the problem\nconsidered. When applying a single nesting level to a problem with constraints\nof size 2 such as the graph coloring problem, this constant $\\alpha$ is\nestimated to be around 0.62 for average instances of maximum difficulty. This\ncorresponds to a square-root speedup over a classical nested search algorithm,\nof which our presented algorithm is the quantum counterpart.",
"arxiv_id": "quant-ph/9806078",
"authors": [
"N. J. Cerf",
"L. K. Grover",
"C. P. Williams"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.61.032303",
"journal_ref": "Phys.Rev. A61 (2000) 032303",
"title": "Nested quantum search and NP-complete problems",
"url": "https://arxiv.org/abs/quant-ph/9806078"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "740a1740-a320-4b8e-8be0-c18784a6a7ee",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}