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:2301.10756 · Physical Review Research

Fermionic quantum approximate optimization algorithm

Takuya Yoshioka, Keita Sasada, Yuichiro Nakano, Keisuke Fujii

Published May 1, 2023• 20 citations
arXivHTMLPDF

Abstract

Quantum computers are expected to accelerate solving combinatorial optimization problems, including algorithms such as Grover adaptive search and quantum approximate optimization algorithm (QAOA). However, many combinatorial optimization problems involve constraints which, when imposed as soft constraints in the cost function, can negatively impact the performance of the optimization algorithm. In this paper, we propose fermionic quantum approximate optimization algorithm (FQAOA) for solving combinatorial optimization problems with constraints. Specifically, FQAOA tackles the constrains issue by using fermion particle number preservation to intrinsically impose them throughout QAOA. We provide a systematic guideline for designing the driver Hamiltonian for a given problem Hamiltonian with constraints. The initial state can be chosen to be a superposition of states satisfying the constraint and the ground state of the driver Hamiltonian. This property is important since FQAOA reduced to quantum adiabatic computation in the large limit of circuit depth $p$ and improved performance, even for shallow circuits with optimizing the parameters starting from the fixed-angle determined by Trotterized quantum adiabatic evolution. We perform an extensive numerical simulation and demonstrate that proposed FQAOA provides substantial performance advantages against existing approaches in portfolio optimization problems. Furthermore, the Hamiltonian design guideline is useful not only for QAOA but also Grover adaptive search and quantum phase estimation to solve combinatorial optimization problems with constraints. Since software tools for fermionic systems have been developed in quantum computational chemistry both for noisy intermediate-scale quantum computers and fault-tolerant quantum computers, FQAOA allows us to apply these tools for constrained combinatorial optimization problems.

DOI
10.1103/physrevresearch.5.023071

Related papers

Experimental Demonstration of Fermionic QAOA with One-Dimensional Cyclic Driver Hamiltonian

Takuya Yoshioka, Keita Sasada, Yuichiro Nakano +1 more

Quantum approximate optimization algorithm (QAOA) has attracted much attention as an algorithm that has the potential to efficiently solve combinatorial optimization problems. Among them, a fermionic QAOA (FQAOA) for solving constrained optimization problems has been developed [Yoshioka, Sasada, Nakano, and Fujii, Phys. Rev. Research vol. 5, 023071, 2023]. In this algorithm, the constraints are essentially imposed as fermion number conservation at arbitrary approximation level. We take the portfolio optimization problem as an application example and propose a new driver Hamiltonian on an one-dimensional cyclic lattice. Our FQAOA with the new driver Hamiltonian reduce the number of gate operations in quantum circuits. Experiments on a trapped-ion quantum computer using 16 qubits on Amazon Braket demonstrates that the proposed driver Hamiltonian effectively suppresses noise effects compared to the previous FQAOA.

arXiv:2312.04710•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•3 citations

Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer

Linghua Zhu, 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\"atze. 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•Physical Review Research•Jul 11, 2022•296 citations

Quantum constraint learning for quantum approximate optimization algorithm

Santosh Kumar Radha

The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm that offers the potential to handle combinatorial optimization problems. Introducing constraints in such combinatorial optimization problems poses a significant challenge in the extensions of QAOA to support relevant larger-scale problems. This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace. We show that this method can be used for encoding any general form of constraints. One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz. This procedure gives the flexibility to control the depth of the circuit at the cost of the accuracy of enforcing the constraint, thus having immediate application in the Noisy Intermediate Scale Quantum (NISQ) era. We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints. Finally, using this metric, we evaluate the performance of the proposed algorithm.

arXiv:2105.06770•May 14, 2021•9 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

Quantum Approximate Optimization Algorithm (QAOA) for Solving NP-Hard Problems

Srikanth Kilaru, Thota Sravya Vardhani, Attluri Udaya Lakshmi +2 more

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm used to study NP-hard combinatorial optimization problems. In this work, we focused on optimization strategies for QAOA including circuit depth reduction, parameter parallelization, and hybrid classical feedback mechanisms. We will consider the application of QAOA to different types of NP-hard problems such as Max-Cut and Vehicle Routing Problem (VRP) and discuss the advantages and disadvantages of each in terms of approximation quality and cost of computation. The comparative simulation on the various qubit counts and depth layers points out the limits of scalability and the constraints of hardware on the current Noisy Intermediate-Scale Quantum (NISQ) devices. And also an improved divide-and-conquer strategy is presented in which parameter reusability and gradient-informed initialization are combined to boost convergence rates. The results of the experiment show that it is more efficient and scalable while maintaining the competitive approximation performance compared to the baseline QAOA. The experimental validation focuses on representative small-size instances, while the proposed framework provides extensions for scalable implementations. Ultimately, this work is a step towards the realization of efficient, hardware-aware, and scalable optimization strategies, thus opening up the practical deployment of QAOA on the quantum systems of the next few years.

IEEE Nexo-Tech International Conference on Advanced Technologies and Innovations (ICATI)•May 8, 2026•0 citations

Low-level circuit optimization for the quantum approximate optimization algorithm

David Owusu-Antwi, P. Gokhale

