arXiv:2306.08529v3 Announce Type: replace-cross
Abstract: 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. We theoretically analyze the quantum machine learning model by calculating its expressibility and entangling capabilities.