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

Enhanced Distributed Variational Quantum Eigensolver for Large-Scale MaxCut Problem

Yuefeng Lin, Kun Wang, Qinyuan Zheng, Rui Zhang, Jing-Kai Fang, Tiejun Meng, Jingen Xiang, Cong Guo, Jun-Han Huang

quant-phSubmitted Dec 26, 2025• Announced Dec 29, 2025• 0 citations
v1 · Dec 26, 2025v2 · Jan 7, 2026
arXivHTMLPDF

Abstract

MaxCut is a canonical NP-hard combinatorial optimization problem in graph theory with broad applications ranging from physics to bioinformatics. Although variational quantum algorithms offer promising new approaches that may eventually outperform classical schemes, they suffer from resource constraints and trainability issues such as barren plateaus, making large-scale instances intractable on noisy intermediate-scale quantum devices. In this paper, we propose an enhanced distributed variational quantum eigensolver for large-scale MaxCut problems, which extends our prior distributed variational quantum eigensolver framework by integrating a novel hybrid classical-quantum perturbation strategy, enhances optimization scalability and efficiency. Our algorithm solves weighted MaxCut instances with up to 1000 vertices using only 10 qubits, and numerical results indicate that it consistently outperforms the Goemans-Williamson algorithm. We further employ a warm-start initialization strategy, seeding the algorithm with high-quality solutions from the Goemans-Williamson algorithm, with results confirming that the optimal classical solution can be effectively further improved. The practical utility of the proposed algorithm is further validated through its application to haplotype phasing on genome sequencing data of the human ABCA1 gene, producing high-quality haplotypes that rival those obtained by the Goemans-Williamson algorithm with $10^6$ projections. These results establish the proposed algorithm as a scalable, NISQ-compatible framework for near-term quantum-enhanced large-scale combinatorial optimization.

Comments
13 pages, 6 figures

Related papers

Towards large-scale quantum optimization solvers with few qubits

Marco Sciorilli, Lucas Borges, Taylor L. Patti +4 more

Quantum computers hold the promise of more efficient combinatorial optimization solvers, which could be game-changing for a broad range of applications. However, a bottleneck for materializing such advantages is that, in order to challenge classical algorithms in practice, mainstream approaches require a number of qubits prohibitively large for near-term hardware. Here we introduce a variational solver for MaxCut problems over $$m={{\mathcal{O}}}({n}^{k})$$ binary variables using only n qubits, with tunable k > 1. The number of parameters and circuit depth display mild linear and sublinear scalings in m, respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. Altogether, this leads to high quantum-solver performances. For instance, for m = 7000, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for m = 2000, experiments with n = 17 trapped-ion qubits feature MaxCut approximation ratios estimated to be beyond the hardness threshold 0.941. Our findings offer an interesting heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near-term quantum devices. Combinatorial optimization problems might be solvable more efficiently with quantum computing, but near-term quantum optimization solvers are limited in qubit size. Here, the authors propose and demonstrate a variational quantum algorithm that polynomially reduces the qubit overhead for applications like MaxCut.

arXiv:2401.09421•Nature Communications•Jan 8, 2025•47 citations

Pushing the Limits of Quantum Computing: Variational Algorithms for Solving NP-Hard Problems

Austin Wenxuan Li, Lilis Stianingsih, Ana Utami Zainal

This study explores the application of variational quantum algorithms to solve NP-hard combinatorial optimization problems, focusing specifically on the MaxBisection problem. The research introduces an enhanced hybrid quantum-classical framework, HTAAC-QSDP, which combines problem-informed ansatz design with semidefinite programming (SDP) relaxation and iterative optimization. Simulation results across multiple graph instances show that the proposed method achieves approximation ratios consistently above 0.95, approaching classical SDP benchmarks. Experiments also demonstrate the sensitivity of performance to key hyperparameters such as circuit depth, rotation scaling, and learning rate. Additionally, hardware implementation on IBM quantum devices reveals the model’s resilience under noise, provided that initialization and optimization strategies are carefully tuned. The findings suggest that variational quantum approaches can provide high-quality approximations for complex NP-hard problems, even in the noisy intermediate-scale quantum (NISQ) era. The results lay the groundwork for scalable quantum optimization frameworks and support the advancement of quantum advantage in real-world applications.