Quantum computer systems require robust software integration to support quantum algorithm development towards addressing practical challenges in many important problem areas including logistics, chemistry, and AI/ML. Researchers predict quantum algorithms will achieve computational advantage over classical algorithms for these specific problem areas in the Noisy Intermediate Scale Quantum (NISQ) era [1]. We consider one such algorithm, the Quantum Approximate Optimization Algorithm (QAOA), a variational quantum algorithm for solving combinatorial optimization problems [2]. QAOA promises to be a practical alternative to inefficient classical algorithms for large problem sizes, but quantum hardware capabilities lag behind the requirements for practical application. We show that the Superstaq quantum compiler can support performance improvements for QAOA by exploiting optimization opportunities only revealed at levels lower than logic gates, i.e., at the level of pulses, quantum hardware instructions.

IET conference proceedings.•Dec 18, 2023•3 citations
Quantum computers are expected to accelerate solving combinatorial optimization problems, including algorithms such as Grover adaptive search and quantum approximate optimization algorithm (QAOA). However, many combinatorial optimization problems involve constraints which, when imposed as soft constraints in the cost function, can negatively impact the performance of the optimization algorithm. In this paper, we propose fermionic quantum approximate optimization algorithm (FQAOA) for solving combinatorial optimization problems with constraints. Specifically, FQAOA tackles the constrains issue by using fermion particle number preservation to intrinsically impose them throughout QAOA. We provide a systematic guideline for designing the driver Hamiltonian for a given problem Hamiltonian with constraints. The initial state can be chosen to be a superposition of states satisfying the constraint and the ground state of the driver Hamiltonian. This property is important since FQAOA reduced to quantum adiabatic computation in the large limit of circuit depth ppp and improved performance, even for shallow circuits with optimizing the parameters starting from the fixed-angle determined by Trotterized quantum adiabatic evolution. We perform an extensive numerical simulation and demonstrate that proposed FQAOA provides substantial performance advantages against existing approaches in portfolio optimization problems. Furthermore, the Hamiltonian design guideline is useful not only for QAOA but also Grover adaptive search and quantum phase estimation to solve combinatorial optimization problems with constraints. Since software tools for fermionic systems have been developed in quantum computational chemistry both for noisy intermediate-scale quantum computers and fault-tolerant quantum computers, FQAOA allows us to apply these tools for constrained combinatorial optimization problems.
Quantum approximate optimization algorithm (QAOA) has attracted much attention as an algorithm that has the potential to efficiently solve combinatorial optimization problems. Among them, a fermionic QAOA (FQAOA) for solving constrained optimization problems has been developed [Yoshioka, Sasada, Nakano, and Fujii, Phys. Rev. Research vol. 5, 023071, 2023]. In this algorithm, the constraints are essentially imposed as fermion number conservation at arbitrary approximation level. We take the portfolio optimization problem as an application example and propose a new driver Hamiltonian on an one-dimensional cyclic lattice. Our FQAOA with the new driver Hamiltonian reduce the number of gate operations in quantum circuits. Experiments on a trapped-ion quantum computer using 16 qubits on Amazon Braket demonstrates that the proposed driver Hamiltonian effectively suppresses noise effects compared to the previous FQAOA.
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\"atze. 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.
The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm that offers the potential to handle combinatorial optimization problems. Introducing constraints in such combinatorial optimization problems poses a significant challenge in the extensions of QAOA to support relevant larger-scale problems. This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace. We show that this method can be used for encoding any general form of constraints. One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz. This procedure gives the flexibility to control the depth of the circuit at the cost of the accuracy of enforcing the constraint, thus having immediate application in the Noisy Intermediate Scale Quantum (NISQ) era. We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints. Finally, using this metric, we evaluate the performance of the proposed algorithm.
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) is a hybrid quantum-classical algorithm used to study NP-hard combinatorial optimization problems. In this work, we focused on optimization strategies for QAOA including circuit depth reduction, parameter parallelization, and hybrid classical feedback mechanisms. We will consider the application of QAOA to different types of NP-hard problems such as Max-Cut and Vehicle Routing Problem (VRP) and discuss the advantages and disadvantages of each in terms of approximation quality and cost of computation. The comparative simulation on the various qubit counts and depth layers points out the limits of scalability and the constraints of hardware on the current Noisy Intermediate-Scale Quantum (NISQ) devices. And also an improved divide-and-conquer strategy is presented in which parameter reusability and gradient-informed initialization are combined to boost convergence rates. The results of the experiment show that it is more efficient and scalable while maintaining the competitive approximation performance compared to the baseline QAOA. The experimental validation focuses on representative small-size instances, while the proposed framework provides extensions for scalable implementations. Ultimately, this work is a step towards the realization of efficient, hardware-aware, and scalable optimization strategies, thus opening up the practical deployment of QAOA on the quantum systems of the next few years.
Quantum computer systems require robust software integration to support quantum algorithm development towards addressing practical challenges in many important problem areas including logistics, chemistry, and AI/ML. Researchers predict quantum algorithms will achieve computational advantage over classical algorithms for these specific problem areas in the Noisy Intermediate Scale Quantum (NISQ) era [1]. We consider one such algorithm, the Quantum Approximate Optimization Algorithm (QAOA), a variational quantum algorithm for solving combinatorial optimization problems [2]. QAOA promises to be a practical alternative to inefficient classical algorithms for large problem sizes, but quantum hardware capabilities lag behind the requirements for practical application. We show that the Superstaq quantum compiler can support performance improvements for QAOA by exploiting optimization opportunities only revealed at levels lower than logic gates, i.e., at the level of pulses, quantum hardware instructions.