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

The Journal of Open Source Software

QAOA.jl: Toolkit for the Quantum and Mean-Field Approximate Optimization Algorithms

Tim Bode, Dmitry Bagrets, Aditi Misra-Spieldenner, Tobias Stollenwerk, Frank K. Wilhelm

Published Jun 28, 2023• 2 citations
Publisher

Abstract

Quantum algorithms are an area of intensive research thanks to their potential for speeding up certain specific tasks exponentially.However, for the time being, high error rates on the existing hardware realizations preclude the application of many algorithms that are based on the assumption of fault-tolerant quantum computation.On such noisy intermediatescale quantum (NISQ) devices (Preskill, 2018), the exploration of the potential of heuristic quantum algorithms has attracted much interest.A leading candidate for solving combinatorial optimization problems is the so-called Quantum Approximate Optimization Algorithm (QAOA) (Farhi et al., 2014).QAOA.jl is a Julia package (Bezanson et al., 2017) that implements the mean-field Approximate Optimization Algorithm (mean-field AOA) (Misra-Spieldenner et al., 2023) -a quantum-inspired classical algorithm derived from the QAOA via the mean-field approximation.This novel algorithm is useful in assisting the search for quantum advantage by providing a tool to discriminate (combinatorial) optimization problems that can be solved classically from those that cannot.Note that QAOA.jl has already been used during the research leading to Misra-Spieldenner et al. (2023).

DOI
10.21105/joss.05364

Related papers

Mean-Field Approximate Optimization Algorithm

Aditi Misra-Spieldenner, Tim Bode, Peter Schuhmacher +3 more

The quantum approximate optimization algorithm (QAOA) is suggested as a promising application on early quantum computers.Here a quantum-inspired classical algorithm, the mean-field approximate optimization algorithm (mean-field AOA), is developed by replacement of the quantum evolution of the QAOA with classical spin dynamics through the mean-field approximation.Because of the alternating structure of the QAOA, this classical dynamics can be found exactly for any number of QAOA layers.We benchmark its performance against the QAOA on the Sherrington-Kirkpatrick model and the partition problem, and find that the mean-field AOA outperforms the QAOA in both cases for most instances.Our algorithm can thus serve as a tool to delineate optimization problems that can be solved classically from those that cannot, i.e., we believe that it will help to identify instances where a true quantum advantage can be expected from the QAOA.To quantify quantum fluctuations around the mean-field trajectories, we solve an effective scattering problem in time, which is characterized by a spectrum of time-dependent Lyapunov exponents.These provide an indicator for the hardness of a given optimization problem relative to the mean-field AOA.

PRX Quantum•Sep 12, 2023•22 citations

Mean-Field Approximate Optimization Algorithm

Aditi Misra-Spieldenner, Tim Bode, Schuhmacher, Peter K. +3 more

The Quantum Approximate Optimization Algorithm (QAOA) is suggested as a promising application on early quantum computers. Here, a quantum-inspired classical algorithm, the mean-field Approximate Optimization Algorithm (mean-field AOA), is developed by replacing the quantum evolution of the QAOA with classical spin dynamics through the mean-field approximation. Due to the alternating structure of the QAOA, this classical dynamics can be found exactly for any number of QAOA layers. We benchmark its performance against the QAOA on the Sherrington-Kirkpatrick (SK) model and the partition problem, and find that the mean-field AOA outperforms the QAOA in both cases for most instances. Our algorithm can thus serve as a tool to delineate optimization problems that can be solved classically from those that cannot, i.e. we believe that it will help to identify instances where a true quantum advantage can be expected from the QAOA. To quantify quantum fluctuations around the mean-field trajectories, we solve an effective scattering problem in time, which is characterized by a spectrum of time-dependent Lyapunov exponents. These provide an indicator for the hardness of a given optimization problem relative to the mean-field AOA.

arXiv:2303.00329•Mar 1, 2023•2 citations

Quantum Approximate Optimization: A Computational Intelligence Perspective

Christo Meriwether Keller, Satyajayant Misra, Andreas Bärtschi +1 more

