Qubit-efficient encoding schemes for binary optimisation problems

Benjamin Tan; Marc-Antoine Lemonde; Supanut Thanasilp; Jirawat Tangpanitanon; Dimitris G. Angelakis

doi:10.22331/q-2021-05-04-454

Qubit-efficient encoding schemes for binary optimisation problems

Benjamin Tan¹, Marc-Antoine Lemonde¹, Supanut Thanasilp¹, Jirawat Tangpanitanon¹, and Dimitris G. Angelakis^1,2

¹Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore 117543
²School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece 73100

Published:	2021-05-04, volume 5, page 454
Eprint:	arXiv:2007.01774v2
Doi:	https://doi.org/10.22331/q-2021-05-04-454
Citation:	Quantum 5, 454 (2021).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We propose and analyze a set of variational quantum algorithms for solving quadratic unconstrained binary optimization problems where a problem consisting of $n_c$ classical variables can be implemented on $\mathcal O(\log n_c)$ number of qubits. The underlying encoding scheme allows for a systematic increase in correlations among the classical variables captured by a variational quantum state by progressively increasing the number of qubits involved. We first examine the simplest limit where all correlations are neglected, i.e. when the quantum state can only describe statistically independent classical variables. We apply this minimal encoding to find approximate solutions of a general problem instance comprised of $64$ classical variables using $7$ qubits. Next, we show how two-body correlations between the classical variables can be incorporated in the variational quantum state and how it can improve the quality of the approximate solutions. We give an example by solving a $42$-variable Max-Cut problem using only $8$ qubits where we exploit the specific topology of the problem. We analyze whether these cases can be optimized efficiently given the limited resources available in state-of-the-art quantum platforms. Lastly, we present the general framework for extending the expressibility of the probability distribution to any multi-body correlations.

Featured image: Our encoding scheme uses qubits to capture classical correlations between subgroups of classical variables in a QUBO problem, allowing for approximate solutions to be found with fewer qubits. The encoding scheme provides flexibility in the amount of correlations to be captured and by extension, the number of qubits required to solve the problem.

Popular summary

One promising application where quantum computers are expected to become a disruptive innovation is in the field of combinatorial optimization. So far, most quantum algorithms for combinatorial problems entail mapping each classical variable to single qubit in the quantum device. While this mapping in principle allows for an efficient search over the exponentially large number of possible solutions, the quantum resources required and restricted connectivity of current quantum hardware limits the problem sizes to toy models. Current state-of-the-art quantum experiments have found approximate solutions for a fully connected problem of only $17$ variables while modern classical methods can find solutions for problem sizes with over $10^4$ variables. In our work, we introduce an alternative encoding scheme that could allow intermediate-scale quantum devices to tackle problem sizes rivaling the biggest instances that can be solved using modern classical methods.

We adopt a fundamentally different approach by using a quantum state to encode correlations between restricted subsets of variables. In the simplest allowed encoding, each subset consists of a single variable, allowing for approximate solutions to be found using exponentially fewer qubits. The flexibility of our encoding scheme allows for additional qubits to systematically increase the correlations captured by the quantum state. Using numerical simulations, we demonstrate this encoding scheme on a $64$-variable optimization problem using only $7$ qubits and $104$ gates in the limiting case where no correlations are captured. We also demonstrate, with a $42$-variable example using $8$ qubits, how capturing two-body correlation yields better results. Lastly, we include results showing how this reduction in resources is advantageous compared to standard quantum approaches when implemented on noisy quantum hardware.

Moving forward, we aim to explore the possibilities of enhancing the performance of this encoding scheme to compete alongside state-of-the-art classical algorithms

► BibTeX data

