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.
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.
Efficient query optimization is crucial for relational database systems, especially for optimizing join orders in complex queries. This work introduces a hybrid approach that integrates Eliminating Cartesian Products (ECP) with splitting the QUBO search space (SQSS) to reduce the size of the QUBO problem, minimizing binary variables and constraints. This improves the performance of the quantum algorithm while lowering hardware requirements. We evaluate our method using real-world SQL queries from the ErgastF1 dataset on quantum and classical algorithms, including Quantum Annealing (QA), Simulated Annealing (SA), QAOA, and VQE, implemented on D-Wave's Quantum Annealer and universal gate-based simulators. Additionally, we analyze the impact of selectivity and SQSS on QUBO weight distribution and algorithmic performance, highlighting optimization efficiency for QA and SA. Experimental results show consistent optimal join orders and enhanced query optimization for various selectivity conditions, and they also highlight the limitations of current quantum hardware for complex queries. This study further confirms the potential of hybrid quantum-classical methods for scalable quantum-enhanced database optimization.
Large-scale combinatorial scheduling problems -- job-shop scheduling, flow-shop scheduling, and vehicle routing among them -- remain NP-hard at practically relevant scale, and quantum computing has entered this space along two related tracks: genuinely quantum solvers, principally quantum annealers and gate-based devices running the quantum approximate optimization algorithm (QAOA), and quantum-inspired classical solvers, such as coherent Ising machines and digital annealers, that borrow the same Ising/QUBO problem structure without requiring quantum hardware. This article synthesizes both tracks as applied specifically to scheduling. We trace the theoretical foundations from quantum and simulated annealing through the QUBO formulation techniques that make scheduling problems solver-ready, then review direct applications to job-shop, flow-shop, and vehicle-routing problems, reporting the concrete, verified numbers the underlying studies provide. The consistent finding is that quantum hardware remains constrained by qubit connectivity, embedding overhead, and shallow achievable circuit depth to small benchmark instances, while quantum-inspired classical solvers, unconstrained by qubit count, already reach scheduling-relevant problem sizes with reported performance competitive with or exceeding classical heuristics. We close by identifying benchmarking rigor, hardware connectivity, and the near-total absence of work on dynamic, online scheduling as the field's clearest open problems.
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.
Quantum technology offers a transformative approach to solving complex computational challenges in decentralized systems, particularly in blockchain transaction scheduling. Efficient transaction scheduling is critical in distributed ledger systems, which often face challenges like dynamic transaction loads. This work proposes a novel approach namely Hybrid Quantum Approximate Optimization Algorithm (HQAOA) which combines Multi-Agent QAOA (MA-QAOA) and Adaptive Layer QAOA (AL-QAOA) to provide a robust solution to such issues. HQAOA leverages a decentralized optimization framework where multiple agents, each representing a node in the network, optimize local transaction scheduling while considering global constraints. Additionally, HQAOA adapts to varying transaction loads by dynamically adjusting the number of quantum layers for each agent, ensuring computational efficiency under different conditions. Such dynamic layer adjustment mechanisms mitigate the adverse effects of quantum noise and ensures optimal performance in scenarios with fluctuating transaction loads. In contrast to traditional QAOA, which struggles with noise and scaling issues, HQAOA provides improved performance by balancing the complexity of the problem with available quantum resources. Experimental results signify the future potential of HQAOA to outperform QAOA, particularly in noisy environments and irregular transaction conditions. This work demonstrates the potential of HQAOA to optimize blockchain transaction scheduling in decentralized systems.
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.
Large-scale combinatorial scheduling problems -- job-shop scheduling, flow-shop scheduling, and vehicle routing among them-- remain NP-hard at practically relevant scale, and quantum computing has entered this space along two related tracks:genuinely quantum solvers, principally quantum annealers and gate-based devices running the quantum approximateoptimization algorithm (QAOA), and quantum-inspired classical solvers, such as coherent Ising machines and digitalannealers, that borrow the same Ising/QUBO problem structure without requiring quantum hardware. This article synthesizesboth tracks as applied specifically to scheduling. We trace the theoretical foundations from quantum and simulated annealingthrough the QUBO formulation techniques that make scheduling problems solver-ready, then review direct applications tojob-shop, flow-shop, and vehicle-routing problems, reporting the concrete, verified numbers the underlying studies provide. Theconsistent finding is that quantum hardware remains constrained by qubit connectivity, embedding overhead, and shallowachievable circuit depth to small benchmark instances, while quantum-inspired classical solvers, unconstrained by qubitcount, already reach scheduling-relevant problem sizes with reported performance competitive with or exceeding classicalheuristics. We close by identifying benchmarking rigor, hardware connectivity, and the near-total absence of work on dynamic,online scheduling as the field's clearest open problems.