dorsal/arxiv
View SchemaSophisticated quantum search without entanglement
| Authors | David A. Meyer |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0007070 |
| URL | https://arxiv.org/abs/quant-ph/0007070 |
| DOI | 10.1103/PhysRevLett.85.2014 |
Abstract
Although entanglement is widely considered to be necessary for quantum algorithms to improve on classical ones, Lloyd has observed recently that Grover's quantum search algorithm can be implemented without entanglement, by replacing multiple particles with a single particle having exponentially many states. We explain that this maneuver removes entanglement from any quantum algorithm. But all physical resources must be accounted for to quantify algorithm complexity, and this scheme typically incurs exponential costs in some other resource(s). In particular, we demonstrate that a recent experimental realization requires exponentially increasing precision. There is, however, a quantum algorithm which searches a `sophisticated' database (not unlike a Web search engine) with a single query, but which we show does not require entanglement even for multiparticle implementations.
{
"annotation_id": "2c88ba99-b9d0-45bc-af4b-6021fb959f87",
"date_created": "2026-03-02T18:01:38.923000Z",
"date_modified": "2026-03-02T18:01:38.923000Z",
"file_hash": "278ad7ea8d56824844199ff5d8d15c80ddee5905e6da140609604302300fe9f1",
"private": false,
"record": {
"abstract": "Although entanglement is widely considered to be necessary for quantum\nalgorithms to improve on classical ones, Lloyd has observed recently that\nGrover\u0027s quantum search algorithm can be implemented without entanglement, by\nreplacing multiple particles with a single particle having exponentially many\nstates. We explain that this maneuver removes entanglement from any quantum\nalgorithm. But all physical resources must be accounted for to quantify\nalgorithm complexity, and this scheme typically incurs exponential costs in\nsome other resource(s). In particular, we demonstrate that a recent\nexperimental realization requires exponentially increasing precision. There is,\nhowever, a quantum algorithm which searches a `sophisticated\u0027 database (not\nunlike a Web search engine) with a single query, but which we show does not\nrequire entanglement even for multiparticle implementations.",
"arxiv_id": "quant-ph/0007070",
"authors": [
"David A. Meyer"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevLett.85.2014",
"title": "Sophisticated quantum search without entanglement",
"url": "https://arxiv.org/abs/quant-ph/0007070"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "92b8fa7e-9113-4aa1-a99f-26b306f986ab",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}