Digitized Counter-Diabatic Quantum Optimization for Bin Packing Problem

Abstract

The bin packing problem, a classical NP-hard combinatorial optimization challenge, has emerged as a promising candidate for quantum computing applications. In this work, we address the one-dimensional bin packing problem (1dBPP) using a digitized counter-diabatic quantum algorithm (DC-QAOA), which incorporates counter-diabatic (CD) driving to reduce quantum resource requirements while maintaining high solution quality, outperforming traditional methods such as QAOA. We evaluate three ansatz schemes-DC-QAOA, a CD-inspired ansatz, and a CD-mixer ansatz-each integrating CD terms with distinct combinations of cost and mixer Hamiltonians, resulting in different DC-QAOA variants. Among these, the CD-mixer ansatz demonstrates superior performance, showing robustness across various iteration counts, layer depths, and Hamiltonian steps, while consistently producing the most accurate approximations to exact solutions. To validate our approach, we solve a 10-item 1dBPP instance on an IBM quantum computer, optimizing circuit structures through simulations. Despite constraints on circuit depth, the CD-mixer ansatz achieves high accuracy and a high likelihood of success. These findings establish DC-QAOA, particularly the CD-mixer variant, as a powerful framework for solving combinatorial optimization problems on near-term quantum devices.

12 pages, 7 figures

References in corpus (29)

• Variational Quantum Algorithms
• Noisy intermediate-scale quantum (NISQ) algorithms
• Warm-starting quantum optimization
• Improving Variational Quantum Optimization using CVaR
• Floquet-engineering counterdiabatic protocols in quantum many-body systems
• A Lie Algebraic Theory of Barren Plateaus for Deep Parameterized Quantum Circuits
• IBM Quantum Computers: Evolution, Performance, and Future Directions
• Shortcuts to Adiabaticity in Digitized Adiabatic Quantum Computing
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Digitized-counterdiabatic quantum approximate optimization algorithm
• A case study of variational quantum algorithms for a job shop scheduling problem
• Digitized-Counterdiabatic Quantum Algorithm for Protein Folding
• Portfolio Optimization with Digitized-Counterdiabatic Quantum Algorithms
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms
• Towards large-scale quantum optimization solvers with few qubits
• Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
• Hybrid Approach for Solving Real-World Bin Packing Problem Instances Using Quantum Annealers
• Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
• Transfer learning of optimal QAOA parameters in combinatorial optimization
• Optimizing edge state transfer in a Su-Schrieffer-Heeger chain via hybrid analog-digital strategies
• Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem
• Benchmark dataset and instance generator for Real-World Three-Dimensional Bin Packing Problems
• Digitized Counterdiabatic Quantum Algorithms for Logistics Scheduling
• Bias-field digitized counterdiabatic quantum optimization
• Solving Logistic-Oriented Bin Packing Problems Through a Hybrid Quantum-Classical Approach
• Benchmarking hybrid digitized-counterdiabatic quantum optimization
• Second-order optimisation strategies for neural network quantum states
• Exploring Ground States of Fermi-Hubbard Model on Honeycomb Lattices with Counterdiabaticity
• Simplifying the simulation of local Hamiltonian dynamics