dorsal/arxiv
View SchemaLocal Search Methods for Quantum Computers
| Authors | Tad Hogg, Mehmet Yanik |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9802043 |
| URL | https://arxiv.org/abs/quant-ph/9802043 |
Abstract
Local search algorithms use the neighborhood relations among search states and often perform well for a variety of NP-hard combinatorial search problems. This paper shows how quantum computers can also use these neighborhood relations. An example of such a local quantum search is evaluated empirically for the satisfiability (SAT) problem and shown to be particularly effective for highly constrained instances. For problems with an intermediate number of constraints, it is somewhat less effective at exploiting problem structure than incremental quantum methods, in spite of the much smaller search space used by the local method.
{
"annotation_id": "7a332c7c-f1e7-4d07-851a-8e5d5ebd4e35",
"date_created": "2026-03-02T18:02:41.419000Z",
"date_modified": "2026-03-02T18:02:41.419000Z",
"file_hash": "48a9dc8b8e5f25876a0a130e72d5087c6fefd0a911e29719c732f4e13829cb3e",
"private": false,
"record": {
"abstract": "Local search algorithms use the neighborhood relations among search states\nand often perform well for a variety of NP-hard combinatorial search problems.\nThis paper shows how quantum computers can also use these neighborhood\nrelations. An example of such a local quantum search is evaluated empirically\nfor the satisfiability (SAT) problem and shown to be particularly effective for\nhighly constrained instances. For problems with an intermediate number of\nconstraints, it is somewhat less effective at exploiting problem structure than\nincremental quantum methods, in spite of the much smaller search space used by\nthe local method.",
"arxiv_id": "quant-ph/9802043",
"authors": [
"Tad Hogg",
"Mehmet Yanik"
],
"categories": [
"quant-ph"
],
"title": "Local Search Methods for Quantum Computers",
"url": "https://arxiv.org/abs/quant-ph/9802043"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "56450ba8-2456-4e8f-a646-8271244cda27",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}