{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T03:22:26Z","timestamp":1773804146381,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Quantum Comput."],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>\n                    Quantum annealing (QA) has great potential to solve combinatorial optimization problems efficiently. However, the effectiveness of QA algorithms is heavily based on the embedding of problem instances, represented as logical graphs, into the quantum processing unit (QPU) whose topology is in the form of a limited connectivity graph, known as the minor embedding problem. Because the minor embedding problem is an NP-hard problem\u00a0[\n                    <jats:xref ref-type=\"bibr\">11<\/jats:xref>\n                    ], existing methods for the minor embedding problem suffer from scalability issues when faced with larger problem sizes. In this article, we propose a novel approach utilizing Reinforcement Learning (RL) techniques to address the minor embedding problem, named CHARME. CHARME includes three key components: a Graph Neural Network (GNN) architecture for policy modeling, a state transition algorithm that ensures solution validity, and an order exploration strategy for effective training. Through comprehensive experiments on synthetic and real-world instances, we demonstrate the efficiency of our proposed order exploration strategy as well as our proposed RL framework, CHARME. In particular, CHARME yields superior solutions in terms of qubit usage compared to fast embedding methods such as Minorminer and ATOM. Moreover, our method surpasses the OCT-based approach, known for its slower runtime but high-quality solutions, in several cases. In addition, our proposed exploration enhances the efficiency of the training of the CHARME framework by providing better solutions compared to the greedy strategy.\n                  <\/jats:p>","DOI":"10.1145\/3763244","type":"journal-article","created":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T14:01:08Z","timestamp":1761314468000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["CHARME: A Chain-based Reinforcement Learning Approach for the Minor Embedding Problem"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-9647-7011","authenticated-orcid":false,"given":"Hoang","family":"Ngo","sequence":"first","affiliation":[{"name":"Computer and Information Science and Engineering, University of Florida","place":["Gainesville, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3384-9129","authenticated-orcid":false,"given":"Nguyen","family":"Do","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science and Engineering, University of Florida","place":["Gainesville, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8727-0350","authenticated-orcid":false,"given":"Minh","family":"Vu","sequence":"additional","affiliation":[{"name":"Theoritical Division, Los Alamos National Laboratory","place":["Los Alamos, United States"]},{"name":"University of Florida","place":["Los Alamos, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1998-4842","authenticated-orcid":false,"given":"Tre","family":"Jeter","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science and Engineering, University of Florida","place":["Gainesville, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4403-8612","authenticated-orcid":false,"given":"Tamer","family":"Kahveci","sequence":"additional","affiliation":[{"name":"University of Florida","place":["Gainesville, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0503-2012","authenticated-orcid":false,"given":"My","family":"Thai","sequence":"additional","affiliation":[{"name":"CISE, University of Florida","place":["Gainesville, United States"]}]}],"member":"320","published-online":{"date-parts":[[2025,10,24]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.07.063"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-58942-4_8"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","unstructured":"Kelly Boothby Paul Bunyk Jack Raymond and Aidan Roy. 2020. Next-generation topology of D-wave quantum processors. arXiv:2003.00133 [quant-ph]. 10.48550\/arXiv.2003.00133","DOI":"10.48550\/arXiv.2003.00133"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-015-1150-6"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","unstructured":"Jun Cai William G. Macready and Aidan Roy. 2014. A practical heuristic for finding graph minors. arXiv:1406.2741 [quant-ph]. 10.48550\/arXiv.1406.2741","DOI":"10.48550\/arXiv.1406.2741"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","unstructured":"Jo\u00e3o Caldeira Joshua Job Steven H. Adachi Brian Nord and Gabriel N. Perdue. 2020. Restricted Boltzmann Machines for galaxy morphology classification with a quantum annealer. arXiv:1911.06259 [quant-ph]. 10.48550\/arXiv.1911.06259","DOI":"10.48550\/arXiv.1911.06259"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1088\/2632-2153\/ac4559"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-010-0200-3"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3489517.3530403"},{"issue":"4","key":"e_1_3_1_11_2","first-page":"1","article-title":"RNA folding using quantum computers","volume":"18","year":"2022","unstructured":"Dillion M. Fox, Christopher M. MacDermaid, Andrea M. A. Schreij, Magdalena Zwierzyna, and Ross C. Walker. 2022. RNA folding using quantum computers. PLOS Computational Biology 18, 4 (2022), 1\u201317.","journal-title":"PLOS Computational Biology"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-018-1863-4"},{"key":"e_1_3_1_13_2","first-page":"1","article-title":"Deep space network scheduling using quantum annealing","volume":"3","year":"2022","unstructured":"Alexandre Guillaume, Edwin Y. Goh, Mark D. Johnston, Brian D. Wilson, Anita Ramanan, Frances Tibble, and Brad Lackey. 2022. Deep space network scheduling using quantum annealing. IEEE Transactions on Quantum Engineering 3 (2022), 1\u201313.","journal-title":"IEEE Transactions on Quantum Engineering"},{"key":"e_1_3_1_14_2","unstructured":"Mikael Henaff Joan Bruna and Yann LeCun. 2015. Deep Convolutional Networks on Graph-Structured Data. (2015). arXiv:1506.05163. Retrieved from https:\/\/arxiv.org\/abs\/1506.05163"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSPCS47537.2019.9008543"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/28.1.27"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i03.5616"},{"key":"e_1_3_1_18_2","volume-title":"Proceedings of the 5th International Conference on Learning Representations.","author":"Kipf Thomas N.","year":"2017","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference on Learning Representations. Retrieved from https:\/\/openreview.net\/forum?id=SJU4ayYgl"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-013-0683-9"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TQE.2023.3301899"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/3045390.3045594"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature14236"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature24047"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","unstructured":"Vikram Khipple Mulligan Hans Melo Haley Irene Merritt Stewart Slocum Brian D. Weitzner Andrew M. Watkins P. Douglas Renfrew Craig Pelissier Paramjit S. Arora and Richard Bonneau. 2019. Designing peptides on a quantum computer. BioRxiv (2019). 10.1101\/752485","DOI":"10.1101\/752485"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICC45041.2023.10279010"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioadv\/vbad112"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/3045390.3045603"},{"key":"e_1_3_1_28_2","first-page":"18182","volume-title":"Proceedings of the Advances in Neural Information Processing Systems.","volume":"34","author":"Ostaszewski Mateusz","year":"2021","unstructured":"Mateusz Ostaszewski, Lea M. Trenkwalder, Wojciech Masarczyk, Eleanor Scerri, and Vedran Dunjko. 2021. Reinforcement learning for optimization of variational quantum circuit architectures. In Proceedings of the Advances in Neural Information Processing Systems.M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.), Vol. 34, Curran Associates, Inc., 18182\u201318194. Retrieved from https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2021\/file\/9724412729185d53a2e3e7f889d9f057-Paper.pdf"},{"key":"e_1_3_1_29_2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/978-3-030-20656-7_7","volume-title":"Proceedings of the High Performance Computing.","author":"Pinilla Jose P.","year":"2019","unstructured":"Jose P. Pinilla and Steven J. E. Wilton. 2019. Layout-aware embedding for quantum annealing processors. In Proceedings of the High Performance Computing.Mich\u00e8le Weiland, Guido Juckeland, Carsten Trinitis, and Ponnuswamy Sadayappan (Eds.), Springer International Publishing, Cham, 121\u2013139."},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-012-0506-4"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2023.3340608"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2021.1065"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007678930559"},{"key":"e_1_3_1_34_2","volume-title":"Proceedings of the Advances in Neural Information Processing Systems.","volume":"12","author":"Sutton Richard S.","year":"1999","unstructured":"Richard S. Sutton, David McAllester, Satinder Singh, and Yishay Mansour. 1999. Policy gradient methods for reinforcement learning with function approximation. In Proceedings of the Advances in Neural Information Processing Systems.S. Solla, T. Leen, and K. M\u00fcller (Eds.), Vol. 12, MIT Press. Retrieved from https:\/\/proceedings.neurips.cc\/paper_files\/paper\/1999\/file\/464d828b85b0bed98e80ade0a5c43b0f-Paper.pdf"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.3389\/fcomp.2024.1286057"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevResearch.2.033446"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763244","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T14:01:11Z","timestamp":1761314471000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763244"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,24]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1145\/3763244"],"URL":"https:\/\/doi.org\/10.1145\/3763244","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,24]]},"assertion":[{"value":"2024-03-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}