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

Toward quantum advantage: Quantum variational algorithms for NP-hard approximations

Li, Austin Wenxuan

Published Jan 1, 2023• 0 citations
OpenAlex

Abstract

Quantum computing is a computing paradigm that promises computational advantage (and in some cases, supremacy) across many domains. Diverse applications across fields (cryptography, complexity theory, generative chemistry, finance) make the development and understanding of quantum algorithms extremely valuable. In this thesis, we consider the application of quantum computing to NP-hard approximation. Through the use of semidefinite relaxations of linear program formulations of the maximum graph bisection problem, and quantum-classical hybrid methods, we show that a novel quantum variational method (HTAAC-QSDP) provides solution quality equivalent to the best classical approximation algorithms. We simulate these hybrid circuits using feed-forward neural networks and determine that the solution quality (cut ratio) achieved is CQ/CSDP = 0.987 for the training graph and CQ/CSDP ≥ 0.97 for all other graphs, where CQ is the cut achieved by the quantum variational method and CSDP is the cut achieved by the classical solver. Our results experimentally verify the results provided in literature and show that quantum variational algorithms may be the path towards achieving near-term quantum advantage.

Related papers

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

Quantum Approaches to NP-Hard Combinatorial Optimization Problems: A Review

Charan Karnati, P. Venkata Subba Reddy

NP-hard problems are one of the most computationally intensive challenges in computer science, appearing in many domains such as logistics, cybersecurity, drug design, and financial modelling. Classical algorithms become impractical as problem size increases due to combinatorial explosion. This paper presents a structured framework for analysing quantum algorithms targeting NP-hard optimization problems, like the Traveling Salesman Problem (TSP), Max-Cut, and Boolean Satisfiability (SAT). We have developed a taxonomy which categorizes quantum approaches—quantum annealing, variational algorithms (QAOA/VQE), and Grover-based search—based on problem encoding strategies, resource requirements, and theoretical guarantees. From the comparative analysis of existing literature, we: 1) Map algorithm classes to problem domains (e.g., QAOA for Max-Cut, annealing for TSP) 2) Identify performance trade-offs between solution quality, qubit counts, and circuit depth 3) Analyse hardware compatibility constraints across NISQ platforms 4) Reveal fundamental scalability barriers including noise susceptibility and embedding overhead The framework establishes implementation guidelines for near- term quantum hardware and proposes hybrid quantum-classical pathways to bridge theoretical potential and practical deployment. This systematic analysis prioritizes research directions for achieving quantum advantage in combinatorial optimization.

•Aug 5, 2025•0 citations

Assessing the Efficacy of Hybrid Quantum-Classical Computing for Combinatorial Optimization: A Comparative Analysis of QAOA and Classical Solver

Ayan Khan

This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.

•May 7, 2026•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•20 citations

A quantum algorithm to train neural networks using low-depth circuits

Guillaume Verdon, Michael Broughton, Jacob Biamonte

Can near-term gate model based quantum processors offer quantum advantage for practical applications in the pre-fault tolerance noise regime? A class of algorithms which have shown some promise in this regard are the so-called classical-quantum hybrid variational algorithms. Here we develop a low-depth quantum algorithm to generative neural networks using variational quantum circuits. We introduce a method which employs the quantum approximate optimization algorithm as a subroutine in order produce then sample low-energy distributions of Ising Hamiltonians. We sample these states to train neural networks and demonstrate training convergence for numerically simulated noisy circuits with depolarizing errors of rates of up to $4\%$.

arXiv:1712.05304•Dec 14, 2017•135 citations

Training Variational Quantum Algorithms Is NP-Hard

Lennart Bittel, Martin Kliesch

Variational quantum algorithms are proposed to solve relevant computational problems on near term quantum devices. Popular versions are variational quantum eigensolvers and quantum approximate optimization algorithms that solve ground state problems from quantum chemistry and binary optimization problems, respectively. They are based on the idea of using a classical computer to train a parametrized quantum circuit. We show that the corresponding classical optimization problems are NP-hard. Moreover, the hardness is robust in the sense that, for every polynomial time algorithm, there are instances for which the relative error resulting from the classical optimization problem can be arbitrarily large assuming that P≠NP. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard. This elucidates that the classical optimization is intrinsically hard and does not merely inherit the hardness from the ground state problem. Our analysis shows that the training landscape can have many far from optimal persistent local minima This means gradient and higher order descent algorithms will generally converge to far from optimal solutions.

