Increase of degeneracy improves the performance of the quantum adiabatic algorithm

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

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 languageEnglish (US)
Article number052317
JournalPhysical Review A - Atomic, Molecular, and Optical Physics
Volume90
Issue number5
DOIs
StatePublished - Nov 13 2014
Externally publishedYes

ASJC Scopus subject areas

  • Atomic and Molecular Physics, and Optics

Fingerprint

Dive into the research topics of 'Increase of degeneracy improves the performance of the quantum adiabatic algorithm'. Together they form a unique fingerprint.

Cite this