{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,3]],"date-time":"2026-01-03T04:36:12Z","timestamp":1767414972029,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2019,10,10]],"date-time":"2019-10-10T00:00:00Z","timestamp":1570665600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["406377\/2018-9"],"award-info":[{"award-number":["406377\/2018-9"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004901","name":"FAPEMIG","doi-asserted-by":"crossref","award":["APQ-03832-14"],"award-info":[{"award-number":["APQ-03832-14"]}],"id":[{"id":"10.13039\/501100004901","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2019,10,10]]},"abstract":"<jats:p>In 2016, the first quantum processors have been made available to the general public. The possibility of programming an actual quantum device has elicited much enthusiasm. Yet, such possibility also brought challenges. One challenge is the so called Qubit Allocation problem: the mapping of a virtual quantum circuit into an actual quantum architecture. There exist solutions to this problem; however, in our opinion, they fail to capitalize on decades of improvements on graph theory. In contrast, this paper shows how to model qubit allocation as the combination of Subgraph Isomorphism and Token Swapping. This idea has been made possible by the publication of an approximative solution to the latter problem in 2016. We have compared our algorithm against five other qubit allocators, all independently designed in the last two years, including the winner of the IBM Challenge. When evaluated in \"Tokyo\", a quantum architecture with 20 qubits, our technique outperforms these state-of-the-art approaches in terms of the quality of the solutions that it finds and the amount of memory that it uses, while showing practical runtime.<\/jats:p>","DOI":"10.1145\/3360546","type":"journal-article","created":{"date-parts":[[2019,10,11]],"date-time":"2019-10-11T14:53:33Z","timestamp":1570805613000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":54,"title":["Qubit allocation as a combination of subgraph isomorphism and token swapping"],"prefix":"10.1145","volume":"3","author":[{"given":"Marcos Yukio","family":"Siraichi","sequence":"first","affiliation":[{"name":"Federal University of Minas Gerais, Brazil"}]},{"given":"Vin\u00edcius Fernandes dos","family":"Santos","sequence":"additional","affiliation":[{"name":"Federal University of Minas Gerais, Brazil"}]},{"given":"Caroline","family":"Collange","sequence":"additional","affiliation":[{"name":"Inria, France \/ University of Rennes, France \/ CNRS, France \/ IRISA, France"}]},{"given":"Fernando Magno Quint\u00e3o","family":"Pereira","sequence":"additional","affiliation":[{"name":"Federal University of Minas Gerais, Brazil"}]}],"member":"320","published-online":{"date-parts":[[2019,10,10]]},"reference":[{"key":"e_1_2_2_1_1","first-page":"6","article-title":"A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum","volume":"32","author":"Amy Matthew","year":"2013","unstructured":"Matthew Amy , Dmitri Maslov , Michele Mosca , and Martin Roetteler . 2013 . A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits. Trans. Comp.-Aided Des. Integ. Cir. Sys. 32 , 6 (jun 2013), 818\u2013830. Matthew Amy, Dmitri Maslov, Michele Mosca, and Martin Roetteler. 2013. A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits. Trans. Comp.-Aided Des. Integ. Cir. Sys. 32, 6 (jun 2013), 818\u2013830.","journal-title":"Circuits. Trans. Comp.-Aided Des. Integ. Cir. Sys."},{"key":"e_1_2_2_2_1","volume-title":"Elementary gates for quantum computation. Physical review A 52, 5","author":"Barenco Adriano","year":"1995","unstructured":"Adriano Barenco , Charles H Bennett , Richard Cleve , David P DiVincenzo , Norman Margolus , Peter Shor , Tycho Sleator , John A Smolin , and Harald Weinfurter . 1995. Elementary gates for quantum computation. Physical review A 52, 5 ( 1995 ), 3457. Adriano Barenco, Charles H Bennett, Richard Cleve, David P DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A Smolin, and Harald Weinfurter. 1995. Elementary gates for quantum computation. Physical review A 52, 5 (1995), 3457."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/102435"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.64.022312"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2245737.2245881"},{"volume-title":"STOC. ACM","author":"Cook Stephen A.","key":"e_1_2_2_6_1","unstructured":"Stephen A. Cook . 1971. The Complexity of Theorem-proving Procedures . In STOC. ACM , NY , USA , 151\u2013158. Stephen A. Cook. 1971. The Complexity of Theorem-proving Procedures. In STOC. ACM, NY, USA, 151\u2013158."},{"volume-title":"SPAA","author":"Copsey Dean","key":"e_1_2_2_7_1","unstructured":"Dean Copsey , Mark Oskin , Tzvetan Metodiev , Frederic T. Chong , Isaac Chuang , and John Kubiatowicz . 2003. The Effect of Communication Costs in Solid-state Quantum Computing Architectures . In SPAA . ACM , New York, NY, USA , 65\u201374. Dean Copsey, Mark Oskin, Tzvetan Metodiev, Frederic T. Chong, Isaac Chuang, and John Kubiatowicz. 2003. The Effect of Communication Costs in Solid-state Quantum Computing Architectures. In SPAA. ACM, New York, NY, USA, 65\u201374."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_2_9_1","volume-title":"Gambetta","author":"Cross Andrew W.","year":"2017","unstructured":"Andrew W. Cross , Lev S. Bishop , John A. Smolin , and Jay M . Gambetta . 2017 . Open Quantum Assembly Language. IBM, Armonk, NY, USA. Andrew W. Cross, Lev S. Bishop, John A. Smolin, and Jay M. Gambetta. 2017. Open Quantum Assembly Language. IBM, Armonk, NY, USA."},{"key":"e_1_2_2_10_1","first-page":"116","article-title":"Optimising Matrix Product State Simulations of Shor\u2019s Algorithm","volume":"3","author":"Dang Aidan","year":"2019","unstructured":"Aidan Dang , Charles D. Hill , and Lloyd C. L. Hollenberg . 2019 . Optimising Matrix Product State Simulations of Shor\u2019s Algorithm . CoRR 3 (2019), 116 \u2013 125 . Aidan Dang, Charles D. Hill, and Lloyd C. L. Hollenberg. 2019. Optimising Matrix Product State Simulations of Shor\u2019s Algorithm. CoRR 3 (2019), 116\u2013125.","journal-title":"CoRR"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.94.032329"},{"key":"e_1_2_2_12_1","volume-title":"Superconducting qubits: A short review. arXiv 0411174","author":"Devoret Michel H","year":"2004","unstructured":"Michel H Devoret , Andreas Wallraff , and John M Martinis . 2004. Superconducting qubits: A short review. arXiv 0411174 ( 2004 ), 1\u201341. Michel H Devoret, Andreas Wallraff, and John M Martinis. 2004. Superconducting qubits: A short review. arXiv 0411174 (2004), 1\u201341."},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On Random Graphs I","volume":"6","author":"Erd\u00f6s P.","year":"1959","unstructured":"P. Erd\u00f6s and A. R\u00e9nyi . 1959 . On Random Graphs I . Publicationes Mathematicae 6 (1959), 290 \u2013 297 . P. Erd\u00f6s and A. R\u00e9nyi. 1959. On Random Graphs I. Publicationes Mathematicae 6 (1959), 290\u2013297.","journal-title":"Publicationes Mathematicae"},{"key":"e_1_2_2_14_1","volume-title":"Article 2","author":"Gambetta Jay M","year":"2017","unstructured":"Jay M Gambetta , Jerry M Chow , and Matthias Steffen . 2017. Building logical qubits in a superconducting quantum computing system. NPJ Quantum Mechanics 3 , Article 2 ( 2017 ), 7 pages. Jay M Gambetta, Jerry M Chow, and Matthias Steffen. 2017. Building logical qubits in a superconducting quantum computing system. NPJ Quantum Mechanics 3, Article 2 (2017), 7 pages."},{"key":"e_1_2_2_15_1","unstructured":"Dario Gil. 2017. The Future of Computing: AI and Quantum. Online video.  Dario Gil. 2017. The Future of Computing: AI and Quantum. Online video."},{"key":"e_1_2_2_16_1","volume-title":"Neil J Ross, Peter Selinger, and Beno\u00eet Valiron.","author":"Green Alexander S","year":"2013","unstructured":"Alexander S Green , Peter LeFanu Lumsdaine , Neil J Ross, Peter Selinger, and Beno\u00eet Valiron. 2013 . Quipper: a scalable quantum programming language. In SIGPLAN Notices, Vol. 48 . ACM, NY, USA , 333\u2013342. Alexander S Green, Peter LeFanu Lumsdaine, Neil J Ross, Peter Selinger, and Beno\u00eet Valiron. 2013. Quipper: a scalable quantum programming language. In SIGPLAN Notices, Vol. 48. ACM, NY, USA, 333\u2013342."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_2_18_1","volume-title":"A Software Methodology for Compiling Quantum Programs. CoRR abs\/1604.01401","author":"H\u00e4ner Thomas","year":"2016","unstructured":"Thomas H\u00e4ner , Damian S. Steiger , Krysta M. Svore , and Matthias Troyer . 2016. A Software Methodology for Compiling Quantum Programs. CoRR abs\/1604.01401 ( 2016 ), 1\u201314. Thomas H\u00e4ner, Damian S. Steiger, Krysta M. Svore, and Matthias Troyer. 2016. A Software Methodology for Compiling Quantum Programs. CoRR abs\/1604.01401 (2016), 1\u201314."},{"key":"e_1_2_2_19_1","unstructured":"IBM. 2016. IBM QX Devices. https:\/\/quantumexperience.ng.bluemix.net\/qx\/devices  IBM. 2016. IBM QX Devices. https:\/\/quantumexperience.ng.bluemix.net\/qx\/devices"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3287624.3287701"},{"volume-title":"Computing Frontiers. ACM","author":"Javadi-Abhari Ali","key":"e_1_2_2_21_1","unstructured":"Ali Javadi-Abhari , Shruti Patil , Daniel Kudrow , Jeff Heckey , Alexey Lvov , Frederic T Chong , and Margaret Martonosi . 2014. ScaffCC: a framework for compilation and analysis of quantum computing programs . In Computing Frontiers. ACM , NY , USA , 1. Ali Javadi-Abhari, Shruti Patil, Daniel Kudrow, Jeff Heckey, Alexey Lvov, Frederic T Chong, and Margaret Martonosi. 2014. ScaffCC: a framework for compilation and analysis of quantum computing programs. In Computing Frontiers. ACM, NY, USA, 1."},{"volume-title":"The Time Complexity of the Token Swapping Problem and Its Parallel Variants","author":"Kawahara Jun","key":"e_1_2_2_22_1","unstructured":"Jun Kawahara , Toshiki Saitoh , and Ryo Yoshinaka . 2017. The Time Complexity of the Token Swapping Problem and Its Parallel Variants . In WALCOM. Springer , Heidelberg, Germany , 448\u2013459. Jun Kawahara, Toshiki Saitoh, and Ryo Yoshinaka. 2017. The Time Complexity of the Token Swapping Problem and Its Parallel Variants. In WALCOM. Springer, Heidelberg, Germany, 448\u2013459."},{"key":"e_1_2_2_23_1","volume-title":"Martinis","author":"Kelly J.","year":"2014","unstructured":"J. Kelly , R. Barends , A. G. Fowler , A. Megrant , E. Jeffrey , T. C. White , D. Sank , J. Y. Mutus , B. Campbell , Yu Chen , Z. Chen , B. Chiaro , A. Dunsworth , I.-C. Hoi , C. Neill , P. J. J. O\u2019Malley , C. Quintana , P. Roushan , A. Vainsencher , J. Wenner , A. N. Cleland , and John M . Martinis . 2014 . State preservation by repetitive error detection in a superconducting quantum circuit. CoRR arXiv:1411.7403 (2014), 1\u201330. J. Kelly, R. Barends, A. G. Fowler, A. Megrant, E. Jeffrey, T. C. White, D. Sank, J. Y. Mutus, B. Campbell, Yu Chen, Z. Chen, B. Chiaro, A. Dunsworth, I.-C. Hoi, C. Neill, P. J. J. O\u2019Malley, C. Quintana, P. Roushan, A. Vainsencher, J. Wenner, A. N. Cleland, and John M. Martinis. 2014. State preservation by repetitive error detection in a superconducting quantum circuit. CoRR arXiv:1411.7403 (2014), 1\u201330."},{"key":"e_1_2_2_24_1","doi-asserted-by":"crossref","unstructured":"L. Lao B. van Wee I. Ashraf J. van Someren N. Khammassi K. Bertels and C. G. Almudever. 2018. Mapping of Lattice Surgery-based Quantum Circuits on Surface Code Architectures. arXiv: arXiv:1805.11127  L. Lao B. van Wee I. Ashraf J. van Someren N. Khammassi K. Bertels and C. G. Almudever. 2018. Mapping of Lattice Surgery-based Quantum Circuits on Surface Code Architectures. arXiv: arXiv:1805.11127","DOI":"10.1088\/2058-9565\/aadd1a"},{"key":"e_1_2_2_25_1","unstructured":"Gushu Li Yufei Ding and Yuan Xie. 2018. Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices. arXiv: arXiv:1809.02573 To appear in ASPLOS\u201919.  Gushu Li Yufei Ding and Yuan Xie. 2018. Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices. arXiv: arXiv:1809.02573 To appear in ASPLOS\u201919."},{"key":"e_1_2_2_26_1","first-page":"1221","article-title":"PAQCS: Physical Design-Aware Fault-Tolerant Quantum Circuit Synthesis","volume":"23","author":"Lin C. C.","year":"2015","unstructured":"C. C. Lin , S. Sur-Kolay , and N. K. Jha . 2015 . PAQCS: Physical Design-Aware Fault-Tolerant Quantum Circuit Synthesis . TVLSI 23 , 7 (2015), 1221 \u2013 1234 . C. C. Lin, S. Sur-Kolay, and N. K. Jha. 2015. PAQCS: Physical Design-Aware Fault-Tolerant Quantum Circuit Synthesis. TVLSI 23, 7 (2015), 1221\u20131234.","journal-title":"TVLSI"},{"key":"e_1_2_2_27_1","first-page":"1574","article-title":"Layout Synthesis for Topological Quantum Circuits With 1-D and 2-D Architectures","volume":"37","author":"Lin Y.","year":"2018","unstructured":"Y. Lin , B. Yu , M. Li , and D. Z. Pan . 2018 . Layout Synthesis for Topological Quantum Circuits With 1-D and 2-D Architectures . TCAD 37 , 8 (2018), 1574 \u2013 1587 . Y. Lin, B. Yu, M. Li, and D. Z. Pan. 2018. Layout Synthesis for Topological Quantum Circuits With 1-D and 2-D Architectures. TCAD 37, 8 (2018), 1574\u20131587.","journal-title":"TCAD"},{"key":"e_1_2_2_28_1","volume-title":"Fast and Unconditional All-Microwave Reset of a Superconducting Qubit. CoRR arXiv:1801.07689","author":"Magnard Paul","year":"2018","unstructured":"Paul Magnard , Philipp Kurpiers , Baptiste Royer , Theo Walter , Jean-Claude Besse , Simone Gasparinetti , Marek Pechal , Johannes Heinsoo , Simon Storz , Alexandre Blais , and Andreas Wallraff . 2018. Fast and Unconditional All-Microwave Reset of a Superconducting Qubit. CoRR arXiv:1801.07689 ( 2018 ), 1\u20139. Paul Magnard, Philipp Kurpiers, Baptiste Royer, Theo Walter, Jean-Claude Besse, Simone Gasparinetti, Marek Pechal, Johannes Heinsoo, Simon Storz, Alexandre Blais, and Andreas Wallraff. 2018. Fast and Unconditional All-Microwave Reset of a Superconducting Qubit. CoRR arXiv:1801.07689 (2018), 1\u20139."},{"key":"e_1_2_2_29_1","volume-title":"Quantum Supremacy Is Both Closer and Farther than It Appears. CoRR arXiv:1807.10749","author":"Markov Igor L.","year":"2018","unstructured":"Igor L. Markov , Aneeqa Fatima , Sergei V. Isakov , and Sergio Boixo . 2018. Quantum Supremacy Is Both Closer and Farther than It Appears. CoRR arXiv:1807.10749 ( 2018 ), 1\u201332. Igor L. Markov, Aneeqa Fatima, Sergei V. Isakov, and Sergio Boixo. 2018. Quantum Supremacy Is Both Closer and Farther than It Appears. CoRR arXiv:1807.10749 (2018), 1\u201332."},{"key":"e_1_2_2_30_1","first-page":"752","article-title":"Quantum Circuit Placement","volume":"27","author":"Maslov D.","year":"2008","unstructured":"D. Maslov , S. M. Falconer , and M. Mosca . 2008 . Quantum Circuit Placement . TCAD 27 , 4 (2008), 752 \u2013 763 . D. Maslov, S. M. Falconer, and M. Mosca. 2008. Quantum Circuit Placement. TCAD 27, 4 (2008), 752\u2013763.","journal-title":"TCAD"},{"key":"e_1_2_2_31_1","first-page":"1","article-title":"Approximation and Hardness of Token Swapping. In ESA. Schloss Dagstuhl, Dagstuhl","volume":"66","author":"Miltzow Tillmann","year":"2016","unstructured":"Tillmann Miltzow , Lothar Narins , Yoshio Okamoto , G\u00fcnter Rote , Antonis Thomas , and Takeaki Uno . 2016 . Approximation and Hardness of Token Swapping. In ESA. Schloss Dagstuhl, Dagstuhl , Germany , 66 : 1 \u2013 66 :15. Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, G\u00fcnter Rote, Antonis Thomas, and Takeaki Uno. 2016. Approximation and Hardness of Token Swapping. In ESA. Schloss Dagstuhl, Dagstuhl, Germany, 66:1\u201366:15.","journal-title":"Germany"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.976922"},{"key":"e_1_2_2_33_1","volume-title":"Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits. CoRR arXiv:1710.05867","author":"Pednault Edwin","year":"2018","unstructured":"Edwin Pednault , John A. Gunnels , Giacomo Nannicini , Lior Horesh , Thomas Magerlein , Edgar Solomonik , Erik W. Draeger , Eric T. Holland , and Robert Wisnieff . 2018. Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits. CoRR arXiv:1710.05867 ( 2018 ), 1\u201329. Edwin Pednault, John A. Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, Erik W. Draeger, Eric T. Holland, and Robert Wisnieff. 2018. Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits. CoRR arXiv:1710.05867 (2018), 1\u201329."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCAS.2016.2549950"},{"volume-title":"Register Allocation Via Coloring of Chordal Graphs","author":"Quint\u00e3o Pereira Fernando Magno","key":"e_1_2_2_35_1","unstructured":"Fernando Magno Quint\u00e3o Pereira and Jens Palsberg . 2005. Register Allocation Via Coloring of Chordal Graphs . In APLAS. Springer , Heidelberg, Germany , 315\u2013329. Fernando Magno Quint\u00e3o Pereira and Jens Palsberg. 2005. Register Allocation Via Coloring of Chordal Graphs. In APLAS. Springer, Heidelberg, Germany, 315\u2013329."},{"key":"e_1_2_2_36_1","unstructured":"A. Saito K. Kioi Y. Akagi N. Hashizume and K. Ohta. 2000. Actual computational time-cost of the Quantum Fourier Transform in a quantum computer using nuclear spins. arXiv: quant-ph\/0001113  A. Saito K. Kioi Y. Akagi N. Hashizume and K. Ohta. 2000. Actual computational time-cost of the Quantum Fourier Transform in a quantum computer using nuclear spins. arXiv: quant-ph\/0001113"},{"key":"e_1_2_2_37_1","unstructured":"Daniel Sank Evan Jeffrey J.Y. Mutus T.C. White J. Kelly R. Barends Y. Chen Z. Chen B. Chiaro A. Megrant A. Dunsworth P.J.J. O\u2019Malley C. Neill P. Roushan A. Vainsencher J. Wenner A.N. Cleland and J.M. Martinis. 2014. Fast Scalable State Measurement with Superconducting Qubits. CoRR arXiv:1401.0257 (2014) 1\u20139.  Daniel Sank Evan Jeffrey J.Y. Mutus T.C. White J. Kelly R. Barends Y. Chen Z. Chen B. Chiaro A. Megrant A. Dunsworth P.J.J. O\u2019Malley C. Neill P. Roushan A. Vainsencher J. Wenner A.N. Cleland and J.M. Martinis. 2014. Fast Scalable State Measurement with Superconducting Qubits. CoRR arXiv:1401.0257 (2014) 1\u20139."},{"key":"e_1_2_2_38_1","doi-asserted-by":"crossref","unstructured":"A. Shafaei M. Saeedi and M. Pedram. 2014. Qubit placement to minimize communication overhead in 2D quantum architectures. In ASP-DAC. IEEE Washington DC USA 495\u2013500.  A. Shafaei M. Saeedi and M. Pedram. 2014. Qubit placement to minimize communication overhead in 2D quantum architectures. In ASP-DAC. IEEE Washington DC USA 495\u2013500.","DOI":"10.1109\/ASPDAC.2014.6742940"},{"key":"e_1_2_2_39_1","doi-asserted-by":"crossref","unstructured":"R. R. Shrivastwa K. Datta and I. Sengupta. 2015. Fast Qubit Placement in 2D Architecture Using Nearest Neighbor Realization. In iNIS. IEEE NY USA 95\u2013100.  R. R. Shrivastwa K. Datta and I. Sengupta. 2015. Fast Qubit Placement in 2D Architecture Using Nearest Neighbor Realization. In iNIS. IEEE NY USA 95\u2013100.","DOI":"10.1109\/iNIS.2015.59"},{"key":"e_1_2_2_40_1","volume-title":"Caroline Collange, and Fernando Magno Quintao Pereira.","author":"Siraichi Marcos Yukio","year":"2018","unstructured":"Marcos Yukio Siraichi , Vin\u00edcius Fernandes dos Santos , Caroline Collange, and Fernando Magno Quintao Pereira. 2018 . Qubit Allocation. In CGO. ACM, NY, USA , 113?125. Marcos Yukio Siraichi, Vin\u00edcius Fernandes dos Santos, Caroline Collange, and Fernando Magno Quintao Pereira. 2018. Qubit Allocation. In CGO. ACM, NY, USA, 113?125."},{"key":"e_1_2_2_41_1","doi-asserted-by":"crossref","unstructured":"Pavel Surynek. 2018. Finding Optimal Solutions to Token Swapping by Conflict-based Search and Reduction to SAT. arXiv: arXiv:1806.09487  Pavel Surynek. 2018. Finding Optimal Solutions to Token Swapping by Conflict-based Search and Reduction to SAT. arXiv: arXiv:1806.09487","DOI":"10.1109\/ICTAI.2018.00096"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2006.4"},{"key":"e_1_2_2_43_1","unstructured":"Krysta Marie Svore A. Cross and I-Hsun Chuang. 2004. Toward a Software Architecture for Quantum Computing Design Tools.  Krysta Marie Svore A. Cross and I-Hsun Chuang. 2004. Toward a Software Architecture for Quantum Computing Design Tools."},{"volume-title":"ASPLOS. ACM","author":"Tannu Swamit","key":"e_1_2_2_44_1","unstructured":"Swamit Tannu and Moinuddin Qureshi . 2019. A Case for Variability-Aware Policies for NISQ-Era Quantum Computers . In ASPLOS. ACM , NY , USA, To appear. Swamit Tannu and Moinuddin Qureshi. 2019. A Case for Variability-Aware Policies for NISQ-Era Quantum Computers. In ASPLOS. ACM, NY, USA, To appear."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"e_1_2_2_46_1","doi-asserted-by":"crossref","unstructured":"R. Wille D. Gro\u00dfe L. Teuber G. W. Dueck and R. Drechsler. 2008. RevLib: An Online Resource for Reversible Functions and Reversible Circuits. In ISMVL. IEEE NY USA 220\u2013225.  R. Wille D. Gro\u00dfe L. Teuber G. W. Dueck and R. Drechsler. 2008. RevLib: An Online Resource for Reversible Functions and Reversible Circuits. In ISMVL. IEEE NY USA 220\u2013225.","DOI":"10.1109\/ISMVL.2008.43"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1038\/299802a0"},{"volume-title":"WALCOM: Algorithms and Computation, Sheung-Hung Poon, Md","author":"Yamanaka Katsuhisa","key":"e_1_2_2_48_1","unstructured":"Katsuhisa Yamanaka , Erik D. Demaine , Takashi Horiyama , Akitoshi Kawamura , Shin-ichi Nakano, Yoshio Okamoto , Toshiki Saitoh , Akira Suzuki , Ryuhei Uehara , and Takeaki Uno . 2017. Sequentially Swapping Colored Tokens on Graphs . In WALCOM: Algorithms and Computation, Sheung-Hung Poon, Md . Saidur Rahman, and Hsu-Chun Yen (Eds.). Springer , Heidelberg, Germany , 435\u2013447. Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, and Takeaki Uno. 2017. Sequentially Swapping Colored Tokens on Graphs. In WALCOM: Algorithms and Computation, Sheung-Hung Poon, Md. Saidur Rahman, and Hsu-Chun Yen (Eds.). Springer, Heidelberg, Germany, 435\u2013447."},{"volume-title":"Swapping Labeled Tokens on Graphs","author":"Yamanaka Katsuhisa","key":"e_1_2_2_49_1","unstructured":"Katsuhisa Yamanaka , Erik D. Demaine , Takehiro Ito , Jun Kawahara , Masashi Kiyomi , Yoshio Okamoto , Toshiki Saitoh , Akira Suzuki , Kei Uchizawa , and Takeaki Uno . 2014. Swapping Labeled Tokens on Graphs . Springer , Heidelberg, Germany , 364\u2013375. Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno. 2014. Swapping Labeled Tokens on Graphs. Springer, Heidelberg, Germany, 364\u2013375."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920887"},{"volume-title":"Efficient mapping of quantum circuits to the IBM QX architectures","author":"Zulehner Alwin","key":"e_1_2_2_51_1","unstructured":"Alwin Zulehner , Alexandru Paler , and Robert Wille . 2018. Efficient mapping of quantum circuits to the IBM QX architectures . In DATE. IEEE, NY , USA , 1135\u20131138. Alwin Zulehner, Alexandru Paler, and Robert Wille. 2018. Efficient mapping of quantum circuits to the IBM QX architectures. In DATE. IEEE, NY, USA, 1135\u20131138."},{"volume-title":"ASPDAC","author":"Zulehner Alwin","key":"e_1_2_2_52_1","unstructured":"Alwin Zulehner and Robert Wille . 2019. Compiling SU(4) Quantum Circuits to IBM QX Architectures . In ASPDAC . ACM , New York, NY, USA , 185\u2013190. Alwin Zulehner and Robert Wille. 2019. Compiling SU(4) Quantum Circuits to IBM QX Architectures. In ASPDAC. ACM, New York, NY, USA, 185\u2013190."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3360546","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3360546","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:22:58Z","timestamp":1750202578000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3360546"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,10]]},"references-count":52,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2019,10,10]]}},"alternative-id":["10.1145\/3360546"],"URL":"https:\/\/doi.org\/10.1145\/3360546","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2019,10,10]]},"assertion":[{"value":"2019-10-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}