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:2002.00943

Quantum approximate algorithm for NP optimization problems with constraints

Yue Ruan, S. Marsh, Xilin Xue, Xi Li, Zhihao Liu, Jingbo B. Wang

Published Feb 1, 2020• 9 citations
arXivHTMLPDF

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is an algorithmic framework for finding approximate solutions to combinatorial optimization problems, derived from an approximation to the Quantum Adiabatic Algorithm (QAA). In solving combinatorial optimization problems with constraints in the context of QAOA or QAA, one needs to find a way to encode problem constraints into the scheme. In this paper, we formalize different constraint types to linear equalities, linear inequalities, and arbitrary form. Based on this, we propose constraint-encoding schemes well-fitting into the QAOA framework for solving NP combinatorial optimization problems. The implemented algorithms demonstrate the effectiveness and efficiency of the proposed scheme by the testing results of varied instances of some well-known NP optimization problems. We argue that our work leads to a generalized framework for finding, in the context of QAOA, high-quality approximate solutions to combinatorial problems with various types of constraints.

DOI
10.48550/arxiv.2002.00943

Related papers

The Quantum Approximate Algorithm for Solving Traveling Salesman Problem

Yue Ruan, S. Marsh, Xilin Xue +2 more

The Quantum Approximate Optimization Algorithm (QAOA) is an algorithmic framework for finding approximate solutions to combinatorial optimization problems. It consists of interleaved unitary transformations induced by two operators labelled the mixing and problem Hamiltonians. To fit this framework, one needs to transform the original problem into a suitable form and embed it into these two Hamiltonians. In this paper, for the well-known NP-hard Traveling Salesman Problem (TSP), we encode its constraints into the mixing Hamiltonian rather than the conventional approach of adding penalty terms to the problem Hamiltonian. Moreover, we map edges (routes) connecting each pair of cities to qubits, which decreases the search space significantly in comparison to other approaches. As a result, our method can achieve a higher probability for the shortest round-trip route with only half the number of qubits consumed compared to IBM Q’s approach. We argue the formalization approach presented in this paper would lead to a generalized framework for finding, in the context of QAOA, high-quality approximate solutions to NP optimization problems.

Computers, materials & continua/Computers, materials & continua (Print)•Jan 1, 2020•44 citations

The Art of Avoiding Constraints: A Penalty-free Approach to Constrained Combinatorial Optimization with QAOA

Prashanti Priya Angara, Danylo Lykov, Ulrike Stege +2 more

The quantum approximate optimization algorithm (QAOA) is designed to determine optimum and near optimum solutions of quadratic (and higher order) unconstrained binary optimization (QUBO or HUBO) problems, which in turn accurately model unconstrained combinatorial optimization problems. While the solution space of an unconstrained combinatorial optimization problem consists of all possible combinations of the objective function's decision variables, for a constrained combinatorial optimization problem, the solution space consists only of solutions that satisfy the problem constraints. While solving such a QUBO problem optimally results in an optimal solution to the underlying constrained problem, setting the right penalty parameters is crucial. Moreover, finding suitable penalties that ensure near-optimal solutions is also challenging. In this article, we introduce our innovative profit-relaxation framework to solve constrained combinatorial optimization problems. Our effective hybrid approach transforms a selected constrained combinatorial optimization problem into an unconstrained profit problem, such that the solution spaces of the two problems are interrelated with respect to their solution qualities. This allows us to determine optimal and near-optimal solutions for the constrained problem. We use three NP-hard problems -- Minimum Vertex Cover, Maximum Independent Set, and Maximum Clique -- to demonstrate the feasibility and effectiveness of our approach. We conducted a detailed performance evaluation of our profit-relaxation framework on two different platforms: Xanadu PennyLane and Argonne QTensor Quantum Circuit Simulator.

arXiv:2503.10077•IEEE Transactions on Quantum Engineering•Jan 1, 2026•0 citations

Compressed Space Quantum Approximate Optimization Algorithm for Constrained Combinatorial Optimization

Tatsuhiko Shirai, Nozomu Togawa

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.

arXiv:2410.05703•IEEE Transactions on Quantum Engineering•Jan 1, 2025•5 citations

LE-QAOA: A Complexity Theory Enhanced Tool for Quantum Optimization

Carla Piazza, Riccardo Romanello, Beniamino Todone

