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)

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

Sven Groppe, Jinghua Groppe

Published Jul 14, 2021• 28 citations
Publisher

Abstract

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.

DOI
10.1145/3472163.3472164

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

Avoiding blocking by scheduling transactions using quantum annealing

Tim Bittner, Sven Groppe

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.

International Database Engineering and Applications Symposium (IDEAS)•Aug 12, 2020•31 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

A Quantum Global Optimization Algorithm: Application to the Knapsack Problem

Mohamed Yassine Cherif, Wided Lejouad Chaari, Olfa Belkahla Driss

Abstract Solving combinatorial optimization problems represents a challenge for researchers, especially hard NP-complete problems that are commonly handled through heuristic methods providing approximate solutions. The emergence of quantum computing, which enables performing parallel computation, raises hope for solving such problems within a reasonable time frame. This paper proposes a quantum global optimization algorithm for solving combinatorial optimization problems with improved performance and runtime approaching Grover’s optimal time of quantum search. The algorithm determines the global optimum of the objective function defining the addressed problem using an enhanced application of Grover’s search by simultaneously exploring all comparison cases of possible solutions without requiring iterative operations, unlike previous approaches, which affect performance and runtime. The paper also introduces a version of the proposed algorithm for solving the knapsack problem, along with its execution results and a comparison with other competing algorithms.

•Jan 12, 2026•0 citations

Grover Optimization for Lock Scheduling Problems

Freyja Ullinger, Jannes Weghake, Oliver Sefrin +5 more

There exist several quantum algorithms with a proven quantum advantage. One of them is the Grover Search Algorithm [1], which finds an item in an unordered database with quadratic speed-up. By mapping optimization problems to search problems, one is able to harvest this quantum advantage. A particularly interesting NP-hard problem explored in the project QCMobility is the lock scheduling problem. Here we aim at deriving an optimal schedule to lock the incoming ships, while minimizing for example waiting times or water consumption. In this poster, we investigate the solution of the lock scheduling problem. For this purpose, we formulate it as a quadratic unconstrained binary optimization (QUBO) problem and find the global optimum with Grover Adaptive Search [2]. Our results are obtained on quantum hardware simulators. [1] L. K. Grover, Proc. 28th Annu. ACM Symp. Theory Comput., 212 - 219 (1996). [2] W. P. Baritompa, D. W. Bulger, and G. R. Wood, SIAM J. Optim. 15, 1170 (2005).

•Mar 5, 2026•0 citations

Implementation of Efficient Quantum Computing Algorithm for Searching

Nirhali Atharva, Malwade Rohit, P. Akshay +2 more

The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.

International Research Journal on Advanced Engineering Hub (IRJAEH)•May 21, 2025•0 citations
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.
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 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.
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.
Abstract Solving combinatorial optimization problems represents a challenge for researchers, especially hard NP-complete problems that are commonly handled through heuristic methods providing approximate solutions. The emergence of quantum computing, which enables performing parallel computation, raises hope for solving such problems within a reasonable time frame. This paper proposes a quantum global optimization algorithm for solving combinatorial optimization problems with improved performance and runtime approaching Grover’s optimal time of quantum search. The algorithm determines the global optimum of the objective function defining the addressed problem using an enhanced application of Grover’s search by simultaneously exploring all comparison cases of possible solutions without requiring iterative operations, unlike previous approaches, which affect performance and runtime. The paper also introduces a version of the proposed algorithm for solving the knapsack problem, along with its execution results and a comparison with other competing algorithms.
There exist several quantum algorithms with a proven quantum advantage. One of them is the Grover Search Algorithm [1], which finds an item in an unordered database with quadratic speed-up. By mapping optimization problems to search problems, one is able to harvest this quantum advantage. A particularly interesting NP-hard problem explored in the project QCMobility is the lock scheduling problem. Here we aim at deriving an optimal schedule to lock the incoming ships, while minimizing for example waiting times or water consumption. In this poster, we investigate the solution of the lock scheduling problem. For this purpose, we formulate it as a quadratic unconstrained binary optimization (QUBO) problem and find the global optimum with Grover Adaptive Search [2]. Our results are obtained on quantum hardware simulators. [1] L. K. Grover, Proc. 28th Annu. ACM Symp. Theory Comput., 212 - 219 (1996). [2] W. P. Baritompa, D. W. Bulger, and G. R. Wood, SIAM J. Optim. 15, 1170 (2005).
The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.