caa a22 4500 445886269 CHVBK 20180317145600.0 cr unu---uuuuu 170323e20110201xx s 000 0 eng 10.1007/s11128-010-0168-z doi (NATIONALLICENCE)springer-10.1007/s11128-010-0168-z A study of heuristic guesses for adiabatic quantum computation [Elektronische Daten] [Alejandro Perdomo-Ortiz, Salvador Venegas-Andraca, Alán Aspuru-Guzik] 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. Springer Science+Business Media, LLC, 2010 Heuristic algorithms nationallicence Adiabatic quantum computation nationallicence Adiabatic preparation nationallicence Quantum algorithms nationallicence Perdomo-Ortiz Alejandro Department of Chemistry and Chemical Biology, Harvard University, 12 Oxford Street, 02138, Cambridge, MA, USA aut Venegas-Andraca Salvador Quantum Information Processing Group, Tecnológico de Monterrey Campus Estado de México, Carretera Lago Gpe, Km 3.5, Atizapán de Zaragoza, Edo. México, México aut Aspuru-Guzik Alán Department of Chemistry and Chemical Biology, Harvard University, 12 Oxford Street, 02138, Cambridge, MA, USA aut Quantum Information Processing Springer US; http://www.springer-ny.com 10/1(2011-02-01), 33-52 1570-0755 10:1<33 2011 10 11128 https://doi.org/10.1007/s11128-010-0168-z text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11128-010-0168-z text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Perdomo-Ortiz Alejandro Department of Chemistry and Chemical Biology, Harvard University, 12 Oxford Street, 02138, Cambridge, MA, USA aut NATIONALLICENCE 700 1- Venegas-Andraca Salvador Quantum Information Processing Group, Tecnológico de Monterrey Campus Estado de México, Carretera Lago Gpe, Km 3.5, Atizapán de Zaragoza, Edo. México, México aut NATIONALLICENCE 700 1- Aspuru-Guzik Alán Department of Chemistry and Chemical Biology, Harvard University, 12 Oxford Street, 02138, Cambridge, MA, USA aut NATIONALLICENCE 773 0- Quantum Information Processing Springer US; http://www.springer-ny.com 10/1(2011-02-01), 33-52 1570-0755 10:1<33 2011 10 11128 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer