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:2401.09421 · Nature Communications

Towards large-scale quantum optimization solvers with few qubits

Marco Sciorilli, Lucas Borges, Taylor L. Patti, Diego García-Martín, Giancarlo Camilo, Animashree Anandkumar, Leandro Aolita

Published Jan 8, 2025• 47 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1038/s41467-024-55346-z

Related papers

A Variational Qubit-Efficient MaxCut Heuristic Algorithm

Yovav Tene-Cohen, Tomer Kelman, Ohad Lev +1 more

Abstract MaxCut is a key NP-hard combinatorial optimization problem. Quantum computing offers methods to solve such problems potentially better than classical counterparts, with the Quantum Approximate Optimization Algorithm (QAOA) being a state-of-the-art example. However, the performance of quantum methods is currently hindered by hardware noise and limited qubit volumes. We present a variational Qubit-Efficient MaxCut (QEMC) algorithm that requires only $$O(\log N)$$ O ( log N ) qubits to tackle graphs of size N , an exponential reduction compared to QAOA. We demonstrate cutting-edge performance for 32-node graph instances (5 qubits) on real superconducting hardware, and for graphs with up to 2048 nodes (11 qubits) via classical simulations. The QEMC algorithm is based on an innovative encoding scheme, with potentially broad applicability, that empowers it with strong noise resilience, but also enables its efficient classical simulation. As such, the QEMC algorithm provides a challenging benchmark for QAOA on noisy devices and offers a novel quantum-inspired approach.

arXiv:2308.10383•npj Quantum Information•Feb 16, 2026•3 citations

Performant near-term quantum combinatorial optimization

Titus Morris, Kaushik, Ananth, Roetteler, Martin +1 more

Combinatorial optimization is a promising application for near-term quantum computers, however, identifying performant algorithms suited to noisy quantum hardware remains as an important goal to potentially realizing quantum computational advantages. To address this we present a variational quantum algorithm for solving combinatorial optimization problems with linear-depth circuits. Our algorithm uses an ansatz composed of Hamiltonian generators designed to control each term in the target combinatorial function, along with parameter updates following a modified version of quantum imaginary time evolution. We evaluate this ansatz in numerical simulations that target solutions to the MAXCUT problem. The state evolution is shown to closely mimic imaginary time evolution, and its optimal-solution convergence is further improved using adaptive transformations of the classical Hamiltonian spectrum. With these innovations, the algorithm consistently converges to optimal solutions, with interesting highly-entangled dynamics along the way. We further demonstrate the success of this approach by performing optimization of a truncated version of our ansatz with up to 32 qubits in a trapped-ion quantum computer, using measurements from the quantum computer to train the ansatz and prepare optimal solutions with high fidelity in the majority of cases we consider. The success of these large-scale quantum circuit optimizations, in the presence of realistic hardware constraints and without error mitigation, mark significant progress on the path towards solving combinatorial problems using quantum computers. We conclude our performant and resource-minimal approach is a promising candidate for potential quantum computational advantages.

arXiv:2404.16135•Apr 24, 2024•1 citation

A Depth-Independent Linear Chain Ansatz for Large-Scale Quantum Approximate Optimization

Zixu Wang, Mandell, Jack, Yangyang Xu +1 more

Combinatorial optimization lies at the heart of numerous real-world applications. For a broad category of optimization problems, quantum computing is expected to exhibit quantum speed-up over classic computing. Among various quantum algorithms, the Quantum Approximate Optimization Algorithm (QAOA), as one of variational quantum algorithms, shows promise on demonstrating quantum advantage on noisy intermediate-scale quantum (NISQ) hardware. However, with increasing problem size, the circuit depth demanded by original QAOA scales rapidly and quickly surpasses the threshold at which meaningful results can be obtained. To address this challenge, in this work, we propose a variant of QAOA (termed linear chain QAOA) and demonstrate its advantages over original QAOA on paradigmatic MaxCut problems. In original QAOA, each graph edge is encoded with one entangling gate. In our ansatz, we locate a linear chain from the original MaxCut graph and place entangling gates sequentially along this chain. This linear-chain ansatz is featured by shallow quantum circuits and with the low execution time that scales independently of the problem size. Leveraging this ansatz, we demonstrate an approximation ratio of 0.78 (without post-processing) on non-hardware-native random regular MaxCut instances with 100 vertices in a digital quantum processor using 100 qubits. Our findings offer new insights into the design of hardware-efficient ansatz and point toward a promising route for tackling large-scale combinatorial optimization problems on NISQ devices.