arXiv:2101.07267•Physical Review Letters•Sep 17, 2021•503 citations
Quantum computing is a computing paradigm that promises computational advantage (and in some cases, supremacy) across many domains. Diverse applications across fields (cryptography, complexity theory, generative chemistry, finance) make the development and understanding of quantum algorithms extremely valuable. In this thesis, we consider the application of quantum computing to NP-hard approximation. Through the use of semidefinite relaxations of linear program formulations of the maximum graph bisection problem, and quantum-classical hybrid methods, we show that a novel quantum variational method (HTAAC-QSDP) provides solution quality equivalent to the best classical approximation algorithms. We simulate these hybrid circuits using feed-forward neural networks and determine that the solution quality (cut ratio) achieved is CQ/CSDP = 0.987 for the training graph and CQ/CSDP ≥ 0.97 for all other graphs, where CQ is the cut achieved by the quantum variational method and CSDP is the cut achieved by the classical solver. Our results experimentally verify the results provided in literature and show that quantum variational algorithms may be the path towards achieving near-term quantum advantage.
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.
NP-hard problems are one of the most computationally intensive challenges in computer science, appearing in many domains such as logistics, cybersecurity, drug design, and financial modelling. Classical algorithms become impractical as problem size increases due to combinatorial explosion. This paper presents a structured framework for analysing quantum algorithms targeting NP-hard optimization problems, like the Traveling Salesman Problem (TSP), Max-Cut, and Boolean Satisfiability (SAT). We have developed a taxonomy which categorizes quantum approaches—quantum annealing, variational algorithms (QAOA/VQE), and Grover-based search—based on problem encoding strategies, resource requirements, and theoretical guarantees. From the comparative analysis of existing literature, we: 1) Map algorithm classes to problem domains (e.g., QAOA for Max-Cut, annealing for TSP) 2) Identify performance trade-offs between solution quality, qubit counts, and circuit depth 3) Analyse hardware compatibility constraints across NISQ platforms 4) Reveal fundamental scalability barriers including noise susceptibility and embedding overhead The framework establishes implementation guidelines for near- term quantum hardware and proposes hybrid quantum-classical pathways to bridge theoretical potential and practical deployment. This systematic analysis prioritizes research directions for achieving quantum advantage in combinatorial optimization.
This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.
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.
Can near-term gate model based quantum processors offer quantum advantage for practical applications in the pre-fault tolerance noise regime? A class of algorithms which have shown some promise in this regard are the so-called classical-quantum hybrid variational algorithms. Here we develop a low-depth quantum algorithm to generative neural networks using variational quantum circuits. We introduce a method which employs the quantum approximate optimization algorithm as a subroutine in order produce then sample low-energy distributions of Ising Hamiltonians. We sample these states to train neural networks and demonstrate training convergence for numerically simulated noisy circuits with depolarizing errors of rates of up to 4%4\%4%.
Variational quantum algorithms are proposed to solve relevant computational problems on near term quantum devices. Popular versions are variational quantum eigensolvers and quantum approximate optimization algorithms that solve ground state problems from quantum chemistry and binary optimization problems, respectively. They are based on the idea of using a classical computer to train a parametrized quantum circuit. We show that the corresponding classical optimization problems are NP-hard. Moreover, the hardness is robust in the sense that, for every polynomial time algorithm, there are instances for which the relative error resulting from the classical optimization problem can be arbitrarily large assuming that P≠NP. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard. This elucidates that the classical optimization is intrinsically hard and does not merely inherit the hardness from the ground state problem. Our analysis shows that the training landscape can have many far from optimal persistent local minima This means gradient and higher order descent algorithms will generally converge to far from optimal solutions.