@article{Tan2021qubitefficient,
  doi = {10.22331/q-2021-05-04-454},
  url = {https://doi.org/10.22331/q-2021-05-04-454},
  title = {Qubit-efficient encoding schemes for binary optimisation problems},
  author = {Tan, Benjamin and Lemonde, Marc-Antoine and Thanasilp, Supanut and Tangpanitanon, Jirawat and Angelakis, Dimitris G.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {454},
  month = may,
  year = {2021}
}

► References

[1] Deanna M. Abrams, Nicolas Didier, Blake R. Johnson, Marcus P. da Silva, and Colm A. Ryan. Implementation of xy entangling gates with a single calibrated pulse. Nature Electronics, 3 (12): 744–750, Nov 2020. ISSN 2520-1131. 10.1038/s41928-020-00498-1.
https://doi.org/10.1038/s41928-020-00498-1

[2] Tameem Albash and Daniel A. Lidar. Adiabatic quantum computation. Rev. Mod. Phys., 90: 015002, Jan 2018. 10.1103/RevModPhys.90.015002.
https://doi.org/10.1103/RevModPhys.90.015002

[3] Arya K. Babbush R. et al. Arute, F. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505–510, 2019. 10.1038/s41586-019-1666-5.
https://doi.org/10.1038/s41586-019-1666-5

[4] Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan. Quantum algorithms for quantum chemistry and quantum materials science. Chemical Reviews, 120 (22): 12685–12717, Oct 2020. ISSN 1520-6890. 10.1021/acs.chemrev.9b00829.
https://doi.org/10.1021/acs.chemrev.9b00829

[5] Andreas Bengtsson, Pontus Vikstål, Christopher Warren, Marika Svensson, Xiu Gu, Anton Frisk Kockum, Philip Krantz, Christian Križan, Daryoush Shiri, Ida-Maria Svensson, and et al. Improved success probability with greater circuit depth for the quantum approximate optimization algorithm. Physical Review Applied, 14 (3), Sep 2020. ISSN 2331-7019. 10.1103/physrevapplied.14.034010.
https://doi.org/10.1103/physrevapplied.14.034010

[6] Lee Braine, Daniel J Egger, Jennifer Glick, and Stefan Woerner. Quantum algorithms for mixed binary optimization applied to transaction settlement. arXiv preprint arXiv:1910.05788, 2019.
arXiv:1910.05788

[7] Fernando G.S.L. Brandão, Aram W. Harrow, and Michał Horodecki. Local Random Quantum Circuits are Approximate Polynomial-Designs. Communications in Mathematical Physics, 346 (2): 397–434, 2016. ISSN 14320916. 10.1007/s00220-016-2706-8.
https://doi.org/10.1007/s00220-016-2706-8

[8] Colin D. Bruzewicz, John Chiaverini, Robert McConnell, and Jeremy M. Sage. Trapped-ion quantum computing: Progress and challenges. Applied Physics Reviews, 6 (2): 021314, 2019. 10.1063/1.5088164.
https://doi.org/10.1063/1.5088164

[9] M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles. Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature Communications, 12 (1), Mar 2021. ISSN 2041-1723. 10.1038/s41467-021-21728-w.
https://doi.org/10.1038/s41467-021-21728-w

[10] Brian Coyle, Daniel Mills, Vincent Danos, and Elham Kashefi. The born supremacy: quantum advantage and training of an ising born machine. npj Quantum Information, 6 (1), Jul 2020. ISSN 2056-6387. 10.1038/s41534-020-00288-9.
https://doi.org/10.1038/s41534-020-00288-9

[11] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, and Dacheng Tao. Expressive power of parametrized quantum circuits. Physical Review Research, 2 (3), Jul 2020. ISSN 2643-1564. 10.1103/physrevresearch.2.033125.
https://doi.org/10.1103/physrevresearch.2.033125

[12] Suguru Endo, Zhenyu Cai, Simon C. Benjamin, and Xiao Yuan. Hybrid quantum-classical algorithms and quantum error mitigation. Journal of the Physical Society of Japan, 90 (3): 032001, Mar 2021. ISSN 1347-4073. 10.7566/jpsj.90.032001.
https://doi.org/10.7566/jpsj.90.032001

[13] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014a.
arXiv:1411.4028

[14] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. arXiv preprint arXiv:1412.6062, 2014b.
arXiv:1412.6062

[15] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. The quantum approximate optimization algorithm and the sherrington-kirkpatrick model at infinite size. arXiv preprint arXiv:1910.08187, 2019.
arXiv:1910.08187

[16] Dimitris Fouskakis and David Draper. Stochastic optimization: a review. International Statistical Review, 70 (3): 315–349, 2002. 10.1111/j.1751-5823.2002.tb00174.x.
https://doi.org/10.1111/j.1751-5823.2002.tb00174.x

[17] F. Glover M. Lewis Z.P Lü H.B Wang Y. Wang G. Kochenberger, J.K. Hao. The unconstrained binary quadratic programming problem: a survey. Journal of Combinatorial Optimization, 28 (1): 58–81, 2014. 10.1007/s10878-014-9734-0.
https://doi.org/10.1007/s10878-014-9734-0

[18] Michael R Garey and David S Johnson. Computers and intractability, volume 174. freeman San Francisco, 1979.
https://dl.acm.org/doi/book/10.5555/574848

[19] Lov K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 79: 325–328, Jul 1997. 10.1103/PhysRevLett.79.325.
https://doi.org/10.1103/PhysRevLett.79.325

[20] LLC Gurobi Optimization. Gurobi optimizer reference manual, 2020. URL http://www.gurobi.com.
http://www.gurobi.com

[21] Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, Sergio Boixo, and et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics, 17 (3): 332–336, Feb 2021. ISSN 1745-2481. 10.1038/s41567-020-01105-y.
https://doi.org/10.1038/s41567-020-01105-y

[22] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 549 (7671): 242–246, 2017. 10.1038/nature23879.
https://doi.org/10.1038/nature23879

[23] Richard M. Karp. Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA, 1972. ISBN 978-1-4684-2001-2. 10.1007/978-1-4684-2001-2_9.
https://doi.org/10.1007/978-1-4684-2001-2_9

[24] Nathan Killoran, Thomas R. Bromley, Juan Miguel Arrazola, Maria Schuld, Nicolás Quesada, and Seth Lloyd. Continuous-variable quantum neural networks. Phys. Rev. Research, 1: 033063, Oct 2019. 10.1103/PhysRevResearch.1.033063.
https://doi.org/10.1103/PhysRevResearch.1.033063

[25] Tjalling C. Koopmans and Martin Beckmann. Assignment problems and the location of economic activities. Econometrica, 25 (1): 53–76, 1957. ISSN 00129682, 14680262. 10.2307/1907742.
https://doi.org/10.2307/1907742

[26] Nathan Lacroix, Christoph Hellings, Christian Kraglund Andersen, Agustin Di Paolo, Ants Remm, Stefania Lazar, Sebastian Krinner, Graham J. Norris, Mihai Gabureac, Johannes Heinsoo, and et al. Improving the performance of deep quantum optimization algorithms with continuous gate sets. PRX Quantum, 1 (2), Oct 2020. ISSN 2691-3399. 10.1103/prxquantum.1.020304.
https://doi.org/10.1103/prxquantum.1.020304

[27] Jose I. Latorre. Image compression and entanglement. arXiv preprint arXiv:0510031, 2005.
arXiv:quant-ph/0510031

[28] Wim Lavrijsen, Ana Tudor, Juliane Müller, Costin Iancu, and Wibe de Jong. Classical optimizers for noisy intermediate-scale quantum devices. arXiv preprint arXiv:2004.03004, 2020. 10.1109/QCE49297.2020.00041.
https://doi.org/10.1109/QCE49297.2020.00041
arXiv:2004.03004

[29] Wolfgang Lechner, Philipp Hauke, and Peter Zoller. A quantum annealing architecture with all-to-all connectivity from local interactions. Science Advances, 1 (9): 1–6, 2015. ISSN 23752548. 10.1126/sciadv.1500838.
https://doi.org/10.1126/sciadv.1500838

[30] Harry Markowitz. Portfolio selection. The Journal of Finance, 7 (1): 77–91, 1952. 10.2307/2975974.
https://doi.org/10.2307/2975974

[31] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan. Quantum computational chemistry. Rev. Mod. Phys., 92: 015003, Mar 2020a. 10.1103/RevModPhys.92.015003.
https://doi.org/10.1103/RevModPhys.92.015003

[32] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan. Quantum computational chemistry. Reviews of Modern Physics, 92 (1), Mar 2020b. ISSN 1539-0756. 10.1103/revmodphys.92.015003.
https://doi.org/10.1103/revmodphys.92.015003

[33] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics, 18 (2): 023023, feb 2016. 10.1088/1367-2630/18/2/023023.
https://doi.org/10.1088/1367-2630/18/2/023023

[34] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications, 9 (1): 4812, 2018. 10.1038/s41467-018-07090-4.
https://doi.org/10.1038/s41467-018-07090-4

[35] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn, Abhinav Kandala, Antonio Mezzacapo, Peter Müller, Walter Riess, Gian Salis, John Smolin, Ivano Tavernelli, and Kristan Temme. Quantum optimization using variational algorithms on near-term quantum devices. Quantum Science and Technology, 3 (3): 030503, jun 2018. 10.1088/2058-9565/aab822.
https://doi.org/10.1088/2058-9565/aab822

[36] J. S. Otterbach, R. Manenti, N. Alidoust, A. Bestwick, M. Block, B. Bloom, S. Caldwell, N. Didier, E. Schuyler Fried, S. Hong, P. Karalekas, C. B. Osborn, A. Papageorge, E. C. Peterson, G. Prawiroatmodjo, N. Rubin, Colm A. Ryan, D. Scarabelli, M. Scheer, E. A. Sete, P. Sivarajah, Robert S. Smith, A. Staley, N. Tezak, W. J. Zeng, A. Hudson, Blake R. Johnson, M. Reagor, M. P. da Silva, and C. Rigetti. Unsupervised machine learning on a hybrid quantum computer. arXiv preprint arXiv:1712.05771, 2017.
arXiv:1712.05771

[37] Guido Pagano, Aniruddha Bapat, Patrick Becker, Katherine S. Collins, Arinjoy De, Paul W. Hess, Harvey B. Kaplan, Antonis Kyprianidis, Wen Lin Tan, Christopher Baldwin, and et al. Quantum approximate optimization of the long-range ising model with a trapped-ion quantum simulator. Proceedings of the National Academy of Sciences, 117 (41): 25396–25401, Oct 2020. ISSN 1091-6490. 10.1073/pnas.2006373117.
https://doi.org/10.1073/pnas.2006373117

[38] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O'Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5 (1): 4213, 2014. 10.1038/ncomms5213.
https://doi.org/10.1038/ncomms5213

[39] M. Powell. A view of algorithms for optimization without derivatives. Mathematics TODAY, 43, 01 2007.

[40] John Preskill. Quantum Computing in the NISQ era and beyond. Quantum, 2: 79, August 2018. ISSN 2521-327X. 10.22331/q-2018-08-06-79.
https://doi.org/10.22331/q-2018-08-06-79

[41] Xiaogang Qiang, Xiaoqi Zhou, Jianwei Wang, Callum M. Wilkes, Thomas Loke, Sean O'Gara, Laurent Kling, Graham D. Marshall, Raffaele Santagati, Timothy C. Ralph, Jingbo B. Wang, Jeremy L. O'Brien, Mark G. Thompson, and Jonathan C. F. Matthews. Large-scale silicon quantum photonics implementing arbitrary two-qubit processing. Nature Photonics, 12 (9): 534–539, 2018. 10.1038/s41566-018-0236-y.
https://doi.org/10.1038/s41566-018-0236-y

[42] Arthur G. Rattew, Shaohan Hu, Marco Pistoia, Richard Chen, and Steve Wood. A domain-agnostic, noise-resistant, hardware-efficient evolutionary variational quantum eigensolver. arXiv preprint arXiv:1910.09694, 2019.
arXiv:1910.09694

[43] Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, John M. Martinis, Daniel A. Lidar, and Matthias Troyer. Defining and detecting quantum speedup. Science, 345 (6195): 420–424, 2014. ISSN 0036-8075. 10.1126/science.1252319.
https://doi.org/10.1126/science.1252319

[44] M Saffman. Quantum computing with atomic qubits and rydberg interactions: progress and challenges. Journal of Physics B: Atomic, Molecular and Optical Physics, 49 (20): 202001, oct 2016. 10.1088/0953-4075/49/20/202001.
https://doi.org/10.1088/0953-4075/49/20/202001

[45] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26 (5): 1484–1509, 1997. 10.1137/S0097539795293172.
https://doi.org/10.1137/S0097539795293172

[46] Kevin J Sung, Jiahao Yao, Matthew P Harrigan, Nicholas C Rubin, Zhang Jiang, Lin Lin, Ryan Babbush, and Jarrod R McClean. Using models to improve optimizers for variational quantum algorithms. Quantum Science and Technology, 5 (4): 044008, Oct 2020. ISSN 2058-9565. 10.1088/2058-9565/abb6d9.
https://doi.org/10.1088/2058-9565/abb6d9

[47] IBM Quantum team. Retrieved from https://quantum-computing.ibm.com. Ibmq, 2020.
https://quantum-computing.ibm.com

[48] G Wendin. Quantum information processing with superconducting circuits: a review. Reports on Progress in Physics, 80 (10): 106001, sep 2017. 10.1088/1361-6633/aa7e1a.
https://doi.org/10.1088/1361-6633/aa7e1a

[49] Madita Willsch, Dennis Willsch, Fengping Jin, Hans De Raedt, and Kristel Michielsen. Benchmarking the quantum approximate optimization algorithm. Quantum Information Processing, 19 (7), Jun 2020. ISSN 1573-1332. 10.1007/s11128-020-02692-8.
https://doi.org/10.1007/s11128-020-02692-8

[50] Stephen J. Wright. Continuous optimization (nonlinear and linear programming). In Nicholas J. Higham, Mark R. Dennis, Paul Glendinning, Paul A. Martin, Fadil Santosa, and Jared Tanner, editors, The Princeton Companion to Applied Mathematics, chapter 4, page 281–293. Princeton University Press, Princeton, 2015.

[51] 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. Physical Review X, 10 (2), Jun 2020. ISSN 2160-3308. 10.1103/physrevx.10.021067.
https://doi.org/10.1103/physrevx.10.021067

Cited by

[1] Marco Sciorilli, Lucas Borges, Taylor L. Patti, Diego García-Martín, Giancarlo Camilo, Anima Anandkumar, and Leandro Aolita, "Towards large-scale quantum optimization solvers with few qubits", Nature Communications 16 1, 476 (2025).

[2] Chen-Yu Liu, 2023 International Conference on Computational Science and Computational Intelligence (CSCI) 397 (2023) ISBN:979-8-3503-6151-3.

[3] Krzysztof Domino, Emery Doucet, Reece Robertson, Bartłomiej Gardas, and Sebastian Deffner, "On the Baltimore Light RailLink into the quantum future", Scientific Reports 15 1, 29576 (2025).

[4] Muhammad Umer, Eleftherios Mastorakis, Sofia Evangelou, and Dimitris G. Angelakis, "Probing the limits of variational quantum algorithms for nonlinear ground states on real quantum hardware: The effects of noise", Physical Review A 111 1, 012626 (2025).

[5] Rafael Simões do Carmo, Renato Gomes dos Reis, Samuel Fernando F Silva, Luiz Gustavo E. Arruda, and Felipe F. Fanchini, "Warm-Starting PCE for Traveling Salesman Problem", Brazilian Journal of Physics 56 1, 49 (2026).

[6] Muhammad Umer, Eleftherios Mastorakis, and Dimitris G Angelakis, "Efficient estimation and sequential optimization of cost functions in variational quantum algorithms", Quantum Science and Technology 10 3, 035022 (2025).

[7] Marko J. Rančić, "Noisy intermediate-scale quantum computing algorithm for solving an n -vertex MaxCut problem with log( n ) qubits", Physical Review Research 5 1, L012021 (2023).

[8] Shota Koshikawa, Aruto Hosaka, and Tsuyoshi Yoshida, "Efficient bit labeling in factorization machines with annealing for traveling salesman problem", Scientific Reports 15 1, 26910 (2025).

[9] Mikhail Podobrii, Viacheslav Kuzmin, Vladimir Voloshinov, Margarita Veshchezerova, and Michael R. Perelshtein, "Qubit‐Efficient Quantum Local Search for Combinatorial Optimization", Advanced Quantum Technologies 9 3, e00438 (2026).

[10] Filip B. Maciejewski, Bao G. Bach, Maxime Dupont, P. Aaron Lott, Bhuvanesh Sundar, David E. Bernal Neira, Ilya Safro, and Davide Venturelli, 2024 IEEE High Performance Extreme Computing Conference (HPEC) 1 (2024) ISBN:979-8-3503-8713-1.

[11] Mateo Alonso, Guillermo Rubiños Rodríguez, Pablo Díez-Valle, Ana Garbayo, Xela García-Santiago, and Gonzalo Blázquez Gil, "Modeling Energy Communities: A Case Study of Quantum Approximate Optimization on a Superconducting Processor", IEEE Access 13, 106140 (2025).

[12] Francesco Martini, Daniele Lizzio Bosco, Carlo Barbanera, Serena Bernardini, Giacomo Ranieri, Francesca Cibrario, Davide Corbelletto, Giuseppe Bruno, Alessandra Di Pierro, and Luca Dellantonio, "Securities transaction settlement optimization on superconducting quantum devices", Journal of Economic Dynamics and Control 190, 105384 (2026).

[13] Ningyi Xie, Xinwei Lee, Tiejin Chen, Yoshiyuki Saito, Nobuyoshi Asai, and Dongsheng Cail, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 208 (2025) ISBN:979-8-3315-5736-2.

[14] Yovav Tene-Cohen, Tomer Kelman, Ohad Lev, and Adi Makmal, "A Variational Qubit-Efficient MaxCut Heuristic Algorithm", npj Quantum Information 12 1, 50 (2026).

[15] Ioannis D. Leonidas, Alexander Dukakis, Benjamin Tan, and Dimitris G. Angelakis, "Qubit Efficient Quantum Algorithms for the Vehicle Routing Problem on Noisy Intermediate‐Scale Quantum Processors", Advanced Quantum Technologies 7 5, 2300309 (2024).

[16] Adam Glos, Aleksandra Krawiec, and Zoltán Zimborás, "Space-efficient binary optimization for variational quantum computing", npj Quantum Information 8 1, 39 (2022).

[17] Bryce Fuller, Charles Hadfield, Jennifer R. Glick, Takashi Imamichi, Toshinari Itoko, Richard J. Thompson, Yang Jiao, Marna M. Kagele, Adriana W. Blom-Schieber, Rudy Raymond, and Antonio Mezzacapo, "Approximate Solutions of Combinatorial Problems via Quantum Relaxations", IEEE Transactions on Quantum Engineering 5, 1 (2024).

[18] Toonyawat Angkhanawin, Aydin Deger, Jonathan D Pritchard, and C Stuart Adams, "Graph coloring via quantum optimization on a Rydberg-qudit atom array", Quantum Science and Technology 11 2, 025012 (2026).

[19] Hiromichi Matsuyama, Wei-hao Huang, Kohji Nishimura, and Yu Yamashiro, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 470 (2024) ISBN:979-8-3315-4137-8.

[20] Nils Quetschlich, Lukas Burgholzer, and Robert Wille, 2023 IEEE 53rd International Symposium on Multiple-Valued Logic (ISMVL) 134 (2023) ISBN:978-1-6654-6416-1.

[21] Hian Lee Kwa, Bing Hong Teh, Teck Yoong Chai, and Yung Sze Gan, Communications in Computer and Information Science 2744, 335 (2026) ISBN:978-3-032-13854-5.

[22] David Winderl, Nicola Franco, and Jeanette Miriam Lorenz, "A Comparative Study on Solving Optimization Problems With Exponentially Fewer Qubits", IEEE Transactions on Quantum Engineering 5, 1 (2024).

[23] Elias X. Huber, Benjamin Y. L. Tan, Paul R. Griffin, and Dimitris G. Angelakis, "Exponential qubit reduction in optimization for financial transaction settlement", EPJ Quantum Technology 11 1, 52 (2024).

[24] Kentaro Tamura, Yohichi Suzuki, Rudy Raymond, Hiroshi C. Watanabe, Yuki Sato, Ruho Kondo, Michihiko Sugawara, and Naoki Yamamoto, "Noise Robustness of Quantum Relaxation for Combinatorial Optimization", IEEE Transactions on Quantum Engineering 5, 1 (2024).

[25] Chen-Yu Liu and Hsi-Sheng Goan, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 246 (2023) ISBN:979-8-3503-4323-6.

[26] Rudy Raymond, Alexander Buts, and Marco Pistoia, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 01 (2025) ISBN:979-8-3315-5736-2.

[27] Abhishek Awasthi, Francesco Bär, Joseph Doetsch, Hans Ehm, Marvin Erdmann, Maximilian Hess, Johannes Klepsch, Peter A. Limacher, Andre Luckow, Christoph Niedermeier, Lilly Palackal, Ruben Pfeiffer, Philipp Ross, Hila Safi, Janik Schönmeier-Kromer, Oliver von Sicard, Yannick Wenger, Karen Wintersperger, and Sheir Yarkoni, Lecture Notes in Networks and Systems 739, 264 (2023) ISBN:978-3-031-37962-8.

[28] Supreeth Mysore Venkatesh, Antonio Macaluso, Marlon Nuske, Matthias Klusch, and Andreas Dengel, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 450 (2024) ISBN:979-8-3315-4137-8.

[29] Gereon Koßmann, Lennart Binkowski, Lauritz van Luijk, Timo Ziegler, and René Schwonnek, "Deep-Circuit QAOA", Quantum 9, 1882 (2025).

[30] M. R. Perelshtein, A. I. Pakhomchik, Ar. A. Melnikov, M. Podobrii, A. Termanova, I. Kreidich, B. Nuriev, S. Iudin, C. W. Mansell, and V. M. Vinokur, "NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization", Quantum 7, 1186 (2023).

[31] V. E. Zobov and I. S. Pichkovskiy, "Clustering by quantum annealing on the three-level quantum elements qutrits", Quantum Information Processing 21 4, 144 (2022).

[32] Manuel Schnaus, Lilly Palackal, Benedikt Poggel, Xiomara Runge, Hans Ehm, Jeanette Miriam Lorenz, and Christian B. Mendl, 2024 IEEE International Conference on Quantum Software (QSW) 81 (2024) ISBN:979-8-3503-6847-5.

[33] Eleftherios Mastorakis, Muhammad Umer, Milena Guevara-Bertsch, Juris Ulmanis, Felix Rohde, and Dimitris G Angelakis, "Resource-efficient Hadamard test tailored variational framework for nonlinear dynamics on quantum computers", Quantum Science and Technology 11 1, 015061 (2026).

[34] Tino Werner and Freyja Ullinger, "Quantum algorithms for scheduling problems: a survey", EPJ Quantum Technology 13 1, 31 (2026).

[35] Mojdeh S. Najafabadi, Daniel Schumayer, Chee-Kong Lee, Dieter Jaksch, and David A. W. Hutchinson, "Improving quantum annealing by engineering the coupling to the environment", EPJ Quantum Technology 10 1, 44 (2023).

[36] Margarita Veshchezerova, Mikhail Somov, David Bertsche, Steffen Limmer, Sebastian Schmitt, Michael Perelshtein, and Ayush Joshi Tripathi, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 636 (2023) ISBN:979-8-3503-4323-6.

[37] Bhuvanesh Sundar and Maxime Dupont, "Qubit-efficient quantum combinatorial-optimization solver", Physical Review Applied 25 3, 034071 (2026).

[38] Tian Huang, Jun Xu, Tao Luo, Xiaozhe Gu, Rick Goh, and Weng-Fai Wong, "Benchmarking Quantum(-Inspired) Annealing Hardware on Practical Use Cases", IEEE Transactions on Computers 72 6, 1692 (2023).

[39] Muhammad Zaman, Tanzila Kehkashan, Adnan Akhunzada, Hashem Alaidaros, Mueen Uddin, and Muhammad Azeem, 2024 International Conference on Digital Image Computing: Techniques and Applications (DICTA) 730 (2024) ISBN:979-8-3503-7903-7.

[40] Florian Klug, "Quantum approaches to the traveling salesman problem: A critical review of formulations, complexity, and implementation limits", Physica A: Statistical Mechanics and its Applications 695, 131649 (2026).

[41] Supreeth Mysore Venkatesh, Antonio Macaluso, Marlon Nuske, Matthias Klusch, and Andreas Dengel, "Qubit-efficient Variational Quantum Algorithms for Image Segmentation", arXiv:2405.14405, (2024).

[42] Adam Glos, Aleksandra Krawiec, and Zoltán Zimborás, "Space-efficient binary optimization for variational computing", arXiv:2009.07309, (2020).

[43] Kieran McDowall, Theodoros Kapourniotis, Christopher Oliver, Phalgun Lolur, and Konstantinos Georgopoulos, "Cross-Platform Benchmarking of Near-Term Quantum Optimisation Algorithms", arXiv:2504.06885, (2025).

[44] Tristan Zaborniak, Prashanti Priya Angara, Vikram Khipple Mulligan, Hausi Müller, and Ulrike Stege, "Qubit-efficient and gate-efficient encodings of graph partitioning problems for quantum optimization", arXiv:2604.21123, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-07-15 04:35:03) and SAO/NASA ADS (last updated successfully 2026-07-14 14:46:55). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-07-15 04:35:03: Cannot retrieve data from ADS due to rate limitations.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.