{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T08:00:14Z","timestamp":1776931214976,"version":"3.51.2"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","funder":[{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["No.2023YFF0905200"],"award-info":[{"award-number":["No.2023YFF0905200"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,10,18]]},"DOI":"10.1145\/3725843.3756107","type":"proceedings-article","created":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T17:19:56Z","timestamp":1760721596000},"page":"764-777","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Rasengan: A Transition Hamiltonian-based Approximation Algorithm for Solving Constrained Binary Optimization Problems"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-1965-6361","authenticated-orcid":false,"given":"Qifan","family":"Jiang","sequence":"first","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3801-6847","authenticated-orcid":false,"given":"Liqiang","family":"Lu","sequence":"additional","affiliation":[{"name":"ZJU-Ningbo Global Innovation Center, Zhejiang University, Ningbo, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-5333-6955","authenticated-orcid":false,"given":"Debin","family":"Xiang","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-0378-8502","authenticated-orcid":false,"given":"Tianyao","family":"Chu","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-8350-0351","authenticated-orcid":false,"given":"Tianze","family":"Zhu","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5660-5493","authenticated-orcid":false,"given":"Jingwen","family":"Leng","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9076-7998","authenticated-orcid":false,"given":"Yun","family":"Liang","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0281-1670","authenticated-orcid":false,"given":"Xiaoming","family":"Sun","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4703-7348","authenticated-orcid":false,"given":"Jianwei","family":"Yin","sequence":"additional","affiliation":[{"name":"ZJU-Ningbo Global Innovation Center, Zhejiang University, Ningbo, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,10,17]]},"reference":[{"key":"e_1_3_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/DAC18072.2020.9218558"},{"key":"e_1_3_3_1_3_2","doi-asserted-by":"crossref","unstructured":"Khulood Alyahya and Jonathan\u00a0E. Rowe. 2019. Landscape Analysis of a Class of NP-Hard Binary Packing Problems. Evolutionary Computation 27 1 (03 2019) 47\u201373.","DOI":"10.1162\/evco_a_00237"},{"key":"e_1_3_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3575693.3575741"},{"key":"e_1_3_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-04148-8_11"},{"key":"e_1_3_3_1_6_2","doi-asserted-by":"crossref","unstructured":"Sebastian Brandhofer Daniel Braun Vanessa Dehn Gerhard Hellstern Matthias H\u00fcls Yanjun Ji Ilia Polian Amandeep\u00a0Singh Bhatia and Thomas Wellens. 2023. Benchmarking the performance of portfolio optimization with QAOA. Quantum Inf. Process. 22 25 (2023).","DOI":"10.1007\/s11128-022-03766-5"},{"key":"e_1_3_3_1_7_2","doi-asserted-by":"crossref","unstructured":"Thang\u00a0Nguyen Bui and Byung\u00a0Ro Moon. 1996. Genetic algorithm and graph partitioning. IEEE Transactions on Computers (TC) 45 7 (1996) 841\u2013855.","DOI":"10.1109\/12.508322"},{"key":"e_1_3_3_1_8_2","doi-asserted-by":"crossref","unstructured":"Lukas Burgholzer Alexander Ploier and Robert Wille. 2023. Simulation Paths for Quantum Circuit Simulation With Decision Diagrams What to Learn From Tensor Networks and What Not. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 42 4 (2023) 1113\u20131122.","DOI":"10.1109\/TCAD.2022.3197969"},{"key":"e_1_3_3_1_9_2","doi-asserted-by":"crossref","unstructured":"Alberto Caprara Paolo Toth and Matteo Fischetti. 2000. Algorithms for the set covering problem. Annals of Operations Research 98 1 (2000) 353\u2013371.","DOI":"10.1023\/A:1019225027893"},{"key":"e_1_3_3_1_10_2","doi-asserted-by":"crossref","unstructured":"Marco Cerezo Andrew Arrasmith Ryan Babbush Simon\u00a0C Benjamin Suguru Endo Keisuke Fujii Jarrod\u00a0R McClean Kosuke Mitarai Xiao Yuan Lukasz Cincio and Patrick\u00a0J Coles. 2021. Variational quantum algorithms. Nature Reviews Physics 3 9 (2021) 625\u2013644.","DOI":"10.1038\/s42254-021-00348-9"},{"key":"e_1_3_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3623278.3624764"},{"key":"e_1_3_3_1_12_2","unstructured":"IBM\u00a0Quantum Devices. 2024. ibmq quito. https:\/\/quantum-computing.ibm.com\/services\/resources"},{"key":"e_1_3_3_1_13_2","volume-title":"The Principles of Quantum Mechanics (1st ed.)","author":"Dirac Paul A.\u00a0M.","year":"1930","unstructured":"Paul A.\u00a0M. Dirac. 1930. The Principles of Quantum Mechanics (1st ed.). Oxford University Press, Oxford, UK."},{"key":"e_1_3_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1629911.1630100"},{"key":"e_1_3_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7908-2151-2"},{"key":"e_1_3_3_1_16_2","unstructured":"Edward Farhi Jeffrey Goldstone and Sam Gutmann. 2014. A quantum approximate optimization algorithm. arXiv preprint arXiv:https:\/\/arXiv.org\/abs\/1411.4028 (2014)."},{"key":"e_1_3_3_1_17_2","doi-asserted-by":"crossref","unstructured":"David Fitzek Toheed Ghandriz Leo Laine Mats Granath and Anton\u00a0Frisk Kockum. 2024. Applying quantum approximate optimization to the heterogeneous vehicle routing problem. Sci. Rep. 14 25415 (2024).","DOI":"10.1038\/s41598-024-76967-w"},{"key":"e_1_3_3_1_18_2","doi-asserted-by":"crossref","unstructured":"Franz\u00a0Georg Fuchs Kjetil\u00a0Olsen Lye Halvor M\u00f8ll\u00a0Nilsen Alexander\u00a0Johannes Stasik and Giorgio Sartor. 2022. Constraint preserving mixers for the quantum approximate optimization algorithm. Algorithms 15 6 (2022) 202.","DOI":"10.3390\/a15060202"},{"key":"e_1_3_3_1_19_2","doi-asserted-by":"crossref","unstructured":"Austin Gilliam Stefan Woerner and Constantin Gonciulea. 2021. Grover adaptive search for constrained polynomial binary optimization. Quantum 5 (2021) 428.","DOI":"10.22331\/q-2021-04-08-428"},{"key":"e_1_3_3_1_20_2","first-page":"K36\u2013008","volume-title":"APS March Meeting Abstracts","author":"Gokhale Pranav","year":"2022","unstructured":"Pranav Gokhale. 2022. Q-CHOP: Quantum Constrained Hamiltonian OPtimization. In APS March Meeting Abstracts , Vol.\u00a02022. K36\u2013008."},{"key":"e_1_3_3_1_21_2","doi-asserted-by":"crossref","unstructured":"TM Graham Y Song J Scott C Poole L Phuttitarn K Jooya P Eichler X Jiang A Marra B Grinkemeyer M Kwon M Ebert J Cherek MT Lichtman M Gillette J Gilbert D Bowman T Ballance C Campbell ED Dahl O Crawford NS Blunt B Rogers T Noel and M Saffman. 2022. Multi-qubit entanglement and algorithms on a neutral-atom quantum computer. Nature 604 7906 (2022) 457\u2013462.","DOI":"10.1038\/s41586-022-04603-6"},{"key":"e_1_3_3_1_22_2","volume-title":"Linear algebra","author":"Greub Werner\u00a0H","year":"2012","unstructured":"Werner\u00a0H Greub. 2012. Linear algebra. Vol.\u00a023. Springer Science & Business Media."},{"key":"e_1_3_3_1_23_2","doi-asserted-by":"crossref","unstructured":"Itay Hen and Marcelo\u00a0S Sarandy. 2016. Driver Hamiltonians for constrained optimization in quantum annealing. Physical Review A 93 6 (2016) 062312.","DOI":"10.1103\/PhysRevA.93.062312"},{"key":"e_1_3_3_1_24_2","volume-title":"Graph coloring problems","author":"Jensen Tommy\u00a0R","year":"2011","unstructured":"Tommy\u00a0R Jensen and Bjarne Toft. 2011. Graph coloring problems. John Wiley & Sons."},{"key":"e_1_3_3_1_25_2","doi-asserted-by":"crossref","unstructured":"Abhinav Kandala Antonio Mezzacapo Kristan Temme Maika Takita Markus Brink Jerry\u00a0M Chow and Jay\u00a0M Gambetta. 2017. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature 549 7671 (2017) 242\u2013246.","DOI":"10.1038\/nature23879"},{"key":"e_1_3_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/DAC56929.2023.10247886"},{"key":"e_1_3_3_1_27_2","unstructured":"A\u00a0Yu Kitaev. 1995. Quantum measurements and the Abelian stabilizer problem. arXiv preprint quant-ph\/9511026 (1995)."},{"key":"e_1_3_3_1_28_2","doi-asserted-by":"crossref","unstructured":"Du\u0161an Knop Micha\u0142 Pilipczuk and Marcin Wrochna. 2020. Tight complexity lower bounds for integer linear programming with few constraints. ACM Transactions on Computation Theory (TCT) 12 3 (2020) 1\u201319.","DOI":"10.1145\/3397484"},{"key":"e_1_3_3_1_29_2","doi-asserted-by":"crossref","unstructured":"Christopher\u00a0R Laumann Roderich Moessner Antonello Scardicchio and Shivaji\u00a0Lal Sondhi. 2015. Quantum annealing: The fastest route to quantum computation. The European Physical Journal Special Topics 224 1 (2015) 75\u201388.","DOI":"10.1140\/epjst\/e2015-02344-2"},{"key":"e_1_3_3_1_30_2","doi-asserted-by":"crossref","unstructured":"Hannes Leipold and Federico\u00a0M Spedalieri. 2021. Constructing driver Hamiltonians for optimization problems with linear constraints. Quantum Science and Technology 7 1 (2021) 015013.","DOI":"10.1088\/2058-9565\/ac16b8"},{"key":"e_1_3_3_1_31_2","doi-asserted-by":"crossref","unstructured":"Gui-Lu Long. 2001. Grover algorithm with zero theoretical failure rate. Physical Review A 64 2 (2001) 022307.","DOI":"10.1103\/PhysRevA.64.022307"},{"key":"e_1_3_3_1_32_2","doi-asserted-by":"crossref","unstructured":"Ant\u00f3n Makarov Carlos P\u00e9rez-Herrad\u00f3n Giacomo Franceschetto M\u00e1rcio\u00a0M. Taddei Eneko Osaba Paloma del Barrio\u00a0Cabello Esther Villar-Rodriguez and Izaskun Oregi. 2024. Quantum Optimization Methods for Satellite Mission Planning. IEEE Access 12 (2024) 71808\u201371820.","DOI":"10.1109\/ACCESS.2024.3402990"},{"key":"e_1_3_3_1_33_2","doi-asserted-by":"crossref","unstructured":"Alberto Peruzzo Jarrod McClean Peter Shadbolt Man-Hong Yung Xiao-Qi Zhou Peter\u00a0J Love Al\u00e1n Aspuru-Guzik and Jeremy\u00a0L O\u2019brien. 2014. A variational eigenvalue solver on a photonic quantum processor. Nature communications 5 1 (2014) 4213.","DOI":"10.1038\/ncomms5213"},{"key":"e_1_3_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-8330-5_4"},{"key":"e_1_3_3_1_35_2","doi-asserted-by":"crossref","unstructured":"Giuseppe\u00a0E Santoro and Erio Tosatti. 2006. Optimization using quantum mechanics: quantum annealing through adiabatic evolution. Journal of Physics A: Mathematical and General 39 36 (2006) R393.","DOI":"10.1088\/0305-4470\/39\/36\/R01"},{"key":"e_1_3_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_3_3_1_37_2","doi-asserted-by":"crossref","unstructured":"Michael Streif and Martin Leib. 2020. Training the quantum approximate optimization algorithm without access to a quantum processing unit. Quantum Science and Technology 5 3 (2020) 034008.","DOI":"10.1088\/2058-9565\/ab8c2b"},{"key":"e_1_3_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA56546.2023.10071022"},{"key":"e_1_3_3_1_39_2","doi-asserted-by":"crossref","unstructured":"Jules Tilly Hongxiang Chen Shuxiang Cao Dario Picozzi Kanav Setia Ying Li Edward Grant Leonard Wossnig Ivan Rungger George\u00a0H. Booth and Jonathan Tennyson. 2022. The Variational Quantum Eigensolver: A review of methods and best practices. Physics Reports 986 (2022) 1\u2013128. The Variational Quantum Eigensolver: a review of methods and best practices.","DOI":"10.1016\/j.physrep.2022.08.003"},{"key":"e_1_3_3_1_40_2","doi-asserted-by":"crossref","unstructured":"Amit Verma and Mark Lewis. 2022. Penalty and partitioning techniques to improve performance of QUBO solvers. Discrete Optimization 44 (2022) 100594.","DOI":"10.1016\/j.disopt.2020.100594"},{"key":"e_1_3_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3620665.3640363"},{"key":"e_1_3_3_1_42_2","doi-asserted-by":"crossref","unstructured":"Sha-Sha Wang Hai-Ling Liu Yong-Mei Li Fei Gao Su-Juan Qin and Qiao-Yan Wen. 2024. Variational Quantum Algorithm-Preserving Feasible Space for Solving the Uncapacitated Facility Location Problem. Advanced Quantum Technologies (2024) 2400201.","DOI":"10.1002\/qute.202400201"},{"key":"e_1_3_3_1_43_2","unstructured":"Wikipedia contributors. 2024. Identical-machines scheduling \u2014 Wikipedia The Free Encyclopedia. https:\/\/en.wikipedia.org\/wiki\/Identical-machines_scheduling [Online; accessed 12-October-2024]."},{"key":"e_1_3_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA61900.2025.00031"},{"key":"e_1_3_3_1_45_2","doi-asserted-by":"crossref","unstructured":"Leo Zhou Sheng-Tao Wang Soonwon Choi Hannes Pichler and Mikhail\u00a0D Lukin. 2020. Quantum approximate optimization algorithm: Performance mechanism and implementation on near-term devices. Physical Review X 10 2 (2020) 021067.","DOI":"10.1103\/PhysRevX.10.021067"},{"key":"e_1_3_3_1_46_2","doi-asserted-by":"crossref","unstructured":"Alwin Zulehner and Robert Wille. 2019. Advanced Simulation of Quantum Computations. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 38 5 (2019) 848\u2013859.","DOI":"10.1109\/TCAD.2018.2834427"}],"event":{"name":"MICRO 2025: 58th IEEE\/ACM International Symposium on Microarchitecture","location":"Seoul Korea","acronym":"MICRO 2025","sponsor":["SIGMICRO ACM Special Interest Group on Microarchitectural Research and Processing"]},"container-title":["Proceedings of the 58th IEEE\/ACM International Symposium on Microarchitecture"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725843.3756107","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,26]],"date-time":"2026-01-26T21:43:34Z","timestamp":1769463814000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725843.3756107"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,17]]},"references-count":45,"alternative-id":["10.1145\/3725843.3756107","10.1145\/3725843"],"URL":"https:\/\/doi.org\/10.1145\/3725843.3756107","relation":{},"subject":[],"published":{"date-parts":[[2025,10,17]]},"assertion":[{"value":"2025-10-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}