Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

9-2025

Abstract

Solving NP-hard constrained combinatorial optimization problems using quantum algorithms remains a challenging yet promising avenue toward quantum advantage. Variational Quantum Algorithms (VQAs), such as the Variational Quantum Eigensolver (VQE), typically require constrained problems to be reformulated as unconstrained ones using penalty methods. A common approach introduces slack variables and quadratic penalties in the QUBO formulation to handle inequality constraints. However, this leads to increased qubit requirements and often distorts the optimization landscape, making it harder to find high-quality feasible solutions. To address these issues, we explore a slack-free formulation that directly encodes inequality constraints using custom penalty functions, specifically the exponential function and the Heaviside step function. These steplike penalties suppress infeasible solutions without introducing additional qubits or requiring finely tuned weights. Inspired by recent developments in quantum annealing and thresholdbased constraint handling in gate-based algorithms, we implement and evaluate our approach on the Multiple Knapsack Problem (MKP). Experimental results show that the step-based formulation significantly improves feasibility and optimality rates compared to unbalanced penalization, while reducing overall qubit overhead.

Discipline

Artificial Intelligence and Robotics

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Sustainability

Publication

Proceedings of the 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), Albuquerque, USA, August 20 - September 5

First Page

2112

Last Page

2119

Publisher

IEEE

City or Country

Los Alamitos, CA

Additional URL

https://doi.org/10.1109/QCE65121.2025.00231

Download

Share

COinS