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

ACM Computing Surveys

Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study

Felix Gemeinhardt, Antonio Garmendía, Manuel Wimmer, Benjamin Weder, Frank Leymann

Published Sep 5, 2023• 31 citations
Publisher

Abstract

The application of quantum computing to combinatorial optimization problems is attracting increasing research interest, resulting in diverse approaches and research streams. This study aims at identifying, classifying, and understanding existing solution approaches as well as typical use cases in the field. The obtained classification schemes are based on a full-text analysis of 156 included papers. Our results can be used by researchers and practitioners to (i) better understand adaptations to and utilizations of existing gate-based and quantum annealing approaches and (ii) identify typical use cases for quantum computing in areas such as graph optimization, routing, and scheduling.

DOI
10.1145/3620668

Related papers

Unlocking Quantum Optimization: A Use Case Study on NISQ Systems

Sturm, Andreas, Bharadwaj Chowdary Mummaneni, Leon Rullkötter

The major advances in quantum computing over the last few decades have sparked great interest in applying it to solve the most challenging computational problems in a wide variety of areas. One of the most pronounced domains here are optimization problems and a number of algorithmic approaches have been proposed for their solution. For the current noisy intermediate-scale quantum (NISQ) computers the quantum approximate optimization algorithm (QAOA), the variational quantum eigensolver (VQE), and quantum annealing (QA) are the central algorithms for this problem class. The two former can be executed on digital gate-model quantum computers, whereas the latter requires a quantum annealer. Across all hardware architectures and manufactures, the quantum computers available today share the property of being too error-prone to reliably execute involved quantum circuits as they typically arise from quantum optimization algorithms. In order to characterize the limits of existing quantum computers, many component and system level benchmarks have been proposed. However, owing to the complex nature of the errors in quantum systems these benchmark fail to provide predictive power beyond simple quantum circuits and small examples. Application oriented benchmarks have been proposed to remedy this problem, but both, results from real quantum systems as well as use cases beyond constructed academic examples, remain very rare. This paper addresses precisely this gap by considering two industrial relevant use cases: one in the realm of optimizing charging schedules for electric vehicles, the other concerned with the optimization of truck routes. Our central contribution are systematic series of examples derived from these uses cases that we execute on different processors of the gate-based quantum computers of IBM as well as on the quantum annealer of D-Wave.

arXiv:2404.07171•Apr 10, 2024•5 citations

A Comprehensive Survey on Quantum Annealing: Applications, Challenges, and Future Research Directions

Rajeshwar Tripathi, Sahil Tomar, Sandeep Kumar

Quantum annealing has emerged as a transformative approach in solving combinatorial optimization problems by leveraging the principles of quantum mechanics. A comprehensive survey of quantum annealing is presented, delineating its foundational concepts, state-of-the-art advancements, and diverse applications across domains such as logistics, finance, machine learning, and energy optimization. Notable contributions include the introduction of a systematic benchmarking framework to evaluate quantum annealing against classical optimization techniques across metrics like time-to-target, scalability, and energy efficiency. Additionally, novel hybrid quantum-classical paradigms and hardware advancements are explored, addressing challenges in qubit connectivity, coherence, and noise resilience. Optimization problems are mapped to suitable quantum annealing platforms, offering practical guidelines for leveraging quantum technologies in real-world scenarios. Critical gaps in scalability and integration with machine learning are identified, with future research directions proposed to bridge these challenges. These findings provide a holistic understanding of quantum annealing's potential, offering a foundational resource for advancing quantum computing in optimization.

•Jan 7, 2025•6 citations

Quantum Computing for Scheduling Problems: A Survey

Sirine Ben Ammar, Bilel Marzouki, Olfa Belkahla Driss

In recent years, quantum computing has emerged as a rapidly advancing interdisciplinary field, attracting growing attention from both academia and industry owing to its fundamentally novel approach to information processing and its potential to achieve computational capabilities beyond the reach of classical systems. This paper presents a structured review of quantum computing approaches applied to scheduling problems, which are among the most challenging NP-hard optimization problems. We first introduce fundamental principles of quantum computing, including gate-based models, quantum annealing, and hybrid frameworks. We then explore how various scheduling problems such as job-shop, flow-shop, and project scheduling-are encoded into quantum models, particularly using QUBO formulations suitable for current quantum devices. Finally, we discuss key limitations such as hardware constraints and model scalability, and we identify research directions to advance quantumenhanced scheduling methods. By grounding theory in empirical case studies and highlighting near-term deployable solutions, this study bridges the gap between quantum algorithm development and practical scheduling demands, offering a roadmap for researchers and practitioners in quantum optimization.

