Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2403.05653 · ACM Transactions on Quantum Computing

Q-CHOP: Quantum constrained Hamiltonian optimization

Michael A. Perlin, Ruslan Shaydulin, Benjamin Hall, Pierre Minssen, Changhao Li, Kabir Dubey, Richard Rines, Eric R. Anschuetz, Marco Pistoia, Pranav Gokhale

Published Dec 2, 2025• 0 citations
arXivHTMLPDF

Abstract

Combinatorial optimization problems that arise in science and industry typically have constraints. Yet the presence of constraints makes them challenging to tackle using both classical and quantum optimization algorithms. We propose a new quantum algorithm for constrained optimization, which we call quantum constrained Hamiltonian optimization (Q-CHOP). Our algorithm leverages the observation that for many problems, while the best solution is difficult to find, the worst feasible (constraint-satisfying) solution is known. The basic idea of Q-CHOP is to enforce a Hamiltonian constraint at all times, thereby restricting evolution to the subspace of feasible states, and slowly “rotate” an objective Hamiltonian to trace an adiabatic path from the worst feasible state to the best feasible state. Q-CHOP thereby assigns qualitatively distinct roles to the constraint and objective functions of a constrained optimization problem. We additionally propose a version of Q-CHOP that can start in any feasible state. Finally, we benchmark Q-CHOP against the commonly-used adiabatic algorithm of quantum annealing with an objective function that penalizes constraint violation, and find that Q-CHOP consistently performs significantly better on a wide range of problems, including textbook graph problems, knapsack problems, combinatorial auctions, and a real-world financial use case of bond exchange-traded fund basket optimization.

DOI
10.1145/3778864

Related papers

Quantum Optimization Algorithms for Industrial Problems

Maximilian Nikolaus Hess

The semiconductor supply chain gives rise to many complex, large and heavily constrained combinatorial optimization problems. We derive simpler problems from these complex formulations and analyze quantum algorithms for their solution. We study two main regimes: variational algorithms derived from the Quantum Approximate Optimization Algorithm (QAOA) and quantum search algorithms based on Grover’s search algorithm and Amplitude Amplification. In the first case, the main challenge lies in integrating problem constraints into the QAOA framework, which was originally devised for unconstrained problems such as MaxCut. The canonical method of adding penalty terms to the objective leads to an undesirable inflation of the energy spectrum. Instead, we examine alternative problem encodings as well as constraint-preserving mixing operators, which are designed to limit the quantum algorithm to the subspace of feasible states. We make explicit suggestions for a wide selection of problems. In the second case, we operate under the premise that any quantum search protocol for combinatorial optimization must use tailored initial states– otherwise the square root speedup of quantum search is not enough to offset the exponential size of the search space in a combinatorial optimization problem. Consequently, we examine state preparation routines for a wide range or problems. The main devices lie in preparing superpositions of only feasible states and superpositions which are centered around a reference solution. We present a benchmarking technique, in an exact and an approximate version, which allows us to generate performance metrics for our algorithms based on quantum search. We use the benchmarking tools to carry out numerical studies for a selection of problems. We conclude that our variational methods tailored to constrained problems while technically sound– lead to deep quantum circuits which are not suitable for the NISQ machines which QAOA was originally developed for. Our conclusion for optimization algorithms based on quantum search is more optimisitic. Their compatability with classical optimization principles, such as neighborhood search, gives rise to promising further research directions. Advanced benchmarking techniques allow us to test these algorithms independently of quantum hardware developments.

•Jan 1, 2026•0 citations

Constrained Quantum Optimization at Utility Scale: Application to the Knapsack Problem

Naeimeh Mohseni, Julien-Pierre Houle, Ibrahim Shehzad +3 more

Constrained combinatorial optimization problems are challenging for quantum computing, particularly at utility-relevant scales and on near-term hardware. At the same time, these problems are of practical significance in industry; for example, the Unit Commitment (UC) problem in energy systems involves complex operational constraints. To address this challenge, we apply copula-QAOA (cop-QAOA), a hardware-efficient approach for constrained optimization to a single-period UC that can be reduced to a one-dimensional knapsack. Cop-QAOA biases the quantum state toward feasible solutions using constant-depth mixers and appropriately biased initial states. We implement our benchmark on problem instances that are confirmed to be hard for classical solvers such as Gurobi. Our results show that cop-QAOA often finds solutions better than a lazy greedy baseline and very close to, and in some instances surpasses, those obtained by Gurobi, with only a few QAOA rounds. This work presents the largest successful demonstration of the knapsack problem on IBM Quantum hardware using up to 150 qubits, and more generally, the largest demonstration of constrained combinatorial optimization where constraints are enforced via shallow mixers.

