This study proposes a novel method for simplifying inequality constraints in Higher-Order Binary Optimization (HOBO) formulations. The proposed method addresses challenges associated with Quadratic Unconstrained Binary Optimization (QUBO) formulations, specifically the increased computational complexity and reduced solution accuracy caused by the introduction of slack variables and the resulting growth in auxiliary qubits. By efficiently integrating constraints, the method enhances the computational efficiency and accuracy of both quantum and classical solvers. The effectiveness of the proposed approach is demonstrated through numerical experiments applied to combinatorial optimization problems. The results indicate that this method expands the applicability of quantum algorithms to high-dimensional problems and improves the practicality of classical optimization solvers for optimization problems involving inequality constraints.
This study proposes a novel method for simplifying inequality constraints in Higher-Order Binary Optimization (HOBO) formulations. The proposed method addresses challenges associated with Quadratic Unconstrained Binary Optimization (QUBO) formulations, specifically the increased computational complexity and reduced solution accuracy caused by the introduction of slack variables and the resulting growth in auxiliary qubits. By efficiently integrating constraints, the method enhances the computational efficiency and accuracy of both quantum and classical solvers. The effectiveness of the proposed approach is demonstrated through numerical experiments applied to combinatorial optimization problems. The results indicate that this method expands the applicability of quantum algorithms to high-dimensional problems and improves the practicality of classical optimization solvers for optimization problems involving inequality constraints.
Quantum computing approaches, such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), have emerged as promising candidates for solving combinatorial optimization problems. Since these approaches typically work with Quadratic Unconstrained Binary Optimization (QUBO) problems, constraints, when present, are commonly encoded as penalty terms. Conventional approaches to incorporate inequality constraints into QUBO formulations additionally require the introduction of slack variables, increasing the required number of qubits. The Knapsack and Bin Packing problems are optimization problems with such inequality constraints. We show that the number of slack variables required to formulate the Knapsack problem as a QUBO problem can be reduced using certain properties specific to this problem. Moreover, we present two separate strategies for the Knapsack and Bin Packing problems that avoid using the costly slack variables altogether. Instead, both strategies solve several QUBO problems, with varying penalty constants, such that at least one of them is a good representation of the given optimization problem. Numerical simulations of QAOA, as well as experiments on a D-Wave quantum annealer, show that these slack-less approaches can improve performance compared to the conventional slack variable method (in terms of success probability), even when the latter is allowed to vary penalty constants too.
Quantum annealing is an optimization technique that uses quantum fluctuation effects to search for solutions and is being applied as a metaheuristic method. Quantum annealing solves a problem expressed as quadratic unconstrained binary optimization (QUBO). Many practical problems have complex constraints, and formulating them can lead to third-order or higher expressions. In such cases, higher-order expressions have been converted to QUBO by order reduction. Various order reduction methods have been used, but they have issues, such as the need to add more auxiliary variables and difficulty in obtaining optimal solutions. This paper discusses a method for formulating problems with complex constraints using inequalities. In this approach, each constraint is defined as a linear function and added together to form an inequality. The inequality is then transformed to QUBO by introducing a slack variable. The application to the quantum minimum fill-in algorithm, a fill-in reduction ordering algorithm for sparse matrices, and the maximum satisfiability problem are also presented. The results of solving these problems with a quantum-inspired annealing machine show that higher-quality solutions are obtained with fewer variables than when using higher-order expressions with order reduction.
Abstract Solving combinatorial optimization problems of the kind that can be codified by quadratic unconstrained binary optimization (QUBO) is a promising application of quantum computation. Some problems of this class suitable for practical applications such as the traveling salesman problem (TSP), the bin packing problem (BPP), or the knapsack problem (KP) have inequality constraints that require a particular cost function encoding. The common approach is the use of slack variables to represent the inequality constraints in the cost function. However, the use of slack variables considerably increases the number of qubits and operations required to solve these problems using quantum devices. In this work, we present an alternative method that does not require extra slack variables and consists of using an unbalanced penalization function to represent the inequality constraints in the QUBO. This function is characterized by larger penalization when the inequality constraint is not achieved than when it is. We evaluate our approach on the TSP, BPP, and KP, successfully encoding the optimal solution of the original optimization problem near the ground state cost Hamiltonian. Additionally, we employ D -Wave Advantage and D -Wave hybrid solvers to solve the BPP, surpassing the performance of the slack variables approach by achieving solutions for up to 29 items, whereas the slack variables approach only handles up to 11 items. This new approach can be used to solve combinatorial problems with inequality constraints with a reduced number of resources compared to the slack variables approach using quantum annealing or variational quantum algorithms.
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 Montanez-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.
We propose a new method for solving binary optimization problems under inequality constraints using a quantum annealer. To deal with inequality constraints, we often use slack variables, as in previous approaches. When we use slack variables, we usually conduct a binary expansion, which requires numerous physical qubits. Therefore, the problem of the current quantum annealer is limited to a small scale. In this study, we employ the alternating direction method of multipliers. This approach allows us to deal with various types using constraints in the current quantum annealer without slack variables. To test the performance of our algorithm, we use quadratic knapsack problems (QKPs). We compared the accuracy obtained by our method with a simulated annealer and the optimization and sampling mode of a D-Wave machine. As a result of our experiments, we found that the sampling mode shows the best accuracy. We also found that the computational time of our method is faster than that of the exact solver when we tackle various QKPs defined on dense graphs.