A study of heuristic guesses for adiabatic quantum computation. (English) Zbl 1209.81072
Summary: 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.
Keywords:
heuristic algorithms; adiabatic quantum computation; adiabatic preparation; quantum algorithmsReferences:
| [1] | Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution, quant-ph/0001106 (2000) |
| [2] | Childs A.M., Farhi E., Preskill J.: Robustness of adiabatic quantum computation. Phys. Rev. A 65, 012322 (2001) · doi:10.1103/PhysRevA.65.012322 |
| [3] | Lidar D.A.: Towards fault tolerant adiabatic quantum computation. Phys. Rev. Lett. 100, 160506 (2008) · doi:10.1103/PhysRevLett.100.160506 |
| [4] | Farhi E., Goldstone J., Gutmann S., Lapan J., Lundgren A., Preda D.: A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 472–475 (2001) · Zbl 1226.81046 · doi:10.1126/science.1057726 |
| [5] | Hogg T.: Adiabatic quantum computing for random satisfiability problems. Phys. Rev. A 67, 022314 (2003) · doi:10.1103/PhysRevA.67.022314 |
| [6] | Young A.P., Knysh S., Smelyanskiy V.N.: Size dependence of the minimum excitation gap in the quantum adiabatic algorithm. Phys. Rev. Lett. 101, 170503 (2008) · doi:10.1103/PhysRevLett.101.170503 |
| [7] | Perdomo A., Truncik C., Tubert-Brohman I., Rose G., Aspuru-Guzik A.: Construction of model Hamiltonians for adiabatic quantum computation and its application to finding low-energy conformations of lattice protein models. Phys. Rev. A 78, 012320 (2008) · doi:10.1103/PhysRevA.78.012320 |
| [8] | Farhi, E., Goldstone, J., Gutmann, S.: Quantum adiabatic evolution algorithms with different paths, quant-ph/0208135 (2002) · Zbl 1187.81063 |
| [9] | Rezakhani A.T., Kuo W., Hamma A., Lidar D.A., Zanardi P.: Quantum adiabatic brachistochrone. Phys. Rev. Lett. 103, 080502 (2009) · doi:10.1103/PhysRevLett.103.080502 |
| [10] | Farhi E., Goldstone J., Gutmann S., Nagaj D.: How to make the quantum adiabatic algorithm fail. Int. J. Quantum Inf. 06, 503–516 (2008) · Zbl 1192.81064 · doi:10.1142/S021974990800358X |
| [11] | Roland J., Cerf N.J.: Quantum search by local adiabatic evolution. Phys. Rev. A 65, 042308 (2002) · doi:10.1103/PhysRevA.65.042308 |
| [12] | Znidaric M., Horvat M.: Exponential complexity of an adiabatic algorithm for an NP-complete problem. Phys. Rev. A 73, 022329 (2006) · doi:10.1103/PhysRevA.73.022329 |
| [13] | Amin M.H.S.: Effect of local minima on adiabatic quantum optimization. Phys. Rev. Lett. 100, 130503 (2008) · doi:10.1103/PhysRevLett.100.130503 |
| [14] | Garey M., Johnson D.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979) · Zbl 0411.68039 |
| [15] | Sipser M.: Introduction to the Theory of Computation. PWS Publishing Company, Boston (2005) · Zbl 1169.68300 |
| [16] | Hogg T.: Highly structured searches with quantum computers. Phys. Rev. Lett. 80, 2473 (1998) · doi:10.1103/PhysRevLett.80.2473 |
| [17] | Hogg T.: Quantum search heuristics. Phys. Rev. A 61, 052311 (2000) · Zbl 0983.81006 · doi:10.1103/PhysRevA.61.052311 |
| [18] | Grover L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79, 325 (1997) · doi:10.1103/PhysRevLett.79.325 |
| [19] | Aspuru-Guzik A., Dutoi A.D., Love P.J., Head-Gordon M.: Simulated quantum computation of molecular energies. Science 309, 1704–1707 (2005) · doi:10.1126/science.1113479 |
| [20] | Ward N.J., Kassal I., Aspuru-Guzik A.: Preparation of many-body states for quantum simulation. J. Chem. Phys. 130, 194105 (2009) · doi:10.1063/1.3115177 |
| [21] | Wang H., Kais S., Aspuru-Guzik A., Hoffmann M.R.: Quantum algorithm for obtaining the energy spectrum of molecular systems. Phys. Chem. Chem. Phys. 10, 5388–5393 (2008) · doi:10.1039/b804804e |
| [22] | Wang H., Ashhab S., Nori F.: Efficient quantum algorithm for preparing molecular-system-like states on a quantum computer. Phys. Rev. A 79, 042335 (2009) · doi:10.1103/PhysRevA.79.042335 |
| [23] | Kohen D., Tannor D.J.: Quantum adiabatic switching. J. Chem. Phys. 98, 3168 (1993) · doi:10.1063/1.464089 |
| [24] | Aharonov, D., Ta-Shma, A.: Adiabatic quantum state generation and statistical zero knowledge, In: Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, pp. 20–29. San Diego, CA, USA, ACM (2003) · Zbl 1192.81048 |
| [25] | Messiah A.: Quantum Mechanics (Physics). Dover Publications, Mineola (1999) · Zbl 0102.42602 |
| [26] | Marzlin K., Sanders B.C.: Inconsistency in the application of the adiabatic theorem. Phys. Rev. Lett. 93, 160408 (2004) · doi:10.1103/PhysRevLett.93.160408 |
| [27] | Tong D.M., Singh K., Kwek L.C., Oh C.H.: Sufficiency criterion for the validity of the adiabatic approximation. Phys. Rev. Lett. 98, 150402 (2007) · doi:10.1103/PhysRevLett.98.150402 |
| [28] | Wei Z., Ying M.: Quantum adiabatic computation and adiabatic conditions. Phys. Rev. A 76, 024304 (2007) · doi:10.1103/PhysRevA.76.024304 |
| [29] | Zhao Y.: Reexamination of the quantum adiabatic theorem. Phys. Rev. A 77, 032109 (2008) · doi:10.1103/PhysRevA.77.032109 |
| [30] | Amin M.H.S.: Consistency of the adiabatic theorem. Phys. Rev. Lett. 102, 220401 (2009) · doi:10.1103/PhysRevLett.102.220401 |
| [31] | MacKenzie R., Morin-Duchesne A., Paquette H., Pinel J.: Validity of the adiabatic approximation in quantum mechanics. Phys. Rev. A 76, 044102 (2007) · doi:10.1103/PhysRevA.76.044102 |
| [32] | Ambainis, A., Regev, O.: An elementary proof of the quantum adiabatic theorem, quant-ph/0411152s (2004) |
| [33] | Jansen S., Ruskai M., Seiler R.: Bounds for the adiabatic approximation with applications to quantum computation. J. Math. Phys. 48, 102111 (2007) · Zbl 1152.81490 · doi:10.1063/1.2798382 |
| [34] | Da Wu, J., Sheng Z.M., Lan C.J., De Zhang, Y.: Adiabatic approximation condition, arXiv:0706.0264v2 (2007) |
| [35] | Chen, J.-L., Sheng Z.M., Da Wu, J., De Zhang, Y.: Invariant perturbation theory of adiabatic process, http://arxiv.org/abs/0706.0299 (2007) |
| [36] | Andrecut M., Ali M.K.: Unstructured adiabatic quantum search. Int. J. Theor. Phys. 43, 925–931 (2004) · Zbl 1060.81513 · doi:10.1023/B:IJTP.0000048589.20608.aa |
| [37] | Siu M.S.: Adiabatic rotation, quantum search, and preparation of superposition states. Phys. Rev. A 75, 062337 (2007) · doi:10.1103/PhysRevA.75.062337 |
| [38] | Acharyya S.: SAT algorithms for colouring some special classes of graphs: some theoretical and experimental results. J. Satisfiability, Boolean Model. Comput. 4, 33–35 (2007) · Zbl 1147.68700 |
| [39] | Gent, I., Walsh, T.: The search for satisfaction, Internal report, department of computer science, University of Strathclyde (1999) |
| [40] | Mezard M., Parisi G., Zecchina R.: Analytic and algorithmic solution of random satisfiability problems. Science 297, 812–815 (2002) · doi:10.1126/science.1073287 |
| [41] | Achlioptas D., Naor A., Peres Y.: Rigorous location of phase transitions in hard optimization problems. Nature 435, 759–764 (2005) · doi:10.1038/nature03602 |
| [42] | Mezard M., Mora T., Zecchina R.: Clustering of solutions in the random satisfiability problem. Phys. Rev. Lett. 94, 197205 (2005) · doi:10.1103/PhysRevLett.94.197205 |
| [43] | Watanabe research group of Department of Mathematics and Computing Sciences, Tokyo Institute of Technology, http://www.is.titech.ac.jp/\(\sim\)watanabe/gensat/ |
| [44] | Farhi, E., Goldstone, J., Gosset, D., Gutmann, S., Meyer, H., Shor, P.: Quantum adiabatic algorithms, small gaps, and different paths, arxiv.org/abs/0909.4766 (2009) · Zbl 1247.81085 |
| [45] | Žnidaric M.: Scaling of the running time of the quantum adiabatic algorithm for propositional satisfiability. Phys. Rev. A 71, 062305 (2005) · doi:10.1103/PhysRevA.71.062305 |
| [46] | Du J., Hu L., Wang Y., Wu J., Zhao M., Suter D.: Experimental study of the validity of quantitative conditions in the quantum adiabatic theorem. Phys. Rev. Lett. 101, 060403 (2008) · doi:10.1103/PhysRevLett.101.060403 |
| [47] | Kautz H., Selman B.: The state of SAT. Discrete Appl. Math. 155, 1514–1524 (2007) · Zbl 1121.68108 · doi:10.1016/j.dam.2006.10.004 |
| [48] | Farhi, E., Goldstone, J., Gutmann, S.: Quantum adiabatic evolution algorithms with different paths, quant-ph/0208135 (2002) · Zbl 1187.81063 |
| [49] | Kempe J., Kitaev A., Regev O.: The complexity of the local Hamiltonian problem. SIAM J. Comput. 35, 1070–1097 (2006) · Zbl 1102.81032 · doi:10.1137/S0097539704445226 |
| [50] | Bravyi, S.: Efficient algorithm for a quantum analogue of 2-SAT, quant-ph/0602108 (2006) |
| [51] | Oliveira R., Terhal B.M.: The complexity of quantum system on a two-dimensional square lattice. Quantum Inf. Comput. 8, 0900–0924 (2008) |
| [52] | Aharonov D., Ta-Shma A.: Adiabatic quantum state generation. SIAM J. Comput. 37, 47–82 (2007) · Zbl 1134.81008 · doi:10.1137/060648829 |
| [53] | Mizel A., Lidar D.A., Mitchell M.: Simple proof of equivalence between adiabatic quantum computation and the circuit model. Phys. Rev. Lett. 99, 070502 (2007) · doi:10.1103/PhysRevLett.99.070502 |
| [54] | Schutzhold R., Schaller G.: Adiabatic quantum algorithms as quantum phase transitions: first versus second order. Phys. Rev. A 74, 060304 (2006) · doi:10.1103/PhysRevA.74.060304 |
| [55] | Latorre J., Orus R.: Adiabatic quantum computation and quantum phase transitions. Phys. Rev. A 69, 062302 (2004) · doi:10.1103/PhysRevA.69.062302 |
| [56] | Orus R., Latorre J.I.: Universality of entanglement and quantum-computation complexity. Phys. Rev. A 69, 052308 (2004) · doi:10.1103/PhysRevA.69.052308 |
| [57] | Young, A.P., Knysh, S., Smelyanskiy, V.N.: First-order phase transition in the quantum adiabatic algorithm. Phys. Rev. Lett. 104 (2010) · Zbl 1219.81081 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
