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

Multi-sequence alignment using the Quantum Approximate Optimization Algorithm

Sebastian Yde Madsen, Frederik K. Marqversen, S. E. Rasmussen, Nikolaj Thomas Zinner

Published Aug 23, 2023• 4 citations
arXivHTMLPDF

Abstract

The task of Multiple Sequence Alignment (MSA) is a constrained combinatorial optimization problem that is generally considered a complex computational problem. In this paper, we first present a binary encoding of MSA and devise a corresponding soft-constrained cost-function that enables a Hamiltonian formulation and implementation of the MSA problem with the variational Quantum Approximate Optimization Algorithm (QAOA). Through theoretical analysis, a bound on the ratio of the number of feasible states to the size of the Hilbert space is determined. Furthermore, we consider a small instance of our QAOA-MSA algorithm in both a quantum simulator and its performance on an actual quantum computer. While the ideal solution to the instance of MSA investigated is shown to be the most probable state sampled for a shallow p<5 quantum circuit in the simulation, the level of noise in current devices is still a formidable challenge for the kind of MSA-QAOA algorithm developed here. In turn, we are not able to distinguish the feasible solutions from other states in the quantum hardware output data at this point. This indicates a need for further investigation into both the strategy utilized for compiling the quantum circuit, but also the possibility of devising a more compact ansatz, as one might achieve through constraint-preserving mixers for QAOA.

DOI
10.48550/arxiv.2308.12103

Related papers

Toward Quantum Combinatorial Optimization

Yunpyo Hong, Jaejoon Gill, Daeyeun Kim +3 more

The Quantum Approximate Optimization Algorithm (QAOA) has emerged as one of the most prominent hybrid quantum–classical algorithms for combinatorial optimization on noisy intermediate-scale quantum (NISQ) hardware. QAOA maps real-world problems into Ising or quadratic unconstrained binary optimization (QUBO) forms and alternates cost and mixer operators in a shallow parameterized circuit whose angles are tuned by a classical optimizer. This article introduces QAOA from fundamentals to practice, emphasizing why it aligns with industrial optimization through binary decision modeling and the presence of severe scaling challenges in classical optimization. We review research trends that improve expressivity and trainability, including ansatz engineering, parameter initialization, and hybrid training strategies, drawing parallels to developments in artificial intelligence. After that, we survey representative applications in emerging domains such as drug discovery, materials design, semiconductor design, logistics, and finance highlighting practical encodings and constraint-preserving formulations that keep quantum evolution within feasible subspaces beyond penalty-based methods. Finally, we present QAOA as a rapidly maturing framework with credible pathways toward near-term utility in real industrial workflows.

IEEE Nanotechnology Magazine•Jan 1, 2026•0 citations

Quantum algorithms for combinatorial optimization

Vanessa Minouche Dehn

