{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,11]],"date-time":"2024-12-11T05:46:15Z","timestamp":1733895975850,"version":"3.30.1"},"reference-count":68,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2024,7,31]],"date-time":"2024-07-31T00:00:00Z","timestamp":1722384000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,12,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The lack of purely Quantum Programming Languages constitutes a hurdle in the general description of quantum computational processes; the implementation is heavily dependent on the considered quantum computational model. To bypass the obstacle, this paper pursues a new direction, investigating the compilation of classical programming paradigms over different quantum computational models: Gate-Based, Measurement-Based and Adiabatic Quantum Computation. Since graphs can be exploited to describe both classical and quantum computations, the problem of graph encoding on quantum hardware is tightly connected to our purposes. As such, it holds a major relevance in our quest for quantum compilation. While studying these topics through the lenses of Graph Theory, declarative programming emerges as the ideal candidate for such endeavour. In this paper we consider some existing quantum computational models and for each of them we identify the main subtleties in the compilation of classical languages. In turn, we break these complexities down into easier problems to stimulate further developments in this area of research. As it turns out, the observations for each model differ widely. Nevertheless, as for the tasks here considered, no model seems to claim supremacy over the others. In contrast, declarative programming maintains the spot as the ideal candidate for quantum compilation, independently of the model.<\/jats:p>","DOI":"10.1093\/logcom\/exae040","type":"journal-article","created":{"date-parts":[[2024,8,1]],"date-time":"2024-08-01T02:13:48Z","timestamp":1722478428000},"page":"1526-1555","source":"Crossref","is-referenced-by-count":0,"title":["Classical computation over quantum architectures"],"prefix":"10.1093","volume":"34","author":[{"given":"Alex","family":"Della Schiava","sequence":"first","affiliation":[{"name":"University of Udine Department of Mathematics, Computer Science and Physics, , Udine 33100 ,","place":["Italy"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carla","family":"Piazza","sequence":"additional","affiliation":[{"name":"Department of Mathematics , Computer Science and Physics, , Udine 33100 ,","place":["Italy"]},{"name":"University of Udine , Computer Science and Physics, , Udine 33100 ,","place":["Italy"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Riccardo","family":"Romanello","sequence":"additional","affiliation":[{"name":"Department of Mathematics , Computer Science and Physics, , Udine 33100 ,","place":["Italy"]},{"name":"University of Udine , Computer Science and Physics, , Udine 33100 ,","place":["Italy"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2024,7,31]]},"reference":[{"key":"2024121019262506300_ref1","first-page":"755","article-title":"Adiabatic quantum computation is equivalent to standard quantum computation","volume-title":"SIAM Rev.","author":"Aharonov","year":"2005"},{"key":"2024121019262506300_ref2","first-page":"92540I","article-title":"Programming non-trivial algorithms in the measurement-based quantum computation model","volume-title":"Emerging Technologies in Security and Defence II; and Quantum-Physics-Based Information Security III","author":"Alsing","year":"2014"},{"key":"2024121019262506300_ref3","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0304-4149(89)90040-9","article-title":"Quantum stochastic optimization","volume":"33","author":"Apolloni","year":"1989","journal-title":"Stochastic Processes and Their Applications"},{"key":"2024121019262506300_ref4","first-page":"46","article-title":"Abstract argumentation goes quantum: an encoding to QUBO problems","volume-title":"PRICAI 2022: Trends in Artificial Intelligence","author":"Baioletti","year":"2022"},{"key":"2024121019262506300_ref5","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1007\/BF01011339","article-title":"The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines","volume":"22","author":"Benioff","year":"1980","journal-title":"Journal of Statistical Physics"},{"article-title":"Quantum finite automata: survey, status and research directions","year":"2019","author":"Bhatia","key":"2024121019262506300_ref6"},{"key":"2024121019262506300_ref7","doi-asserted-by":"crossref","first-page":"023029","DOI":"10.1088\/1367-2630\/17\/2\/023029","article-title":"Generalized cluster states based on finite groups","volume":"17","author":"Brell","year":"2015","journal-title":"New Journal of Physics"},{"key":"2024121019262506300_ref8","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1017\/S1471068419000474","article-title":"Solving advanced argumentation problems with answer set programming","volume":"20","author":"Brewka","year":"2020","journal-title":"Theory and Practice of Logic Programming"},{"key":"2024121019262506300_ref9","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.tcs.2017.04.016","article-title":"QUBO formulations for the graph isomorphism problem and related problems","volume":"701","author":"Calude","year":"2017","journal-title":"Theoretical Computer Science"},{"key":"2024121019262506300_ref10","doi-asserted-by":"crossref","first-page":"180501","DOI":"10.1103\/PhysRevLett.102.180501","article-title":"Universal computation by quantum walk","volume":"102","author":"Childs","year":"2009","journal-title":"Physical Review Letters"},{"key":"2024121019262506300_ref11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00026-005-0237-z","article-title":"Laplacians and the Cheeger inequality for directed graphs","volume":"9","author":"Chung","year":"2005","journal-title":"Annals of Combinatorics"},{"key":"2024121019262506300_ref12","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/j.tcs.2008.09.055","article-title":"Quantum approaches to graph colouring","volume":"410","author":"D\u2019Hondt","year":"2009","journal-title":"Theoretical Computer Science"},{"key":"2024121019262506300_ref13","doi-asserted-by":"crossref","DOI":"10.1109\/SFCS.2001.959902","article-title":"How powerful is adiabatic quantum computation","volume-title":"Proceedings 42nd IEEE Symposium on Foundations of Computer Science","author":"van Dam","year":"2001"},{"key":"2024121019262506300_ref14","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-3-031-09005-9_6","article-title":"Directed graph encoding in quantum computing supporting edge-failures","volume-title":"Reversible Computation","author":"Della Giustina","year":"2022"},{"key":"2024121019262506300_ref15","doi-asserted-by":"crossref","first-page":"100925","DOI":"10.1016\/j.jlamp.2023.100925","article-title":"Quantum encoding of dynamic directed graphs","volume":"136","author":"Della Giustina","year":"2024","journal-title":"Journal of Logical and Algebraic Methods in Programming"},{"key":"2024121019262506300_ref16","article-title":"Speeding up Answer Set Programming by Quantum Computing","volume-title":"Proceedings of Workshop on Quantum Search and Information Retrieval (QUASAR\u201924), Association for Computing Machinery","author":"Della Giustina","year":"2024"},{"key":"2024121019262506300_ref17","article-title":"Graph-theoretical arguments in support of a quantum declarative manifesto","volume-title":"Proceedings of the 38th Italian Conference on Computational Logic (CILC\u201923)","author":"Della Schiava","year":"2023"},{"key":"2024121019262506300_ref18","first-page":"79","article-title":"ASPARTIX-V19 an answer-set programming based system for abstract argumentation","volume-title":"International Symposium on Foundations of Information and Knowledge Systems","author":"Dvo\u0159\u00e1k","year":"2020"},{"key":"2024121019262506300_ref19","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1080\/19462166.2010.486479","article-title":"Answer-set programming encodings for argumentation frameworks","volume":"1","author":"Egly","year":"2010","journal-title":"Argument & Computation"},{"key":"2024121019262506300_ref20","first-page":"128","article-title":"Solutio problematis ad geometriam situs pertinentis","volume":"8","author":"Euler","year":"1736","journal-title":"Commentarii Academiae Scientiarum Imperialis Petropolitanae"},{"article-title":"Quantum computation by adiabatic evolution","year":"2000","author":"Farhi","key":"2024121019262506300_ref21"},{"key":"2024121019262506300_ref22","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/BF02650179","article-title":"Simulating physics with computers","volume":"21","author":"Feynman","year":"1982","journal-title":"International Journal of Theoretical Physics"},{"key":"2024121019262506300_ref23","article-title":"A graph-theoretic approach to map conceptual designs to XML schemas","volume":"38","author":"Franceschet","journal-title":"ACM Transactions on Database Systems"},{"key":"2024121019262506300_ref24","first-page":"156","article-title":"Computing the shortest path: a search meets graph theory","volume-title":"Int. Symposium on Discrete Algorithms (SODA)","author":"Goldberg","year":"2005"},{"key":"2024121019262506300_ref25","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1038\/46503","article-title":"Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations","volume":"402","author":"Gottesman","year":"1999","journal-title":"Nature"},{"key":"2024121019262506300_ref26","first-page":"212","article-title":"A fast quantum mechanical algorithm for database search","volume-title":"Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC\u201996), Association for Computing Machinery","author":"Grover","year":"1996"},{"volume-title":"Graph Theory, Addison Wesley Series in Mathematics","year":"1971","author":"Harary","key":"2024121019262506300_ref27"},{"key":"2024121019262506300_ref28","doi-asserted-by":"crossref","first-page":"150502","DOI":"10.1103\/PhysRevLett.103.150502","article-title":"Quantum algorithm for linear systems of equations","volume":"103","author":"Harrow","year":"2009","journal-title":"Physical Review Letters"},{"key":"2024121019262506300_ref29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/HPEC.2019.8916231","article-title":"C to D-wave: a high-level C compilation framework for quantum Annealers","volume-title":"2019 IEEE High Performance Extreme Computing Conference (HPEC)","author":"Hassan","year":"2019"},{"key":"2024121019262506300_ref30","article-title":"Solving the graph-isomorphism problem with a quantum annealer","volume":"86","author":"Hen","journal-title":"Physical Review A"},{"key":"2024121019262506300_ref31","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511810817","volume-title":"Matrix Analysis","author":"Horn","year":"1985"},{"key":"2024121019262506300_ref32","article-title":"Computing graph edit distance on quantum devices","volume":"4","author":"Incudini","journal-title":"Quantum Machine Intelligence"},{"key":"2024121019262506300_ref33","first-page":"137","article-title":"An introduction to measurement based quantum computation","volume-title":"NATO Science Series, III: Computer and Systems Sciences. Quantum Information Processing-From Theory to Experiment","author":"Jozsa","year":"2005"},{"key":"2024121019262506300_ref34","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1143\/JPSJ.5.435","article-title":"On the adiabatic theorem of quantum mechanics","volume":"5","author":"Kato","year":"1950","journal-title":"Journal of the Physical Society of Japan"},{"key":"2024121019262506300_ref35","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1080\/00107151031000110776","article-title":"Quantum random walks: an introductory overview","volume":"44","author":"Kempe","year":"2003","journal-title":"Contemporary Physics"},{"article-title":"Synthesis of unitaries with Clifford+T circuits","year":"2013","author":"Kliuchnikov","key":"2024121019262506300_ref36"},{"key":"2024121019262506300_ref37","article-title":"The unconstrained binary quadratic programming problem: a survey","volume":"28","author":"Kochenberger","journal-title":"Journal of Combinatorial Optimization"},{"article-title":"Graph coloring with quantum annealing","year":"2020","author":"Kwok","key":"2024121019262506300_ref38"},{"key":"2024121019262506300_ref39","article-title":"Universal quantum computation using the discrete-time quantum walk","volume":"81","author":"Lovett","journal-title":"Physical Review A"},{"key":"2024121019262506300_ref40","first-page":"15","article-title":"Computable and uncomputable","volume":"128","author":"Manin","year":"1980","journal-title":"Sovetskoye Radio, Moscow"},{"key":"2024121019262506300_ref41","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/978-3-030-29662-9_16","article-title":"Proportional Lumpability","volume-title":"Formal Modeling and Analysis of Timed Systems: 17th International Conference (FORMATS 2019)","author":"Marin","year":"2019"},{"key":"2024121019262506300_ref42","first-page":"285","article-title":"Finding stable models via quantum computation","volume":"2004","author":"Meyer","year":"2004","journal-title":"NMR"},{"volume-title":"Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications","year":"1987","author":"Mezard","key":"2024121019262506300_ref43"},{"key":"2024121019262506300_ref44","article-title":"Can a quantum walk tell which is which? A study of quantum walk-based graph similarity","volume":"21","author":"Minello","journal-title":"Entropy"},{"article-title":"Quantum walks on directed graphs","author":"Montanaro","key":"2024121019262506300_ref45","doi-asserted-by":"crossref","DOI":"10.26421\/QIC7.1-2-5"},{"key":"2024121019262506300_ref46","article-title":"Factoring semi-primes with (quantum) SAT-solvers","volume":"12","author":"Mosca","journal-title":"Scientific Reports"},{"key":"2024121019262506300_ref47","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"Motwani","year":"1995"},{"key":"2024121019262506300_ref48","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/S0375-9601(02)01803-0","article-title":"Quantum computation by measurement and quantum memory","volume":"308","author":"Nielsen","year":"2003","journal-title":"Physics Letters A"},{"key":"2024121019262506300_ref49","first-page":"558","volume-title":"Quantum Computation and Quantum Information","author":"Nielsen","year":"2002"},{"key":"2024121019262506300_ref50","first-page":"1","article-title":"Advanced exact synthesis of Clifford+T circuits","volume":"19","author":"Niemann","journal-title":"Quantum Information Processing"},{"key":"2024121019262506300_ref51","first-page":"374","article-title":"Quantum circuit compilation for the graph Coloring problem","volume-title":"AIxIA 2022\u2014Advances in Artificial Intelligence","author":"Oddi","year":"2023"},{"volume-title":"Computational Complexity","year":"1993","author":"Papadimitriou","key":"2024121019262506300_ref52"},{"key":"2024121019262506300_ref53","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0167-6377(92)90043-3","article-title":"Complexity of uniqueness and local search in quadratic 0\u20131 programming","volume":"11","author":"Pardalos","year":"1992","journal-title":"Operations Research Letters"},{"key":"2024121019262506300_ref54","first-page":"37","article-title":"Synthesis of CNOT minimal quantum circuits with topological constraints through ASP","volume-title":"Proceedings of the International Workshop on AI for Quantum and Quantum for AI (AIQxQIA 2023)","author":"Piazza","year":"2023"},{"key":"2024121019262506300_ref55","article-title":"Measurement-based quantum computation on cluster states","volume":"68","author":"Raussendorf","journal-title":"Physical Review A"},{"key":"2024121019262506300_ref56","first-page":"2640","article-title":"Quantum weighted model counting","volume-title":"Proc. of European Conference on Artificial Intelligence (ECAI 2020)","author":"Riguzzi","year":"2020"},{"key":"2024121019262506300_ref57","article-title":"Quantum search by local adiabatic evolution","volume":"65","author":"Roland","journal-title":"Physical Review A"},{"key":"2024121019262506300_ref58","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1137\/S0895479802410293","article-title":"On the digraph of a unitary matrix","volume":"25","author":"Severini","year":"2003","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"volume-title":"Graphs of Unitary Matrices","year":"2003","author":"Severini","key":"2024121019262506300_ref59"},{"key":"2024121019262506300_ref60","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1137\/S0036144598347011","article-title":"Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer","volume":"41","author":"Shor","year":"1999","journal-title":"SIAM Review"},{"article-title":"The measurement based quantum computing search algorithm is faster than Grover\u2019s algorithm","year":"2013","author":"Smith","key":"2024121019262506300_ref61"},{"article-title":"Logic synthesis for quantum computing","year":"2017","author":"Soeken","key":"2024121019262506300_ref62"},{"key":"2024121019262506300_ref63","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1143\/PTPS.176.384","article-title":"A short introduction to Fibonacci Anyon models","volume":"176","author":"Trebst","year":"2008","journal-title":"Progress of Theoretical Physics Supplement"},{"volume-title":"Graph Theory and Complex Networks","year":"2010","author":"Van Steen","key":"2024121019262506300_ref64"},{"key":"2024121019262506300_ref65","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1038\/nature03347","article-title":"Experimental one-way quantum computing","volume":"434","author":"Walther","year":"2005","journal-title":"Nature"},{"journal-title":"Oxford Research Encyclopedia of Physics","article-title":"Measurement-based quantum computation","author":"Wei","key":"2024121019262506300_ref66"},{"volume-title":"An Adiabatic Oracle for Grover\u2019s Algorithm","year":"2023","author":"Yan","key":"2024121019262506300_ref67"},{"volume-title":"Foundations of Quantum Programming","year":"2016","author":"Ying","key":"2024121019262506300_ref68"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/34\/8\/1526\/60953014\/exae040.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/34\/8\/1526\/60953014\/exae040.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T20:22:11Z","timestamp":1733862131000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/34\/8\/1526\/7724754"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,31]]},"references-count":68,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2024,7,31]]},"published-print":{"date-parts":[[2024,12,4]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exae040","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"type":"print","value":"0955-792X"},{"type":"electronic","value":"1465-363X"}],"subject":[],"published-other":{"date-parts":[[2024,12]]},"published":{"date-parts":[[2024,7,31]]}}}