LfD Logo

Applicability of Quantum Computing on Database Query Optimization

Abstract

This thesis analyzes the applicability of quantum computing on database query optimization. More specifically, both the multi query optimization (MQO) problem as well as the join ordering problem are investigated to this end. An approach for solving MQO on a D-Wave quantum annealing machine has previously been proposed and experimentally evaluated. For the join ordering problem, this work presents a two-step transformation in which the problem is first reformulated as a binary integer linear programming problem, based on an existing method. The transformed problem can then be formulated as a quadratic unconstrained binary optimization (QUBO) problem, which is a suitable formulation for current quantum systems.

This work further investigates the applicability of the existing approach for MQO via simulations with respect to state-of-the-art gate-based quantum systems, specifically IBM-Q machines, in comparison to the existing results for quantum annealing. Similar simulations for both gate-based and quantum annealing systems are conducted to evaluate the proposed approach for solving join ordering problems. Two variational hybrid quantum-classical algorithms, the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA), are simulated for current IBM-Q machines. Simulation results show that QAOA can in nearly all cases be more reliably executed than VQE with respect to the limited coherence time of current systems. Moreover, for both problems, existing D-Wave quantum annealing systems can solve significantly larger problems than current gate-based IBM-Q systems.

However, these problem sizes are still limited compared to the problem dimensions solvable via classical approaches. Still, considering the rapid evolution of quantum systems, the prospect of using sufficiently mature quantum devices, which may become available in the near future, for practical problem dimensions is promising and motivates further research to identify further suitable database optimization problems.