Abstract
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.
Original language | English (US) |
---|---|
Article number | 052317 |
Journal | Physical Review A - Atomic, Molecular, and Optical Physics |
Volume | 90 |
Issue number | 5 |
DOIs | |
State | Published - Nov 13 2014 |
Externally published | Yes |
ASJC Scopus subject areas
- Atomic and Molecular Physics, and Optics