Quantum computing is an emerging technology that has experienced rapid progress and growing interest in recent years. To realize the potential of quantum computing, it is essential to consider its applicability in various domains. This thesis focuses on a relatively new field, the intersection of quantum computing and query processing in relational databases. During the research conducted for this thesis, the field has undergone substantial growth. The key problem in this field is to identify computationally challenging database optimization or other data management-related problems that can be tackled with quantum computing methods. The methodological core of this thesis centers on three larger themes: quantum machine learning, quantum optimization, and quantum information theory. In each case, the thesis focuses on a specific query-optimization problem that can be addressed by a particular method. The first problem is the challenge of estimating various SQL metrics, such as execution times and cardinalities, for queries before executing them on a relational database. This problem is addressed using a novel quantum natural language processing model that converts SQL queries into parametrized quantum circuits, which serve as the basis for the quantum machine learning model. The second problem, join order selection, is the most-studied query optimization problem at the intersection of quantum computing and databases. While most previous formulations of these problems have been quadratic unconstrained binary optimization problems, this work develops a higher-order binary optimization formulation for join order optimization. The applicability of higher-order binary optimization is also demonstrated by a work that develops an optimization problem to discover practical matrix multiplication algorithms. Finally, the third query processing problem is among the most-studied theoretical database optimization problems. It seeks worst-case size bounds for conjunctive queries with arbitrary functional dependencies. Previous research has developed Shannon-entropy-based linear programming formulations to compute size bounds. Our work proposes replacing Shannon entropy with the quantum Rényi entropy, which yields a similar yet theoretically slightly different formulation. Most importantly, this creates connections between theoretical database research and quantum information theory. Quantum computing has been notoriously challenging to apply to real-world problems. The practical estimates from the quantum machine learning model for the query metrics indicate that the proposed model can learn to estimate query metrics as a classifier for short SQL queries. In particular, the novel encoding mechanism that transforms SQL queries into parameterized quantum circuits is a key contribution of this work. For join order optimization problems, this work develops the first higher-order binary optimization formulations, which achieve comparable accuracy to that of dynamic programming and greedy algorithms, which are foundational methods for the problem in classical computing. Finally, the last article derives the worst-case size bound in terms of Rényi entropy and discusses the differences to those achieved with Shannon entropy. Continued development of quantum computing hardware, software, and algorithms will benefit from research that studies their performance in specific interdisciplinary applications. This thesis introduces relational databases and query processing as a domain that encompasses computationally complex problems at both practical and theoretical levels. It demonstrates how various quantum computational methods can be modified and applied to these problems, showcasing their practical usability while acknowledging their limitations.
Quantum computing is an emerging technology that has experienced rapid progress and growing interest in recent years. To realize the potential of quantum computing, it is essential to consider its applicability in various domains. This thesis focuses on a relatively new field, the intersection of quantum computing and query processing in relational databases. During the research conducted for this thesis, the field has undergone substantial growth. The key problem in this field is to identify computationally challenging database optimization or other data management-related problems that can be tackled with quantum computing methods. The methodological core of this thesis centers on three larger themes: quantum machine learning, quantum optimization, and quantum information theory. In each case, the thesis focuses on a specific query-optimization problem that can be addressed by a particular method. The first problem is the challenge of estimating various SQL metrics, such as execution times and cardinalities, for queries before executing them on a relational database. This problem is addressed using a novel quantum natural language processing model that converts SQL queries into parametrized quantum circuits, which serve as the basis for the quantum machine learning model. The second problem, join order selection, is the most-studied query optimization problem at the intersection of quantum computing and databases. While most previous formulations of these problems have been quadratic unconstrained binary optimization problems, this work develops a higher-order binary optimization formulation for join order optimization. The applicability of higher-order binary optimization is also demonstrated by a work that develops an optimization problem to discover practical matrix multiplication algorithms. Finally, the third query processing problem is among the most-studied theoretical database optimization problems. It seeks worst-case size bounds for conjunctive queries with arbitrary functional dependencies. Previous research has developed Shannon-entropy-based linear programming formulations to compute size bounds. Our work proposes replacing Shannon entropy with the quantum Rényi entropy, which yields a similar yet theoretically slightly different formulation. Most importantly, this creates connections between theoretical database research and quantum information theory. Quantum computing has been notoriously challenging to apply to real-world problems. The practical estimates from the quantum machine learning model for the query metrics indicate that the proposed model can learn to estimate query metrics as a classifier for short SQL queries. In particular, the novel encoding mechanism that transforms SQL queries into parameterized quantum circuits is a key contribution of this work. For join order optimization problems, this work develops the first higher-order binary optimization formulations, which achieve comparable accuracy to that of dynamic programming and greedy algorithms, which are foundational methods for the problem in classical computing. Finally, the last article derives the worst-case size bound in terms of Rényi entropy and discusses the differences to those achieved with Shannon entropy. Continued development of quantum computing hardware, software, and algorithms will benefit from research that studies their performance in specific interdisciplinary applications. This thesis introduces relational databases and query processing as a domain that encompasses computationally complex problems at both practical and theoretical levels. It demonstrates how various quantum computational methods can be modified and applied to these problems, showcasing their practical usability while acknowledging their limitations.
Recent advances in quantum computing have led to progress in exploring quantum applications across diverse fields, including databases and data management. This work presents a quantum machine learning model that tackles the challenge of estimating metrics, such as cardinalities, execution times, and costs, for SQL queries in relational databases. Precise estimations are crucial for the query optimizer to optimize query processing in relational databases efficiently. Our proposed quantum machine learning model consists of a novel query encoding mechanism, which maps SQL queries into high-dimensional Hilbert spaces using grammatical representations of the queries. The encoding mechanism translates SQL queries into parameterized quantum circuits, forming the core of the quantum machine learning model. The parameters in this model are tuned using standard quantum machine learning techniques. This encoding was first developed in quantum natural language processing (QNLP), and this work demonstrates its natural application in database optimization. Because the encoding mechanism is mathematically robust, the quantum machine learning model is also explainable, allowing us to draw a one-to-one correspondence between the elements in SQL queries and the model's parameters. The method is also scalable because it consists of multiple circuits, and we train and evaluate the model with hundreds of queries. Compared to previous research, our model achieves high accuracy, supporting the results obtained in the original QNLP research. We extend the previous QNLP work by adding 4-class and 8 -class classification tasks and comparing the cardinality estimation results with those from state-of-the-art databases. This model shows a competitive accuracy compared to the estimators in the databases. We theoretically analyze the quantum machine learning model by calculating its expressibility and entangling capabilities, which have been suggested as representative metrics describing the model's trainability and learnability features.
Quantum Natural Language Processing (QNLP) is built on a novel, category theoretical quantum machine learning model, which we use to solve a well-researched problem in the database field: estimating metrics for SQL queries. The metrics we focus on are latency (i.e., the execution time), cost (i.e., a value of how expensive the query is in total), and cardinality (i.e., the number of rows in the result table). The critical link between QNLP and the database problem lies in using grammars, such as context-free grammar. Both natural language and SQL queries admit grammatical presentations, which allow us to develop a comprehensive framework for applying QNLP methods to solve the query estimation problem. The model comprises an encoding mechanism and a training phase, integrating classical and quantum subroutines. The encoding mechanism transforms SQL queries into parametrized quantum circuits as in QNLP. Classical optimization algorithms optimize the circuit parameters during training to predict query metrics. Comparing our model to the QNLP models, our model achieves accuracy comparable to the QNLP model in binary classification tasks. Additionally, we expand upon previous research by implementing multi-class classification tasks and comparing the cardinality estimation results to those of state-of-the-art databases. Our theoretical analysis of the quantum machine learning model includes calculations of its expressibility and entangling capabilities. The analysis reveals that the model possesses beneficial properties, making it suitable to be executed on near-term quantum hardware.
In the last few years, the field of quantum computing has experienced remarkable progress. The prototypes of quantum computers already exist and have been made available to users through cloud services (e.g., IBM Q experience, Google quantum AI, or Xanadu quantum cloud). While fault-tolerant and large-scale quantum computers are not available yet (and may not be for a long time, if ever), the potential of this new technology is undeniable. Quantum algorithms have the proven ability to either outperform classical approaches for several tasks, or are impossible to be efficiently simulated by classical means under reasonable complexity-theoretic assumptions. Even imperfect current-day technology is speculated to exhibit computational advantages over classical systems. Recent research is using quantum computers to solve machine learning tasks. Meanwhile, the database community has already successfully applied various machine learning algorithms for data management tasks, so combining the fields seems to be a promising endeavour. However, quantum machine learning is a new research field for most database researchers. In this tutorial, we provide a fundamental introduction to quantum computing and quantum machine learning and show the potential benefits and applications for database research. In addition, we demonstrate how to apply quantum machine learning to the join order optimization problem in databases.
Join order optimization is among the most crucial query optimization problems, and its central position is also evident in the new research field where quantum computing is applied to database optimization and data management. In this field, join order optimization is the most studied database problem, typically tackled with a quadratic unconstrained binary optimization model, which is solved using various meta-heuristics, such as quantum and digital annealing, the quantum approximate optimization algorithm, or the variational quantum eigensolver. In this study, we continue developing quantum computing techniques for left-deep join order optimization by presenting three novel quantum optimization algorithms. These algorithms are based on a higher-order unconstrained binary optimization model, which is a generalization of the quadratic model and has not previously been applied to database problems. Theoretically, these optimization problems naturally map to universal quantum computers and quantum annealers. Compared to previous studies, two of our algorithms are the first quantum algorithms to model the join order cost function precisely. We prove theoretical bounds by showing that these two methods encode the same plans as the dynamic programming algorithm with respect to the query graph, which provides the optimal result up to cross products. The third algorithm achieves plans at least as good as those of the greedy algorithm with respect to the query graph. These results establish a meaningful theoretical connection between classical and quantum algorithms for selecting left-deep join orders. To demonstrate the practical usability of our algorithms, we have conducted an extensive experimental evaluation on thousands of clique, cycle, star, tree, and chain query graphs using both quantum and classical solvers.
Deriving formulations to estimate worst-case size bounds for conjunctive queries under various constraints has been at the core of theoretical database research. If the problem has no constraints or has a single functional dependency, tight worst-case size bounds are computable. If the problem has more than one functional dependency, computing tight bounds can be difficult in practice and may even require an infinite number of linear inequalities in its optimization formulation. While these challenges have been addressed with varying methods, no prior research has employed quantum information theory to address this problem. In this work, we establish a connection between earlier classical information theory-based works and quantum information theory. We propose replacing the classical Shannon entropy formulation with the quantum Rényi entropy of order α∈(0,1) whose entropy cone is characterized simply by non-negativity. The first key result is to express the bound in terms of optimizing over quantum states and Rényi entropy. Optimizing with respect to quantum states rather than classical distributions transfers the hardness into the problem of characterizing classical states, yielding a sound but generally not tight upper bound. We further quantify this hardness explicitly by proposing a dichotomy theorem: if the query satisfies a head absorption rule, then the Rényi program value is at most one and ∣Q(D)∣≤rmax(D). Otherwise, the program is unbounded.
The theories of optimization and machine learning answer foundational questions in computer science and lead to new algorithms for practical applications. While these topics have been extensively studied in the context of classical computing, their quantum counterparts are far from well-understood. In this thesis, we explore algorithms that bridge the gap between the fields of quantum computing and machine learning. First, we consider general optimization problems with only function evaluations. For two core problems, namely general convex optimization and volume estimation of convex bodies, we give quantum algorithms as well as quantum lower bounds that constitute the quantum speedups of both problems to be polynomial compared to their classical counterparts. We then consider machine learning and optimization problems with input data stored explicitly as matrices. We first look at semidefinite programs and provide quantum algorithms with polynomial speedup compared to the classical state-of-the-art. We then move to machine learning and give the optimal quantum algorithms for linear and kernel-based classifications. To complement with our quantum algorithms, we also introduce a framework for quantum-inspired classical algorithms, showing that for low-rank matrix arithmetics there can only be polynomial quantum speedup. Finally, we study statistical problems on quantum computers, with the focus on testing properties of probability distributions. We show that for testing various properties including L1-distance, L2-distance, Shannon and Renyi entropies, etc., there are polynomial quantum speedups compared to their classical counterparts. We also extend these results to testing properties of quantum states.