Sombrero adiabatic quantum computation

@misc{citeulike:2954745, abstract = {Adiabatic quantum computation (AQC) employs the ground state of time-dependent Hamiltonians for algorithm implementation. AQC initial Hamiltonians conventionally have a uniform superposition as ground state. We diverge from this practice by introducing a new strategy, in which adiabatic evolution starts with an initial guess chosen at random or following intuition about the problem, followed by a ``sombrero-like'' perturbation, hence the name sombrero AQC (SAQC). We provide a scheme to build initial Hamiltonians which encode such initial guesses in their ground states, and we present a proof of concept for SAQC by performing an exhaustive numerical study on hard-to-satisfy instances of the satisfiability problem (3-SAT). Our results show that about 35\% of the initial 7 variable guesses have a significantly larger minimum gap compared to the minimum gap expected for conventional AQC (CAQC), possibly allowing for more efficient quantum algorithms. Finally, we propose serial and parallel versions of a quantum adiabatic algorithm based on SAQC.}, author = {Perdomo, Alejandro and Venegas-Andraca, Salvador E. and Aspuru-Guzik, Al\&\#xe1;n }, citeulike-article-id = {2954745}, eprint = {0807.0354}, month = {Jul}, posted-at = {2008-07-03 02:00:57}, priority = {2}, title = {Sombrero adiabatic quantum computation}, url = {http://arxiv.org/abs/0807.0354}, year = {2008} }

TY - ELEC ID - citeulike:2954745 L3 - citeulike-article-id:2954745 TI - Sombrero adiabatic quantum computation N2 - Adiabatic quantum computation (AQC) employs the ground state of time-dependent Hamiltonians for algorithm implementation. AQC initial Hamiltonians conventionally have a uniform superposition as ground state. We diverge from this practice by introducing a new strategy, in which adiabatic evolution starts with an initial guess chosen at random or following intuition about the problem, followed by a ``sombrero-like'' perturbation, hence the name sombrero AQC (SAQC). We provide a scheme to build initial Hamiltonians which encode such initial guesses in their ground states, and we present a proof of concept for SAQC by performing an exhaustive numerical study on hard-to-satisfy instances of the satisfiability problem (3-SAT). Our results show that about 35% of the initial 7 variable guesses have a significantly larger minimum gap compared to the minimum gap expected for conventional AQC (CAQC), possibly allowing for more efficient quantum algorithms. Finally, we propose serial and parallel versions of a quantum adiabatic algorithm based on SAQC. AU - Perdomo, Alejandro AU - Venegas-Andraca, Salvador AU - Aspuru-Guzik, Alán PY - 2008/Jul/02/ UR - http://arxiv.org/abs/0807.0354 ER -