Combinatorial Optimization problems play an important role in various domains such as logis- tics, life science or the financial sector. As their complexity in general grows exponentially with their problem size, finding the optimal solution classically becomes infeasible very fast. This raises the central question of whether quantum computers are in principle suitable for solving combinatorial optimization problems better and faster than classical computers. In order to find answers to that question, one needs to study quantum algorithms designed for those problems under ideal conditions (i.e., simulations, which are however limited due to exponential scaling) to investigate their potential, but one also needs real quantum hardware to test its viability and evaluate whether practical advantages are reasonable. In this regard, we consider variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) consisting of a problem and a mixer Hamiltonian with freely selectable parameters, originally proposed as variational hybrid ansatz with classical optimization. This algorithm structure of- fers flexible and relatively shallow circuits, which makes it suitable for current NISQ hardware. However, optimizing the variational circuit parameters can be an NP-hard problem at worst. In this thesis, we study different versions of QAOA, especially with a focus on limitations, perfor- mance and potential advantages opposite classical methods. The first part of the thesis concerns the investigation of various aspects regarding the imple- mentation of the variational QAOA protocol such as: the incorporation of a problem constraint either by adding a suitable penalty term of by choosing a suitable mixer (that restricts the search space), the scaling of the problem Hamiltonian in comparison to the mixer Hamiltonian, the choice of the initial values for the classical optimization of the circuit parameters, and finally the choice of the function to be minimized (i.e., CVaR vs. expectation value). We apply this proto- col to both the portfolio optimization and the feature selection and evaluate the performance. In order to improve QAOA, we consider the warm-start QAOA for different problem instances and analyze its improved performance with regard to involved quantum effects. For this purpose, we propose a classical pre-processing method and demonstrate that the warm-start results can be reproduced or even exceeded by this method. The second part addresses the issue that the standard variational form requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which is a major limitationforachievingpotentialscalingadvantagescomparedtoclassicalmethods. Toovercome this limitation, we investigate and further develop fixed schedules for QAOA, which only rely on two free parameters. We start with introducing the continuous adiabatic theorem as it motivates the form of QAOA and show its limitations, which we address by applying a discrete version of the theorem. With our findings, a new version of QAOA based on linear-ramps (LR-QAOA) is introduced and further developed. In order to derive suitable parameter values for this schedule, we propose a method based on extrapolation from smaller towards larger problem sizes. With our results obtained on a noiseless emulator, we evaluate the quantum runtime scaling and discuss whether a scaling advantage can be achieved compared to classical methods.

•Jan 1, 2026•0 citations

Multi-angle quantum approximate optimization algorithm

Rebekah Herrman, Phillip C. Lotshaw, James Ostrowski +2 more

The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate noise and circuit complexity undermine performance in practice. Here, we investigate a multi-angle ansatz for QAOA that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. Even though the number of parameters increases, our results indicate that good parameters can be found in polynomial time for a test dataset we consider. This new ansatz gives a 33% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by the conventional ansatz, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. Similarly, multi-angle QAOA yields a higher approximation ratio than QAOA at the same depth on a collection of MaxCut instances on fifty and one-hundred vertex graphs. Many of the optimized parameters are found to be zero, so their associated gates can be removed from the circuit, further decreasing the circuit depth. These results indicate that multi-angle QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices.

arXiv:2109.11455•Scientific Reports•Apr 26, 2022•167 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•10 citations

A Quantum Approach for Stochastic Constrained Binary Optimization

Sarthak Gupta, Vassilis Kekatos

Analytical and practical evidence indicates the advantage of quantum computing solutions over classical alternatives. Quantum-based heuristics relying on the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA) have been shown numerically to generate high-quality solutions to hard combinatorial problems, yet incorporating constraints to such problems has been elusive. To this end, this work puts forth a quantum heuristic to cope with stochastic binary quadratically constrained quadratic programs (QCQP). Identifying the strength of quantum circuits to efficiently generate samples from probability distributions that are otherwise hard to sample from, the variational quantum circuit is trained to generate binaryvalued vectors to approximately solve the aforesaid stochastic program. The method builds upon dual decomposition and entails solving a sequence of judiciously modified standard VQE tasks. Tests on several synthetic problem instances using a quantum simulator corroborate the near-optimality and feasibility of the method, and its potential to generate feasible solutions for the deterministic QCQP too.

arXiv:2301.01443•IEEE International Conference on Acoustics Speech and Signal Processing•May 5, 2023•4 citations

Quantum approximate optimization algorithm with cat qubits

Pontus Vikstål, Laura García-Álvarez, Shruti Puri +1 more

