|
related topics |
{state, algorithm, problem} |
{algorithm, log, probability} |
{states, state, optimal} |
{classical, space, random} |
{information, entropy, channel} |
{theory, mechanics, state} |
{trap, ion, state} |
|
Local Search Methods for Quantum Computers
Tad Hogg, Mehmet Yanik
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.
- oai_identifier:
- oai:arXiv.org:quant-ph/9802043
- categories:
- quant-ph
- comments:
- 28 pages, 6 figures, for related papers see
http://www.parc.xerox.com/dynamics/www/quantum.html
- arxiv_id:
- quant-ph/9802043
- created:
- 1998-02-16
Full article ▸
|
|
related documents |
0212094v2 |
0301023v2 |
0504101v1 |
0601116v1 |
0001106v1 |
0405168v2 |
0108048v1 |
0206059v2 |
0204013v1 |
0308060v1 |
0605244v3 |
0611140v3 |
0506270v2 |
0210077v1 |
0702007v2 |
0411194v2 |
0105071v2 |
0312083v1 |
0010021v1 |
0609125v1 |
0106152v1 |
0303070v1 |
0204044v5 |
0502014v2 |
0510179v1 |
|