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

A data-driven system for combinatorial optimization problems (本文)

カズヒロ サイトウ, Kazuhiro Saito, 和広 斉藤

Published Jan 1, 2023• 0 citations
OpenAlex

Abstract

In recent years, data-driven systems such as machine learning are expected to solve social problems.the data-driven systems need to connect to various databases to collect the necessary data.In addition, when the problem of utilizing the predicted results from machine learning involves combinatorial optimization, it is difficult to achieve the desired performance using existing classical optimization methods due to the large scale of the problem.To solve these issues, this thesis proposes a data-driven system for combinatorial optimization problems with a virtual integrated data platform by data virtualization and a high-performance optimization environment by quantum annealing.This system integrates multiple data sources into a single virtual database system through data virtualization and provides a unified interface to users without modifying existing data sources.Furthermore, quantum annealing, a metaheuristic for combinatorial optimization based on quantum effects, enables fast solution of combinatorial optimization problems that are difficult to solve with conventional classical computers.We have implemented the proposed data-driven system for several data sources and used an actual quantum annealing machine, in order to evaluate the impact of communication between the data virtualization system and data sources on the system performance and to quantitatively compare quantum annealing and classical methods.The evaluation results show that the proposed data-driven system is effective for large-scale data in data infrastructure environments where a single query processing engine shares multiple data sources, as well as when a single data source is partitioned into multiple data sources.We also show that quantum annealing is effective in the vehicle routing problem and the grouping problem as specific combinatorial optimization problems, and discuss the overall performance of the proposed data-driven system from data collection to solving these optimization problems.

Related papers

QCE'24 Tutorial: Quantum Annealing -- Emerging Exploration for Database Optimization

Nayak, Nitin, Manuel Schönberger, Valter Uotila +4 more

Quantum annealing is a meta-heuristic approach tailored to solve combinatorial optimization problems with quantum annealers. In this tutorial, we provide a fundamental and comprehensive introduction to quantum annealing and modern data management systems and show quantum annealing's potential benefits and applications in the realm of database optimization. We demonstrate how to apply quantum annealing for selected database optimization problems, which are critical challenges in many data management platforms. The demonstrations include solving join order optimization problems in relational databases, optimizing sophisticated transaction scheduling, and allocating virtual machines within cloud-based architectures with respect to sustainability metrics. On the one hand, the demonstrations show how to apply quantum annealing on key problems of database management systems (join order selection, transaction scheduling), and on the other hand, they show how quantum annealing can be integrated as a part of larger and dynamic optimization pipelines (virtual machine allocation). The goal of our tutorial is to provide a centralized and condensed source regarding theories and applications of quantum annealing technology for database researchers, practitioners, and everyone who wants to understand how to potentially optimize data management with quantum computing in practice. Besides, we identify the advantages, limitations, and potentials of quantum computing for future database and data management research.

arXiv:2411.04638•Nov 7, 2024•6 citations

Quantum annealing for vehicle routing and scheduling problems

Alex Syrichas

Metaheuristic approaches to solving combinatorial optimization problems have many attractions. They sidestep the issue of combinatorial explosion; they return good results; they are often conceptually simple and straight forward to implement. There are also shortcomings. Optimal solutions are not guaranteed; choosing the metaheuristic which best fits a problem is a matter of experimentation; and conceptual differences between metaheuristics make absolute comparisons of performance difficult. There is also the difficulty of configuration of the algorithm - the process of identifying precise values for the parameters which control the optimization process. Quantum annealing is a metaheuristic which is the quantum counterpart of the well known classical Simulated Annealing algorithm for combinatorial optimization problems. This research investigates the application of quantum annealing to the Vehicle Routing Problem, a difficult problem of practical significance within industries such as logistics and workforce scheduling. The work devises spin encoding schemes for routing and scheduling problem domains, enabling an effective quantum annealing algorithm which locates new solutions to widely used benchmarks. The performance of the metaheuristic is further improved by the development of an enhanced tuning approach using fitness clouds as behaviour models. The algorithm is shown to be further enhanced by taking advantage of multiprocessor environments, using threading techniques to parallelize the optimization workload. The work also shows quantum annealing applied successfully in an industrial setting to generate solutions to complex scheduling problems, results which created extra savings over an incumbent optimization technique. Components of the intellectual property rendered in this latter effort went on to secure a patent-protected status.

•May 28, 2026•2 citations

Quantum Annealing-based Solution for Combinatorial Optimization Problems

Jincheng Zhang