Ambidextrous•Aug 11, 2026•0 citations

Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA

Aniello Esposito, Tamuz Danzig

The Quantum approximate optimization algorithm (QAOA) is a leading hybrid classical-quantum algorithm for solving complex combinatorial optimization problems. QAOA-in-QAOA (QAOA2) uses a divide-and-conquer heuristic to solve large-scale Maximum Cut (MaxCut) problems, where many sub-graph problems can be solved in parallel. In this work, an implementation of the QAOA2method for the scalable solution of the MaxCut problem is presented, based on the Classiq platform. The framework is executed on an HPE-Cray EX supercomputer by means of the Message Passing Interface (MPI) and the SLURM workload manager. The limits of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA are investigated to understand if QAOA2could benefit from solving certain sub-graphs classically. Results from large-scale simulations of up to 33 qubits are presented, showing the advantage of QAOA in certain cases and the efficiency of the implementation, as well as the adequacy of the workflow in the preparation of real quantum devices. For the considered graphs, the best choice for the sub-graphs does not significantly improve results and is still outperformed by GW.

arXiv:2406.17383•IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 27, 2024•4 citations

An Adaptive Weighted Qite-Vqe Algorithm for Combinatorial Optimization Problems

Ningyi Xie, Xinwei Lee, Tiejin Chen +3 more

The variational quantum eigensolver (VQE) is an algorithm for finding the ground states of a given Hamiltonian. Its application to binary-formulated combinatorial optimization (CO) has been widely studied in recent years. However, typical VQE approaches for CO problems often suffer from local minima or barren plateaus, limiting their ability to achieve optimal solutions. The quantum imaginary time evolution (QITE) offers an alternative approach for effective ground-state preparation but requires large circuits to approximate non-unitary operations. Although compressed QITE (cQITE) reduces circuit depth, accumulated errors eventually cause energy increases. To address these challenges, we propose an Adaptive Weighted QITE-VQE (AWQV) algorithm that integrates the VQE gradients with the cQITE updates through an adaptive weighting scheme during optimization. In numerical simulations for MaxCut on unweighted regular graphs, AWQV achieves near-optimal approximation ratios, while for weighted Erdős-Rényi instances, it outperforms the classical Goemans-Williamson algorithm.

arXiv:2504.10651•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•1 citation

Tensor Network Assisted Distributed Variational Quantum Algorithm for Large Scale Combinatorial Optimization Problem

Yuhan Huang, Siyuan Jin, Yichi Zhang +3 more

Although quantum computing holds promise for solving Combinatorial Optimization Problems (COPs), the limited qubit capacity of NISQ hardware makes large-scale instances intractable. Conventional methods attempt to bridge this gap through decomposition or compression, yet they frequently fail to capture global correlations of subsystems, leading to solutions of limited quality. We propose the Distributed Variational Quantum Algorithm (DVQA) to overcome these limitations, enabling the solution of 1,000-variable instances on constrained hardware. A key innovation of DVQA is its use of the truncated higher-order singular value decomposition to preserve inter-variable dependencies without relying on complex long-range entanglement, leading to a natural form of noise localization where errors scale with subsystem size rather than total qubit count, thus reconciling scalability with accuracy. Theoretical bounds confirm the algorithm's robustness for p-local Hamiltonians. Empirically, DVQA achieves state-of-the-art performance in simulations and has been experimentally validated on the Wu Kong quantum computer for portfolio optimization. This work provides a scalable, noise-resilient framework that advances the timeline for practical quantum optimization algorithms.

quant-pharXiv:2601.13956•Jan 21, 2026•0 citations

Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms

Shuaiqun Pan, Yash J. Patel, Aneta Neumann +3 more

