dorsal/arxiv
View SchemaStructured quantum search in NP-complete problems using the cumulative density of states
| Authors | Keith Kastella, Richard Freeling |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0109087 |
| URL | https://arxiv.org/abs/quant-ph/0109087 |
| DOI | 10.1103/PhysRevA.83.014302 |
Abstract
In the multitarget Grover algorithm, we are given an unstructured N-element list of objects S_i containing a T-element subset tau and function f, called an oracle, such that f(S_i)=1 if S_i is in tau, otherwise f(S_i) = 0. By using quantum parallelism, an element of tau can be retrieved in O(sqrt(N/T)) steps, compared to O(N/T) for any classical algorithm. It is shown here that in combinatorial optimization problems with N=4^M, the density of states can be used in conjunction with the multitarget Grover algorithm to construct a sequence of oracles that structure the search so that the optimum state is obtained with certainty in O(log(N)) steps.
{
"annotation_id": "fa25cc52-ec40-455f-86c4-b462a8d99d1a",
"date_created": "2026-03-02T18:01:45.412000Z",
"date_modified": "2026-03-02T18:01:45.412000Z",
"file_hash": "0d7510343b5a3cc4a8833a978280518717f5705675ff6ea9a75b4befa782291d",
"private": false,
"record": {
"abstract": "In the multitarget Grover algorithm, we are given an unstructured N-element\nlist of objects S_i containing a T-element subset tau and function f, called an\noracle, such that f(S_i)=1 if S_i is in tau, otherwise f(S_i) = 0. By using\nquantum parallelism, an element of tau can be retrieved in O(sqrt(N/T)) steps,\ncompared to O(N/T) for any classical algorithm. It is shown here that in\ncombinatorial optimization problems with N=4^M, the density of states can be\nused in conjunction with the multitarget Grover algorithm to construct a\nsequence of oracles that structure the search so that the optimum state is\nobtained with certainty in O(log(N)) steps.",
"arxiv_id": "quant-ph/0109087",
"authors": [
"Keith Kastella",
"Richard Freeling"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.83.014302",
"title": "Structured quantum search in NP-complete problems using the cumulative density of states",
"url": "https://arxiv.org/abs/quant-ph/0109087"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "a6f74e2d-ab37-41d9-a52e-76e763d16fc3",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}