A Study of Heuristic Guesses for Adiabatic Quantum Computation

DSpace/Manakin Repository

A Study of Heuristic Guesses for Adiabatic Quantum Computation

Citable link to this page


Title: A Study of Heuristic Guesses for Adiabatic Quantum Computation
Author: Perdomo-Ortiz, Alejandro; Venegas-Andraca, Salvador E.; Aspuru-Guzik, Alan

Note: Order does not necessarily reflect citation order of authors.

Citation: Perdomo-Ortiz, Alejandro, Salvador E. Venegas-Andraca, and Alán Aspuru-Guzik. 2010. A study of heuristic guesses for adiabatic quantum computation. Quantum Information Processing: 1-20.
Full Text & Related Files:
Abstract: Adiabatic quantum computation (AQC) is a universal model for quantum computation which seeks to transform the initial ground state of a quantum system into a final ground state encoding the answer to a computational problem. AQC initial Hamiltonians conventionally have a uniform superposition as ground state. We diverge from this practice by introducing a simple form of heuristics: the ability to start the quantum evolution with a state which is a guess to the solution of the problem. With this goal in mind, we explain the viability of this approach and the needed modifications to the conventional AQC (CAQC) algorithm. By performing a numerical study on hard-to-satisfy 6 and 7 bit random instances of the satisfiability problem (3-SAT), we show how this heuristic approach is possible and we identify that the performance of the particular algorithm proposed is largely determined by the Hamming distance of the chosen initial guess state with respect to the solution. Besides the possibility of introducing educated guesses as initial states, the new strategy allows for the possibility of restarting a failed adiabatic process from the measured excited state as opposed to restarting from the full superposition of states as in CAQC. The outcome of the measurement can be used as a more refined guess state to restart the adiabatic evolution. This concatenated restart process is another heuristic that the CAQC strategy cannot capture.
Published Version: doi:10.1007/s11128-010-0168-z
Other Sources: http://arxiv.org/abs/0807.0354
Terms of Use: This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#OAP
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:4646352
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search