Abstract The Quantum Approximate Optimization Algorithm (QAOA)–a prominent candidate for near-term quantum computing applications–is tailored to find approximate solutions to combinatorial optimization problems using shallow quantum circuits. In this work, we investigate implementations of QAOA based on cat qubits, where the logical states $$|0\rangle$$ and $$|1\rangle$$ are represented by coherent states of opposite amplitudes, $$|\alpha \rangle$$ and $$|-\alpha \rangle$$ . Within this encoding, the primary source of noise–photon loss–induces a bias toward Z -type errors. We focus specifically on an imlementation employing Kerr resonators. By numerically simulating the gate sequences required for QAOA on these nonlinear resonators, we analyze performance on Max-Cut problems and benchmark it against conventional qubits realized as ideal two-level systems subject to single-photon loss. Our findings indicate that the use of cat qubits leads to improved approximation ratios for random Max-Cut instances compared to standard qubit encodings.

arXiv:2305.05556•Scientific Reports•Nov 10, 2026•6 citations
The task of Multiple Sequence Alignment (MSA) is a constrained combinatorial optimization problem that is generally considered a complex computational problem. In this paper, we first present a binary encoding of MSA and devise a corresponding soft-constrained cost-function that enables a Hamiltonian formulation and implementation of the MSA problem with the variational Quantum Approximate Optimization Algorithm (QAOA). Through theoretical analysis, a bound on the ratio of the number of feasible states to the size of the Hilbert space is determined. Furthermore, we consider a small instance of our QAOA-MSA algorithm in both a quantum simulator and its performance on an actual quantum computer. While the ideal solution to the instance of MSA investigated is shown to be the most probable state sampled for a shallow p<5 quantum circuit in the simulation, the level of noise in current devices is still a formidable challenge for the kind of MSA-QAOA algorithm developed here. In turn, we are not able to distinguish the feasible solutions from other states in the quantum hardware output data at this point. This indicates a need for further investigation into both the strategy utilized for compiling the quantum circuit, but also the possibility of devising a more compact ansatz, as one might achieve through constraint-preserving mixers for QAOA.
The Quantum Approximate Optimization Algorithm (QAOA) has emerged as one of the most prominent hybrid quantum–classical algorithms for combinatorial optimization on noisy intermediate-scale quantum (NISQ) hardware. QAOA maps real-world problems into Ising or quadratic unconstrained binary optimization (QUBO) forms and alternates cost and mixer operators in a shallow parameterized circuit whose angles are tuned by a classical optimizer. This article introduces QAOA from fundamentals to practice, emphasizing why it aligns with industrial optimization through binary decision modeling and the presence of severe scaling challenges in classical optimization. We review research trends that improve expressivity and trainability, including ansatz engineering, parameter initialization, and hybrid training strategies, drawing parallels to developments in artificial intelligence. After that, we survey representative applications in emerging domains such as drug discovery, materials design, semiconductor design, logistics, and finance highlighting practical encodings and constraint-preserving formulations that keep quantum evolution within feasible subspaces beyond penalty-based methods. Finally, we present QAOA as a rapidly maturing framework with credible pathways toward near-term utility in real industrial workflows.
Combinatorial Optimization problems play an important role in various domains such as logis- tics, life science or the financial sector. As their complexity in general grows exponentially with their problem size, finding the optimal solution classically becomes infeasible very fast. This raises the central question of whether quantum computers are in principle suitable for solving combinatorial optimization problems better and faster than classical computers. In order to find answers to that question, one needs to study quantum algorithms designed for those problems under ideal conditions (i.e., simulations, which are however limited due to exponential scaling) to investigate their potential, but one also needs real quantum hardware to test its viability and evaluate whether practical advantages are reasonable. In this regard, we consider variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) consisting of a problem and a mixer Hamiltonian with freely selectable parameters, originally proposed as variational hybrid ansatz with classical optimization. This algorithm structure of- fers flexible and relatively shallow circuits, which makes it suitable for current NISQ hardware. However, optimizing the variational circuit parameters can be an NP-hard problem at worst. In this thesis, we study different versions of QAOA, especially with a focus on limitations, perfor- mance and potential advantages opposite classical methods. The first part of the thesis concerns the investigation of various aspects regarding the imple- mentation of the variational QAOA protocol such as: the incorporation of a problem constraint either by adding a suitable penalty term of by choosing a suitable mixer (that restricts the search space), the scaling of the problem Hamiltonian in comparison to the mixer Hamiltonian, the choice of the initial values for the classical optimization of the circuit parameters, and finally the choice of the function to be minimized (i.e., CVaR vs. expectation value). We apply this proto- col to both the portfolio optimization and the feature selection and evaluate the performance. In order to improve QAOA, we consider the warm-start QAOA for different problem instances and analyze its improved performance with regard to involved quantum effects. For this purpose, we propose a classical pre-processing method and demonstrate that the warm-start results can be reproduced or even exceeded by this method. The second part addresses the issue that the standard variational form requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which is a major limitationforachievingpotentialscalingadvantagescomparedtoclassicalmethods. Toovercome this limitation, we investigate and further develop fixed schedules for QAOA, which only rely on two free parameters. We start with introducing the continuous adiabatic theorem as it motivates the form of QAOA and show its limitations, which we address by applying a discrete version of the theorem. With our findings, a new version of QAOA based on linear-ramps (LR-QAOA) is introduced and further developed. In order to derive suitable parameter values for this schedule, we propose a method based on extrapolation from smaller towards larger problem sizes. With our results obtained on a noiseless emulator, we evaluate the quantum runtime scaling and discuss whether a scaling advantage can be achieved compared to classical methods.
The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate noise and circuit complexity undermine performance in practice. Here, we investigate a multi-angle ansatz for QAOA that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. Even though the number of parameters increases, our results indicate that good parameters can be found in polynomial time for a test dataset we consider. This new ansatz gives a 33% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by the conventional ansatz, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. Similarly, multi-angle QAOA yields a higher approximation ratio than QAOA at the same depth on a collection of MaxCut instances on fifty and one-hundred vertex graphs. Many of the optimized parameters are found to be zero, so their associated gates can be removed from the circuit, further decreasing the circuit depth. These results indicate that multi-angle QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices.
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.
Analytical and practical evidence indicates the advantage of quantum computing solutions over classical alternatives. Quantum-based heuristics relying on the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA) have been shown numerically to generate high-quality solutions to hard combinatorial problems, yet incorporating constraints to such problems has been elusive. To this end, this work puts forth a quantum heuristic to cope with stochastic binary quadratically constrained quadratic programs (QCQP). Identifying the strength of quantum circuits to efficiently generate samples from probability distributions that are otherwise hard to sample from, the variational quantum circuit is trained to generate binaryvalued vectors to approximately solve the aforesaid stochastic program. The method builds upon dual decomposition and entails solving a sequence of judiciously modified standard VQE tasks. Tests on several synthetic problem instances using a quantum simulator corroborate the near-optimality and feasibility of the method, and its potential to generate feasible solutions for the deterministic QCQP too.
Abstract The Quantum Approximate Optimization Algorithm (QAOA)–a prominent candidate for near-term quantum computing applications–is tailored to find approximate solutions to combinatorial optimization problems using shallow quantum circuits. In this work, we investigate implementations of QAOA based on cat qubits, where the logical states ∣0⟩|0\rangle∣0⟩ and ∣1⟩|1\rangle∣1⟩ are represented by coherent states of opposite amplitudes, ∣α⟩|\alpha \rangle∣α⟩ and ∣−α⟩|-\alpha \rangle∣−α⟩ . Within this encoding, the primary source of noise–photon loss–induces a bias toward Z -type errors. We focus specifically on an imlementation employing Kerr resonators. By numerically simulating the gate sequences required for QAOA on these nonlinear resonators, we analyze performance on Max-Cut problems and benchmark it against conventional qubits realized as ideal two-level systems subject to single-photon loss. Our findings indicate that the use of cat qubits leads to improved approximation ratios for random Max-Cut instances compared to standard qubit encodings.