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

Evaluating performance of hybrid quantum optimization algorithms for MAXCUT Clustering using IBM runtime environment

Daniel Beaulieu, Pham, Anh

Published Dec 6, 2021• 2 citations
arXivHTMLPDF

Abstract

Quantum algorithms can be used to perform unsupervised machine learning tasks like data clustering by mapping the distance between data points to a graph optimization problem (i.e. MAXCUT) and finding optimal solution through energy minimization using hybrid quantum classical methods. Taking advantage of the IBM runtime environment, we benchmark the performance of the "Warm-Start" (ws) variant of Quantum Approximate Optimization Algorithm (QAOA) versus the standard implementation of QAOA and the variational quantum eigensolver (VQE) for unstructured clustering problems using real world dataset with respect to accuracy and execution time. Our numerical results show a strong speedup in execution time for different optimization algorithms using the IBM Qiskit Runtime architecture and increased speedup in classification accuracy in ws-QAOA algorithm

DOI
10.48550/arxiv.2112.03199

Related papers

Max-cut Clustering Utilizing Warm-Start QAOA and IBM Runtime

Daniel Beaulieu, Pham, Anh

Quantum optimization algorithms can be used to recreate unsupervised learning clustering of data by mapping the problem to a graph optimization problem and finding the minimum energy for a MaxCut problem formulation. This research tests the "Warm Start" variant of Quantum Approximate Optimization Algorithm (QAOA) versus the standard implementation of QAOA for unstructured clustering problems. The performance for IBM's new Qiskit Runtime API for speeding up optimization algorithms is also tested in terms of speed up and relative performance compared to the standard implementation of optimization algorithms. Warm-start QAOA performs better than any other optimization algorithm, though standard QAOA runs the fastest. This research also used a non-convex optimizer to relax the quadratic program for the Warm-start QAOA.

arXiv:2108.13464•Aug 30, 2021•7 citations

Systematic study on the dependence of the warm-start quantum approximate optimization algorithm on approximate solutions

Ken N. Okada, Hirofumi Nishi, Taichi Kosugi +1 more

Quantum approximate optimization algorithm (QAOA) is a promising hybrid quantum-classical algorithm to solve combinatorial optimization problems in the era of noisy intermediate-scale quantum computers. Recently it has been revealed that warm-start approaches can improve the performance of QAOA, where approximate solutions are obtained by classical algorithms in advance and incorporated into the initial state and/or unitary ansatz. In this work, we study in detail how the accuracy of approximate solutions affects the performance of the warm-start QAOA (WS-QAOA). We numerically find that in typical MAX-CUT problems, WS-QAOA achieves higher fidelity (probability that exact solutions are observed) and approximation ratio than QAOA as the Hamming distance of approximate solutions to the exact ones becomes smaller. We reveal that this could be quantitatively attributed to the initial state of the ansatz. We also solve MAX-CUT problems by WS-QAOA with approximate solutions obtained via QAOA, having higher fidelity and approximation ratio than QAOA especially when the circuit is relatively shallow. We believe that our study may deepen understanding of the performance of WS-QAOA and also provide a guide as to the necessary quality of approximate solutions.

arXiv:2209.02942•Scientific Reports•Jan 12, 2024•8 citations

Hybrid Quantum-HPC Solutions for Max-Cut: Bridging Classical and Quantum Algorithms

Ishan Patwardhan, Akhil Akkapelli

This research explores the integration of the Quantum Approximate Optimization Algorithm (QAOA) into Hybrid Quantum-HPC systems for solving the Max-Cut problem, comparing its performance with classical algorithms like brute-force search and greedy heuristics. We develop a theoretical model to analyze the time complexity, scalability, and communication overhead in hybrid systems. Using simulations, we evaluate QAOA's performance on small-scale Max-Cut instances, benchmarking its runtime, solution accuracy, and resource utilization. The study also investigates the scalability of QAOA with increasing problem size, offering insights into its potential advantages over classical methods for large-scale combinatorial optimization problems, with implications for future Quantum computing applications in HPC environments.

arXiv:2410.15626•Oct 21, 2024•0 citations

Integrating Quantum Approximate Optimization Algorithm with Machine Learning for Graph-Structured Problem Solving

Dr. Mamta Singh