Quantum computing is an emerging field on the multidisciplinary interface between physics, engineering, and computer science with the potential to make a large impact on computational intelligence (CI). The aim of this paper is to introduce quantum approximate optimization methods to the CI community because of direct relevance to solving combinatorial problems. We introduce quantum computing and variational quantum algorithms (VQAs). VQAs are an effective method for the near-term implementation of quantum solutions on noisy intermediate-scale quantum (NISQ) devices with less reliable qubits and early-stage error correction. Then, we explain Farhi et al.'s quantum approximate optimization algorithm (Farhi's QAOA, to prevent confusion). This VQA is generalized by Hadfield et al. to the quantum alternating operator ansatz (QAOA), which is a nature-inspired (particularly, adiabatic) quantum metaheuristic for approximately solving combinatorial optimization problems on gate-based quantum computers. We discuss connections of QAOA to relevant domains, such as computational learning theory and genetic algorithms, discussing current techniques and known results regarding hybrid quantum-classical intelligence systems. We present a schematic of how QAOA is constructed, and also discuss how CI techniques can be used to improve QAOA. We conclude with QAOA implementations for the well-known maximum cut, maximum bisection, and traveling salesperson problems, which can serve as templates for CI practitioners interested in using QAOA.

arXiv:2407.07202•Jul 9, 2024•1 citation

Multiscale quantum approximate optimization algorithm

Ping Zou

The quantum approximate optimization algorithm (QAOA) is one of the canonical algorithms designed to find approximate solutions for combinatorial optimization problems on current noisy intermediate-scale quantum (NISQ) devices. The primary focus of ongoing research is to exhibit its speed advantage over classical algorithms. However, the performance of QAOA is restricted at lower depths, while higher depths are limited by current experimental techniques. We propose an algorithm that amalgamates the capabilities of QAOA and the real-space renormalization group transformation. Numerical simulations indicate that our proposed algorithm can deliver precise solutions for specific randomly generated instances using QAOA at shallow depths, even at the lowest depth. This algorithm is particularly suitable for current NISQ devices, offering the potential to demonstrate a quantum advantage.

arXiv:2312.06181•Physical Review A•Jan 17, 2025•2 citations

A Tutorial on Quantum Approximate Optimization Algorithm (QAOA): Fundamentals and Applications

Jaeho Choi, Joongheon Kim

Over the past few years, many researchers around the world have been keen to know the potential and efficiency of quantum computers. The researchers have focused on specific issues that classical computers cannot solve or issues that quantum computers can handle in a better way. Among these various attractive research topics in quantum computers, this paper introduces the Quantum Approximate Optimization Algorithm (QAOA) which guarantees relatively considerable performances in many combinatorial optimization problems. For the comprehensive understanding of QAOA, this paper also describes the approximate optimization, the Quantum Alternating Operator Ansatz, and applications. Besides the theories of QAOA and Quantum Alternating Operator Ansatz, this paper explains the applications of QAOA to major combinatorial optimization problems such as maximum cut (MaxCut) problem and the max-independent set (MIS) problem.

