{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T18:37:46Z","timestamp":1764700666525,"version":"3.37.3"},"reference-count":44,"publisher":"Cambridge University Press (CUP)","issue":"5-6","license":[{"start":{"date-parts":[[2018,5,6]],"date-time":"2018-05-06T00:00:00Z","timestamp":1525564800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2018,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A<jats:italic>quantum annealer<\/jats:italic>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.<\/jats:p>","DOI":"10.1017\/s1471068418000066","type":"journal-article","created":{"date-parts":[[2018,5,5]],"date-time":"2018-05-05T23:17:07Z","timestamp":1525562227000},"page":"928-949","source":"Crossref","is-referenced-by-count":12,"title":["Performing fully parallel constraint logic programming on a quantum annealer"],"prefix":"10.1017","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5220-1985","authenticated-orcid":false,"given":"SCOTT","family":"PAKIN","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,5,6]]},"reference":[{"key":"S1471068418000066_ref30","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"S1471068418000066_ref32","doi-asserted-by":"publisher","DOI":"10.3389\/fphy.2014.00005"},{"key":"S1471068418000066_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/1097-024X(200009)30:11<1203::AID-SPE338>3.0.CO;2-N"},{"key":"S1471068418000066_ref29","doi-asserted-by":"crossref","unstructured":"Kaminsky W. M. , Lloyd S. and Orlando T. P. 2004. Scalable superconducting architecture for adiabatic quantum computation. arXiv:quant-ph\/0403090v2.","DOI":"10.1007\/978-1-4419-9092-1_25"},{"key":"S1471068418000066_ref24","unstructured":"James R. P. , Ortiz G. and Sabry A. 2011. Quantum computing over finite fields. arXiv:1101.3764 [quant-ph]."},{"key":"S1471068418000066_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2014.12.001"},{"key":"S1471068418000066_ref37","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144598347011"},{"key":"S1471068418000066_ref2","unstructured":"Berkeley Logic Synthesis and Verification Group. 2016. ABC: A system for sequential synthesis and verification. URL: http:\/\/www.eecs.berkeley.edu\/~alanmi\/abc\/. [Accessed on April 24, 2018]."},{"key":"S1471068418000066_ref22","unstructured":"Heim B. , Brown E. W. , Wecker D. and Troyer M. 2017. Designing adiabatic quantum optimization: A case study for the traveling salesman problem. arXiv:1702.06248v1 [quant-ph]."},{"volume-title":"The Verilog Hardware Description Language","year":"2002","author":"Thomas","key":"S1471068418000066_ref39"},{"key":"S1471068418000066_ref26","doi-asserted-by":"publisher","DOI":"10.1038\/nature10012"},{"volume-title":"Developer Guide for Python","year":"2017","key":"S1471068418000066_ref11"},{"key":"S1471068418000066_ref23","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.061152"},{"volume-title":"Deqo: A Direct Embedding Quantum Optimizer","year":"2014","author":"Dahl","key":"S1471068418000066_ref13"},{"volume-title":"ToQ Overview","year":"2017","key":"S1471068418000066_ref12"},{"key":"S1471068418000066_ref43","unstructured":"Wolf C. and Glaser J. 2013. Yosys\u2013-A free Verilog synthesis suite. In Proc. of the 21st Austrian Workshop on Microelectronics (Austrochip 2013). Linz, Austria."},{"key":"S1471068418000066_ref3","unstructured":"Bravyi S. , Bessen A. J. and Terhal B. M. 2006. Merlin-Arthur games and stoquastic complexity. arXiv:quant-ph\/0611021v2."},{"key":"S1471068418000066_ref7","unstructured":"Cai J. , Macready B. and Roy A. 2014. A practical heuristic for finding graph minors. arXiv:1406.2741 [quant-ph]."},{"key":"S1471068418000066_ref15","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.57.2403"},{"key":"S1471068418000066_ref18","unstructured":"Fujitsu Laboratories Ltd. 2017. Fujitsu Laboratories Develops New Architecture that Rivals Quantum Computers in Utility. Press release, 20 October 2016, Kawasaki, Japan. URL: http:\/\/www.fujitsu.com\/global\/about\/resources\/news\/press-releases\/2016\/1020-02.html [Accessed on April 24, 2018]."},{"key":"S1471068418000066_ref34","unstructured":"Nethercote N. , Stuckey P. J. , Becket R. , Brand S. , Duck G. J. and Tack G. 2007. MiniZinc: Towards a standard CP modelling language. In Proc. of the 13th International Conference on Principles and Practice of Constraint Programming, C. Bessi\u00e8re , Ed. Springer, Berlin, Heidelberg, 529\u2013543."},{"key":"S1471068418000066_ref27","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.58.5355"},{"key":"S1471068418000066_ref33","unstructured":"Microsoft Corp. 2017. The Q# progamming language. URL: https:\/\/docs.microsoft.com\/en-us\/quantum\/quantum-qr-intro [Accessed on April 24, 2018]."},{"key":"S1471068418000066_ref40","doi-asserted-by":"crossref","unstructured":"Triska M. 2012. The finite domain constraint solver of SWI-Prolog. In Proc. of the 11th International Symposium on Functional and Logic Programming (FLOPS 2012). Lecture Notes in Computer Science, vol. 7294. Kobe, Japan, 307\u2013316.","DOI":"10.1007\/978-3-642-29822-6_24"},{"key":"S1471068418000066_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-008-0082-9"},{"key":"S1471068418000066_ref42","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000494"},{"key":"S1471068418000066_ref20","doi-asserted-by":"crossref","unstructured":"Green A. S. , Lumsdaine P. L. , Ross N. J. , Selinger P. and Valiron B. 2013. Quipper: A scalable quantum programming language. In Proc. of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York, USA, 333\u2013342.","DOI":"10.1145\/2491956.2462177"},{"key":"S1471068418000066_ref1","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/15\/10\/028"},{"key":"S1471068418000066_ref21","doi-asserted-by":"crossref","unstructured":"Grover L. K. 1996. A fast quantum mechanical algorithm for database search. In Proc. of the 28th Annual ACM Symposium on Theory of Computing. ACM, New York, NY, USA, 212\u2013219.","DOI":"10.1145\/237814.237866"},{"key":"S1471068418000066_ref41","unstructured":"Wecker D. and Svore K. M. 2014. LIQUi|\u3009: A software design architecture and domain-specific language for quantum computing. arXiv:1402.4467 [quant-ph]."},{"key":"S1471068418000066_ref5","doi-asserted-by":"crossref","unstructured":"Brayton R. and Mishchenko A. 2010. ABC: An academic industrial-strength verification tool. In Proc. 22nd International Conference on Computer Aided Verification, T. Touili , B. Cook , and P. Jackson , Eds. Springer, Berlin, Heidelberg, Edinburgh, UK, 24\u201340.","DOI":"10.1007\/978-3-642-14295-6_5"},{"volume-title":"Introduction to Algorithms","year":"2001","author":"Cormen","key":"S1471068418000066_ref9"},{"key":"S1471068418000066_ref44","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1109\/JSSC.2015.2498601","article-title":"A 20k-spin Ising chip to solve combinatorial optimization problems with CMOS annealing","volume":"51","author":"Yamaoka","year":"2016","journal-title":"IEEE Journal of Solid-State Circuits"},{"key":"S1471068418000066_ref14","unstructured":"Dutra I. 2010. Constraint logic programming: A short tutorial. URL: https:\/\/www.dcc.fc.up.pt\/~ines\/talks\/clp-v1.pdf. [Accessed on April 24, 2018]."},{"key":"S1471068418000066_ref36","doi-asserted-by":"publisher","DOI":"10.1145\/321250.321253"},{"key":"S1471068418000066_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0009-2614(94)00117-0"},{"key":"S1471068418000066_ref10","unstructured":"Cross A. W. , Bishop L. S. , Smolin J. A. and Gambetta J. M. 2017. Open quantum assembly language. arXiv:1707.03429 [quant-ph]."},{"key":"S1471068418000066_ref6","doi-asserted-by":"publisher","DOI":"10.1109\/TASC.2014.2318294"},{"key":"S1471068418000066_ref35","doi-asserted-by":"crossref","unstructured":"Pakin S. 2016. A quantum macro assembler. In Proc. of the 2016 IEEE High Performance Extreme Computing Conference (HPEC).","DOI":"10.1109\/HPEC.2016.7761637"},{"key":"S1471068418000066_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-016-2787-4"},{"key":"S1471068418000066_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01886518"},{"key":"S1471068418000066_ref31","unstructured":"Knight W. 2017. IBM Raises the Bar with a 50-Qubit Quantum Computer. MIT Technology Review. 10 November 2017. ISSN: 0040-1692. URL: https:\/\/www.technologyreview.com\/s\/609451\/ibm-raises-the-bar-with-a-50-qubit-quantum-computer [Accessed on April 24, 2018]."},{"key":"S1471068418000066_ref38","unstructured":"Smith R. S. , Curtis M. J. and Zeng W. J. 2017. A practical quantum instruction set architecture. arXiv:1608.03355 [quant-ph]."},{"key":"S1471068418000066_ref28","unstructured":"Kahn H. , La Fontaine R. and Lau R. 2000. Electronic design interchange format (EDIF): Part 2: Version 4 0 0. Standard IEC 61690-2:2000, International Electrotechnical Commission, Manchester, UK."}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068418000066","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,17]],"date-time":"2019-10-17T11:27:22Z","timestamp":1571311642000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068418000066\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,6]]},"references-count":44,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["S1471068418000066"],"URL":"https:\/\/doi.org\/10.1017\/s1471068418000066","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2018,5,6]]}}}