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

Quantum Frontiers Journal

Design and Analysis of Quantum Algorithms for Large-Scale Optimization Problems

Laura Bianchi

Published Mar 28, 2024• 0 citations
OpenAlex

Abstract

Large-scale combinatorial and continuous optimisation problems remain intractable for classical algorithms as problem dimensionality scales. Quantum computing offers advantages through parallelism, amplitude amplification, and tunnelling, but practical realisation on near-term noisy intermediate-scale quantum (NISQ) devices demands careful algorithm design balancing advantage against noise resilience and circuit depth constraints. This paper presents the Quantum Optimisation Algorithm Suite (QOAS), a systematic framework across four algorithmic paradigms: Adaptive QAOA with dynamic depth scheduling; Variational Quantum Eigensolver (VQE) for QUBO problems; hybrid Quantum Annealing (QA); and Grover-enhanced Branch and Bound (GBB) for constrained integer programming. QOAS is benchmarked on five problem classes (MaxCut, TSP, Portfolio, Drug-Target, Feature Selection) across n = 12-84 qubits on IBM Quantum Eagle (127-qubit) and Falcon (27-qubit). Adaptive QAOA achieves approximation ratio 0.924 (SD = 0.018) for MaxCut at n = 48 -- outperforming standard QAOA (0.848) and Goemans-Williamson (0.878) at equivalent wall-clock time. GBB achieves 28.4x speedup over classical branch-and-bound for the n = 24 drug-target problem. QOAS provides systematic methodology for algorithm selection, circuit depth optimisation, and noise mitigation for NISQ workloads.

Related papers

Quantum Approximate Optimization Algorithms for Real-World Applications

Erik Lindberg, Ivan Lindberg

The Quantum Approximate Optimisation Algorithm (QAOA) has emerged as a leading candidate for near-term quantum advantage in combinatorial optimisation, but most evaluations remain confined to synthetic benchmarks such as random MaxCut instances. Translating QAOA to real-world problem instances -- with irregular graph structures, heterogeneous constraint types, and practical scale requirements -- introduces additional challenges including QUBO formulation overhead, hardware embedding costs, and the performance gap between QAOA on structured real instances vs. random benchmarks. This paper presents the Real-World QAOA (RW-QAOA) framework, a systematic methodology for applying QAOA to four real-world application domains: supply chain network optimisation, financial portfolio rebalancing, telecommunications frequency assignment, and traffic signal timing optimisation. RW-QAOA introduces three methodological contributions: a domain-adaptive QUBO formulator (DAQF) encoding real-world constraints as penalised QUBO terms with penalty coefficient auto-tuning; a warm-start initialisation strategy (WSIS) using classical heuristic solutions to seed QAOA parameter search; and a layered noise adaptation protocol (LNAP) adjusting circuit depth based on real-time device calibration data. RW-QAOA is evaluated on real problem instances from industry partners across all four domains on IBM Quantum Eagle (127-qubit). RW-QAOA achieves solution quality within 4.2% of classical exact solvers across all four domains, outperforming classical greedy heuristics by 12.4% (SD = 3.8%) on average. WSIS reduces QAOA parameter convergence iterations by 48.4%. LNAP improves approximation ratio by 8.4pp vs. fixed-depth QAOA under device noise variation.

Quantum Frontiers Journal•Mar 28, 2024•0 citations

Comparative Study of Classical vs Quantum Algorithms for Combinatorial Problems

Daniel Popescu, Helena Petrov

Claims of quantum advantage for combinatorial optimisation require rigorous comparison against state-of-the-art classical algorithms under controlled experimental conditions -- yet the quantum computing literature frequently benchmarks quantum methods against weak classical baselines such as greedy heuristics or random search, inflating apparent quantum advantage. This paper presents the Quantum-Classical Combinatorial Benchmark (QCCB), a rigorous comparative study of quantum optimisation algorithms (QAOA, VQE-QUBO, hybrid QA) against nine state-of-the-art classical algorithms (Goemans-Williamson SDP, simulated annealing, tabu search, CPLEX branch-and-bound, OR-Tools CP-SAT, Gurobi MIP, Benders decomposition, extremal optimisation, and population-based iterated local search) across six canonical combinatorial problem classes (MaxCut, Vertex Cover, Graph Colouring, Knapsack, Set Cover, and Weighted Max-SAT) at problem sizes n = 12 to n = 256. QCCB finds that no quantum algorithm consistently outperforms all classical baselines across all problem classes at current NISQ scale. QAOA with QOAS adaptive depth (Bianchi, 2024) outperforms all nine classical algorithms on MaxCut at n = 48 (approximation ratio 0.924 vs. GW 0.878). However, classical Gurobi MIP and CPLEX solve MaxCut exactly for n up to n = 84 within the same time budget, eliminating the QAOA advantage at moderate scale. QCCB provides nuanced guidance on problem classes, instance sizes, and time budgets where quantum algorithms offer genuine near-term advantage.

