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

Lecture notes in computer science

Solving Maximum Cut Problem with Multi-objective Enhance Quantum Approximate Optimization Algorithm

Huy Phuc Nguyen Ha, Viết Hùng Nguyễn, Anh Son Ta

Published Jan 1, 2024• 0 citations
Publisher
DOI
10.1007/978-3-031-65343-8_16

Related papers

Quantum approximate multi-objective optimization

Ayse Kotil, Elijah Pelofske, Stephanie Riedmüller +4 more

The goal of multi-objective optimization is to understand optimal trade-offs between competing objective functions by finding the Pareto front, that is, the set of all Pareto-optimal solutions, where no objective can be improved without degrading another one. Multi-objective optimization can be challenging classically, even if the corresponding single-objective optimization problems are efficiently solvable. Thus, multi-objective optimization represents a compelling problem class to analyze with quantum computers. Here we use a low-depth quantum approximate optimization algorithm to approximate the optimal Pareto front of certain multi-objective weighted maximum-cut problems. We demonstrate its performance on an IBM Quantum computer, as well as with matrix product state numerical simulation, and show its potential to outperform classical approaches. This study explores the use of quantum computing to address multi-objective optimization challenges. By using a low-depth quantum approximate optimization algorithm to approximate the optimal Pareto front of multi-objective weighted max-cut problems, the authors demonstrate promising results—both in simulation and on IBM Quantum hardware—surpassing classical approaches.

arXiv:2503.22797•Nature Computational Science•Oct 24, 2025•44 citations

Quantum Approximate Optimization Algorithm: Applications, Limitations and Enhancement

Pablo Herrero Gómez, Marcos Alemany Manzanaro, David Gil +1 more

Communications in computer and information science•Jan 1, 2026•0 citations

Quantum approximate optimization algorithm: a review study and problems

Laith Abualigah, Saif AlNajdawi, Abiodun Motunrayo Ikotun +7 more

Elsevier eBooks•Jan 1, 2024•18 citations

Quantum approximate optimization algorithms for maximum cut on low-girth graphs

Tongyang Li, Yan‐Kun Su, Ziyi Yang +1 more

Maximum cut (MaxCut) on graphs is a classic NP-hard problem. In quantum computing, Farhi, Gutmann, and Goldstone proposed the quantum approximate optimization algorithm (QAOA) for solving the MaxCut problem. Its guarantee on the cut fraction (the fraction of edges in the output cut over all edges) was mainly studied for high-girth graphs, i.e., graphs with only long cycles. On the other hand, low-girth graphs are ubiquitous in theoretical computer science, including expander graphs, which are outstanding examples with wide applications in theory and beyond. In this paper, we apply QAOA to MaxCut on a set of expander graphs proposed by Mohanty and O'Donnell, known as additive product graphs. Additionally, we apply multi-angle QAOA (ma-QAOA) to better utilize the graph structure of additive product graphs in the ansatz design. In theory, we derive an iterative formula to calculate the expected cut fraction of such graphs. This formula also extends to the quantum MaxCut problem. On the other hand, we conduct numerical experiments to compare the best-known classical local algorithms and QAOA with constant depth. Our results demonstrate that QAOA outperforms these best-known classical algorithms by 0.3% to 5.2% on several additive product graphs, while ma-QAOA further enhances this advantage by an additional 0.6% to 2.5%. In particular, we observe cases in which ma-QAOA exhibits superiority over the best-known classical algorithms but QAOA does not. Furthermore, we extend our experiments to planar graphs, such as tiling grid graphs, where QAOA also demonstrates an advantage.

arXiv:2410.04409•Physical Review Research•May 28, 2025•5 citations

A Layerwise-Multi-Angle Approach to Fine-Tuning the Quantum Approximate Optimization Algorithm

Leonardo Lavagna, Andrea Ceschini, Antonello Rosato +1 more

This paper introduces a novel variational quantum algorithm built upon the established Quantum Approximate Optimization Algorithm also known as QAOA. Since the known parameter fixing strategy imposes constraints on QAOA to enhance tractability at the cost of some expressive power, the proposed layerwise approach integrates it with the existing Multi-Angle QAOA technique, which is characterized in turn by height-ened expressiveness through an increased number of parameters, albeit with increased optimization challenges. Consequently, the proposed layerwise-Multi-Angle QAOA combines the strengths of one variant with the limitations of the other, striking a balance in algorithmic design. The effectiveness of the proposed algorithm is assessed through experimental evaluations on the Maximum Cut problem. This study reveals promising results in heuristic predictions, with robustness both in terms of approximation ratio and optimization capabilities.

International Joint Conference on Neural Networks (IJCNN)•Jun 30, 2024•6 citations

Quantum Approximate Multi-Objective Optimization in Routing Problems

Eduardo Willwock Lussi, Alisson dos Passos Fumaco, Marcos Vinicius Reballo +3 more