quant-pharXiv:2603.00260•Mar 3, 2026•0 citations

Quantum Annealing-Based Combinatorial Optimization Algorithm

Jincheng Zhang

This paper investigates the application of quantum annealing for solving complex combinatorial optimization problems. The core claim is that quantum annealing leverages its global search capabilities to efficiently address such problems. The proposed mechanism involves formulating the combinatorial optimization problem as a quantum annealing problem and utilizing the simulated annealing process within quantum annealing to conduct a search for the optimal solution. This research explores the potential of quantum annealing in practical applications, acknowledging that its application in combinatorial optimization is still in its exploratory phase. The algorithm is designed to minimize the energy of a system described by a Hamiltonian, which evolves over time according to the time-dependent Schrödinger equation. The core of the algorithm lies in mapping the problem's constraints and objective function into this Hamiltonian. The search process is governed by quantum fluctuations, represented by the operator $\hat{H}$, which encourages transitions to lower energy states, effectively navigating the solution space. The effectiveness of the algorithm is evaluated based on the quality of the solution found and the computational resources required. This work provides a foundational exploration of quantum annealing's potential within the field of combinatorial optimization.

•Sep 3, 2026•0 citations

Constraint-Aware Quantum Optimization: Theoretical Foundations for Preserving Problem Structure in QUBO Formulations

Jeffrey Quinn Cordova

This paper establishes a theoretical framework for constraint-preserving quantum optimization that maintains problem structure throughout quantum algorithm execution, addressing a fundamental challenge in translating real-world optimization problems to quantum hardware. We develop mathematical formulations that embed hard constraints directly into quantum circuit design rather than relying solely on penalty methods, proving that certain constraint classes can be exactly enforced through quantum state space restriction. Our theory characterizes the complexity of constraint preservation across different problem classes including facility location, network optimization, and resource allocation, deriving conditions under which quantum algorithms can explore only feasible solution spaces. We introduce automated repair mechanisms with theoretical guarantees on convergence to valid solutions and establish bounds on the additional quantum resources required for constraint maintenance. The framework provides rigorous analysis of trade-offs between constraint flexibility, quantum circuit depth, and solution quality, identifying problem structures amenable to efficient constraint-preserving quantum formulations. We extend the theory to socioeconomic weighting and multi-objective scenarios, proving that preference structures can be incorporated without compromising feasibility guarantees. This theoretical foundation advances practical quantum optimization by ensuring quantum algorithms produce implementable solutions while maintaining provable performance characteristics across diverse constrained optimization domains including logistics, energy systems, and infrastructure planning.

•Nov 10, 2025•0 citations

Optimization Algorithms for Combinatorial Problems: A Comparative Study of Quantum Annealing and Classical Methods

Suresh A. J.

Optimization algorithms for combinatorial problems play a critical role in a wide range of applications, from logistics and scheduling to cryptography and artificial intelligence. Traditional classical methods, such as simulated annealing, genetic algorithms, and branch-and-bound techniques, have been widely employed to solve these problems, but they often face limitations in terms of computational efficiency and scalability as problem complexity grows. In recent years, quantum computing has emerged as a promising alternative, with quantum annealing offering a novel approach to solving combinatorial optimization problems. This study provides a comparative analysis of quantum annealing and classical optimization methods, highlighting their respective strengths and limitations. We explore how quantum annealing, through leveraging quantum tunnelling and superposition, has the potential to outperform classical algorithms in specific problem domains and Noisy Mean Field Annealing (NMFA) is used to comparisons of all algorithms. Benchmarking various combinatorial problems, such as the Traveling Salesman Problem (TSP), Max-Cut, Knapsack, and Quadratic Assignment Problem (QAP), this paper discusses performance metrics, computational time, and scalability. The findings suggest that while classical methods remain robust and practical for many real-world problems, quantum annealing holds significant promise, especially as quantum hardware continues to mature. However, there remain challenges in terms of noise, coherence, and problem mapping, which currently limit the full realization of quantum annealing's potential. This study offers insights into the future directions of optimization techniques and the evolving role of quantum computing in solving complex combinatorial problems.