Quantum Frontiers Journal•Mar 28, 2024•0 citations

Dynamic adaptive quantum approximate optimization algorithm for shallow, noise-resilient circuits

Nikola Yanakiev, Normann Mertig, Christopher K. Long +1 more

The quantum approximate optimization algorithm (QAOA) is an appealing proposal to solve NP problems on noisy intermediate-scale quantum (NISQ) hardware. Making NISQ implementations of the QAOA resilient to noise requires short ansatz circuits with as few controlled- () gates as possible. Here we present the dynamic adaptive quantum approximate optimization algorithm (Dynamic-ADAPT-QAOA). Our algorithm significantly reduces the circuit depth and the count of standard ADAPT-QAOA, a leading proposal for near-term implementations of the QAOA. Throughout our algorithm, the decision to apply -intensive operations is made dynamically, based on algorithmic benefits. Using density-matrix simulations, we benchmark the noise resilience of ADAPT-QAOA and Dynamic-ADAPT-QAOA. We compute the gate-error probability p gate ★ below which these algorithms provide, on average, more accurate solutions than the classical, polynomial-time approximation algorithm by Goemans and Williamson. For small systems with six to ten qubits, we show that p gate ★ > 10 − 3 for Dynamic-ADAPT-QAOA. Compared to standard ADAPT-QAOA, this constitutes an order-of-magnitude improvement in noise resilience. This improvement should make Dynamic-ADAPT-QAOA viable for implementations on superconducting NISQ hardware, even in the absence of error mitigation. Published by the American Physical Society 2024

arXiv:2309.00047•Physical Review A•Mar 20, 2024•26 citations

Exploring Quantum Computing Algorithms for Optimization Problems

Ananya Krishnan, Edward Tanaka

Optimization problems are pervasive across various domains, including logistics, finance, machine learning, and operations research. Quantum computing has emerged as a promising frontier to address these challenges, offering potential speedups for certain classes of optimization tasks. This paper explores the development and application of quantum algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA), Variational Quantum Eigensolver (VQE), and Grover’s search algorithm, tailored for optimization. Recent advancements in hardware, hybrid quantum-classical approaches, and variational techniques have enabled practical implementations on Noisy Intermediate-Scale Quantum (NISQ) devices. Challenges such as noise, scalability, and performance limitations are also discussed. Through theoretical analysis and case studies, this work demonstrates how quantum computing can complement classical methods, paving the way for breakthroughs in solving complex optimization problems.

International Journal on Advanced Computer Theory and Engineering•Apr 15, 2025•1 citation

Hybrid Quantum-Classical Computing: Benchmarking Algorithm Performance on Near-Term Quantum Processors for Optimization Problems

Alvira Nursahira, Reni Safitri, Muhammad Alvin +3 more

This paper presents a qualitative analysis of hybrid quantum-classical computing approaches aimed at solving complex optimization problems using near-term quantum processors. Hybrid algorithms leverage the strengths of quantum and classical computing to tackle computationally intensive tasks often constrained by current quantum hardware limitations. Through an extensive literature review and synthesis of recent empirical studies, we benchmark various hybrid algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE), focusing on their performance, scalability, and practical applicability on noisy intermediate-scale quantum (NISQ) devices. The study highlights the advantages, challenges, and future prospects of integrating hybrid quantum-classical computation in optimization domains, providing a comprehensive framework and qualitative insights into benchmarking methodologies and critical performance metrics.

Jurnal Info Sains Informatika dan Sains•Aug 12, 2025•0 citations

Quantum Optimization Algorithms and Application

N. Manglani, Dhruv Solanki, Ankit Das