The integration of quantum algorithms into machine learning pipelines offers a promising direction for addressing complex combinatorial optimization problems inherent in graph-structured data. This study investigates the use of the Quantum Approximate Optimization Algorithm (QAOA) as a quantum subroutine within a hybrid quantum–classical framework to enhance machine learning solutions for graph-based tasks. QAOA is employed to solve NP-hard graph optimization problems such as Max-Cut, graph coloring, and community detection, which are reformulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. The solutions provided by QAOA are then incorporated into machine learning models, such as Graph Neural Networks (GNNs) or clustering algorithms, as enriched features or optimized graph partitions. The hybrid approach is evaluated on benchmark datasets, demonstrating competitive accuracy and improved scalability in certain problem instances compared to purely classical methods. The findings highlight the potential of leveraging near-term quantum hardware for augmenting classical learning systems in domains such as logistics, social network analysis, and computational biology.

•Mar 25, 2026•0 citations

Multistart Methods for Quantum Approximate optimization

Ruslan Shaydulin, Ilya Safro, Jeffrey M. Larson

Hybrid quantum-classical algorithms such as the quantum approximate optimization algorithm (QAOA) are considered one of the most promising approaches for leveraging near-term quantum computers for practical applications. Such algorithms are often implemented in a variational form, combining classical optimization methods with a quantum machine to find parameters that maximize performance. The quality of the QAOA solution depends heavily on quality of the parameters produced by the classical optimizer. Moreover, the presence of multiple local optima makes it difficult for the classical optimizer to identify high-quality parameters. In this paper we study the use of a multistart optimization approach within QAOA to improve the performance of quantum machines on important graph clustering problems. We also demonstrate that reusing the optimal parameters from similar problems can improve the performance of classical optimization methods, expanding on similar results for MAXCUT.

arXiv:1905.08768•IEEE High Performance Extreme Computing Conference•Sep 1, 2019•109 citations

Warm-start adaptive-bias quantum approximate optimization algorithm

Yunlong Yu, Xiang‐Bin Wang, Nic Shannon +1 more

In the search for quantum advantage in real--world problems, one promising avenue is to use a quantum algorithm to improve on the solution found using an efficient classical algorithm. The quantum approximate optimization algorithm (QAOA) is particularly well adapted for such a "warm start" approach, and can be combined with the powerful classical Goemans-Williamson (GW) algorithms based on semi-definite programming. Nonetheless, the best way to leverage the power of the QAOA remains an open question. Here we propose a general model that describes a class of QAOA variants, and use it to explore routes to quantum advantages in a canonical optimization problem, MaxCut. For these algorithms we derive analytic expectation values of the cost Hamiltonian for the MaxCut problem in the level-1 case. Using these analytic results we obtain reliable averages over many instances for fairly large numbers of qubits. We find that the warm start adaptive-bias QAOA (WS-ab-QAOA) initialized by the GW algorithm outperforms previously proposed warm start variants on problems with $40$ to $180$ qubits. To assess whether a quantum advantage exists with this algorithm, we did numerical simulations with up to $1000$ qubits to see whether the level-1 WS-ab-QAOA can improve the GW solution for 3-regular graphs. In fact the improvement in the $1000$-qubit case even in level 1 can only be matched by the GW algorithm after about $10^{5.5}$ random projections performed after the semi-definite program stage. This work gives evidence that the final stage of optimization after an efficient classical algorithm has produced an approximate solution may be a place where quantum advantages can be realized.

