Qubit-Efficient QUBO Formulation for Constrained Optimization Problems Meerzhan Kanatbekova, Vincenzo De Maio, Ivona Brandic Abstract Quantum computing has emerged as a promising alternative for solving combinatorial optimization problems. The standard approach for encoding optimization problems on quantum processing units (QPUs) involves transforming them into their Quadratic Unconstrained Binary Optimization (QUBO) representation. However, encoding constraints of optimization problems, particularly inequality constraints, into QUBO requires additional variables, which results in more qubits. Considering the limited availability of qubits in NISQ machines, existing encoding methods fail to scale due to their reliance on large numbers of qubits. We propose a generalized exponential penalty framework for QUBO inequality constraints inspired by a class of exponential functions , which we call exponential penalization. This paper presents an encoding strategy for inequality constraints in combinatorial optimization problems, inspired by a class of exponential functions , which we call exponential penalization. The initial idea of using exponential penalties for QUBO formulation was introduced by Montañez-Barrera et al. by applying a specific exponential function to reduce qubit requirements. In this work, we extend that approach by conducting a comprehensive study on a broader class of exponential functions, analyzing their theoretical properties and empirical performance. Our experimental results demonstrate that an exponential penalization achieves 57%, 83% qubit number reduction for Bin Packing Problem (BPP) and Traveling Salesman Problem (TSP), respectively. And we demonstrate comparable solution quality to classical with a probability of 6% and 21% accuracy for BPP with 8 and TSP with 12 qubits, respectively. 1 Introduction Optimization problems play a critical role in diverse industrial and scientific domains, yet their increasing scale has led to computational demands that exceed the capabilities of classical methods. As transistor miniaturization slows and Moores Law approaches its physical limits, classical computing architectures face inherent barriers in efficiently addressing large-scale combinatorial problems. These challenges have directed growing attention toward quantum computing, which has recently become an active field of research for solving complex optimization problems [ 1 , 2 , 3 , 4 , 5 ] . To solve the optimization problem on a quantum computer, first, it has to be encoded in quantum states. The standard approach for encoding optimization problems on quantum processing units (QPUs) involves transforming them into their Quadratic Unconstrained Binary Optimization (QUBO) representation [ 6 ] . Within the QUBO framework, the constraints of the optimization problem are incorporated into the objective function as penalty terms. Existing constraint-encoding methods, such as linear, quadratic penalties [ 7 ] , have shown effectiveness in classical optimization frameworks but often lack scalability when applied to quantum systems [ 8 ] , since inequality constraints require additional decision variables in their QUBO formulation. The commonly used approach involves incorporating extra variables (so-called slack variables) to encode these constraints [ 7 ] . However, this method leads to an increase in the dimensionality of the problem, which poses a significant challenge to quantum computers, where the number of qubits is limited. To address these challenges, exponential penalization for inequality constraints has been proposed in [ 9 ] . Exponential penalties offer a steeper growth rate compared to quadratic penalties, allowing for more efficient enforcement of constraints with potentially lower qubit count. The authors in [ 9 ] demonstrated that exponential penalization can substantially reduce the number of qubits required for problems such as the Bin Packing Problem (BPP), the Travelling Salesman Problem (TSP), and the Knapsack Problem (KP). Quadratic penalties grow polynomially, providing moderate enforcement that can be too forgiving in some cases. In contrast, exponential penalties grow rapidly with the magnitude of constraint violations, allowing them to penalize large violations more severely and potentially achieve better constraint satisfaction with fewer qubits. However, the work in [ 9 ] was limited to a single type of exponential function. In this work, we extend the concept of exponential penalization by considering a class of exponential penalty functions. This class captures various exponential growth behaviors that can be tuned to enforce constraints more effectively across different problem instances. Specifically, we investigate three different forms of exponential penalty functions derived from the main formulation and analyze their impact on solution quality, time complexity, and convergence behavior. Our focus is on combinatorial optimization problems, including BPP and TSP, as representative benchmarks. While the detailed methodology and experimental setup are provided in subsequent sections, an overview of the computational pipeline is illustrated in Figure 1 . Given optimization problems such as the BPP and the TSP, we begin by applying our proposed exponential encoding method to derive the QUBO formulation. This efficient QUBO representation is then transformed into an equivalent Ising Hamiltonian, which serves as the input to quantum computing frameworks. We subsequently solve the problem on a quantum computer (or a quantum simulator) using the Quantum Approximate Optimization Algorithm (QAOA) and obtain the final solution. The experimental framework utilizes IBM’s Qiskit simulator, enabling controlled evaluation of solution quality, qubit requirements, and execution times under realistic quantum settings. Figure 1 : Overview of the optimization problem solution pipeline on classical-quantum computers, featuring the QUBO formulation derived using exponential penalty functions. In summary, the key contributions of the paper are: – We propose an exponential penalization method using a class of exponential penalty functions to encode inequality constraints in optimization problems. We also provide different functions within the class of exponential functions. – We empirically evaluate the proposed method on generated datasets and compare it to existing baseline approaches with respect to execution time, solution quality, qubit count compression/reduction rate. – Our extensive experiments on IBM simulator demonstrate that an exponential penalization achieves 57%, 83% qubit count reduction rate while preserving 6%, 21% solution accuracy for BPP, TSP respectively. – We optimize the exponential penalty parameters such as r,s,p and provide an empirical study on them by determining the significance factor of each. The structure of the paper is as follows. Section 2 reviews existing encoding techniques and their relevance to quantum optimization. Section 3 describes the background and introduces the benchmark problems. Section 4 introduces the proposed exponential penalization, including a detailed theoretical analysis. Section 5 describes the experimental setup and metrics. Section 6 presents experimental results demonstrating the effectiveness of the approach in both classical and quantum optimization settings. Finally, Section 7 concludes the paper and outlines potential directions for future research. 2 Related Work Constraint handling in optimization problems has been extensively studied, both in classical and quantum computing domains. In the literature, two primary penalization strategies are commonly used: interior and exterior penalty methods [ 10 ] . Interior penalty methods penalize violations within the feasible region, while exterior penalty methods penalize infeasible solutions. Exterior penalties typically include linear and quadratic, each with distinct enforcement characteristics. Several recent works have proposed more qubit-efficient encodings of optimization problems. Tan et al. [ 11 ] tackle optimization problems by proposing an encoding scheme for QUBO models with n variables that can be implemented on O(logn) number of qubits. They propose a strategy using n ancilla qubits and r register qubits to divide the QUBO problem into 2r subsystems of n classical variables, requiring a total of t=n+r qubits. For example, optimization problems with a problem size of 10^{4} can be solved only using no more than 15 qubits. However, this method focuses primarily on encoding the final QUBO representation more efficiently, and does not directly address constraint handling or inequality encoding. A specialized encoding for the Travelling Salesman Problem (TSP) was proposed in [ 12 ] through permutation encoding based on Heap’s algorithm. This approach maps each TSP route to a unique permutation index, significantly reducing the qubit requirement to \log(n!) compared to the n^{2} qubits typically needed in standard QUBO formulations. While this method is highly qubit-efficient for routing problems, it is not directly applicable to general constrained optimization problems, especially those with complex inequality constraints. Leonidas et al. [ 13 ] investigated encoding strategies for the Vehicle Routing Problem with Time Windows (VRPTW). They compared minimal and full encoding schemes across problem instances ranging from 11 to 3964 routes, evaluating performance on both simulators and quantum hardware. Their results showed that minimal encoding could reduce qubit usage, but each classical variable still typically required dedicated qubits unless further optimizations were introduced. Their focus was primarily on mapping efficiency rather than constraint flexibility. Roch et al. [ 14 ] empirically studied the effect of penalty weight selection on the minimum spectral gap of constrained optimization problems when solved via quantum annealing. They demonstrated that carefully tuned penalty weights can improve solution quality by enlarging the spectral gap, and they proposed using machine learning models to predict optimal penalty coefficients. However, their work is focused on penalty magnitude selection rather than exploring different penalty functions. Montanez et al. [ 9 ] proposed an alternative method for encoding inequality constraints without introducing slack variables. Their approach uses an exponential penalty function that rapidly penalizes constraint violations, reducing the number of qubits needed compared to traditional methods. However, their study is limited to a single form of exponential function and does not investigate how different exponential growth rates or types of exponential functions could affect performance, solution quality, or qubit efficiency. In contrast to these works, our study proposes a generalized exponential penalization framework that introduces a tunable class of exponential functions for inequality constraint encoding. Unlike previous methods, our approach: • Systematically explores multiple exponential penalty functions. • Optimizes the penalty parameters empirically for each problem class. • Demonstrates substantial qubit savings without sacrificing solution quality. • Provides flexibility across diverse combinatorial optimization problems. 3 Background 3.1 Combinatorial Optimization Problems A combinatorial optimization problem (COP) is a set of components (S,S^{\prime},f,g,h) , where S is the finite search space, S^{\prime}\subset S is the set of feasible solutions in S , f:S^{\prime}\rightarrow\mathbb{R} is an objective function. The goal is to find x^{*}\in S^{\prime} that maximizes or minimizes the objective function f(x) , subject to constraints g and h defined on S . COPs are defined as: \displaystyle\min/\max\quad \displaystyle f(x) (1) s.t. \displaystyle g_{i}(x)=0, \displaystyle\forall i (2) \displaystyle h_{j}(x)\leq 0, \displaystyle\forall j (3) where f:S^{\prime}\rightarrow\mathbb{R} is an objective function, g_{i}:S^{\prime}\rightarrow\mathbb{R},i=1,...,m are equality constraints and h_{j}:S^{\prime}\rightarrow\mathbb{R},j=1,...,k are inequality constraints. In contrast to continuous optimization problems, where the solution space is continuous, in COP the feasible solutions are discrete, i.e., the focus is on discrete structures, such as graphs or permutations. Moreover, certain COPs are known to be NP-hard, implying that the solution is computationally challenging and may demand superpolynomial time in worst-case scenarios. In this work, we experimented proposed encoding method on two well-known COPs: Bin Packing Problem (BPP) and Travelling Salesperson Problem (TSP). 3.1.1 The Bin Packing Problem (BPP) is a well-known combinatorial optimization problem that arises in logistics, manufacturing, and resource allocation [ 15 , 16 ] . Given a set of items with known weights, the goal is to pack them into a minimum number of bins while ensuring that the total weight in each bin does not exceed a fixed capacity. We consider the 1-d offline BPP . Each item x_{ij} has a weight, w_{i} , and has to be assigned to a bin B_{j} using a minimum number of bins with fixed capacity C . Formally, \displaystyle\min\quad \displaystyle\sum_{j=1}^{K}B_{j} (4) s.t. \displaystyle\sum_{j=1}^{K}x_{ij}=1, \displaystyle\forall i (5) \displaystyle\sum_{i=1}^{N}w_{i}x_{ij}\leq C\cdot B_{j}, \displaystyle\forall j (6) where N and K are the number of items and bins, respectively. The equality constraint g(x_{ij}) in 5 implies that each item can be packed into at most one bin, and the inequality constraint h(x_{ij}) in 6 says that the weight of bin item can not exceed the given capacity C . Table 1 : Summary of notation and descriptions for the Bin Packing Problem (BPP) with one type of example solved as part of the experiments. Notation Description Example N Total number of items 3 K Total number of bins 2 w_{i} Weight of item i [25,25,30] C Capacity of a single bin 100 B_{j} Binary variable: 1 if bin j is used, 0 otherwise {0,1} x_{ij} Binary variable: 1 if item i is assigned to bin j , 0 otherwise {0,1} In BPP, determining whether a given set of items can be packed into at most K bins is NP-complete, while the optimization part, which seeks to minimize the number of bins used, is NP-hard. This complexity arises from the difficulty of partitioning items optimally among bins, which is equivalent to solving a subset sum problem, a known NP-complete problem. Additionally, the number of feasible packing assignments grows exponentially as O(K^{N}) , making it computationally infeasible for large instances. The Table 1 summarizes the notations used for BPP formulation. 3.1.2 Traveling Salesman Problem (TSP) Let G=(V,E,w:E\mapsto\mathbb{R}) be a weighted graph with vertices V , edges E and w a weight function on E . In TSP, the aim is to find the minimum weight loop in G that visits each vertex of V exactly once and returns to the starting point. Let |V|=n and w_{ij} the weight between vertices i and j . TSP is then formulated as: \displaystyle\min\quad \displaystyle\sum_{i=1}^{n}\sum_{\begin{subarray}{c}j=1\\ j\neq i\end{subarray}}^{n}w_{ij}\,x_{ij} (7) s.t. \displaystyle\sum_{\begin{subarray}{c}j=1\\ j\neq i\end{subarray}}^{n}x_{ij}=1, \displaystyle\forall i (8) \displaystyle\sum_{\begin{subarray}{c}i=1\\ i\neq j\end{subarray}}^{n}x_{ij}=1, \displaystyle\forall j (9) \displaystyle\sum_{i\in Q}\sum_{j\in Q}x_{ij}\leq|Q|-1, \displaystyle\forall Q\subset V (10) where x_{ij}=1 if edge (i,j) is part of the solution, 0 otherwise. Q is the sub-path with 2\leq\lvert{Q}\rvert1 and F_{3}=f(x)-\sum_{i=1}^{m}\frac{1}{a^{k}}e^{b^{k}g_{i}(x)} (16) when 1