Constrained combinatorial optimization problems, which are ubiquitous in industry, can be solved by quantum algorithms such as quantum annealing (QA) and the quantum approximate optimization algorithm (QAOA). In these quantum algorithms, constraints are typically implemented with quadratic penalty functions. This penalty method can introduce large energy scales and make interaction graphs much more dense. These effects can result in worse performance of quantum optimization, particularly on near-term devices that have sparse hardware graphs and other physical limitations. In this work, we consider linear Ising penalty functions, which are applied with local fields in the Ising model, as an alternative method for implementing constraints that makes more efficient use of physical resources. We study the behavior of the penalty method in the context of quantum optimization for customer data science problems. Our theoretical analysis and numerical simulations of QA and the QAOA indicate that this penalty method can lead to better performance in quantum optimization than the quadratic method. However, the linear Ising penalty method is not suitable for all problems as it cannot always exactly implement the desired constraint. In cases where the linear method is not successful in implementing all constraints, we propose that schemes involving both quadratic and linear Ising penalties can be effective. Published by the American Physical Society 2024
Constrained combinatorial optimization problems, which are ubiquitous in industry, can be solved by quantum algorithms such as quantum annealing (QA) and the quantum approximate optimization algorithm (QAOA). In these quantum algorithms, constraints are typically implemented with quadratic penalty functions. This penalty method can introduce large energy scales and make interaction graphs much more dense. These effects can result in worse performance of quantum optimization, particularly on near-term devices that have sparse hardware graphs and other physical limitations. In this work, we consider linear Ising penalty functions, which are applied with local fields in the Ising model, as an alternative method for implementing constraints that makes more efficient use of physical resources. We study the behavior of the penalty method in the context of quantum optimization for customer data science problems. Our theoretical analysis and numerical simulations of QA and the QAOA indicate that this penalty method can lead to better performance in quantum optimization than the quadratic method. However, the linear Ising penalty method is not suitable for all problems as it cannot always exactly implement the desired constraint. In cases where the linear method is not successful in implementing all constraints, we propose that schemes involving both quadratic and linear Ising penalties can be effective. Published by the American Physical Society 2024
Abstract The standard approach to encoding constraints in quantum optimization is the quadratic penalty method. Quadratic penalties introduce additional couplings and energy scales, which can be detrimental to the performance of a quantum optimizer. In quantum annealing experiments performed on a D-Wave Advantage, we explore an alternative penalty method that only involves linear Ising terms and apply it to a customer data science problem. Our findings support our hypothesis that the linear Ising penalty method should improve the performance of quantum optimization compared to using the quadratic penalty method due to its more efficient use of physical resources. Although the linear Ising penalty method is not guaranteed to exactly implement the desired constraint in all cases, it is able to do so for the majority of problem instances we consider. For problems with many constraints, where making all penalties linear is unlikely to be feasible, we investigate strategies for combining linear Ising penalties with quadratic penalties to satisfy constraints for which the linear method is not well-suited. We find that this strategy is most effective when the penalties that contribute most to limiting the dynamic range are removed.
One of the potential use cases of a quantum computer is to solve combinatorial optimisation problems more efficiently than is possible with the most advanced classical computers. Combinatorial optimisation problems that appear in industry often involve a large number of constraints. This thesis investigates algorithmic techniques that improve the performance of quantum optimisation algorithms in solving problems with constraints. We test these techniques on customer data science problems. We study an alternative penalty method for encoding constraints in Ising Hamiltonians, which can be applied to various quantum algorithms. This method only introduces linear terms to the Ising Hamiltonian, allowing for more efficient use of hardware resources than the standard quadratic penalty method. These efficiency improvements are particularly beneficial for near-term devices with a limited number of qubits that are sparsely connected. We analyse the impact of using this alternative encoding method on the performance of the quantum approximate optimisation algorithm and quantum annealing applied to example problems in customer data science. Our results are based on numerical simulations and experiments on quantum hardware. We introduce a new variant of the quantum approximate optimisation algorithm that improves its ability to solve problems with constraints. In this variant of the algorithm, the strengths of penalty functions are associated with additional variational parameters, allowing them to take different values in each layer of the quantum circuit. We perform numerical simulations of multiple variants of the quantum approximate optimisation algorithm and compare their performance.
Ising machines are expected to be dedicated computers that are capable of efficiently searching for good solutions to combinatorial optimization problems. When solving combinatorial optimization problems with an Ising machine, the objective function and constraints of the combinatorial optimization problems are expressed using the Ising model. Then, the low-energy states of the Ising model are searched by the internal algorithms of Ising machines. Typical internal algorithms are Simulated Annealing (SA) and Quantum Annealing (QA). Both algorithms exhibit stochastic behavior, so the final solution may contain errors. Therefore, it is an essential issue in the field of Ising machines to reduce errors as much as possible. A previous study proposed an error reduction method for QA machines, namely the Quantum Annealing Correction (QAC) model. This method reduces error by introducing penalty interaction and performing a specific decoding method. Building on these valuable insights, we proposed an alternative error reduction method, the stacked model. To verify the effectiveness, we examined on the relationship between the penalty interaction and the success probability of the QAC model and the stacked model on SA. The obtained results differ from the facts observed in QA. In summary, a decoding method different from the one considered effective in QA was found to be effective in SA. This result suggests that when considering an appropriate error reduction method, it is necessary to consider the internal algorithm of the Ising machine.
Constrained combinatorial optimization with strict linear constraints underpins applications in drug discovery, power grids, logistics, and finance, yet remains computationally demanding for classical algorithms, especially at large scales. The Quantum Approximate Optimization Algorithm (QAOA) offers a promising quantum framework, but conventional penalty-based formulations distort optimization landscapes and demand deep circuits, undermining scalability on near-term hardware. In this work, we introduce Hamming Weight Operators, a new class of constraint-aware operators that confine quantum evolution strictly within the feasible subspace. Building on this idea, we develop Adaptive Hamming Weight Operator QAOA, which dynamically selects the most effective operators to construct shallow, problem-tailored circuits. We validate our approach on benchmark tasks from both finance and high-energy physics, specifically portfolio optimization and two-jet clustering with energy balance. Across these problems, our method inherently satisfies all constraints by construction, converges faster, and achieves higher Approximation Ratios than penalty-based QAOA, while requiring roughly half as many gates. By embedding constraint-aware operators into an adaptive variational framework, our approach establishes a scalable and hardware-efficient pathway for solving practical constrained optimization problems on near-term quantum devices.
One of the most prominent application areas for quantum computers is solving hard constraint satisfaction and optimization problems. However, detailed analyses of the complexity of standard quantum algorithms have suggested that outperforming classical methods for these problems would require extremely large and powerful quantum computers. The quantum approximate optimization algorithm (QAOA) is designed for near-term quantum computers, yet previous work has shown strong limitations on the ability of QAOA to outperform classical algorithms for optimization problems. Here we instead apply QAOA to hard constraint satisfaction problems, where both classical and quantum algorithms are expected to require exponential time. We analytically characterize the average success probability of QAOA on a constraint satisfaction problem commonly studied using statistical physics methods: random k -SAT at the threshold for satisfiability, as the number of variables n goes to infinity. We complement these theoretical results with numerical experiments on the performance of QAOA for small n , which match the limiting theoretical bounds closely. We then compare QAOA with leading classical solvers. For random 8-SAT, we find that for more than 14 quantum circuit layers, QAOA achieves more efficient scaling than the highest-performance classical solver we tested, WalkSATlm. Our results suggest that near-term quantum algorithms for solving constraint satisfaction problems may outperform their classical counterparts. Published by the American Physical Society 2024
Combinatorial optimization is a promising area for achieving quantum speedup. The quantum approximate optimization algorithm (QAOA) is designed to search for low-energy states of the Ising model, which correspond to near-optimal solutions of combinatorial optimization problems (COPs). However, effectively dealing with constraints of COPs remains a significant challenge. Existing methods, such as tailoring mixing operators, are typically limited to specific constraint types, like one-hot constraints. To address these limitations, we introduce a method for engineering a compressed space that represents the feasible solution space with fewer qubits than the original. Our approach includes a scalable technique for determining the unitary transformation between the compressed and original spaces on gate-based quantum computers. We then propose compressed space QAOA, which seeks near-optimal solutions within this reduced space, while utilizing the Ising model formulated in the original Hilbert space. Experimental results on a quantum simulator demonstrate the effectiveness of our method in solving various constrained COPs.