arXiv:2509.17296•Sep 22, 2025•0 citations

Variational Quantum Algorithms for Combinatorial Optimization

Daniel F. Pérez-Ramírez

The promise of quantum computing to address complex problems requiring high computational resources has long been hindered by the intrinsic and demanding requirements of quantum hardware development. Nonetheless, the current state of quantum computing, denominated Noisy Intermediate-Scale Quantum (NISQ) era, has introduced algorithms and methods that are able to harness the computational power of current quantum computers with advantages over classical computers (referred to as quantum advantage). Achieving quantum advantage is of particular relevance for the combinatorial optimization domain, since it often implies solving an NP-Hard optimization problem. Moreover, combinatorial problems are highly relevant for practical application areas, such as operations research, or resource allocation problems. Among quantum computing methods, Variational Quantum Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to combinatorial optimization. We identify the Quantum Approximate Optimization Algorithm (QAOA) as the leading candidate for these problems. Furthermore, we implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes, demonstrating the potential and challenges of using VQAs in practical optimization tasks. We release our code, dataset and optimized circuit parameters under https://github.com/DanielFPerez/VQA-for-MaxCut.

arXiv:2407.06421•Jul 8, 2024•3 citations

Enhanced Distributed Variational Quantum Eigensolver for Large-Scale MaxCut Problem

Yuefeng Lin, Kun Wang, Qinyuan Zheng +6 more

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.

quant-pharXiv:2512.22056•Dec 29, 2025•0 citations

Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming

Friedrich Wagner, Jonas Nüßlein, Frauke Liers

To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization. However, when aiming at provable optimality, one has to rely on classical exact methods like integer programming. State-of-the-art integer programming algorithms can compute strong relaxation bounds even for hard instances, but may have to enumerate a large number of subproblems for determining an optimum solution. If the potential of quantum computing is realized, it can be expected that in particular finding high-quality solutions for hard problems can be done fast. Still, near-future quantum hardware considerably limits the size of treatable problems. In this work, we go one step into integrating the potentials of quantum and classical techniques for combinatorial optimization. We propose a hybrid heuristic for the weighted maximum-cut problem and for quadratic unconstrained binary optimization. The heuristic employs a linear programming relaxation, rendering it well-suited for integration into exact branch-and-cut algorithms. For large instances, we reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. Moreover, we improve the applicability of depth-1 QAOA, a parameterized quantum algorithm, by deriving a parameter estimate for arbitrary instances. We present numerous computational results from real quantum hardware.