International Journal of Intelligent Systems and Applications in Engineering•Mar 30, 2023•0 citations

Some Investigations for Solving Constrained Optimization Problems using Adiabatic Quantum Computation

Ashish Mani, C. Patvardhan

Adiabatic Quantum Computation has emerged as a new approach for designing quantum algorithms, which is equivalent to the circuit model but appears to be more robust and suffers from less number of bottlenecks than it. Some investigations have been undertaken in this paper for solving constrained optimization problems using Adiabatic Quantum Computation, as there is no reported approach yet for solving such problems using Quantum Algorithms.

International Conference on Information Technology: New Generations•Apr 1, 2011•0 citations
Combinatorial optimization problems that arise in science and industry typically have constraints. Yet the presence of constraints makes them challenging to tackle using both classical and quantum optimization algorithms. We propose a new quantum algorithm for constrained optimization, which we call quantum constrained Hamiltonian optimization (Q-CHOP). Our algorithm leverages the observation that for many problems, while the best solution is difficult to find, the worst feasible (constraint-satisfying) solution is known. The basic idea of Q-CHOP is to enforce a Hamiltonian constraint at all times, thereby restricting evolution to the subspace of feasible states, and slowly “rotate” an objective Hamiltonian to trace an adiabatic path from the worst feasible state to the best feasible state. Q-CHOP thereby assigns qualitatively distinct roles to the constraint and objective functions of a constrained optimization problem. We additionally propose a version of Q-CHOP that can start in any feasible state. Finally, we benchmark Q-CHOP against the commonly-used adiabatic algorithm of quantum annealing with an objective function that penalizes constraint violation, and find that Q-CHOP consistently performs significantly better on a wide range of problems, including textbook graph problems, knapsack problems, combinatorial auctions, and a real-world financial use case of bond exchange-traded fund basket optimization.
The semiconductor supply chain gives rise to many complex, large and heavily constrained combinatorial optimization problems. We derive simpler problems from these complex formulations and analyze quantum algorithms for their solution. We study two main regimes: variational algorithms derived from the Quantum Approximate Optimization Algorithm (QAOA) and quantum search algorithms based on Grover’s search algorithm and Amplitude Amplification. In the first case, the main challenge lies in integrating problem constraints into the QAOA framework, which was originally devised for unconstrained problems such as MaxCut. The canonical method of adding penalty terms to the objective leads to an undesirable inflation of the energy spectrum. Instead, we examine alternative problem encodings as well as constraint-preserving mixing operators, which are designed to limit the quantum algorithm to the subspace of feasible states. We make explicit suggestions for a wide selection of problems. In the second case, we operate under the premise that any quantum search protocol for combinatorial optimization must use tailored initial states– otherwise the square root speedup of quantum search is not enough to offset the exponential size of the search space in a combinatorial optimization problem. Consequently, we examine state preparation routines for a wide range or problems. The main devices lie in preparing superpositions of only feasible states and superpositions which are centered around a reference solution. We present a benchmarking technique, in an exact and an approximate version, which allows us to generate performance metrics for our algorithms based on quantum search. We use the benchmarking tools to carry out numerical studies for a selection of problems. We conclude that our variational methods tailored to constrained problems while technically sound– lead to deep quantum circuits which are not suitable for the NISQ machines which QAOA was originally developed for. Our conclusion for optimization algorithms based on quantum search is more optimisitic. Their compatability with classical optimization principles, such as neighborhood search, gives rise to promising further research directions. Advanced benchmarking techniques allow us to test these algorithms independently of quantum hardware developments.
Constrained combinatorial optimization problems are challenging for quantum computing, particularly at utility-relevant scales and on near-term hardware. At the same time, these problems are of practical significance in industry; for example, the Unit Commitment (UC) problem in energy systems involves complex operational constraints. To address this challenge, we apply copula-QAOA (cop-QAOA), a hardware-efficient approach for constrained optimization to a single-period UC that can be reduced to a one-dimensional knapsack. Cop-QAOA biases the quantum state toward feasible solutions using constant-depth mixers and appropriately biased initial states. We implement our benchmark on problem instances that are confirmed to be hard for classical solvers such as Gurobi. Our results show that cop-QAOA often finds solutions better than a lazy greedy baseline and very close to, and in some instances surpasses, those obtained by Gurobi, with only a few QAOA rounds. This work presents the largest successful demonstration of the knapsack problem on IBM Quantum hardware using up to 150 qubits, and more generally, the largest demonstration of constrained combinatorial optimization where constraints are enforced via shallow mixers.
This paper investigates the application of quantum annealing for solving complex combinatorial optimization problems. The core claim is that quantum annealing leverages its global search capabilities to efficiently address such problems. The proposed mechanism involves formulating the combinatorial optimization problem as a quantum annealing problem and utilizing the simulated annealing process within quantum annealing to conduct a search for the optimal solution. This research explores the potential of quantum annealing in practical applications, acknowledging that its application in combinatorial optimization is still in its exploratory phase. The algorithm is designed to minimize the energy of a system described by a Hamiltonian, which evolves over time according to the time-dependent Schrödinger equation. The core of the algorithm lies in mapping the problem's constraints and objective function into this Hamiltonian. The search process is governed by quantum fluctuations, represented by the operator H^\hat{H}H^, which encourages transitions to lower energy states, effectively navigating the solution space. The effectiveness of the algorithm is evaluated based on the quality of the solution found and the computational resources required. This work provides a foundational exploration of quantum annealing's potential within the field of combinatorial optimization.
This paper establishes a theoretical framework for constraint-preserving quantum optimization that maintains problem structure throughout quantum algorithm execution, addressing a fundamental challenge in translating real-world optimization problems to quantum hardware. We develop mathematical formulations that embed hard constraints directly into quantum circuit design rather than relying solely on penalty methods, proving that certain constraint classes can be exactly enforced through quantum state space restriction. Our theory characterizes the complexity of constraint preservation across different problem classes including facility location, network optimization, and resource allocation, deriving conditions under which quantum algorithms can explore only feasible solution spaces. We introduce automated repair mechanisms with theoretical guarantees on convergence to valid solutions and establish bounds on the additional quantum resources required for constraint maintenance. The framework provides rigorous analysis of trade-offs between constraint flexibility, quantum circuit depth, and solution quality, identifying problem structures amenable to efficient constraint-preserving quantum formulations. We extend the theory to socioeconomic weighting and multi-objective scenarios, proving that preference structures can be incorporated without compromising feasibility guarantees. This theoretical foundation advances practical quantum optimization by ensuring quantum algorithms produce implementable solutions while maintaining provable performance characteristics across diverse constrained optimization domains including logistics, energy systems, and infrastructure planning.
Optimization algorithms for combinatorial problems play a critical role in a wide range of applications, from logistics and scheduling to cryptography and artificial intelligence. Traditional classical methods, such as simulated annealing, genetic algorithms, and branch-and-bound techniques, have been widely employed to solve these problems, but they often face limitations in terms of computational efficiency and scalability as problem complexity grows. In recent years, quantum computing has emerged as a promising alternative, with quantum annealing offering a novel approach to solving combinatorial optimization problems. This study provides a comparative analysis of quantum annealing and classical optimization methods, highlighting their respective strengths and limitations. We explore how quantum annealing, through leveraging quantum tunnelling and superposition, has the potential to outperform classical algorithms in specific problem domains and Noisy Mean Field Annealing (NMFA) is used to comparisons of all algorithms. Benchmarking various combinatorial problems, such as the Traveling Salesman Problem (TSP), Max-Cut, Knapsack, and Quadratic Assignment Problem (QAP), this paper discusses performance metrics, computational time, and scalability. The findings suggest that while classical methods remain robust and practical for many real-world problems, quantum annealing holds significant promise, especially as quantum hardware continues to mature. However, there remain challenges in terms of noise, coherence, and problem mapping, which currently limit the full realization of quantum annealing's potential. This study offers insights into the future directions of optimization techniques and the evolving role of quantum computing in solving complex combinatorial problems.