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

International Database Engineering and Applications Symposium (IDEAS)

Avoiding blocking by scheduling transactions using quantum annealing

Tim Bittner, Sven Groppe

Published Aug 12, 2020• 31 citations
Publisher

Abstract

Quantum annealers are a special kind of quantum computers for solving optimization problems. In this paper, we investigate the benefits of quantum annealers in the field of transaction synchronization. In particular, we show how transactions using the 2-phase-locking protocol can be optimally distributed to any number of available machines to reduce transaction waiting times. Therefore an instance of the problem will be transformed into a formula that is accepted by quantum annealers. In an experimental evaluation, the runtime on a quantum annealer outperforms the runtime of traditional algorithms to solve combinatorial problems like simulated annealing already for small problem sizes.

DOI
10.1145/3410566.3410593

Related papers

Hardware Accelerating the Optimization of Transaction Schedules via Quantum Annealing by Avoiding Blocking.

Tim Bittner, Sven Groppe

The isolation property of database theory guarantees to avoid problems of not synchronized parallel execution of several transactions. In this paper we propose an algorithm for an optimal transaction schedule for the different cores of a multi-core CPU with minimal execution time ensuring the isolation property. Optimizing the transaction schedule is a combinatorial problem, which is ideal to be solved by quantum annealers as special form of quantum computers. In our contribution we show how to transform an instance of the transaction schedule problem into a formula that is accepted by quantum annealers including a proof of validity and optimality of the obtained result. Furthermore, we analyze the number of required qubits and the preprocessing time, and introduce an approach for caching formulas as result of preprocessing for the purpose of reducing the preprocessing time. In an experimental evaluation, the runtime on a quantum annealer outperforms the runtime of traditional algorithms to solve combinatorial problems like simulated annealing already for small problem sizes.

IEEE International Conference on Cloud Computing Technology and Science•Jan 1, 2020•15 citations

Optimizing Transaction Schedules on Universal Quantum Computers via Code Generation for Grover’s Search Algorithm

Sven Groppe, Jinghua Groppe

Quantum computers are known to be efficient for solving combinatorial problems like finding optimal schedules for processing transactions in parallel without blocking. We show how Grover’s search algorithm for quantum computers can be applied for finding an optimal transaction schedule via generating code from the problem instance. We compare our approach with existing approaches for traditional computers and quantum annealers in terms of preprocessing, runtime, space and code length complexity. Furthermore, we show by experiments the expected number of optimal solutions of this problem as well as suboptimal ones. With the help of an estimator of the number of solutions, we further speed up our optimizer for optimal and suboptimal transaction schedules.

International Database Engineering and Applications Symposium (IDEAS)•Jul 14, 2021•28 citations

Quantum-Enhanced Transaction Scheduling with Reduced Complexity via Solving QUBO Iteratively using a Locking Mechanism

Nitin Nayak, Alexandru Prisacaru, Umut Çalıkyılmaz +2 more

In this work, we investigate the problem of transaction scheduling under conflict constraints and present a hybrid quantum-classical approach to its optimisation.Our proposed algorithm uses the concept of locking the transaction to solve QUBO iteratively, which explores the search space over the different sets of transactions for efficient scheduling.Experiments have been conducted using gate-based quantum simulators with QAOA and classical solvers such as simulated annealing.Our findings suggest that reduced problem formulations (via locking mechanism) for a certain level of problem complexity significantly enhance the solvability of scheduling instances, potentially making them accessible to near-term quantum devices.

Workshop on Quantum Computing and Quantum-Inspired Technology for Data-Intensive Systems and Applications (Q-Data)•Jun 22, 2025•5 citations

Optimization Using Quantum Annealing: A Case Study in Logistics and Scheduling

Murali Krishna Pasupuleti

This study investigates the application of quantum annealing in solving logistics and scheduling problems, areas traditionally challenged by combinatorial complexity. Using a case study approach, quantum annealing was applied to optimize delivery routing and job-shop scheduling problems. The methodology incorporated D-Wave's quantum processing unit (QPU), and performance was benchmarked against classical simulated annealing. Results indicate a significant improvement in computational efficiency and solution optimality, particularly for mid-sized problem instances. The research identifies key parameters influencing performance and provides insights into hybrid quantum-classical integration. These findings contribute to the growing field of quantum computing applications in operations research. Keywords: Quantum annealing, logistics optimization, scheduling algorithms, quantum computing, operations research

International Journal of Academic and Industrial Research Innovations(IJAIRI)•Jun 27, 2025•0 citations

