https://doi.org/10.1140/epjqt/s40507-025-00402-w
Research
Digitized counterdiabatic quantum optimization for bin packing problem
1
Instituto de Ciencia de Materiales de Madrid (CSIC), Cantoblanco, E-28049, Madrid, Spain
2
Departamento de Física Teórica de la Materia Condensada, Universidad Autónoma de Madrid, Madrid, Spain
3
Department of Physical Chemistry, University of the Basque Country UPV/EHU, Apartado 644, 48080, Bilbao, Spain
4
Kipu Quantum GmbH, Greifswalderstrasse 212, 10405, Berlin, Germany
a
yue.ban@csic.es
b
xi.chen@csic.es
Received:
21
February
2025
Accepted:
28
July
2025
Published online:
11
August
2025
The bin packing problem (BPP), a classical NP-hard combinatorial optimization challenge, has emerged as a promising application for quantum computing. In this work, we tackle the one-dimensional BPP (1dBPP) using a digitized counterdiabatic quantum approximate optimization algorithm (DC-QAOA) that incorporates counterdiabatic (CD) driving to achieve a 40% higher feasibility ratio than standard QAOA, while reducing quantum resource requirements. We investigate three ansatz schemes -DC-QAOA, CD-inspired ansatz, and CD-mixer ansatz - each integrating CD terms with distinct combinations of cost and mixer Hamiltonians, resulting in different DC-QAOA variants. Numerical simulations demonstrate that these DC-QAOA variants maintain solution accuracy with less than 5% variance across varying iteration numbers, circuit depths, and Hamiltonian step sizes. Moreover, they require approximately 7 to 8 times fewer measurements to achieve comparable precision under the same parameter variations. Experimental validation on a 10-item 1dBPP instance using IBM quantum computers shows the CD-mixer ansatz achieves five times more feasibility solutions and greater robustness against NISQ noise. Collectively, these results establish DC-QAOA as a resource-efficient framework for combinatorial optimization on near-term quantum devices.
Key words: Digitized counterdiabatic quantum algorithm / Bin packing problem
© The Author(s) 2025
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
