aiqbench analysis
The article presents SamBa-GQW, a non-variational quantum algorithm that leverages offline classical sampling to guide continuous-time quantum walks for combinatorial optimization without requiring iterative classical optimizers. Empirical results show the method achieves high-quality approximate solutions on problems up to 30 qubits, performing comparably to variational approaches like QAOA while offering a potential pathway beyond current NISQ limitations. This work advances the field by addressing a key bottleneck in quantum optimization: the reliance on classical feedback loops that can be unstable or resource-intensive.
Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization
Quantum 10, 2234 (2026). https://doi.org/10.22331/q-2026-10-13-2234 We introduce SamBa-GQW, a novel quantum algorithm for solving binary combinatorial optimization problems of arbitrary degree with no use of any classical optimizer. The algorithm is based on a continuous-time quantum walk on the solution space represented as a graph. The walker explores the solution space to find its way to vertices that minimize the cost function of the optimization problem. The key novelty of our algorithm is an offline classical sampling protocol that gives information about the spectrum of the problem Hamiltonian. Then, the extracted information is used to guide the walker to high quality solutions via a quantum walk with a time-dependent hopping rate. We investigate the performance of SamBa-GQW on several quadratic problems, namely MaxCut, maximum independent set, portfolio optimization, and higher-order polynomial problems such as LABS, MAX-$k$-SAT and a quartic reformulation of the travelling salesperson problem. We empirically demonstrate that SamBa-GQW finds high quality approximate solutions on problems up to a size of $n=30$ qubits by only sampling poly($n$) states among $2^n$ possible decisions. Furthermore, SamBa-GQW compares in par with classically optimized variational approaches, such as the variational guided quantum walk and QAOA (the latter when run on deep circuits). This places Samba-GQW as a promising heuristic to tackle combinatorial problems beyond the NISQ regime.
We introduce SamBa-GQW, a novel quantum algorithm for solving binary combinatorial optimization problems of arbitrary degree with no use of any classical optimizer. The algorithm is based on a continuous-time quantum walk on the solution space represented as a graph. The walker explores the solution space to find its way to vertices that minimize the cost function of the optimization problem. The key novelty of our algorithm is an offline classical sampling protocol that gives information about the spectrum of the problem Hamiltonian. Then, the extracted information is used to guide the walker to high quality solutions via a quantum walk with a time-dependent hopping rate. We investigate the performance of SamBa-GQW on several quadratic problems, namely MaxCut, maximum independent set, portfolio optimization, and higher-order polynomial problems such as LABS, MAX-$k$-SAT and a quartic reformulation of the travelling salesperson problem. We empirically demonstrate that SamBa-GQW finds high quality approximate solutions on problems up to a size of $n=30$ qubits by only sampling poly($n$) states among $2^n$ possible decisions. Furthermore, SamBa-GQW compares in par with classically optimized variational approaches, such as the variational guided quantum walk and QAOA (the latter when run on deep circuits). This places Samba-GQW as a promising heuristic to tackle combinatorial problems beyond the NISQ regime.
[1] Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J Egger, Bruce G Elmegreen, et al. Challenges and opportunities in quantum optimization. Nature Reviews Physics, pages 1–18, 2024. 10.1038/s42254-024-00770-9. URL https://doi.org/10.1038/s42254-024-00770-9. https://doi.org/10.1038/s42254-024-00770-9
[2] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. Nature Reviews Physics, 3 (9): 625–644, 2021. URL https://doi.org/10.1038/s42254-021-00348-9. https://doi.org/10.1038/s42254-021-00348-9
[3] Nicola Mariella and Andrea Simonetto. A quantum algorithm for the sub-graph isomorphism problem. ACM Transactions on Quantum Computing, 4 (2): 1–34, 2023. URL https://doi.org/10.1145/3569095. https://doi.org/10.1145/3569095
[4] Dylan Laplace Mermoud, Andrea Simonetto, and Sourour Elloumi. Variational quantum algorithms for permutation-based combinatorial problems: Optimal ansatz generation with applications to quadratic assignment problems and beyond. Quantum, 10: 1998, February 2026. ISSN 2521-327X. 10.22331/q-2026-02-09-1998. URL https://doi.org/10.22331/q-2026-02-09-1998. https://doi.org/10.22331/q-2026-02-09-1998
[5] John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2: 79, 2018. URL https://doi.org/10.22331/q-2018-08-06-79. https://doi.org/10.22331/q-2018-08-06-79
[6] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm, 2014. URL https://arxiv.org/abs/1411.4028. arXiv:1411.4028
[7] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Phys. Rev. X, 10: 021067, Jun 2020. 10.1103/PhysRevX.10.021067. URL https://doi.org/10.1103/PhysRevX.10.021067. https://doi.org/10.1103/PhysRevX.10.021067
[8] Stuart Hadfield, Zhihui Wang, Bryan O’gorman, Eleanor G Rieffel, Davide Venturelli, and Rupak Biswas. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms, 12 (2): 34, 2019. URL https://doi.org/10.3390/a12020034. https://doi.org/10.3390/a12020034
[9] Daniel J. Egger, Jakub Mareček, and Stefan Woerner. Warm-starting quantum optimization. Quantum, 5: 479, June 2021. ISSN 2521-327X. 10.22331/q-2021-06-17-479. URL https://doi.org/10.22331/q-2021-06-17-479. https://doi.org/10.22331/q-2021-06-17-479
[10] Yunlong Yu, Chenfeng Cao, Carter Dewey, Xiang-Bin Wang, Nic Shannon, and Robert Joynt. Quantum approximate optimization algorithm with adaptive bias fields. Physical Review Research, 4 (2): 023249, 2022. URL https://doi.org/10.1103/PhysRevResearch.4.023249. https://doi.org/10.1103/PhysRevResearch.4.023249
[11] Rebekah Herrman, Phillip C Lotshaw, James Ostrowski, Travis S Humble, and George Siopsis. Multi-angle quantum approximate optimization algorithm. Scientific Reports, 12 (1): 6781, 2022. URL https://doi.org/10.1038/s41598-022-10555-8. https://doi.org/10.1038/s41598-022-10555-8
[12] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to variational quantum optimization from symmetry protection. Phys. Rev. Lett., 125: 260505, Dec 2020. 10.1103/PhysRevLett.125.260505. URL https://doi.org/10.1103/PhysRevLett.125.260505. https://doi.org/10.1103/PhysRevLett.125.260505
[13] Stefan H. Sack and Maksym Serbyn. Quantum annealing initialization of the quantum approximate optimization algorithm. Quantum, 5: 491, July 2021. ISSN 2521-327X. 10.22331/q-2021-07-01-491. URL https://doi.org/10.22331/q-2021-07-01-491. https://doi.org/10.22331/q-2021-07-01-491
[14] Ugo Nzongani, Dylan Laplace Mermoud, and Arthur Braida. Scaling qaoa: transferring optimal adiabatic schedules from small-scale to large-scale variational circuits. In 2026 International Conference on Quantum Control, Computing and Learning (qCCL), pages 1–6, 2026. 10.1109/qCCL70331.2026.11668574. URL https://doi.org/10.1109/qCCL70331.2026.11668574. https://doi.org/10.1109/qCCL70331.2026.11668574
[15] Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M. Dreiling, John P. Gaebler, Thomas M. Gatterman, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny, Tanner Mengle, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, Romina Yalovetzky, and Marco Pistoia. Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem. Science Advances, 10 (22): eadm6761, 2024. 10.1126/sciadv.adm6761. URL https://www.science.org/doi/abs/10.1126/sciadv.adm6761. https://doi.org/10.1126/sciadv.adm6761
[16] Sami Boulebnane and Ashley Montanaro. Solving boolean satisfiability problems with the quantum approximate optimization algorithm. PRX Quantum, 5 (3): 030348, September 2024. ISSN 2691-3399. 10.1103/prxquantum.5.030348. URL https://doi.org/10.1103/PRXQuantum.5.030348. https://doi.org/10.1103/prxquantum.5.030348
[17] Martin Larocca, Supanut Thanasilp, Samson Wang, Kunal Sharma, Jacob Biamonte, Patrick J Coles, Lukasz Cincio, Jarrod R McClean, Zoë Holmes, and Marco Cerezo. Barren plateaus in variational quantum computing. Nature Reviews Physics, pages 1–16, 2025. URL https://doi.org/10.1038/s42254-025-00813-9. https://doi.org/10.1038/s42254-025-00813-9
[18] Francesco De Nicola, Linda Sansoni, Andrea Crespi, Roberta Ramponi, Roberto Osellame, Vittorio Giovannetti, Rosario Fazio, Paolo Mataloni, and Fabio Sciarrino. Quantum simulation of bosonic-fermionic noninteracting particles in disordered systems via a quantum walk. Phys. Rev. A, 89: 032322, Mar 2014. 10.1103/PhysRevA.89.032322. URL https://doi.org/10.1103/PhysRevA.89.032322. https://doi.org/10.1103/PhysRevA.89.032322
[19] Giuseppe Di Molfetta, Marc Brachet, and Fabrice Debbasch. Quantum walks in artificial electric and gravitational fields. Physica A: Statistical Mechanics and its Applications, 397: 157–168, 2014. ISSN 0378-4371. https://doi.org/10.1016/j.physa.2013.11.036. URL https://www.sciencedirect.com/science/article/pii/S0378437113011059. https://doi.org/10.1016/j.physa.2013.11.036 https://www.sciencedirect.com/science/article/pii/S0378437113011059
[20] Giuseppe Di Molfetta, M. Brachet, and Fabrice Debbasch. Quantum walks as massless dirac fermions in curved space-time. Phys. Rev. A, 88: 042301, Oct 2013. 10.1103/PhysRevA.88.042301. URL https://doi.org/10.1103/PhysRevA.88.042301. https://doi.org/10.1103/PhysRevA.88.042301
[21] Julien Zylberman, Giuseppe Di Molfetta, Marc Brachet, Nuno F. Loureiro, and Fabrice Debbasch. Quantum simulations of hydrodynamics via the madelung transformation. Phys. Rev. A, 106: 032408, Sep 2022. 10.1103/PhysRevA.106.032408. URL https://doi.org/10.1103/PhysRevA.106.032408. https://doi.org/10.1103/PhysRevA.106.032408
[22] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. Exponential algorithmic speedup by a quantum walk. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC '03, page 59–68, New York, NY, USA, 2003. Association for Computing Machinery. ISBN 1581136749. 10.1145/780542.780552. URL https://doi.org/10.1145/780542.780552. https://doi.org/10.1145/780542.780552
[23] Andrew M. Childs and Jeffrey Goldstone. Spatial search by quantum walk. Phys. Rev. A, 70: 022314, Aug 2004. 10.1103/PhysRevA.70.022314. URL https://doi.org/10.1103/PhysRevA.70.022314. https://doi.org/10.1103/PhysRevA.70.022314
[24] Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37 (1): 210–239, 2007. 10.1137/S0097539705447311. URL https://doi.org/10.1137/S0097539705447311. https://doi.org/10.1137/S0097539705447311
[25] S. Marsh and J. B. Wang. Deterministic spatial search using alternating quantum walks. Phys. Rev. A, 104: 022216, Aug 2021. 10.1103/PhysRevA.104.022216. URL https://doi.org/10.1103/PhysRevA.104.022216. https://doi.org/10.1103/PhysRevA.104.022216
[26] Mathieu Roget and Giuseppe Di Molfetta. A quantum walk-based scheme for distributed searching on arbitrary graphs. In Mamata Dalui, Sukanta Das, and Enrico Formenti, editors, Cellular Automata Technology, pages 72–83, Cham, 2024. Springer Nature Switzerland. ISBN 978-3-031-56943-2. URL https://doi.org/10.1007/978-3-031-56943-2_6. https://doi.org/10.1007/978-3-031-56943-2_6
[27] Alvin Gonzales, Rebekah Herrman, Colin Campbell, Igor Gaidai, Ji Liu, Teague Tomesh, and Zain H Saleem. Efficient sparse state preparation via quantum walks. npj Quantum Information, 11 (1): 143, 2025. URL https://doi.org/10.1038/s41534-025-01093-y. https://doi.org/10.1038/s41534-025-01093-y
[28] Neil B. Lovett, Sally Cooper, Matthew Everitt, Matthew Trevers, and Viv Kendon. Universal quantum computation using the discrete-time quantum walk. Phys. Rev. A, 81: 042330, Apr 2010. 10.1103/PhysRevA.81.042330. URL https://doi.org/10.1103/PhysRevA.81.042330. https://doi.org/10.1103/PhysRevA.81.042330
[29] Andrew M. Childs. Universal computation by quantum walk. Phys. Rev. Lett., 102: 180501, May 2009. 10.1103/PhysRevLett.102.180501. URL https://doi.org/10.1103/PhysRevLett.102.180501. https://doi.org/10.1103/PhysRevLett.102.180501
[30] Y. Aharonov, L. Davidovich, and N. Zagury. Quantum random walks. Phys. Rev. A, 48: 1687–1690, Aug 1993. 10.1103/PhysRevA.48.1687. URL https://doi.org/10.1103/PhysRevA.48.1687. https://doi.org/10.1103/PhysRevA.48.1687
[31] Edward Farhi and Sam Gutmann. Quantum computation and decision trees. Phys. Rev. A, 58: 915–928, Aug 1998. 10.1103/PhysRevA.58.915. URL https://doi.org/10.1103/PhysRevA.58.915. https://doi.org/10.1103/PhysRevA.58.915
[32] Jessica Lemieux, Bettina Heim, David Poulin, Krysta Svore, and Matthias Troyer. Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm. Quantum, 4: 287, June 2020. ISSN 2521-327X. 10.22331/q-2020-06-29-287. URL https://doi.org/10.22331/q-2020-06-29-287. https://doi.org/10.22331/q-2020-06-29-287
[33] Roberto Campos, Pablo AM Casares, and MA Martin-Delgado. Quantum metropolis solver: a quantum walks approach to optimization problems. Quantum Machine Intelligence, 5 (2): 28, 2023. URL https://doi.org/10.1007/s42484-023-00119-y. https://doi.org/10.1007/s42484-023-00119-y
[34] Adam Callison, Nicholas Chancellor, Florian Mintert, and Viv Kendon. Finding spin glass ground states using quantum walks. New Journal of Physics, 21 (12): 123022, dec 2019. 10.1088/1367-2630/ab5ca2. URL https://doi.org/10.1088/1367-2630/ab5ca2. https://doi.org/10.1088/1367-2630/ab5ca2
[35] S. Marsh and J. B. Wang. Combinatorial optimization via highly efficient quantum walks. Phys. Rev. Res., 2: 023302, Jun 2020. 10.1103/PhysRevResearch.2.023302. URL https://doi.org/10.1103/PhysRevResearch.2.023302. https://doi.org/10.1103/PhysRevResearch.2.023302
[36] T. Bennett, E. Matwiejew, S. Marsh, and J. B. Wang. Quantum walk-based vehicle routing optimisation. Frontiers in Physics, Volume 9 - 2021, 2021. ISSN 2296-424X. 10.3389/fphy.2021.730856. URL https://www.frontiersin.org/journals/physics/articles/10.3389/fphy.2021.730856. https://doi.org/10.3389/fphy.2021.730856
[37] N. Slate, E. Matwiejew, S. Marsh, and J. B. Wang. Quantum walk-based portfolio optimisation. Quantum, 5: 513, July 2021. ISSN 2521-327X. 10.22331/q-2021-07-28-513. URL https://doi.org/10.22331/q-2021-07-28-513. https://doi.org/10.22331/q-2021-07-28-513
[38] Adam Callison, Max Festenstein, Jie Chen, Laurentiu Nita, Viv Kendon, and Nicholas Chancellor. Energetic perspective on rapid quenches in quantum annealing. PRX Quantum, 2: 010338, Mar 2021. 10.1103/PRXQuantum.2.010338. URL https://doi.org/10.1103/PRXQuantum.2.010338. https://doi.org/10.1103/PRXQuantum.2.010338
[39] Robert J. Banks, Ehsan Haque, Farah Nazef, Fatima Fethallah, Fatima Ruqaya, Hamza Ahsan, Het Vora, Hibah Tahir, Ibrahim Ahmad, Isaac Hewins, Ishaq Shah, Krish Baranwal, Mannan Arora, Mateen Asad, Mubasshirah Khan, Nabian Hasan, Nuh Azad, Salgai Fedaiee, Shakeel Majeed, Shayam Bhuyan, Tasfia Tarannum, Yahya Ali, Dan E. Browne, and P. A. Warburton. Continuous-time quantum walks for MAX-CUT are hot. Quantum, 8: 1254, February 2024. ISSN 2521-327X. 10.22331/q-2024-02-13-1254. URL https://doi.org/10.22331/q-2024-02-13-1254. https://doi.org/10.22331/q-2024-02-13-1254
[40] Sebastian Schulz, Dennis Willsch, and Kristel Michielsen. Guided quantum walk. Phys. Rev. Res., 6: 013312, Mar 2024. 10.1103/PhysRevResearch.6.013312. URL https://doi.org/10.1103/PhysRevResearch.6.013312. https://doi.org/10.1103/PhysRevResearch.6.013312
[41] Robert J. Banks, Georgios S. Raftis, Dan E. Browne, and P. A. Warburton. Continuous-time quantum optimization without the adiabatic principle. Phys. Rev. A, 111: 032414, Mar 2025. 10.1103/PhysRevA.111.032414. URL https://doi.org/10.1103/PhysRevA.111.032414. https://doi.org/10.1103/PhysRevA.111.032414
[42] Alejandro Gomez Cadavid, Archismita Dalal, Anton Simen, Enrique Solano, and Narendra N. Hegade. Bias-field digitized counterdiabatic quantum optimization. Phys. Rev. Res., 7: L022010, Apr 2025. 10.1103/PhysRevResearch.7.L022010. URL https://doi.org/10.1103/PhysRevResearch.7.L022010. https://doi.org/10.1103/PhysRevResearch.7.L022010
[43] Bin Yan and Nikolai A Sinitsyn. Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian. Nature Communications, 13 (1): 2212, 2022. URL https://doi.org/10.1038/s41467-022-29887-0. https://doi.org/10.1038/s41467-022-29887-0
[44] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum computation by adiabatic evolution. arXiv preprint quant-ph/0001106, 2000. URL https://doi.org/10.48550/arXiv.quant-ph/0001106. https://doi.org/10.48550/arXiv.quant-ph/0001106 arXiv:quant-ph/0001106
[45] Tameem Albash and Daniel A. Lidar. Adiabatic quantum computation. Rev. Mod. Phys., 90: 015002, Jan 2018. 10.1103/RevModPhys.90.015002. URL https://doi.org/10.1103/RevModPhys.90.015002. https://doi.org/10.1103/RevModPhys.90.015002
[46] David R. Burt, Carl Edward Rasmussen, and Mark van der Wilk. Convergence of sparse variational inference in gaussian processes regression. Journal of Machine Learning Research, 21 (131): 1–63, 2020. URL http://jmlr.org/papers/v21/19-1015.html. http://jmlr.org/papers/v21/19-1015.html
[47] Masuo Suzuki. Decomposition formulas of exponential operators and lie exponentials with some applications to quantum mechanics and statistical physics. Journal of mathematical physics, 26 (4): 601–612, 1985. URL https://doi.org/10.1063/1.526596. https://doi.org/10.1063/1.526596
[48] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu. Theory of trotter error with commutator scaling. Phys. Rev. X, 11: 011020, Feb 2021. 10.1103/PhysRevX.11.011020. URL https://doi.org/10.1103/PhysRevX.11.011020. https://doi.org/10.1103/PhysRevX.11.011020
[49] Andrew Lucas. Ising formulations of many np problems. Frontiers in Physics, 2, 2014. ISSN 2296-424X. 10.3389/fphy.2014.00005. URL http://dx.doi.org/10.3389/fphy.2014.00005. https://doi.org/10.3389/fphy.2014.00005
[50] Zoé Verchère, Sourour Elloumi, and Andrea Simonetto. Optimizing variational circuits for higher-order binary optimization. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 01, pages 19–25, 2023. 10.1109/QCE57702.2023.00011. URL https://doi.org/10.1109/QCE57702.2023.00011. https://doi.org/10.1109/QCE57702.2023.00011
[51] Julien Zylberman, Ugo Nzongani, Andrea Simonetto, and Fabrice Debbasch. Efficient quantum circuits for non-unitary and unitary diagonal operators with space-time-accuracy trade-offs. ACM Transactions on Quantum Computing, 6 (2), April 2025. 10.1145/3718348. URL https://doi.org/10.1145/3718348. https://doi.org/10.1145/3718348
[52] Brent N. Clark, Charles J. Colbourn, and David S. Johnson. Unit disk graphs. Discrete Mathematics, 86 (1): 165–177, 1990. ISSN 0012-365X. https://doi.org/10.1016/0012-365X(90)90358-O. URL https://www.sciencedirect.com/science/article/pii/0012365X9090358O. https://doi.org/10.1016/0012-365X(90)90358-O https://www.sciencedirect.com/science/article/pii/0012365X9090358O
[53] S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, X.-Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S.-T. Wang, M. Greiner, V. Vuletić, and M. D. Lukin. Quantum optimization of maximum independent set using rydberg atom arrays. Science, 376 (6598): 1209–1215, 2022. 10.1126/science.abo6587. URL https://www.science.org/doi/abs/10.1126/science.abo6587. https://doi.org/10.1126/science.abo6587
[54] Constantin Dalyac, Lucas Leclerc, Louis Vignoli, Mehdi Djellabi, Wesley da Silva Coelho, Bruno Ximenez, Alexandre Dareau, Davide Dreon, Vincent E Elfving, Adrien Signoles, et al. Graph algorithms with neutral atom quantum processors. The European Physical Journal A, 60 (9): 177, 2024. URL https://doi.org/10.1140/epja/s10050-024-01385-5. https://doi.org/10.1140/epja/s10050-024-01385-5
[55] Constantin Dalyac, Loïc Henriet, Emmanuel Jeandel, Wolfgang Lechner, Simon Perdrix, Marc Porcheron, and Margarita Veshchezerova. Qualifying quantum approaches for hard industrial optimization problems. a case study in the field of smart-charging of electric vehicles. EPJ Quantum Technology, 8 (1): 12, 2021. URL https://doi.org/10.1140/epjqt/s40507-021-00100-3. https://doi.org/10.1140/epjqt/s40507-021-00100-3
[56] Lucas Leclerc, Constantin Dalyac, Pascale Bendotti, Rodolphe Griset, Joseph Mikael, and Loic Henriet. Implementing transferable annealing protocols for combinatorial optimization on neutral-atom quantum processors: A case study on smart charging of electric vehicles. Phys. Rev. A, 111: 032611, Mar 2025. 10.1103/PhysRevA.111.032611. URL https://doi.org/10.1103/PhysRevA.111.032611. https://doi.org/10.1103/PhysRevA.111.032611
[57] Ruben S. Andrist, Martin J. A. Schuetz, Pierre Minssen, Romina Yalovetzky, Shouvanik Chakrabarti, Dylan Herman, Niraj Kumar, Grant Salton, Ruslan Shaydulin, Yue Sun, Marco Pistoia, and Helmut G. Katzgraber. Hardness of the maximum-independent-set problem on unit-disk graphs and prospects for quantum speedups. Phys. Rev. Res., 5: 043277, Dec 2023. 10.1103/PhysRevResearch.5.043277. URL https://doi.org/10.1103/PhysRevResearch.5.043277. https://doi.org/10.1103/PhysRevResearch.5.043277
[58] Pierre Cazals, Aymeric François, Loïc Henriet, Lucas Leclerc, Malory Marin, Yassine Naghmouchi, Wesley da Silva Coelho, Florian Sikora, Vittorio Vitale, Rémi Watrigant, Monique Witt Garzillo, and Constantin Dalyac. Identifying hard native instances for the maximum-independent-set problem on neutral-atom quantum processors. Phys. Rev. Appl., 25: 034085, Mar 2026. 10.1103/8gjv-ll1f. URL https://doi.org/10.1103/8gjv-ll1f. https://doi.org/10.1103/8gjv-ll1f
[59] Victor A. Penas, Marcelo Losada, and Pedro W. Lamberti. Quantum imaginary time evolution and the unit-disk maximum independent set problem. Phys. Rev. A, 111: 042403, Apr 2025. 10.1103/PhysRevA.111.042403. URL https://doi.org/10.1103/PhysRevA.111.042403. https://doi.org/10.1103/PhysRevA.111.042403
[60] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy, and Eleanor G. Rieffel. $xy$ mixers: Analytical and numerical results for the quantum alternating operator ansatz. Phys. Rev. A, 101: 012320, Jan 2020. 10.1103/PhysRevA.101.012320. URL https://doi.org/10.1103/PhysRevA.101.012320. https://doi.org/10.1103/PhysRevA.101.012320
[61] Andreas Bärtschi and Stephan Eidenbenz. Deterministic preparation of dicke states. In Leszek Antoni Gąsieniec, Jesper Jansson, and Christos Levcopoulos, editors, Fundamentals of Computation Theory, pages 126–139, Cham, 2019. Springer International Publishing. ISBN 978-3-030-25027-0. URL https://doi.org/10.1007/978-3-030-25027-0_9. https://doi.org/10.1007/978-3-030-25027-0_9
[62] Tom Packebusch and Stephan Mertens. Low autocorrelation binary sequences. Journal of Physics A: Mathematical and Theoretical, 49 (16): 165001, mar 2016. 10.1088/1751-8113/49/16/165001. URL https://doi.org/10.1088/1751-8113/49/16/165001. https://doi.org/10.1088/1751-8113/49/16/165001
[63] Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC '71, page 151–158, New York, NY, USA, 1971. Association for Computing Machinery. ISBN 9781450374644. 10.1145/800157.805047. URL https://doi.org/10.1145/800157.805047. https://doi.org/10.1145/800157.805047
[64] Elijah Pelofske, Andreas Bärtschi, John Golden, and Stephan Eidenbenz. High-round qaoa for max $k$-sat on trapped ion nisq devices. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 01, pages 506–517, 2023. 10.1109/QCE57702.2023.00064. URL https://doi.org/10.1109/QCE57702.2023.00064. https://doi.org/10.1109/QCE57702.2023.00064
[65] Yunlong Yu, Chenfeng Cao, Xiang-Bin Wang, Nic Shannon, and Robert Joynt. Solution of sat problems with the adaptive-bias quantum approximate optimization algorithm. Phys. Rev. Res., 5: 023147, Jun 2023. 10.1103/PhysRevResearch.5.023147. URL https://doi.org/10.1103/PhysRevResearch.5.023147. https://doi.org/10.1103/PhysRevResearch.5.023147
[66] Rajesh Matai, Surya Singh, and Murari Lal Mittal. Traveling salesman problem: an overview of applications, formulations, and solution approaches. In Donald Davendra, editor, Traveling Salesman Problem - Theory and Applications, chapter 1. IntechOpen, London, 2010. 10.5772/12909. URL https://doi.org/10.5772/12909. https://doi.org/10.5772/12909
[67] Adam Glos, Aleksandra Krawiec, and Zoltán Zimborás. Space-efficient binary optimization for variational quantum computing. npj Quantum Information, 8 (1): 39, 2022. URL https://doi.org/10.1038/s41534-022-00546-y. https://doi.org/10.1038/s41534-022-00546-y
[68] Paul Erdős and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci., 5: 17, 1960.
[69] Thorsten Koch, David E Bernal Neira, Ying Chen, Giorgio Cortiana, Daniel J Egger, Raoul Heese, Narendra N Hegade, Alejandro Gomez Cadavid, Rhea Huang, Toshinari Itoko, et al. The quantum optimization benchmarking library. Nature Computational Science, 6 (6): 653–671, 2026. URL https://doi.org/10.1038/s43588-026-00991-1. https://doi.org/10.1038/s43588-026-00991-1
[70] Quantum Optimization Benchmarking Library (QOBLIB), 2026. URL https://doi.org/10.5281/zenodo.18962381. Zenodo. https://doi.org/10.5281/zenodo.18962381
[71] Przemysław Juszczuk, Ignacy Kaliszewski, Janusz Miroforidis, and Dmitry Podkopaev. Mean-variance data collections for portfolio optimization problems, 2022. URL https://doi.org/10.18150/CZYLOV. https://doi.org/10.18150/CZYLOV
[72] Earl Campbell, Ankur Khurana, and Ashley Montanaro. Applying quantum algorithms to constraint satisfaction problems. Quantum, 3: 167, July 2019. ISSN 2521-327X. 10.22331/q-2019-07-18-167. URL https://doi.org/10.22331/q-2019-07-18-167. https://doi.org/10.22331/q-2019-07-18-167
[73] Rémi Monasson and Riccardo Zecchina. Entropy of the k-satisfiability problem. Phys. Rev. Lett., 76: 3881–3885, May 1996. 10.1103/PhysRevLett.76.3881. URL https://doi.org/10.1103/PhysRevLett.76.3881. https://doi.org/10.1103/PhysRevLett.76.3881
[74] Stephan Mertens, Marc Mézard, and Riccardo Zecchina. Threshold values of random k-sat from the cavity method. Random Structures & Algorithms, 28 (3): 340–373, 2006. https://doi.org/10.1002/rsa.20090. URL https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20090. https://doi.org/10.1002/rsa.20090
[75] Amin Coja-Oghlan. The asymptotic k-sat threshold. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC '14, page 804–813, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450327107. 10.1145/2591796.2591822. URL https://doi.org/10.1145/2591796.2591822. https://doi.org/10.1145/2591796.2591822
[76] Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya, and Alessandro Summer. A review on quantum approximate optimization algorithm and its variants. Physics Reports, 1068: 1–66, 2024. ISSN 0370-1573. https://doi.org/10.1016/j.physrep.2024.03.002. URL https://www.sciencedirect.com/science/article/pii/S0370157324001078. A review on Quantum Approximate Optimization Algorithm and its variants. https://doi.org/10.1016/j.physrep.2024.03.002 https://www.sciencedirect.com/science/article/pii/S0370157324001078
[77] Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M. Dreiling, John P. Gaebler, Thomas M. Gatterman, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny, Tanner Mengle, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, Romina Yalovetzky, and Marco Pistoia. Data from "evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem", July 2023. URL https://doi.org/10.5281/zenodo.8190275. https://doi.org/10.5281/zenodo.8190275
[78] Pierre Guilmin, Adrien Bocquet, Élie Genois, Daniel Weiss, and Ronan Gautier. Dynamiqs: an open-source python library for gpu-accelerated and differentiable simulation of quantum systems. 2025. URL https://github.com/dynamiqs/dynamiqs. https://github.com/dynamiqs/dynamiqs
[79] Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson, and Jay M. Gambetta. Quantum computing with Qiskit, 2024. URL https://doi.org/10.48550/arXiv.2405.08810. https://doi.org/10.48550/arXiv.2405.08810
[80] Alastair Kay. Tutorial on the quantikz package. arXiv preprint arXiv:1809.03842, 2018. URL https://doi.org/10.48550/arXiv.1809.03842. https://doi.org/10.48550/arXiv.1809.03842 arXiv:1809.03842
[81] Aric Hagberg, Pieter J Swart, and Daniel A Schult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Laboratory (LANL), Los Alamos, NM (United States), 2008. URL https://doi.org/10.25080/TCWV9851. https://doi.org/10.25080/TCWV9851
[82] Samba-gqw. https://github.com/ugo-nzongani/SamBa-GQW, 2025. https://github.com/ugo-nzongani/SamBa-GQW
Full text under the publisher's open licence · 2964 words
Related coverage
Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization
arXiv · Oct 2, 2026
Podcast with Stephen DiAdamo, Co-founder and CTO of Qoro Quantum
Quantum Computing Report · Aug 7, 2026
Lattice-Based Cryptography Explained
Quantum Zeitgeist · Aug 15, 2026
Synthesis Superintelligence: from Semiconductors to Superconductors — Periodic Labs’ Liam Fedus and Ekin Dogus Cubuk
Latent Space · Oct 8, 2026