Efficient Combinatorial Optimization Using Quantum Annealing

Hristo N. Djidjev, Guillaume Chapuis, Georg Hahn +1 more

The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.

arXiv:1801.08653•Jan 26, 2018•27 citations

Practical Effectiveness of Quantum Annealing for Shift Scheduling Problem

Natsuki Hamada, Kazuhiro Saito, Hideyuki Kawashima

Quantum annealing (QA) is a novel computing approach for solving computationally demanding problems more rapidly than approaches using classical computers by exploiting parallelism in the variable state updates (spin updates). A number of previous studies have shown that QA performs well in benchmarking combinatorial optimization problems, but no works have evaluated QA in the shift scheduling problem. This paper formulates it for QA and evaluates the effectiveness of QA in comparison with other methods on a classical computer. We confirmed that QA is up to about 14 times faster than classical methods in obtaining high-quality solutions for several instances.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 1, 2022•1 citation
Quantum annealers are a special kind of quantum computers for solving optimization problems. In this paper, we investigate the benefits of quantum annealers in the field of transaction synchronization. In particular, we show how transactions using the 2-phase-locking protocol can be optimally distributed to any number of available machines to reduce transaction waiting times. Therefore an instance of the problem will be transformed into a formula that is accepted by quantum annealers. In an experimental evaluation, the runtime on a quantum annealer outperforms the runtime of traditional algorithms to solve combinatorial problems like simulated annealing already for small problem sizes.
The isolation property of database theory guarantees to avoid problems of not synchronized parallel execution of several transactions. In this paper we propose an algorithm for an optimal transaction schedule for the different cores of a multi-core CPU with minimal execution time ensuring the isolation property. Optimizing the transaction schedule is a combinatorial problem, which is ideal to be solved by quantum annealers as special form of quantum computers. In our contribution we show how to transform an instance of the transaction schedule problem into a formula that is accepted by quantum annealers including a proof of validity and optimality of the obtained result. Furthermore, we analyze the number of required qubits and the preprocessing time, and introduce an approach for caching formulas as result of preprocessing for the purpose of reducing the preprocessing time. In an experimental evaluation, the runtime on a quantum annealer outperforms the runtime of traditional algorithms to solve combinatorial problems like simulated annealing already for small problem sizes.
Quantum computers are known to be efficient for solving combinatorial problems like finding optimal schedules for processing transactions in parallel without blocking. We show how Grover’s search algorithm for quantum computers can be applied for finding an optimal transaction schedule via generating code from the problem instance. We compare our approach with existing approaches for traditional computers and quantum annealers in terms of preprocessing, runtime, space and code length complexity. Furthermore, we show by experiments the expected number of optimal solutions of this problem as well as suboptimal ones. With the help of an estimator of the number of solutions, we further speed up our optimizer for optimal and suboptimal transaction schedules.
In this work, we investigate the problem of transaction scheduling under conflict constraints and present a hybrid quantum-classical approach to its optimisation.Our proposed algorithm uses the concept of locking the transaction to solve QUBO iteratively, which explores the search space over the different sets of transactions for efficient scheduling.Experiments have been conducted using gate-based quantum simulators with QAOA and classical solvers such as simulated annealing.Our findings suggest that reduced problem formulations (via locking mechanism) for a certain level of problem complexity significantly enhance the solvability of scheduling instances, potentially making them accessible to near-term quantum devices.
This study investigates the application of quantum annealing in solving logistics and scheduling problems, areas traditionally challenged by combinatorial complexity. Using a case study approach, quantum annealing was applied to optimize delivery routing and job-shop scheduling problems. The methodology incorporated D-Wave's quantum processing unit (QPU), and performance was benchmarked against classical simulated annealing. Results indicate a significant improvement in computational efficiency and solution optimality, particularly for mid-sized problem instances. The research identifies key parameters influencing performance and provides insights into hybrid quantum-classical integration. These findings contribute to the growing field of quantum computing applications in operations research. Keywords: Quantum annealing, logistics optimization, scheduling algorithms, quantum computing, operations research
The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.
Quantum annealing (QA) is a novel computing approach for solving computationally demanding problems more rapidly than approaches using classical computers by exploiting parallelism in the variable state updates (spin updates). A number of previous studies have shown that QA performs well in benchmarking combinatorial optimization problems, but no works have evaluated QA in the shift scheduling problem. This paper formulates it for QA and evaluates the effectiveness of QA in comparison with other methods on a classical computer. We confirmed that QA is up to about 14 times faster than classical methods in obtaining high-quality solutions for several instances.