Variational quantum algorithms, such as the Recursive Quantum Approximate Optimization Algorithm (RQAOA), have become increasingly popular, offering promising avenues for employing Noisy Intermediate-Scale Quantum devices to address challenging combinatorial optimization tasks like the maximum cut problem. In this study, we utilize an evolutionary algorithm equipped with a unique fitness function. This approach targets hard maximum cut instances within the latent space of a Graph Autoencoder, identifying those that pose significant challenges or are particularly tractable for RQAOA, in contrast to the classic Goemans and Williamson algorithm. Our findings not only delineate the distinct capabilities and limitations of each algorithm but also expand our understanding of RQAOA's operational limits. Furthermore, the diverse set of graphs we have generated serves as a crucial benchmarking asset, emphasizing the need for more advanced algorithms to tackle combinatorial optimization challenges. Additionally, our results pave the way for new avenues in graph generation research, offering exciting opportunities for future explorations.

Genetic and Evolutionary Computation Conference (GECCO)•Jul 8, 2025•1 citation
MaxCut is a canonical NP-hard combinatorial optimization problem in graph theory with broad applications ranging from physics to bioinformatics. Although variational quantum algorithms offer promising new approaches that may eventually outperform classical schemes, they suffer from resource constraints and trainability issues such as barren plateaus, making large-scale instances intractable on noisy intermediate-scale quantum devices. In this paper, we propose an enhanced distributed variational quantum eigensolver for large-scale MaxCut problems, which extends our prior distributed variational quantum eigensolver framework by integrating a novel hybrid classical-quantum perturbation strategy, enhances optimization scalability and efficiency. Our algorithm solves weighted MaxCut instances with up to 1000 vertices using only 10 qubits, and numerical results indicate that it consistently outperforms the Goemans-Williamson algorithm. We further employ a warm-start initialization strategy, seeding the algorithm with high-quality solutions from the Goemans-Williamson algorithm, with results confirming that the optimal classical solution can be effectively further improved. The practical utility of the proposed algorithm is further validated through its application to haplotype phasing on genome sequencing data of the human ABCA1 gene, producing high-quality haplotypes that rival those obtained by the Goemans-Williamson algorithm with 10610^6106 projections. These results establish the proposed algorithm as a scalable, NISQ-compatible framework for near-term quantum-enhanced large-scale combinatorial optimization.
Quantum computers hold the promise of more efficient combinatorial optimization solvers, which could be game-changing for a broad range of applications. However, a bottleneck for materializing such advantages is that, in order to challenge classical algorithms in practice, mainstream approaches require a number of qubits prohibitively large for near-term hardware. Here we introduce a variational solver for MaxCut problems over m=O(nk)m={{\mathcal{O}}}({n}^{k})m=O(nk) binary variables using only n qubits, with tunable k > 1. The number of parameters and circuit depth display mild linear and sublinear scalings in m, respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. Altogether, this leads to high quantum-solver performances. For instance, for m = 7000, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for m = 2000, experiments with n = 17 trapped-ion qubits feature MaxCut approximation ratios estimated to be beyond the hardness threshold 0.941. Our findings offer an interesting heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near-term quantum devices. Combinatorial optimization problems might be solvable more efficiently with quantum computing, but near-term quantum optimization solvers are limited in qubit size. Here, the authors propose and demonstrate a variational quantum algorithm that polynomially reduces the qubit overhead for applications like MaxCut.
This study explores the application of variational quantum algorithms to solve NP-hard combinatorial optimization problems, focusing specifically on the MaxBisection problem. The research introduces an enhanced hybrid quantum-classical framework, HTAAC-QSDP, which combines problem-informed ansatz design with semidefinite programming (SDP) relaxation and iterative optimization. Simulation results across multiple graph instances show that the proposed method achieves approximation ratios consistently above 0.95, approaching classical SDP benchmarks. Experiments also demonstrate the sensitivity of performance to key hyperparameters such as circuit depth, rotation scaling, and learning rate. Additionally, hardware implementation on IBM quantum devices reveals the model’s resilience under noise, provided that initialization and optimization strategies are carefully tuned. The findings suggest that variational quantum approaches can provide high-quality approximations for complex NP-hard problems, even in the noisy intermediate-scale quantum (NISQ) era. The results lay the groundwork for scalable quantum optimization frameworks and support the advancement of quantum advantage in real-world applications.
The Quantum approximate optimization algorithm (QAOA) is a leading hybrid classical-quantum algorithm for solving complex combinatorial optimization problems. QAOA-in-QAOA (QAOA2) uses a divide-and-conquer heuristic to solve large-scale Maximum Cut (MaxCut) problems, where many sub-graph problems can be solved in parallel. In this work, an implementation of the QAOA2method for the scalable solution of the MaxCut problem is presented, based on the Classiq platform. The framework is executed on an HPE-Cray EX supercomputer by means of the Message Passing Interface (MPI) and the SLURM workload manager. The limits of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA are investigated to understand if QAOA2could benefit from solving certain sub-graphs classically. Results from large-scale simulations of up to 33 qubits are presented, showing the advantage of QAOA in certain cases and the efficiency of the implementation, as well as the adequacy of the workflow in the preparation of real quantum devices. For the considered graphs, the best choice for the sub-graphs does not significantly improve results and is still outperformed by GW.
The variational quantum eigensolver (VQE) is an algorithm for finding the ground states of a given Hamiltonian. Its application to binary-formulated combinatorial optimization (CO) has been widely studied in recent years. However, typical VQE approaches for CO problems often suffer from local minima or barren plateaus, limiting their ability to achieve optimal solutions. The quantum imaginary time evolution (QITE) offers an alternative approach for effective ground-state preparation but requires large circuits to approximate non-unitary operations. Although compressed QITE (cQITE) reduces circuit depth, accumulated errors eventually cause energy increases. To address these challenges, we propose an Adaptive Weighted QITE-VQE (AWQV) algorithm that integrates the VQE gradients with the cQITE updates through an adaptive weighting scheme during optimization. In numerical simulations for MaxCut on unweighted regular graphs, AWQV achieves near-optimal approximation ratios, while for weighted Erdős-Rényi instances, it outperforms the classical Goemans-Williamson algorithm.
Although quantum computing holds promise for solving Combinatorial Optimization Problems (COPs), the limited qubit capacity of NISQ hardware makes large-scale instances intractable. Conventional methods attempt to bridge this gap through decomposition or compression, yet they frequently fail to capture global correlations of subsystems, leading to solutions of limited quality. We propose the Distributed Variational Quantum Algorithm (DVQA) to overcome these limitations, enabling the solution of 1,000-variable instances on constrained hardware. A key innovation of DVQA is its use of the truncated higher-order singular value decomposition to preserve inter-variable dependencies without relying on complex long-range entanglement, leading to a natural form of noise localization where errors scale with subsystem size rather than total qubit count, thus reconciling scalability with accuracy. Theoretical bounds confirm the algorithm's robustness for p-local Hamiltonians. Empirically, DVQA achieves state-of-the-art performance in simulations and has been experimentally validated on the Wu Kong quantum computer for portfolio optimization. This work provides a scalable, noise-resilient framework that advances the timeline for practical quantum optimization algorithms.
Variational quantum algorithms, such as the Recursive Quantum Approximate Optimization Algorithm (RQAOA), have become increasingly popular, offering promising avenues for employing Noisy Intermediate-Scale Quantum devices to address challenging combinatorial optimization tasks like the maximum cut problem. In this study, we utilize an evolutionary algorithm equipped with a unique fitness function. This approach targets hard maximum cut instances within the latent space of a Graph Autoencoder, identifying those that pose significant challenges or are particularly tractable for RQAOA, in contrast to the classic Goemans and Williamson algorithm. Our findings not only delineate the distinct capabilities and limitations of each algorithm but also expand our understanding of RQAOA's operational limits. Furthermore, the diverse set of graphs we have generated serves as a crucial benchmarking asset, emphasizing the need for more advanced algorithms to tackle combinatorial optimization challenges. Additionally, our results pave the way for new avenues in graph generation research, offering exciting opportunities for future explorations.