Learning the problem structure at multiple levels of coarseness to inform the decomposition-based hybrid quantum-classical combinatorial optimization solvers is a promising approach to scaling up variational approaches. We introduce a multilevel algorithm reinforced with the spectral graph representation learning-based accelerator to tackle large-scale graph maximum cut instances and fused with several versions of the quantum approximate optimization algorithm (QAOA) and QAOA-inspired algorithms. The graph representation learning model utilizes the idea of QAOA variational parameters concentration and substantially improves the performance of QAOA. We demonstrate the potential of using multilevel QAOA and representation learning-based approaches on extensive graphs by achieving high-quality solutions much faster. Reproducibility: Our source code and results are available at https://github.com/bachbao/MLQAOA.
Learning the problem structure at multiple levels of coarseness to inform the decomposition-based hybrid quantum-classical combinatorial optimization solvers is a promising approach to scaling up variational approaches. We introduce a multilevel algorithm reinforced with the spectral graph representation learning-based accelerator to tackle large-scale graph maximum cut instances and fused with several versions of the quantum approximate optimization algorithm (QAOA) and QAOA-inspired algorithms. The graph representation learning model utilizes the idea of QAOA variational parameters concentration and substantially improves the performance of QAOA. We demonstrate the potential of using multilevel QAOA and representation learning-based approaches on extensive graphs by achieving high-quality solutions much faster. Reproducibility: Our source code and results are available at https://github.com/bachbao/MLQAOA.
Combinatorial optimization is one of the fields where near term quantum devices are being utilized with hybrid quantum-classical algorithms to demonstrate potentially practical applications of quantum computing. One of the most well studied problems in combinatorial optimization is the Max-Cut problem. The problem is also highly relevant to quantum and other types of “post Moore” architectures due to its similarity with the Ising model and other reasons. In this paper, we introduce a scalable hybrid multilevel approach to solve large instances of Max-Cut using both classical only solvers and quantum approximate optimization algorithm (QAOA). We compare the results of our solver to existing state of the art large-scale Max-Cut solvers. We demonstrate excellent performance of both classical and hybrid quantum-classical approaches and show that using QAOA within our framework is comparable to classical approaches. Reproducibility: Our solver is publicly available at https://github.com/angone/MLMax-cut.
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.
Abstract The quantum approximate optimization algorithm (QAOA) is a hybrid quantum–classical algorithm to solve binary-variable optimization problems. Due to the short circuit depth and its expected robustness to systematic errors it is a promising candidate likely to run on near-term quantum devices. We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives. When comparing solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we utilize performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. In particular for three-regular random graphs, QAOA performance shows improvement by up to two orders of magnitude compared to previous estimates, strongly reducing the performance gap with classical alternatives. This was possible by reducing the number of function evaluations per iteration and optimizing the variational parameters on small graph instances and transferring to large via training. Because QAOA’s performance guarantees are only known for limited applications and contexts, we utilize a framework for the search for quantum advantage which incorporates a large number of problem instances and all three classical solver modalities: exact, approximate, and heuristic.
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.
Graph-based combinatorial optimization problems are computationally challenging for classical optimization techniques due to their NP-hard nature. This paper proposes a novel Quantum-Assisted Hybrid Optimization Algorithm (QAHOA) that integrates the Quantum Approximate Optimization Algorithm (QAOA), spectral graph theory, and classical optimization strategies for graph-based combinatorial optimization. The developed framework uses spectral initialization via the graph Laplacian Fiedler vector to provide structurally informed starting variational parameters, aiming to stabilize the parameter search space and improve convergence trajectories under noisy conditions. The mathematical framework, alongside a convergence analysis to first-order stationary points, is provided to establish theoretical baseline properties. Evaluated on synthetic Erdős–Rényi random graph instances, the current study serves as a preliminary, small-to-medium-scale proof-of-concept. Controlled evaluations demonstrate that the proposed QAHOA achieves marginal yet stable and statistically significant improvements in mean cut values and approximation ratios over classical Greedy heuristics, Simulated Annealing, the standard QAOA, and Warm-Start QAOA. Formal paired hypothesis testing mathematically verifies the stability of the framework, while preliminary 4-qubit hardware executions demonstrate baseline architectural compatibility under physical NISQ noise channels.
The Quantum Approximate Optimization Algorithm (QAOA) and its variants are leading algorithms to help solve challenging combinatorial optimization problems. QAOA maps these problems to Ising Hamiltonians such that their ground state is the desired solution. Candidate solutions are then drawn from a variational quantum circuit. The performance of QAOA hinges on a set of variational angles. However, finding good angles is an instance-specific and computationally expensive non-convex classical optimization task. Here, we learn the mapping from the problem instance to high-quality QAOA angles. Our learned models replace the per-instance optimization, that we call the solver, with a single forward pass that is several orders of magnitude faster than the solver with a near identical quality. Our models further generalize to unseen topologies such as Barabási-Albert and 2D grid graphs. Experiments on quantum hardware confirm that QAOA samples with angles produced by our open-source models are indistinguishable from solver angles. Crucially, models sensitive to the topology of the problem instance increase the quality of the QAOA angles. Our work amortizes a major bottleneck in QAOA by an up-front data generation and training cost. Importantly, this cost can be amortized over time in settings where many similar problems are optimized on a regular basis, as is often the case in applications for industry.