This paper explores the application of quantum annealing to solve combinatorial optimization problems. The core idea centers around mapping these problems onto a quantum annealing platform and utilizing the quantum effects to find optimal or near-optimal solutions. Specifically, we investigate the potential of improved parameter tuning and algorithmic modifications to enhance the effectiveness of quantum annealing for problems such as the Traveling Salesperson Problem (TSP) and the Knapsack Problem. While quantum annealing has shown promise, its practical performance remains limited, and this work aims to address this limitation through targeted algorithmic and parameter optimization. The central focus is on demonstrating a method for translating a classical combinatorial problem into a suitable form for quantum annealing, followed by a strategic approach to controlling the annealing process to guide the system toward a desired solution. The efficacy of this approach is evaluated conceptually, with a focus on outlining the necessary steps and considerations for successful implementation.

•Sep 6, 2026•0 citations

How to Solve Combinatorial Optimization Problems Using Real Quantum Machines: A Recent Survey

Sovanmonynuth Heng, Dongmin Kim, Tae-Kyung Kim +1 more

A combinatorial optimization problem (COP) is the problem of finding the optimal solution in a finite set. When the size of the feasible solution set is large, the complexity of the problem increases, and it is not easy to solve in a reasonable time with the current classical computer technology. Quantum annealing (QA) is a method that replaces classical simulated annealing (SA) methods that do not solve these cases. Therefore, several attempts have been made to solve this problem using a special-purpose quantum annealer to which the QA method is applied. In this survey, we analyze recent studies that solve real-scale COPs using quantum annealers. Through this, we discuss how to reduce the size of the COP to be input to overcome the hardware limitations of the existing quantum annealer. Additionally, we demonstrated the applicability of quantum annealer to COP on a practical scale by comparing and analyzing the results of the classical simulated annealing (SA) and QA method from each study.

IEEE Access•Jan 1, 2022•34 citations

Quantum annealing for combinatorial optimization: a benchmarking study

Seongmin Kim, Sang-Woo Ahn, In‐Saeng Suh +3 more

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.

arXiv:2504.06201•npj Quantum Information•May 16, 2025•70 citations

Hybrid Iterative Annealing Method Using a Quantum Annealer and a Classical Computer and Its Evaluation

Keisuke Fukada, Tatsuhiko Shirai, Nozomu Togawa