arXiv:2302.05493•ACM Transactions on Quantum Computing•Jan 13, 2025•2 citations
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.
Abstract MaxCut is a key NP-hard combinatorial optimization problem. Quantum computing offers methods to solve such problems potentially better than classical counterparts, with the Quantum Approximate Optimization Algorithm (QAOA) being a state-of-the-art example. However, the performance of quantum methods is currently hindered by hardware noise and limited qubit volumes. We present a variational Qubit-Efficient MaxCut (QEMC) algorithm that requires only O(log⁡N)O(\log N)O(logN) O ( log N ) qubits to tackle graphs of size N , an exponential reduction compared to QAOA. We demonstrate cutting-edge performance for 32-node graph instances (5 qubits) on real superconducting hardware, and for graphs with up to 2048 nodes (11 qubits) via classical simulations. The QEMC algorithm is based on an innovative encoding scheme, with potentially broad applicability, that empowers it with strong noise resilience, but also enables its efficient classical simulation. As such, the QEMC algorithm provides a challenging benchmark for QAOA on noisy devices and offers a novel quantum-inspired approach.
Combinatorial optimization is a promising application for near-term quantum computers, however, identifying performant algorithms suited to noisy quantum hardware remains as an important goal to potentially realizing quantum computational advantages. To address this we present a variational quantum algorithm for solving combinatorial optimization problems with linear-depth circuits. Our algorithm uses an ansatz composed of Hamiltonian generators designed to control each term in the target combinatorial function, along with parameter updates following a modified version of quantum imaginary time evolution. We evaluate this ansatz in numerical simulations that target solutions to the MAXCUT problem. The state evolution is shown to closely mimic imaginary time evolution, and its optimal-solution convergence is further improved using adaptive transformations of the classical Hamiltonian spectrum. With these innovations, the algorithm consistently converges to optimal solutions, with interesting highly-entangled dynamics along the way. We further demonstrate the success of this approach by performing optimization of a truncated version of our ansatz with up to 32 qubits in a trapped-ion quantum computer, using measurements from the quantum computer to train the ansatz and prepare optimal solutions with high fidelity in the majority of cases we consider. The success of these large-scale quantum circuit optimizations, in the presence of realistic hardware constraints and without error mitigation, mark significant progress on the path towards solving combinatorial problems using quantum computers. We conclude our performant and resource-minimal approach is a promising candidate for potential quantum computational advantages.
Combinatorial optimization lies at the heart of numerous real-world applications. For a broad category of optimization problems, quantum computing is expected to exhibit quantum speed-up over classic computing. Among various quantum algorithms, the Quantum Approximate Optimization Algorithm (QAOA), as one of variational quantum algorithms, shows promise on demonstrating quantum advantage on noisy intermediate-scale quantum (NISQ) hardware. However, with increasing problem size, the circuit depth demanded by original QAOA scales rapidly and quickly surpasses the threshold at which meaningful results can be obtained. To address this challenge, in this work, we propose a variant of QAOA (termed linear chain QAOA) and demonstrate its advantages over original QAOA on paradigmatic MaxCut problems. In original QAOA, each graph edge is encoded with one entangling gate. In our ansatz, we locate a linear chain from the original MaxCut graph and place entangling gates sequentially along this chain. This linear-chain ansatz is featured by shallow quantum circuits and with the low execution time that scales independently of the problem size. Leveraging this ansatz, we demonstrate an approximation ratio of 0.78 (without post-processing) on non-hardware-native random regular MaxCut instances with 100 vertices in a digital quantum processor using 100 qubits. Our findings offer new insights into the design of hardware-efficient ansatz and point toward a promising route for tackling large-scale combinatorial optimization problems on NISQ devices.
The promise of quantum computing to address complex problems requiring high computational resources has long been hindered by the intrinsic and demanding requirements of quantum hardware development. Nonetheless, the current state of quantum computing, denominated Noisy Intermediate-Scale Quantum (NISQ) era, has introduced algorithms and methods that are able to harness the computational power of current quantum computers with advantages over classical computers (referred to as quantum advantage). Achieving quantum advantage is of particular relevance for the combinatorial optimization domain, since it often implies solving an NP-Hard optimization problem. Moreover, combinatorial problems are highly relevant for practical application areas, such as operations research, or resource allocation problems. Among quantum computing methods, Variational Quantum Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to combinatorial optimization. We identify the Quantum Approximate Optimization Algorithm (QAOA) as the leading candidate for these problems. Furthermore, we implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes, demonstrating the potential and challenges of using VQAs in practical optimization tasks. We release our code, dataset and optimized circuit parameters under https://github.com/DanielFPerez/VQA-for-MaxCut.
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.
To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization. However, when aiming at provable optimality, one has to rely on classical exact methods like integer programming. State-of-the-art integer programming algorithms can compute strong relaxation bounds even for hard instances, but may have to enumerate a large number of subproblems for determining an optimum solution. If the potential of quantum computing is realized, it can be expected that in particular finding high-quality solutions for hard problems can be done fast. Still, near-future quantum hardware considerably limits the size of treatable problems. In this work, we go one step into integrating the potentials of quantum and classical techniques for combinatorial optimization. We propose a hybrid heuristic for the weighted maximum-cut problem and for quadratic unconstrained binary optimization. The heuristic employs a linear programming relaxation, rendering it well-suited for integration into exact branch-and-cut algorithms. For large instances, we reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. Moreover, we improve the applicability of depth-1 QAOA, a parameterized quantum algorithm, by deriving a parameter estimate for arbitrary instances. We present numerous computational results from real quantum hardware.