International Conference on Information and Communication Technology Convergence (ICTC)•Oct 1, 2019•121 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•1 citation
Quantum algorithms are an area of intensive research thanks to their potential for speeding up certain specific tasks exponentially.However, for the time being, high error rates on the existing hardware realizations preclude the application of many algorithms that are based on the assumption of fault-tolerant quantum computation.On such noisy intermediatescale quantum (NISQ) devices (Preskill, 2018), the exploration of the potential of heuristic quantum algorithms has attracted much interest.A leading candidate for solving combinatorial optimization problems is the so-called Quantum Approximate Optimization Algorithm (QAOA) (Farhi et al., 2014).QAOA.jl is a Julia package (Bezanson et al., 2017) that implements the mean-field Approximate Optimization Algorithm (mean-field AOA) (Misra-Spieldenner et al., 2023) -a quantum-inspired classical algorithm derived from the QAOA via the mean-field approximation.This novel algorithm is useful in assisting the search for quantum advantage by providing a tool to discriminate (combinatorial) optimization problems that can be solved classically from those that cannot.Note that QAOA.jl has already been used during the research leading to Misra-Spieldenner et al. (2023).
The quantum approximate optimization algorithm (QAOA) is suggested as a promising application on early quantum computers.Here a quantum-inspired classical algorithm, the mean-field approximate optimization algorithm (mean-field AOA), is developed by replacement of the quantum evolution of the QAOA with classical spin dynamics through the mean-field approximation.Because of the alternating structure of the QAOA, this classical dynamics can be found exactly for any number of QAOA layers.We benchmark its performance against the QAOA on the Sherrington-Kirkpatrick model and the partition problem, and find that the mean-field AOA outperforms the QAOA in both cases for most instances.Our algorithm can thus serve as a tool to delineate optimization problems that can be solved classically from those that cannot, i.e., we believe that it will help to identify instances where a true quantum advantage can be expected from the QAOA.To quantify quantum fluctuations around the mean-field trajectories, we solve an effective scattering problem in time, which is characterized by a spectrum of time-dependent Lyapunov exponents.These provide an indicator for the hardness of a given optimization problem relative to the mean-field AOA.
The Quantum Approximate Optimization Algorithm (QAOA) is suggested as a promising application on early quantum computers. Here, a quantum-inspired classical algorithm, the mean-field Approximate Optimization Algorithm (mean-field AOA), is developed by replacing the quantum evolution of the QAOA with classical spin dynamics through the mean-field approximation. Due to the alternating structure of the QAOA, this classical dynamics can be found exactly for any number of QAOA layers. We benchmark its performance against the QAOA on the Sherrington-Kirkpatrick (SK) model and the partition problem, and find that the mean-field AOA outperforms the QAOA in both cases for most instances. Our algorithm can thus serve as a tool to delineate optimization problems that can be solved classically from those that cannot, i.e. we believe that it will help to identify instances where a true quantum advantage can be expected from the QAOA. To quantify quantum fluctuations around the mean-field trajectories, we solve an effective scattering problem in time, which is characterized by a spectrum of time-dependent Lyapunov exponents. These provide an indicator for the hardness of a given optimization problem relative to the mean-field AOA.
Quantum computing is an emerging field on the multidisciplinary interface between physics, engineering, and computer science with the potential to make a large impact on computational intelligence (CI). The aim of this paper is to introduce quantum approximate optimization methods to the CI community because of direct relevance to solving combinatorial problems. We introduce quantum computing and variational quantum algorithms (VQAs). VQAs are an effective method for the near-term implementation of quantum solutions on noisy intermediate-scale quantum (NISQ) devices with less reliable qubits and early-stage error correction. Then, we explain Farhi et al.'s quantum approximate optimization algorithm (Farhi's QAOA, to prevent confusion). This VQA is generalized by Hadfield et al. to the quantum alternating operator ansatz (QAOA), which is a nature-inspired (particularly, adiabatic) quantum metaheuristic for approximately solving combinatorial optimization problems on gate-based quantum computers. We discuss connections of QAOA to relevant domains, such as computational learning theory and genetic algorithms, discussing current techniques and known results regarding hybrid quantum-classical intelligence systems. We present a schematic of how QAOA is constructed, and also discuss how CI techniques can be used to improve QAOA. We conclude with QAOA implementations for the well-known maximum cut, maximum bisection, and traveling salesperson problems, which can serve as templates for CI practitioners interested in using QAOA.
The quantum approximate optimization algorithm (QAOA) is one of the canonical algorithms designed to find approximate solutions for combinatorial optimization problems on current noisy intermediate-scale quantum (NISQ) devices. The primary focus of ongoing research is to exhibit its speed advantage over classical algorithms. However, the performance of QAOA is restricted at lower depths, while higher depths are limited by current experimental techniques. We propose an algorithm that amalgamates the capabilities of QAOA and the real-space renormalization group transformation. Numerical simulations indicate that our proposed algorithm can deliver precise solutions for specific randomly generated instances using QAOA at shallow depths, even at the lowest depth. This algorithm is particularly suitable for current NISQ devices, offering the potential to demonstrate a quantum advantage.
Over the past few years, many researchers around the world have been keen to know the potential and efficiency of quantum computers. The researchers have focused on specific issues that classical computers cannot solve or issues that quantum computers can handle in a better way. Among these various attractive research topics in quantum computers, this paper introduces the Quantum Approximate Optimization Algorithm (QAOA) which guarantees relatively considerable performances in many combinatorial optimization problems. For the comprehensive understanding of QAOA, this paper also describes the approximate optimization, the Quantum Alternating Operator Ansatz, and applications. Besides the theories of QAOA and Quantum Alternating Operator Ansatz, this paper explains the applications of QAOA to major combinatorial optimization problems such as maximum cut (MaxCut) problem and the max-independent set (MIS) problem.
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.