A combinatorial optimization problem is the problem of minimizing the energy function among many combinations of variables, which is often difficult to solve with conventional classical computers. Recently, Ising machines, including quantum annealers, have gained attention as a promising architecture for efficiently solving combinatorial optimization problems. Among various methods for solving such problems using Ising machines, one prominent approach is the three-stage annealing method. The approach effectively solves a combinatorial optimization problem, utilizing an initial solution, but it performs the annealing process only once. Repeating the annealing process several times may enhance the solution more efficiently. In this paper, we propose a novel hybrid iterative annealing method that consists of an initial process using a classical computer, an annealing process using a quantum annealer, and a correction process/selection process using a classical computer. The proposed method repeats the annealing process and the correction process/selection process until the solution is sufficiently converged. In the experimental evaluations through the three types of typical combinatorial optimization problems, the proposed method shows improvements by up to 54.0% compared to the three-stage annealing method.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Oct 7, 2024•0 citations
In recent years, data-driven systems such as machine learning are expected to solve social problems.the data-driven systems need to connect to various databases to collect the necessary data.In addition, when the problem of utilizing the predicted results from machine learning involves combinatorial optimization, it is difficult to achieve the desired performance using existing classical optimization methods due to the large scale of the problem.To solve these issues, this thesis proposes a data-driven system for combinatorial optimization problems with a virtual integrated data platform by data virtualization and a high-performance optimization environment by quantum annealing.This system integrates multiple data sources into a single virtual database system through data virtualization and provides a unified interface to users without modifying existing data sources.Furthermore, quantum annealing, a metaheuristic for combinatorial optimization based on quantum effects, enables fast solution of combinatorial optimization problems that are difficult to solve with conventional classical computers.We have implemented the proposed data-driven system for several data sources and used an actual quantum annealing machine, in order to evaluate the impact of communication between the data virtualization system and data sources on the system performance and to quantitatively compare quantum annealing and classical methods.The evaluation results show that the proposed data-driven system is effective for large-scale data in data infrastructure environments where a single query processing engine shares multiple data sources, as well as when a single data source is partitioned into multiple data sources.We also show that quantum annealing is effective in the vehicle routing problem and the grouping problem as specific combinatorial optimization problems, and discuss the overall performance of the proposed data-driven system from data collection to solving these optimization problems.
Quantum annealing is a meta-heuristic approach tailored to solve combinatorial optimization problems with quantum annealers. In this tutorial, we provide a fundamental and comprehensive introduction to quantum annealing and modern data management systems and show quantum annealing's potential benefits and applications in the realm of database optimization. We demonstrate how to apply quantum annealing for selected database optimization problems, which are critical challenges in many data management platforms. The demonstrations include solving join order optimization problems in relational databases, optimizing sophisticated transaction scheduling, and allocating virtual machines within cloud-based architectures with respect to sustainability metrics. On the one hand, the demonstrations show how to apply quantum annealing on key problems of database management systems (join order selection, transaction scheduling), and on the other hand, they show how quantum annealing can be integrated as a part of larger and dynamic optimization pipelines (virtual machine allocation). The goal of our tutorial is to provide a centralized and condensed source regarding theories and applications of quantum annealing technology for database researchers, practitioners, and everyone who wants to understand how to potentially optimize data management with quantum computing in practice. Besides, we identify the advantages, limitations, and potentials of quantum computing for future database and data management research.
Metaheuristic approaches to solving combinatorial optimization problems have many attractions. They sidestep the issue of combinatorial explosion; they return good results; they are often conceptually simple and straight forward to implement. There are also shortcomings. Optimal solutions are not guaranteed; choosing the metaheuristic which best fits a problem is a matter of experimentation; and conceptual differences between metaheuristics make absolute comparisons of performance difficult. There is also the difficulty of configuration of the algorithm - the process of identifying precise values for the parameters which control the optimization process. Quantum annealing is a metaheuristic which is the quantum counterpart of the well known classical Simulated Annealing algorithm for combinatorial optimization problems. This research investigates the application of quantum annealing to the Vehicle Routing Problem, a difficult problem of practical significance within industries such as logistics and workforce scheduling. The work devises spin encoding schemes for routing and scheduling problem domains, enabling an effective quantum annealing algorithm which locates new solutions to widely used benchmarks. The performance of the metaheuristic is further improved by the development of an enhanced tuning approach using fitness clouds as behaviour models. The algorithm is shown to be further enhanced by taking advantage of multiprocessor environments, using threading techniques to parallelize the optimization workload. The work also shows quantum annealing applied successfully in an industrial setting to generate solutions to complex scheduling problems, results which created extra savings over an incumbent optimization technique. Components of the intellectual property rendered in this latter effort went on to secure a patent-protected status.
This paper explores the application of quantum annealing to solve combinatorial optimization problems. The core idea centers around mapping these problems onto a quantum annealing platform and utilizing the quantum effects to find optimal or near-optimal solutions. Specifically, we investigate the potential of improved parameter tuning and algorithmic modifications to enhance the effectiveness of quantum annealing for problems such as the Traveling Salesperson Problem (TSP) and the Knapsack Problem. While quantum annealing has shown promise, its practical performance remains limited, and this work aims to address this limitation through targeted algorithmic and parameter optimization. The central focus is on demonstrating a method for translating a classical combinatorial problem into a suitable form for quantum annealing, followed by a strategic approach to controlling the annealing process to guide the system toward a desired solution. The efficacy of this approach is evaluated conceptually, with a focus on outlining the necessary steps and considerations for successful implementation.
A combinatorial optimization problem (COP) is the problem of finding the optimal solution in a finite set. When the size of the feasible solution set is large, the complexity of the problem increases, and it is not easy to solve in a reasonable time with the current classical computer technology. Quantum annealing (QA) is a method that replaces classical simulated annealing (SA) methods that do not solve these cases. Therefore, several attempts have been made to solve this problem using a special-purpose quantum annealer to which the QA method is applied. In this survey, we analyze recent studies that solve real-scale COPs using quantum annealers. Through this, we discuss how to reduce the size of the COP to be input to overcome the hardware limitations of the existing quantum annealer. Additionally, we demonstrated the applicability of quantum annealer to COP on a practical scale by comparing and analyzing the results of the classical simulated annealing (SA) and QA method from each study.
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.
A combinatorial optimization problem is the problem of minimizing the energy function among many combinations of variables, which is often difficult to solve with conventional classical computers. Recently, Ising machines, including quantum annealers, have gained attention as a promising architecture for efficiently solving combinatorial optimization problems. Among various methods for solving such problems using Ising machines, one prominent approach is the three-stage annealing method. The approach effectively solves a combinatorial optimization problem, utilizing an initial solution, but it performs the annealing process only once. Repeating the annealing process several times may enhance the solution more efficiently. In this paper, we propose a novel hybrid iterative annealing method that consists of an initial process using a classical computer, an annealing process using a quantum annealer, and a correction process/selection process using a classical computer. The proposed method repeats the annealing process and the correction process/selection process until the solution is sufficiently converged. In the experimental evaluations through the three types of typical combinatorial optimization problems, the proposed method shows improvements by up to 54.0% compared to the three-stage annealing method.