Emerging quantum processors provide an opportunity to explore new approaches for solving traditional problems in the Post Moore's law supercomputing era. However, the limited number of qubits makes it infeasible to tackle massive real-world datasets directly in the near future, leading to new challenges in utilizing these quantum processors for practical purposes. Hybrid quantum-classical algorithms that leverage both quantum and classical types of devices are considered as one of the main strategies to apply quantum computing to large-scale problems. In this paper, we advocate the use of multilevel frameworks for combinatorial optimization as a promising general paradigm for designing hybrid quantum-classical algorithms. In order to demonstrate this approach, we apply this method to two well-known combinatorial optimization problems, namely, the Graph Partitioning Problem, and the Community Detection Problem. We develop hybrid multilevel solvers with quantum local search on D-Wave's quantum annealer and IBM's gate-model based quantum processor. We carry out experiments on graphs that are orders of magnitudes larger than the current quantum hardware size and observe results comparable to state-of-the-art solvers.
Emerging quantum processors provide an opportunity to explore new approaches for solving traditional problems in the Post Moore's law supercomputing era. However, the limited number of qubits makes it infeasible to tackle massive real-world datasets directly in the near future, leading to new challenges in utilizing these quantum processors for practical purposes. Hybrid quantum-classical algorithms that leverage both quantum and classical types of devices are considered as one of the main strategies to apply quantum computing to large-scale problems. In this paper, we advocate the use of multilevel frameworks for combinatorial optimization as a promising general paradigm for designing hybrid quantum-classical algorithms. In order to demonstrate this approach, we apply this method to two well-known combinatorial optimization problems, namely, the Graph Partitioning Problem, and the Community Detection Problem. We develop hybrid multilevel solvers with quantum local search on D-Wave's quantum annealer and IBM's gate-model based quantum processor. We carry out experiments on graphs that are orders of magnitudes larger than the current quantum hardware size and observe results comparable to state-of-the-art solvers.
Emerging quantum processors provide an opportunity to explore new approaches for solving traditional problems in the post Moore’s law supercomputing era. However, the limited number of qubits makes it infeasible to tackle massive real-world datasets directly in the near future, leading to new challenges in utilizing these quantum processors for practical purposes. Hybrid quantum-classical algorithms that leverage both quantum and classical types of devices are considered as one of the main strategies to apply quantum computing to large-scale problems. In this article, we advocate the use of multilevel frameworks for combinatorial optimization as a promising general paradigm for designing hybrid quantum-classical algorithms. To demonstrate this approach, we apply this method to two well-known combinatorial optimization problems, namely, the Graph Partitioning Problem, and the Community Detection Problem. We develop hybrid multilevel solvers with quantum local search on D-Wave’s quantum annealer and IBM’s gate-model based quantum processor. We carry out experiments on graphs that are orders of magnitude larger than the current quantum hardware size, and we observe results comparable to state-of-the-art solvers in terms of quality of the solution. Reproducibility : Our code and data are available at Reference [1].
Combinatorial optimization is one of the fields where near term quantum devices are being utilized with hybrid quantum-classical algorithms to demonstrate potentially practical applications of quantum computing. One of the most well studied problems in combinatorial optimization is the Max-Cut problem. The problem is also highly relevant to quantum and other types of “post Moore” architectures due to its similarity with the Ising model and other reasons. In this paper, we introduce a scalable hybrid multilevel approach to solve large instances of Max-Cut using both classical only solvers and quantum approximate optimization algorithm (QAOA). We compare the results of our solver to existing state of the art large-scale Max-Cut solvers. We demonstrate excellent performance of both classical and hybrid quantum-classical approaches and show that using QAOA within our framework is comparable to classical approaches. Reproducibility: Our solver is publicly available at https://github.com/angone/MLMax-cut.
Combinatorial optimization problems on (hyper)graphs are ubiquitous in science and industry. Because many of these problems are NP-hard, development of sophisticated heuristics is of utmost importance for practical problems. In recent years, the emergence of Noisy Intermediate-Scale Quantum (NISQ) computers has opened up the opportunity to dramaticaly speedup combinatorial optimization. However, the adoption of NISQ devices is impeded by their severe limitations, both in terms of the number of qubits, as well as in their quality. NISQ devices are widely expected to have no more than hundreds to thousands of qubits with very limited error-correction, imposing a strict limit on the size and the structure of the problems that can be tackled directly. A natural solution to this issue is hybrid quantum-classical algorithms that combine a NISQ device with a classical machine with the goal of capturing “the best of both worlds”.\nBeing motivated by lack of high quality optimization solvers for hypergraph partitioning, in this thesis, we begin by discussing classical multilevel approaches for this problem. We present a novel relaxation-based vertex similarity measure termed algebraic distance for hypergraphs and the coarsening schemes based on it. Extending the multilevel method to include quantum optimization routines, we present Quantum Local Search (QLS) – a hybrid iterative improvement approach that is inspired by the classical local search approaches. Next, we introduce the Multilevel Quantum Local Search (ML-QLS) that incorporates the quantum-enhanced iterative improvement scheme introduced in QLS within the multilevel framework, as well as several techniques to further understand and improve the effectiveness of Quantum Approximate Optimization Algorithm used throughout our work.
Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did not show such an advantage over classical methods in past benchmarking studies. Recent advancements in QA with more than 5000 qubits, enhanced qubit connectivity, and the hybrid architecture promise to realize the quantum advantage. Here, we use a quantum annealer with state-of-the-art techniques and benchmark its performance against classical solvers. To compare their performance, we solve over 50 optimization problem instances represented by large and dense Hamiltonian matrices using quantum and classical solvers. The results demonstrate that a state-of-the-art quantum solver has higher accuracy (~0.013%) and a significantly faster problem-solving time (~6561×) than the best classical solver. Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations, for achieving high accuracy and substantially reduced problem solving time in large-scale real-world optimization problems.
Combinatorial optimization problems play a vital role in computer science and engineering, with applications in logistics, network design, finance, and resource allocation. However, many of these problems are NP-hard, making them computationally expensive to solve using classical optimization techniques, especially for large-scale instances. In recent years, quantum computing has emerged as a promising paradigm capable of addressing these limitations by leveraging quantum mechanical principles such as superposition and entanglement. This study investigates the application of quantum computing for solving combinatorial optimization problems, with a focus on algorithm design, complexity analysis, and real-world applicability. The research primarily employs the Quantum Approximate Optimization Algorithm (QAOA) and Grover's search algorithm to solve representative problems such as Max-Cut and the Knapsack problem. The performance of these algorithms is evaluated using key metrics including accuracy, execution time, and approximation ratio, and is compared with classical optimization techniques. The results demonstrate that QAOA is capable of generating near-optimal solutions, achieving accuracy levels of up to 93% for small problem instances. However, the study also highlights the challenges associated with current quantum systems, including noise, limited qubit availability, and increased execution time. Comparative analysis reveals that while classical methods remain more efficient for small-scale problems, quantum algorithms show significant potential for scalability and handling complex optimization tasks. The findings suggest that hybrid quantum-classical approaches offer a practical solution in the current Noisy Intermediate-Scale Quantum (NISQ) era. The study concludes that although quantum computing is still evolving, it holds strong potential for transforming combinatorial optimization in the future.
Abstract Emerging quantum technologies represent a promising alternative for solving hard combinatorial problems in the post-Moore’s law era. For practical purposes, however, the current number of qubits limits the direct applicability to larger real-world instances in the near-term future. Therefore, a promising strategy to overcome this issue is represented by hybrid quantum classical algorithms which leverage classical as well as quantum devices. One prominent example of a hard computational problem is the community detection problem: a partition of a graph into distinct communities such that the ratio between intra-community and inter-community connectivity is maximized. In this paper, we explore the current potential of quantum annealing and gate-based quantum technologies to solve the community detection problem for an arbitrary number of communities. For this purpose, existing algorithms are (re-)implemented and new hybrid algorithms, that can be run on gate-model devices, are proposed. Their performance on standardized benchmark graphs has been evaluated and compared to the one of a state-of-the-art classical heuristic algorithm. Although no quantum speed-up has been achieved, the existing quantum annealing-based methods as well as the novel hybrid algorithms for gate-based quantum computers yield modularity values, which are similar to those of the classical heuristic. However, the modular architecture of the used algorithms allows for fast utilization of more powerful quantum technologies once they become available.Reproducibility:Our code and data are publicly available (Github in Quantum Modularization. https://github.com/jku-win se/quantum_modularization 2021).