IEEE Afro-Mediterranean Conference on Artificial Intelligence (AMCAI)•Oct 14, 2025•0 citations

Quantum Annealing for Combinatorial Optimization: Foundations, Architectures, Benchmarks, and Emerging Directions

Rudraksh Sharma, Ravi Katukam, Arjun Nagulapally

Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.

quant-pharXiv:2602.03101•International Journal for Research in Applied Science and Engineering Technology•Feb 4, 2026•3 citations

Quantum Annealing for Combinatorial Optimization in Large-Scale Network Routing

Jincheng Zhang

This paper investigates the application of quantum annealing to address the challenges of combinatorial optimization within large-scale network routing. Traditional classical algorithms frequently encounter significant computational bottlenecks when attempting to determine optimal routes across complex networks, often failing to scale effectively with increasing network size and complexity. Quantum annealing offers a potentially transformative approach by leveraging quantum mechanical effects to explore solution spaces more efficiently. This work outlines a methodology for mapping network routing problems – characterized by a vast number of possible routes – onto the quantum annealing hardware. We present a model for representing the problem, formulating it as an Ising model, and then detail the annealing process. The core claim is that quantum annealing can provide a viable solution for optimizing network routes, particularly in scenarios where classical methods are computationally intractable. We explore the underlying principles of quantum annealing, focusing on its ability to escape local minima and achieve a lower energy state, representing the optimal solution. The research aims to demonstrate the feasibility and potential advantages of employing quantum annealing in practical network routing applications, paving the way for more efficient and robust network designs.

•Sep 7, 2026•0 citations

Quantum Approaches to CICO Problems- A Survey of Current Solutions and Future Research Directions

Lalit Mohan Singh Negi, Sandeep Kumar

Quantum Computing is revolutionary paradigm that harnesses the principles of quantum mechanics such as superposition and entanglement to process the information in fundamentally new ways. It has shown potential across various fields, including Cryptography, Materials Science, Machine Learning, Optimization and many others. Among its many applications, Combinatorial Optimization problems stand out as a critical area where Quantum Computing can address problems that are often intractable for classical methods. This paper surveys current quantum approaches including Quantum Annealing, Variational Algorithms, Quantum Approximation Optimization Algorithm (QAOA) and asses their effectiveness in solving Classical Intractable Combinatorial Optimization (CICO) problems such as Max Cut Problem, Traveling Salesman Problem, Graph Coloring and Knapsack Problems. The paper explores the QAOA, approach to solve the CICO problems. Practical applications of quantum optimization approaches are highlighted in the fields such as finance, material science, communication networks. Additionally, the case studies demonstrate the algorithm's efficacy in real world scenarios. However, the paper also discusses the challenges that remain including issues related to noise, scalability and complexity of the algorithms. Finally, the survey discusses the future directions for research, emphasizing the potential of hybrid-quantum classical frameworks and the development of new quantum algorithms, aiming to enhance the practical applications in complex optimization scenarios. This survey provides valuable insights for researchers and practitioners interested in leveraging quantum advantages to solve combinatorial optimization problems effectively.