Combinatorial optimization problems are at the heart of modern computational challenges; however, their NP-hard nature often makes exact classical solutions intractable. The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising candidate for NISQ-era optimization. However, a significant performance gap exists between unconstrained and constrained formulations. The former refers to problems in which each solution is valid, either bad or good. The latter, to tasks in which there exist illegal solutions. While native constrained QAOA mixers offer high solution quality, they often suffer from prohibitive runtimes. In this paper, we introduce LE-QAOA (L-reduction Enhanced QAOA), a framework that leverages classical complexity theory to bridge this gap. By utilizing L-reductions to map diverse problems into a canonical Max2SAT form, we are able to solve constrained problems using efficient unconstrained subroutines followed by a classical repairing tournament. Our results on the Maximum Independent Set (MIS) problem show that LE-QAOA achieves solution quality that matches and frequently exceeds that of native constrained solvers, while requiring as little as 10% of the execution time. This approach effectively combines the scalability of unconstrained quantum evolution with the precision of constrained optimization. Moreover, this approach makes it possible to solve combinatorial optimization by reduction to a single chosen problem whose QAOA encoding is optimized, rather than explicitly building specific Hamiltonians.

IEEE International Conference on Quantum Software (QSW)•Jul 1, 2026•0 citations

SCOOP: A Quantum-Computing Framework for Constrained Combinatorial Optimization

Prashanti Priya Angara, Emily Martins, Ulrike Stege +1 more

While the ultimate goal of solving computationally intractable problems is to find a provably optimal solutions, practical constraints of real-world scenarios often necessitate focusing on efficiently obtaining high-quality, near-optimal solutions. The Quantum Approximate Optimization Algorithm (QAOA) is a state-of-the-art hybrid quantum-classical approach for tackling these challenging problems that are encoded using quadratic and higher-order unconstrained binary optimization problems (QUBO and HUBO). We present SCOOP, a novel QAOAbased framework for solving constrained optimization problems. SCOOP transforms a constrained problem into an unconstrained counterpart, forming SCOOP problem twins. The QAOA quantum algorithm operates on the unconstrained twin to identify potential optimal and near-optimal solutions. Effective classical post-processing reduces the solution set to the constrained problem space. Our SCOOP approach is solution-enhanced, objective-function-compatible, and scalable. We demonstrate the framework on three NP-hard problems, Minimum Dominating Set, Minimum Maximal Matching, and Minimum Set Cover appearing in practical application domains such as resource allocation, communication networks, and machine learning. We validate SCOOP's feasibility and effectiveness on Xanadu PennyLane simulators.

arXiv:2504.10897•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer

Zhu, Linghua, Ho Lun Tang, George S. Barron +4 more

The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum-classical algorithm that solves combinatorial optimization problems. While there is evidence suggesting that the fixed form of the standard QAOA ansatz is not optimal, there is no systematic approach for finding better ansätze. We address this problem by developing an iterative version of QAOA that is problem-tailored, and which can also be adapted to specific hardware constraints. We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the standard QAOA, while simultaneously reducing the required number of CNOT gates and optimization parameters. We provide evidence that this speedup is connected to the concept of shortcuts to adiabaticity.

