High-performance computing (HPC) systems handle increasingly complex computational workloads, making efficient resource allocation an important challenge. For example, distributing computational tasks across a limited number of servers while minimizing resource usage can be modeled using the Bin Packing Problem (BPP). Here, computational tasks can represent items, while servers represent bins with limited processing or memory capacity. 

This BPP is an NP-hard optimization problem, which means as the number of computational tasks and servers increases, finding an optimal allocation becomes computationally challenging. Although classical algorithms can find approximate solutions for smaller problem sizes, quantum optimization algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA), are being explored as alternative approaches to solving bigger such problems. 

However, before executing a quantum algorithm, we must first transform the classical optimization problem into a "quantum-compatible" mathematical representation. As discussed in my previous on data loading, problem formulation is an important step in the classical–quantum data pipeline.

An inefficient formulation can introduce additional variables and significantly increase the number of qubits required to represent the problem. This raises an important question: How can we formulate constrained optimization problems more efficiently while reducing their quantum resource requirements?  

The Challenge of Encoding Constraints

Optimization problems involve not only finding the best solution but also satisfying certain constraints. In the basic BPP, for example, every computational task must be assigned to exactly one server, and the total resource consumption of the assigned tasks must not exceed the server's capacity. A common approach to representing optimization problems on quantum computers is to transform them into a Quadratic Unconstrained Binary Optimization (QUBO) formulation. In QUBO, constraints are incorporated into the objective function using penalty terms. However, encoding inequality constraints, such as server capacity limitations, typically requires introducing additional binary variables, known as slack variables. These variables increase the number of qubits required to represent the problem. Since current quantum computers have limited qubit availability, this additional overhead can restrict the size of optimization problems that can be executed.

Our Approach: Class of exponential functions

In our recent paper, Qubit-Efficient QUBO Formulation for Constrained Optimization Problems, we investigate an alternative approach to encoding inequality constraints using exponential penalty functions.

Instead of introducing additional slack variables, our approach directly incorporates inequality constraints into the objective function. The exponential penalty increases as the constraint violation grows, discouraging infeasible solutions without requiring additional qubits to represent slack variables.

We investigate three variants of exponential penalty functions, each having different scaling factor. Our experimental results demonstrate qubit-count reductions of up to 57% for BPP compared with the evaluated slack variable based formulations. These results were obtained using quantum simulations and highlight the potential of efficient constraint encoding for reducing quantum resource requirements.