|
| related topics |
| {state, algorithm, problem} |
| {algorithm, log, probability} |
| {time, wave, function} |
|
Adiabatic Quantum Computing for Random Satisfiability Problems
Tad Hogg
abstract: The discrete formulation of adiabatic quantum computing is compared with
other search methods, classical and quantum, for random satisfiability (SAT)
problems. With the number of steps growing only as the cube of the number of
variables, the adiabatic method gives solution probabilities close to 1 for
problem sizes feasible to evaluate via simulation on current computers.
However, for these sizes the minimum energy gaps of most instances are fairly
large, so the good performance scaling seen for small problems may not reflect
asymptotic behavior where costs are dominated by tiny gaps. Moreover, the
resulting search costs are much higher than for other methods. Variants of the
quantum algorithm that do not match the adiabatic limit give lower costs, on
average, and slower growth than the conventional GSAT heuristic method.
- oai_identifier:
- oai:arXiv.org:quant-ph/0206059
- categories:
- quant-ph
- comments:
- added discussion of discrete adiabatic method, and simulations with
30 bits 8 pages, 8 figures
- doi:
- 10.1103/PhysRevA.67.022314
- arxiv_id:
- quant-ph/0206059
- journal_ref:
- Phys Rev A 67 022314 (2003)
- created:
- 2002-06-11
- updated:
- 2004-01-23
Full article ▸
|
|
| related documents |
| 0108048v1 |
| 0001106v1 |
| 0601116v1 |
| 0308060v1 |
| 0405168v2 |
| 0611140v3 |
| 0605244v3 |
| 0506270v2 |
| 0702007v2 |
| 0411194v2 |
| 0312083v1 |
| 0210077v1 |
| 0609125v1 |
| 0303070v1 |
| 0502014v2 |
| 0506244v2 |
| 0405157v2 |
| 0510179v1 |
| 0406092v1 |
| 0308016v1 |
| 0209092v5 |
| 0602135v1 |
| 0507036v3 |
| 0701096v2 |
| 0410145v2 |
|