Optimization problems are fundamental across various scientific and industrial domains, from logistics and finance to machine learning and drug discovery. Classical optimization algorithms, such as gradient-based methods and heuristic approaches, often struggle with issues like slow convergence, getting trapped in local minima, and inefficiency in handling high-dimensional or combinatorial problems. Applying the concepts of quantum optimization with quantum mechanics algorithms presents viable substitutes with the potential for speedups and better solution quality. Among the significant quantum optimization techniques investigated in this paper are Grover's Search Algorithm, Variational Quantum Eigensolver (VQE), Quantum Annealing, and the Quantum Approximate Optimization Algorithm (QAOA). QAOA is designed for combinatorial optimization problems, blending quantum and classical techniques to approximate optimal solutions. VQE, widely used in quantum chemistry, employs a hybrid quantum-classical approach to determine ground-state energies efficiently. Grover's algorithm fastens up searching databases, indirectly aiding optimization tasks. Quantum annealing, implemented by systems like D-Wave, solves optimization problems by exploiting quantum tunneling to escape local minima. Despite their advantages, these quantum approaches face challenges, including hardware limitations, noise in quantum systems, and scalability concerns. However, these algorithms are expected to be essential in solving complicated optimization problems that are currently intractable by classical approaches when quantum technology develops.

Wiley eBooks•Oct 30, 2026•0 citations
Large-scale combinatorial and continuous optimisation problems remain intractable for classical algorithms as problem dimensionality scales. Quantum computing offers advantages through parallelism, amplitude amplification, and tunnelling, but practical realisation on near-term noisy intermediate-scale quantum (NISQ) devices demands careful algorithm design balancing advantage against noise resilience and circuit depth constraints. This paper presents the Quantum Optimisation Algorithm Suite (QOAS), a systematic framework across four algorithmic paradigms: Adaptive QAOA with dynamic depth scheduling; Variational Quantum Eigensolver (VQE) for QUBO problems; hybrid Quantum Annealing (QA); and Grover-enhanced Branch and Bound (GBB) for constrained integer programming. QOAS is benchmarked on five problem classes (MaxCut, TSP, Portfolio, Drug-Target, Feature Selection) across n = 12-84 qubits on IBM Quantum Eagle (127-qubit) and Falcon (27-qubit). Adaptive QAOA achieves approximation ratio 0.924 (SD = 0.018) for MaxCut at n = 48 -- outperforming standard QAOA (0.848) and Goemans-Williamson (0.878) at equivalent wall-clock time. GBB achieves 28.4x speedup over classical branch-and-bound for the n = 24 drug-target problem. QOAS provides systematic methodology for algorithm selection, circuit depth optimisation, and noise mitigation for NISQ workloads.
The Quantum Approximate Optimisation Algorithm (QAOA) has emerged as a leading candidate for near-term quantum advantage in combinatorial optimisation, but most evaluations remain confined to synthetic benchmarks such as random MaxCut instances. Translating QAOA to real-world problem instances -- with irregular graph structures, heterogeneous constraint types, and practical scale requirements -- introduces additional challenges including QUBO formulation overhead, hardware embedding costs, and the performance gap between QAOA on structured real instances vs. random benchmarks. This paper presents the Real-World QAOA (RW-QAOA) framework, a systematic methodology for applying QAOA to four real-world application domains: supply chain network optimisation, financial portfolio rebalancing, telecommunications frequency assignment, and traffic signal timing optimisation. RW-QAOA introduces three methodological contributions: a domain-adaptive QUBO formulator (DAQF) encoding real-world constraints as penalised QUBO terms with penalty coefficient auto-tuning; a warm-start initialisation strategy (WSIS) using classical heuristic solutions to seed QAOA parameter search; and a layered noise adaptation protocol (LNAP) adjusting circuit depth based on real-time device calibration data. RW-QAOA is evaluated on real problem instances from industry partners across all four domains on IBM Quantum Eagle (127-qubit). RW-QAOA achieves solution quality within 4.2% of classical exact solvers across all four domains, outperforming classical greedy heuristics by 12.4% (SD = 3.8%) on average. WSIS reduces QAOA parameter convergence iterations by 48.4%. LNAP improves approximation ratio by 8.4pp vs. fixed-depth QAOA under device noise variation.
Claims of quantum advantage for combinatorial optimisation require rigorous comparison against state-of-the-art classical algorithms under controlled experimental conditions -- yet the quantum computing literature frequently benchmarks quantum methods against weak classical baselines such as greedy heuristics or random search, inflating apparent quantum advantage. This paper presents the Quantum-Classical Combinatorial Benchmark (QCCB), a rigorous comparative study of quantum optimisation algorithms (QAOA, VQE-QUBO, hybrid QA) against nine state-of-the-art classical algorithms (Goemans-Williamson SDP, simulated annealing, tabu search, CPLEX branch-and-bound, OR-Tools CP-SAT, Gurobi MIP, Benders decomposition, extremal optimisation, and population-based iterated local search) across six canonical combinatorial problem classes (MaxCut, Vertex Cover, Graph Colouring, Knapsack, Set Cover, and Weighted Max-SAT) at problem sizes n = 12 to n = 256. QCCB finds that no quantum algorithm consistently outperforms all classical baselines across all problem classes at current NISQ scale. QAOA with QOAS adaptive depth (Bianchi, 2024) outperforms all nine classical algorithms on MaxCut at n = 48 (approximation ratio 0.924 vs. GW 0.878). However, classical Gurobi MIP and CPLEX solve MaxCut exactly for n up to n = 84 within the same time budget, eliminating the QAOA advantage at moderate scale. QCCB provides nuanced guidance on problem classes, instance sizes, and time budgets where quantum algorithms offer genuine near-term advantage.
The quantum approximate optimization algorithm (QAOA) is an appealing proposal to solve NP problems on noisy intermediate-scale quantum (NISQ) hardware. Making NISQ implementations of the QAOA resilient to noise requires short ansatz circuits with as few controlled- () gates as possible. Here we present the dynamic adaptive quantum approximate optimization algorithm (Dynamic-ADAPT-QAOA). Our algorithm significantly reduces the circuit depth and the count of standard ADAPT-QAOA, a leading proposal for near-term implementations of the QAOA. Throughout our algorithm, the decision to apply -intensive operations is made dynamically, based on algorithmic benefits. Using density-matrix simulations, we benchmark the noise resilience of ADAPT-QAOA and Dynamic-ADAPT-QAOA. We compute the gate-error probability p gate ★ below which these algorithms provide, on average, more accurate solutions than the classical, polynomial-time approximation algorithm by Goemans and Williamson. For small systems with six to ten qubits, we show that p gate ★ > 10 − 3 for Dynamic-ADAPT-QAOA. Compared to standard ADAPT-QAOA, this constitutes an order-of-magnitude improvement in noise resilience. This improvement should make Dynamic-ADAPT-QAOA viable for implementations on superconducting NISQ hardware, even in the absence of error mitigation. Published by the American Physical Society 2024
Optimization problems are pervasive across various domains, including logistics, finance, machine learning, and operations research. Quantum computing has emerged as a promising frontier to address these challenges, offering potential speedups for certain classes of optimization tasks. This paper explores the development and application of quantum algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA), Variational Quantum Eigensolver (VQE), and Grover’s search algorithm, tailored for optimization. Recent advancements in hardware, hybrid quantum-classical approaches, and variational techniques have enabled practical implementations on Noisy Intermediate-Scale Quantum (NISQ) devices. Challenges such as noise, scalability, and performance limitations are also discussed. Through theoretical analysis and case studies, this work demonstrates how quantum computing can complement classical methods, paving the way for breakthroughs in solving complex optimization problems.
This paper presents a qualitative analysis of hybrid quantum-classical computing approaches aimed at solving complex optimization problems using near-term quantum processors. Hybrid algorithms leverage the strengths of quantum and classical computing to tackle computationally intensive tasks often constrained by current quantum hardware limitations. Through an extensive literature review and synthesis of recent empirical studies, we benchmark various hybrid algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE), focusing on their performance, scalability, and practical applicability on noisy intermediate-scale quantum (NISQ) devices. The study highlights the advantages, challenges, and future prospects of integrating hybrid quantum-classical computation in optimization domains, providing a comprehensive framework and qualitative insights into benchmarking methodologies and critical performance metrics.
Optimization problems are fundamental across various scientific and industrial domains, from logistics and finance to machine learning and drug discovery. Classical optimization algorithms, such as gradient-based methods and heuristic approaches, often struggle with issues like slow convergence, getting trapped in local minima, and inefficiency in handling high-dimensional or combinatorial problems. Applying the concepts of quantum optimization with quantum mechanics algorithms presents viable substitutes with the potential for speedups and better solution quality. Among the significant quantum optimization techniques investigated in this paper are Grover's Search Algorithm, Variational Quantum Eigensolver (VQE), Quantum Annealing, and the Quantum Approximate Optimization Algorithm (QAOA). QAOA is designed for combinatorial optimization problems, blending quantum and classical techniques to approximate optimal solutions. VQE, widely used in quantum chemistry, employs a hybrid quantum-classical approach to determine ground-state energies efficiently. Grover's algorithm fastens up searching databases, indirectly aiding optimization tasks. Quantum annealing, implemented by systems like D-Wave, solves optimization problems by exploiting quantum tunneling to escape local minima. Despite their advantages, these quantum approaches face challenges, including hardware limitations, noise in quantum systems, and scalability concerns. However, these algorithms are expected to be essential in solving complicated optimization problems that are currently intractable by classical approaches when quantum technology develops.