×

zbMATH — the first resource for mathematics

Performing fully parallel constraint logic programming on a quantum annealer. (English) Zbl 1452.68039
Summary: A quantum annealer exploits quantum effects to solve a particular type of optimization problem. The advantage of this specialized hardware is that it effectively considers all possible solutions in parallel, thereby potentially outperforming classical computing systems. However, despite quantum annealers having recently become commercially available, there are relatively few high-level programming models that target these devices. In this article, we show how to compile a subset of Prolog enhanced with support for constraint logic programming into a two-local Ising-model Hamiltonian suitable for execution on a quantum annealer. In particular, we describe the series of transformations one can apply to convert constraint logic programs expressed in Prolog into an executable form that bears virtually no resemblance to a classical machine model yet that evaluates the specified constraints in a fully parallel manner. We evaluate our efforts on a 1,095-qubit D-Wave 2X quantum annealer and describe the approach’s associated capabilities and shortcomings.

MSC:
68N17 Logic programming
81P68 Quantum computation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barahona, F., On the computational complexity of Ising spin glass models, Journal of Physics A: Mathematical and General, 15, 10, 3241, (1982)
[2] (2016)
[3] Bravyi, S.; Bessen, A. J.; Terhal, B. M., (2006)
[4] Bravyi, S.; Hastings, M., On complexity of the quantum Ising model, Communications in Mathematical Physics, 349, 1, 1-45, (2017) · Zbl 1357.82009
[5] Brayton, R.; Mishchenko, A.; Touili, T.; Cook, B.; Jackson, P., (2010)
[6] Bunyk, P. I.; Hoskinson, E. M.; Johnson, M. W.; Tolkacheva, E.; Altomare, F.; Berkley, A. J.; Harris, R.; Hilton, J. P.; Lanting, T.; Przybysz, A. J.; Whittaker, J., Architectural considerations in the design of a superconducting quantum annealing processor, IEEE Transactions on Applied Superconductivity, 24, 4, 1-10, (2014)
[7] Cai, J.; Macready, B.; Roy, A., (2014)
[8] Choi, V., Minor-embedding in adiabatic quantum computation: I. The parameter setting problem, Quantum Information Processing, 7, 5, 193-209, (2008) · Zbl 1160.81326
[9] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms, (2001), MIT Press · Zbl 1047.68161
[10] Cross, A. W.; Bishop, L. S.; Smolin, J. A.; Gambetta, J. M., (2017)
[11] Developer Guide for Python, (2017), D-Wave Systems, Inc.: D-Wave Systems, Inc., Burnaby, British Columbia, Canada
[12] ToQ Overview, (2017), D-Wave Systems, Inc.: D-Wave Systems, Inc., Burnaby, British Columbia, Canada
[13] Dahl, E. D., Deqo: A Direct Embedding Quantum Optimizer, (2014), D-Wave Systems, Inc
[14] Dutra, I., (2010)
[15] Farhi, E.; Gutmann, S., Analog analogue of a digital quantum computation, Physical Review A, 57, 2403-2406, (1998)
[16] Feynman, R. P., Quantum mechanical computers, Foundations of Physics, 16, 6, 507-531, (1986)
[17] Finnila, A. B.; Gomez, M. A.; Sebenik, C.; Stenson, C.; Doll, J. D., Quantum annealing: A new method for minimizing multidimensional functions, Chemical Physics Letters, 219, 5, 343-348, (1994)
[18] (2017)
[19] Gansner, E. R.; North, S. C., An open graph visualization system and its applications to software engineering, Software–Practice and Experience, 30, 11, 1203-1233, (2000) · Zbl 1147.68782
[20] Green, A. S.; Lumsdaine, P. L.; Ross, N. J.; Selinger, P.; Valiron, B., (2013)
[21] Grover, L. K., (1996)
[22] Heim, B.; Brown, E. W.; Wecker, D.; Troyer, M., (2017)
[23] Hen, I.; Young, A. P., Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems, Physical Review E, 84, 061152, (2011)
[24] James, R. P.; Ortiz, G.; Sabry, A., (2011)
[25] Javadiabhari, A.; Patil, S.; Kudrow, D.; Heckey, J.; Lvov, A.; Chong, F. T.; Martonosi, M., ScaffCC: Scalable compilation and analysis of quantum programs, Parallel Computing, 45, 2-17, (2015)
[26] Johnson, M. W.; Amin, M. H. S.; Gildert, S.; Lanting, T.; Hamze, F.; Dickson, N.; Harris, R.; Berkley, A. J.; Johansson, J.; Bunyk, P.; Chapple, E. M.; Enderud, C.; Hilton, J. P.; Karimi, K.; Ladizinsky, E.; Ladizinsky, N.; Oh, T.; Perminov, I.; Rich, C.; Thom, M. C.; Tolkacheva, E.; Truncik, C. J. S.; Uchaikin, S.; Wang, J.; Wilson, B.; Rose, G., Quantum annealing with manufactured spins, Nature, 473, 7346, 194-198, (2011)
[27] Kadowaki, T.; Nishimori, H., Quantum annealing in the transverse Ising model, Physical Review E, 58, 5355-5363, (1998)
[28] Kahn, H.; La Fontaine, R.; Lau, R., (2000)
[29] Kaminsky, W. M.; Lloyd, S.; Orlando, T. P., (2004)
[30] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671-680, (1983) · Zbl 1225.90162
[31] Knight, W., (2017)
[32] Lucas, A., Ising formulations of many NP problems, Frontiers in Physics, 2, 5, 1-15, (2014)
[33] (2017)
[34] Nethercote, N.; Stuckey, P. J.; Becket, R.; Brand, S.; Duck, G. J.; Tack, G.; Bessière, C., (2007)
[35] Pakin, S., (2016)
[36] Robinson, J. A., A machine-oriented logic based on the resolution principle, Journal of the ACM, 12, 1, 23-41, (1965) · Zbl 0139.12303
[37] Shor, P. W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Review, 41, 2, 303-332, (1999) · Zbl 1005.11507
[38] Smith, R. S.; Curtis, M. J.; Zeng, W. J., (2017)
[39] Thomas, D.; Moorby, P., The Verilog Hardware Description Language, (2002), Springer
[40] Triska, M., (2012)
[41] Wecker, D.; Svore, K. M., (2014)
[42] Wielemaker, J.; Schrijvers, T.; Triska, M.; Lager, T., SWI-Prolog, Theory and Practice of Logic Programming, 12, 1-2, 67-96, (2012) · Zbl 1244.68023
[43] Wolf, C.; Glaser, J., (2013)
[44] Yamaoka, M.; Yoshimura, C.; Hayashi, M.; Okuyama, T.; Aoki, H.; Mizuno, H., A 20k-spin Ising chip to solve combinatorial optimization problems with CMOS annealing, IEEE Journal of Solid-State Circuits, 51, 1, 303-309, (2016)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.