Multi-objective optimization (MOO) problems are common in logistics, where routing decisions must balance conflicting objectives such as travel distance, delivery time, and operational risk. A recently proposed Quantum Approximate Optimization Algorithm (QAOA) parameter-transfer strategy solves multi-objective MAX-CUT problems by reusing parameters trained on smaller instances, avoiding costly reoptimization for each scalarized problem. However, its effectiveness has only been demonstrated on proof-of-concept instances tailored to quantum hardware connectivity. In this work, we evaluate the applicability of this strategy to realistic routing problems. We formulate the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) as Quadratic Unconstrained Binary Optimization (QUBO) models, reduce them to MAX-CUT, and assess the parameter-transfer framework under conditions matching the original study. Validation is performed through classical simulations and experiments on IBM quantum hardware. The resulting Pareto fronts are compared with those obtained using an adapted classical ε-constraint method, using hypervolume as the primary quality metric. Results indicate that parameter transfer remains effective, frequently achieving higher hypervolume and often finding competitive solutions earlier. However, performance depends on problem structure. The approach is consistently effective for TSP instances but less stable for the more constrained VRP, suggesting that QAOA parameter transferability decreases as the optimization landscape becomes more complex. These results provide the first comprehensive evaluation of QAOA parameter transfer on realistic multi-objective routing problems and demonstrate its potential beyond proof-of-concept MAX-CUT benchmarks.

cs.ETCross-listedarXiv:2610.00168•Sep 17, 2026•0 citations
The goal of multi-objective optimization is to understand optimal trade-offs between competing objective functions by finding the Pareto front, that is, the set of all Pareto-optimal solutions, where no objective can be improved without degrading another one. Multi-objective optimization can be challenging classically, even if the corresponding single-objective optimization problems are efficiently solvable. Thus, multi-objective optimization represents a compelling problem class to analyze with quantum computers. Here we use a low-depth quantum approximate optimization algorithm to approximate the optimal Pareto front of certain multi-objective weighted maximum-cut problems. We demonstrate its performance on an IBM Quantum computer, as well as with matrix product state numerical simulation, and show its potential to outperform classical approaches. This study explores the use of quantum computing to address multi-objective optimization challenges. By using a low-depth quantum approximate optimization algorithm to approximate the optimal Pareto front of multi-objective weighted max-cut problems, the authors demonstrate promising results—both in simulation and on IBM Quantum hardware—surpassing classical approaches.
Maximum cut (MaxCut) on graphs is a classic NP-hard problem. In quantum computing, Farhi, Gutmann, and Goldstone proposed the quantum approximate optimization algorithm (QAOA) for solving the MaxCut problem. Its guarantee on the cut fraction (the fraction of edges in the output cut over all edges) was mainly studied for high-girth graphs, i.e., graphs with only long cycles. On the other hand, low-girth graphs are ubiquitous in theoretical computer science, including expander graphs, which are outstanding examples with wide applications in theory and beyond. In this paper, we apply QAOA to MaxCut on a set of expander graphs proposed by Mohanty and O'Donnell, known as additive product graphs. Additionally, we apply multi-angle QAOA (ma-QAOA) to better utilize the graph structure of additive product graphs in the ansatz design. In theory, we derive an iterative formula to calculate the expected cut fraction of such graphs. This formula also extends to the quantum MaxCut problem. On the other hand, we conduct numerical experiments to compare the best-known classical local algorithms and QAOA with constant depth. Our results demonstrate that QAOA outperforms these best-known classical algorithms by 0.3% to 5.2% on several additive product graphs, while ma-QAOA further enhances this advantage by an additional 0.6% to 2.5%. In particular, we observe cases in which ma-QAOA exhibits superiority over the best-known classical algorithms but QAOA does not. Furthermore, we extend our experiments to planar graphs, such as tiling grid graphs, where QAOA also demonstrates an advantage.
This paper introduces a novel variational quantum algorithm built upon the established Quantum Approximate Optimization Algorithm also known as QAOA. Since the known parameter fixing strategy imposes constraints on QAOA to enhance tractability at the cost of some expressive power, the proposed layerwise approach integrates it with the existing Multi-Angle QAOA technique, which is characterized in turn by height-ened expressiveness through an increased number of parameters, albeit with increased optimization challenges. Consequently, the proposed layerwise-Multi-Angle QAOA combines the strengths of one variant with the limitations of the other, striking a balance in algorithmic design. The effectiveness of the proposed algorithm is assessed through experimental evaluations on the Maximum Cut problem. This study reveals promising results in heuristic predictions, with robustness both in terms of approximation ratio and optimization capabilities.
Multi-objective optimization (MOO) problems are common in logistics, where routing decisions must balance conflicting objectives such as travel distance, delivery time, and operational risk. A recently proposed Quantum Approximate Optimization Algorithm (QAOA) parameter-transfer strategy solves multi-objective MAX-CUT problems by reusing parameters trained on smaller instances, avoiding costly reoptimization for each scalarized problem. However, its effectiveness has only been demonstrated on proof-of-concept instances tailored to quantum hardware connectivity. In this work, we evaluate the applicability of this strategy to realistic routing problems. We formulate the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) as Quadratic Unconstrained Binary Optimization (QUBO) models, reduce them to MAX-CUT, and assess the parameter-transfer framework under conditions matching the original study. Validation is performed through classical simulations and experiments on IBM quantum hardware. The resulting Pareto fronts are compared with those obtained using an adapted classical ε-constraint method, using hypervolume as the primary quality metric. Results indicate that parameter transfer remains effective, frequently achieving higher hypervolume and often finding competitive solutions earlier. However, performance depends on problem structure. The approach is consistently effective for TSP instances but less stable for the more constrained VRP, suggesting that QAOA parameter transferability decreases as the optimization landscape becomes more complex. These results provide the first comprehensive evaluation of QAOA parameter transfer on realistic multi-objective routing problems and demonstrate its potential beyond proof-of-concept MAX-CUT benchmarks.