arXiv:2503.20048•Physical Review A•Jul 14, 2025•4 citations
Quantum algorithms can be used to perform unsupervised machine learning tasks like data clustering by mapping the distance between data points to a graph optimization problem (i.e. MAXCUT) and finding optimal solution through energy minimization using hybrid quantum classical methods. Taking advantage of the IBM runtime environment, we benchmark the performance of the "Warm-Start" (ws) variant of Quantum Approximate Optimization Algorithm (QAOA) versus the standard implementation of QAOA and the variational quantum eigensolver (VQE) for unstructured clustering problems using real world dataset with respect to accuracy and execution time. Our numerical results show a strong speedup in execution time for different optimization algorithms using the IBM Qiskit Runtime architecture and increased speedup in classification accuracy in ws-QAOA algorithm
Quantum optimization algorithms can be used to recreate unsupervised learning clustering of data by mapping the problem to a graph optimization problem and finding the minimum energy for a MaxCut problem formulation. This research tests the "Warm Start" variant of Quantum Approximate Optimization Algorithm (QAOA) versus the standard implementation of QAOA for unstructured clustering problems. The performance for IBM's new Qiskit Runtime API for speeding up optimization algorithms is also tested in terms of speed up and relative performance compared to the standard implementation of optimization algorithms. Warm-start QAOA performs better than any other optimization algorithm, though standard QAOA runs the fastest. This research also used a non-convex optimizer to relax the quadratic program for the Warm-start QAOA.
Quantum approximate optimization algorithm (QAOA) is a promising hybrid quantum-classical algorithm to solve combinatorial optimization problems in the era of noisy intermediate-scale quantum computers. Recently it has been revealed that warm-start approaches can improve the performance of QAOA, where approximate solutions are obtained by classical algorithms in advance and incorporated into the initial state and/or unitary ansatz. In this work, we study in detail how the accuracy of approximate solutions affects the performance of the warm-start QAOA (WS-QAOA). We numerically find that in typical MAX-CUT problems, WS-QAOA achieves higher fidelity (probability that exact solutions are observed) and approximation ratio than QAOA as the Hamming distance of approximate solutions to the exact ones becomes smaller. We reveal that this could be quantitatively attributed to the initial state of the ansatz. We also solve MAX-CUT problems by WS-QAOA with approximate solutions obtained via QAOA, having higher fidelity and approximation ratio than QAOA especially when the circuit is relatively shallow. We believe that our study may deepen understanding of the performance of WS-QAOA and also provide a guide as to the necessary quality of approximate solutions.
This research explores the integration of the Quantum Approximate Optimization Algorithm (QAOA) into Hybrid Quantum-HPC systems for solving the Max-Cut problem, comparing its performance with classical algorithms like brute-force search and greedy heuristics. We develop a theoretical model to analyze the time complexity, scalability, and communication overhead in hybrid systems. Using simulations, we evaluate QAOA's performance on small-scale Max-Cut instances, benchmarking its runtime, solution accuracy, and resource utilization. The study also investigates the scalability of QAOA with increasing problem size, offering insights into its potential advantages over classical methods for large-scale combinatorial optimization problems, with implications for future Quantum computing applications in HPC environments.
The integration of quantum algorithms into machine learning pipelines offers a promising direction for addressing complex combinatorial optimization problems inherent in graph-structured data. This study investigates the use of the Quantum Approximate Optimization Algorithm (QAOA) as a quantum subroutine within a hybrid quantum–classical framework to enhance machine learning solutions for graph-based tasks. QAOA is employed to solve NP-hard graph optimization problems such as Max-Cut, graph coloring, and community detection, which are reformulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. The solutions provided by QAOA are then incorporated into machine learning models, such as Graph Neural Networks (GNNs) or clustering algorithms, as enriched features or optimized graph partitions. The hybrid approach is evaluated on benchmark datasets, demonstrating competitive accuracy and improved scalability in certain problem instances compared to purely classical methods. The findings highlight the potential of leveraging near-term quantum hardware for augmenting classical learning systems in domains such as logistics, social network analysis, and computational biology.
Hybrid quantum-classical algorithms such as the quantum approximate optimization algorithm (QAOA) are considered one of the most promising approaches for leveraging near-term quantum computers for practical applications. Such algorithms are often implemented in a variational form, combining classical optimization methods with a quantum machine to find parameters that maximize performance. The quality of the QAOA solution depends heavily on quality of the parameters produced by the classical optimizer. Moreover, the presence of multiple local optima makes it difficult for the classical optimizer to identify high-quality parameters. In this paper we study the use of a multistart optimization approach within QAOA to improve the performance of quantum machines on important graph clustering problems. We also demonstrate that reusing the optimal parameters from similar problems can improve the performance of classical optimization methods, expanding on similar results for MAXCUT.
In the search for quantum advantage in real--world problems, one promising avenue is to use a quantum algorithm to improve on the solution found using an efficient classical algorithm. The quantum approximate optimization algorithm (QAOA) is particularly well adapted for such a "warm start" approach, and can be combined with the powerful classical Goemans-Williamson (GW) algorithms based on semi-definite programming. Nonetheless, the best way to leverage the power of the QAOA remains an open question. Here we propose a general model that describes a class of QAOA variants, and use it to explore routes to quantum advantages in a canonical optimization problem, MaxCut. For these algorithms we derive analytic expectation values of the cost Hamiltonian for the MaxCut problem in the level-1 case. Using these analytic results we obtain reliable averages over many instances for fairly large numbers of qubits. We find that the warm start adaptive-bias QAOA (WS-ab-QAOA) initialized by the GW algorithm outperforms previously proposed warm start variants on problems with 404040 to 180180180 qubits. To assess whether a quantum advantage exists with this algorithm, we did numerical simulations with up to 100010001000 qubits to see whether the level-1 WS-ab-QAOA can improve the GW solution for 3-regular graphs. In fact the improvement in the 100010001000-qubit case even in level 1 can only be matched by the GW algorithm after about 105.510^{5.5}105.5 random projections performed after the semi-definite program stage. This work gives evidence that the final stage of optimization after an efficient classical algorithm has produced an approximate solution may be a place where quantum advantages can be realized.