•Dec 27, 2024•2 citations
The application of quantum computing to combinatorial optimization problems is attracting increasing research interest, resulting in diverse approaches and research streams. This study aims at identifying, classifying, and understanding existing solution approaches as well as typical use cases in the field. The obtained classification schemes are based on a full-text analysis of 156 included papers. Our results can be used by researchers and practitioners to (i) better understand adaptations to and utilizations of existing gate-based and quantum annealing approaches and (ii) identify typical use cases for quantum computing in areas such as graph optimization, routing, and scheduling.
The major advances in quantum computing over the last few decades have sparked great interest in applying it to solve the most challenging computational problems in a wide variety of areas. One of the most pronounced domains here are optimization problems and a number of algorithmic approaches have been proposed for their solution. For the current noisy intermediate-scale quantum (NISQ) computers the quantum approximate optimization algorithm (QAOA), the variational quantum eigensolver (VQE), and quantum annealing (QA) are the central algorithms for this problem class. The two former can be executed on digital gate-model quantum computers, whereas the latter requires a quantum annealer. Across all hardware architectures and manufactures, the quantum computers available today share the property of being too error-prone to reliably execute involved quantum circuits as they typically arise from quantum optimization algorithms. In order to characterize the limits of existing quantum computers, many component and system level benchmarks have been proposed. However, owing to the complex nature of the errors in quantum systems these benchmark fail to provide predictive power beyond simple quantum circuits and small examples. Application oriented benchmarks have been proposed to remedy this problem, but both, results from real quantum systems as well as use cases beyond constructed academic examples, remain very rare. This paper addresses precisely this gap by considering two industrial relevant use cases: one in the realm of optimizing charging schedules for electric vehicles, the other concerned with the optimization of truck routes. Our central contribution are systematic series of examples derived from these uses cases that we execute on different processors of the gate-based quantum computers of IBM as well as on the quantum annealer of D-Wave.
Quantum annealing has emerged as a transformative approach in solving combinatorial optimization problems by leveraging the principles of quantum mechanics. A comprehensive survey of quantum annealing is presented, delineating its foundational concepts, state-of-the-art advancements, and diverse applications across domains such as logistics, finance, machine learning, and energy optimization. Notable contributions include the introduction of a systematic benchmarking framework to evaluate quantum annealing against classical optimization techniques across metrics like time-to-target, scalability, and energy efficiency. Additionally, novel hybrid quantum-classical paradigms and hardware advancements are explored, addressing challenges in qubit connectivity, coherence, and noise resilience. Optimization problems are mapped to suitable quantum annealing platforms, offering practical guidelines for leveraging quantum technologies in real-world scenarios. Critical gaps in scalability and integration with machine learning are identified, with future research directions proposed to bridge these challenges. These findings provide a holistic understanding of quantum annealing's potential, offering a foundational resource for advancing quantum computing in optimization.
In recent years, quantum computing has emerged as a rapidly advancing interdisciplinary field, attracting growing attention from both academia and industry owing to its fundamentally novel approach to information processing and its potential to achieve computational capabilities beyond the reach of classical systems. This paper presents a structured review of quantum computing approaches applied to scheduling problems, which are among the most challenging NP-hard optimization problems. We first introduce fundamental principles of quantum computing, including gate-based models, quantum annealing, and hybrid frameworks. We then explore how various scheduling problems such as job-shop, flow-shop, and project scheduling-are encoded into quantum models, particularly using QUBO formulations suitable for current quantum devices. Finally, we discuss key limitations such as hardware constraints and model scalability, and we identify research directions to advance quantumenhanced scheduling methods. By grounding theory in empirical case studies and highlighting near-term deployable solutions, this study bridges the gap between quantum algorithm development and practical scheduling demands, offering a roadmap for researchers and practitioners in quantum optimization.
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.
This paper investigates the application of quantum annealing to address the challenges of combinatorial optimization within large-scale network routing. Traditional classical algorithms frequently encounter significant computational bottlenecks when attempting to determine optimal routes across complex networks, often failing to scale effectively with increasing network size and complexity. Quantum annealing offers a potentially transformative approach by leveraging quantum mechanical effects to explore solution spaces more efficiently. This work outlines a methodology for mapping network routing problems – characterized by a vast number of possible routes – onto the quantum annealing hardware. We present a model for representing the problem, formulating it as an Ising model, and then detail the annealing process. The core claim is that quantum annealing can provide a viable solution for optimizing network routes, particularly in scenarios where classical methods are computationally intractable. We explore the underlying principles of quantum annealing, focusing on its ability to escape local minima and achieve a lower energy state, representing the optimal solution. The research aims to demonstrate the feasibility and potential advantages of employing quantum annealing in practical network routing applications, paving the way for more efficient and robust network designs.
Quantum Computing is revolutionary paradigm that harnesses the principles of quantum mechanics such as superposition and entanglement to process the information in fundamentally new ways. It has shown potential across various fields, including Cryptography, Materials Science, Machine Learning, Optimization and many others. Among its many applications, Combinatorial Optimization problems stand out as a critical area where Quantum Computing can address problems that are often intractable for classical methods. This paper surveys current quantum approaches including Quantum Annealing, Variational Algorithms, Quantum Approximation Optimization Algorithm (QAOA) and asses their effectiveness in solving Classical Intractable Combinatorial Optimization (CICO) problems such as Max Cut Problem, Traveling Salesman Problem, Graph Coloring and Knapsack Problems. The paper explores the QAOA, approach to solve the CICO problems. Practical applications of quantum optimization approaches are highlighted in the fields such as finance, material science, communication networks. Additionally, the case studies demonstrate the algorithm's efficacy in real world scenarios. However, the paper also discusses the challenges that remain including issues related to noise, scalability and complexity of the algorithms. Finally, the survey discusses the future directions for research, emphasizing the potential of hybrid-quantum classical frameworks and the development of new quantum algorithms, aiming to enhance the practical applications in complex optimization scenarios. This survey provides valuable insights for researchers and practitioners interested in leveraging quantum advantages to solve combinatorial optimization problems effectively.