Increase of degeneracy improves the performance of the quantum adiabatic algorithm
We propose a strategy to improve the performance of the quantum adiabatic algorithm (QAA) on an NP-hard (nondeterministic-polynomial-time-hard) problem exact cover, by increasing the ground-state degeneracy of the problem Hamiltonian. Our strategy is based on the empirical finding that for the QAA t...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2014
|
| Online Access: | http://hdl.handle.net/1721.1/91591 https://orcid.org/0000-0002-9554-3846 |
| _version_ | 1811075065184256000 |
|---|---|
| author | Zhuang, Quntao |
| author2 | Massachusetts Institute of Technology. Department of Physics |
| author_facet | Massachusetts Institute of Technology. Department of Physics Zhuang, Quntao |
| author_sort | Zhuang, Quntao |
| collection | MIT |
| description | We propose a strategy to improve the performance of the quantum adiabatic algorithm (QAA) on an NP-hard (nondeterministic-polynomial-time-hard) problem exact cover, by increasing the ground-state degeneracy of the problem Hamiltonian. Our strategy is based on the empirical finding that for the QAA the difficulty of random instances decreases with the degeneracy of the ground state. We increase the degeneracy by adding extra qubits to form additional clauses. Our numerical results show that on average our strategy can provide an increase in the minimum gap size along the linear interpolation path of Hamiltonian for both easy and difficult instances. The success probability at fixed total evolution time is thus increased. |
| first_indexed | 2024-09-23T10:00:05Z |
| format | Article |
| id | mit-1721.1/91591 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:00:05Z |
| publishDate | 2014 |
| publisher | American Physical Society |
| record_format | dspace |
| spelling | mit-1721.1/915912022-09-26T15:05:24Z Increase of degeneracy improves the performance of the quantum adiabatic algorithm Zhuang, Quntao Massachusetts Institute of Technology. Department of Physics Zhuang, Quntao We propose a strategy to improve the performance of the quantum adiabatic algorithm (QAA) on an NP-hard (nondeterministic-polynomial-time-hard) problem exact cover, by increasing the ground-state degeneracy of the problem Hamiltonian. Our strategy is based on the empirical finding that for the QAA the difficulty of random instances decreases with the degeneracy of the ground state. We increase the degeneracy by adding extra qubits to form additional clauses. Our numerical results show that on average our strategy can provide an increase in the minimum gap size along the linear interpolation path of Hamiltonian for both easy and difficult instances. The success probability at fixed total evolution time is thus increased. Massachusetts Institute of Technology. Department of Physics 2014-11-17T17:30:33Z 2014-11-17T17:30:33Z 2014-11 2014-09 2014-11-13T23:00:04Z Article http://purl.org/eprint/type/JournalArticle 1050-2947 1094-1622 http://hdl.handle.net/1721.1/91591 Zhuang, Quntao. "Increase of degeneracy improves the performance of the quantum adiabatic algorithm." Phys. Rev. A 90, 052317 (November 2014). © 2014 American Physical Society https://orcid.org/0000-0002-9554-3846 en http://dx.doi.org/10.1103/PhysRevA.90.052317 Physical Review A Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. American Physical Society application/pdf American Physical Society American Physical Society |
| spellingShingle | Zhuang, Quntao Increase of degeneracy improves the performance of the quantum adiabatic algorithm |
| title | Increase of degeneracy improves the performance of the quantum adiabatic algorithm |
| title_full | Increase of degeneracy improves the performance of the quantum adiabatic algorithm |
| title_fullStr | Increase of degeneracy improves the performance of the quantum adiabatic algorithm |
| title_full_unstemmed | Increase of degeneracy improves the performance of the quantum adiabatic algorithm |
| title_short | Increase of degeneracy improves the performance of the quantum adiabatic algorithm |
| title_sort | increase of degeneracy improves the performance of the quantum adiabatic algorithm |
| url | http://hdl.handle.net/1721.1/91591 https://orcid.org/0000-0002-9554-3846 |
| work_keys_str_mv | AT zhuangquntao increaseofdegeneracyimprovestheperformanceofthequantumadiabaticalgorithm |