arXiv:2005.10258•May 20, 2020•25 citations
The Quantum Approximate Optimization Algorithm (QAOA) is an algorithmic framework for finding approximate solutions to combinatorial optimization problems, derived from an approximation to the Quantum Adiabatic Algorithm (QAA). In solving combinatorial optimization problems with constraints in the context of QAOA or QAA, one needs to find a way to encode problem constraints into the scheme. In this paper, we formalize different constraint types to linear equalities, linear inequalities, and arbitrary form. Based on this, we propose constraint-encoding schemes well-fitting into the QAOA framework for solving NP combinatorial optimization problems. The implemented algorithms demonstrate the effectiveness and efficiency of the proposed scheme by the testing results of varied instances of some well-known NP optimization problems. We argue that our work leads to a generalized framework for finding, in the context of QAOA, high-quality approximate solutions to combinatorial problems with various types of constraints.
The Quantum Approximate Optimization Algorithm (QAOA) is an algorithmic framework for finding approximate solutions to combinatorial optimization problems. It consists of interleaved unitary transformations induced by two operators labelled the mixing and problem Hamiltonians. To fit this framework, one needs to transform the original problem into a suitable form and embed it into these two Hamiltonians. In this paper, for the well-known NP-hard Traveling Salesman Problem (TSP), we encode its constraints into the mixing Hamiltonian rather than the conventional approach of adding penalty terms to the problem Hamiltonian. Moreover, we map edges (routes) connecting each pair of cities to qubits, which decreases the search space significantly in comparison to other approaches. As a result, our method can achieve a higher probability for the shortest round-trip route with only half the number of qubits consumed compared to IBM Q’s approach. We argue the formalization approach presented in this paper would lead to a generalized framework for finding, in the context of QAOA, high-quality approximate solutions to NP optimization problems.
The quantum approximate optimization algorithm (QAOA) is designed to determine optimum and near optimum solutions of quadratic (and higher order) unconstrained binary optimization (QUBO or HUBO) problems, which in turn accurately model unconstrained combinatorial optimization problems. While the solution space of an unconstrained combinatorial optimization problem consists of all possible combinations of the objective function's decision variables, for a constrained combinatorial optimization problem, the solution space consists only of solutions that satisfy the problem constraints. While solving such a QUBO problem optimally results in an optimal solution to the underlying constrained problem, setting the right penalty parameters is crucial. Moreover, finding suitable penalties that ensure near-optimal solutions is also challenging. In this article, we introduce our innovative profit-relaxation framework to solve constrained combinatorial optimization problems. Our effective hybrid approach transforms a selected constrained combinatorial optimization problem into an unconstrained profit problem, such that the solution spaces of the two problems are interrelated with respect to their solution qualities. This allows us to determine optimal and near-optimal solutions for the constrained problem. We use three NP-hard problems -- Minimum Vertex Cover, Maximum Independent Set, and Maximum Clique -- to demonstrate the feasibility and effectiveness of our approach. We conducted a detailed performance evaluation of our profit-relaxation framework on two different platforms: Xanadu PennyLane and Argonne QTensor Quantum Circuit Simulator.
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.
Combinatorial optimization problems are at the heart of modern computational challenges; however, their NP-hard nature often makes exact classical solutions intractable. The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising candidate for NISQ-era optimization. However, a significant performance gap exists between unconstrained and constrained formulations. The former refers to problems in which each solution is valid, either bad or good. The latter, to tasks in which there exist illegal solutions. While native constrained QAOA mixers offer high solution quality, they often suffer from prohibitive runtimes. In this paper, we introduce LE-QAOA (L-reduction Enhanced QAOA), a framework that leverages classical complexity theory to bridge this gap. By utilizing L-reductions to map diverse problems into a canonical Max2SAT form, we are able to solve constrained problems using efficient unconstrained subroutines followed by a classical repairing tournament. Our results on the Maximum Independent Set (MIS) problem show that LE-QAOA achieves solution quality that matches and frequently exceeds that of native constrained solvers, while requiring as little as 10% of the execution time. This approach effectively combines the scalability of unconstrained quantum evolution with the precision of constrained optimization. Moreover, this approach makes it possible to solve combinatorial optimization by reduction to a single chosen problem whose QAOA encoding is optimized, rather than explicitly building specific Hamiltonians.
While the ultimate goal of solving computationally intractable problems is to find a provably optimal solutions, practical constraints of real-world scenarios often necessitate focusing on efficiently obtaining high-quality, near-optimal solutions. The Quantum Approximate Optimization Algorithm (QAOA) is a state-of-the-art hybrid quantum-classical approach for tackling these challenging problems that are encoded using quadratic and higher-order unconstrained binary optimization problems (QUBO and HUBO). We present SCOOP, a novel QAOAbased framework for solving constrained optimization problems. SCOOP transforms a constrained problem into an unconstrained counterpart, forming SCOOP problem twins. The QAOA quantum algorithm operates on the unconstrained twin to identify potential optimal and near-optimal solutions. Effective classical post-processing reduces the solution set to the constrained problem space. Our SCOOP approach is solution-enhanced, objective-function-compatible, and scalable. We demonstrate the framework on three NP-hard problems, Minimum Dominating Set, Minimum Maximal Matching, and Minimum Set Cover appearing in practical application domains such as resource allocation, communication networks, and machine learning. We validate SCOOP's feasibility and effectiveness on Xanadu PennyLane simulators.
The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum-classical algorithm that solves combinatorial optimization problems. While there is evidence suggesting that the fixed form of the standard QAOA ansatz is not optimal, there is no systematic approach for finding better ansätze. We address this problem by developing an iterative version of QAOA that is problem-tailored, and which can also be adapted to specific hardware constraints. We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the standard QAOA, while simultaneously reducing the required number of CNOT gates and optimization parameters. We provide evidence that this speedup is connected to the concept of shortcuts to adiabaticity.