M.Sc. Valter Uotila defends his PhD thesis "Quantum Computing Methods for Query Optimization in Relational Databases" on Friday the 13th of March 2026 at 13 in the University of Helsinki Main building, Auditorium Karolina Eskelin (U3032, Unioninkatu 34, 3rd floor). His opponent is Associate Professor Matti Silveri (University of Oulu) and custos Professor Jiaheng Lu (University of Helsinki). The defence will be held in English.
The thesis of Valter Uotila is a part of research done in the Department of Computer Science and in the Unified Database Management Systems and Empirical Software Engineering groups at the University of Helsinki. His supervisors have been Professor Jiaheng Lu and Professor Jukka K. Nurminen (University of Helsinki).
Quantum Computing Methods for Query Optimization in Relational Databases
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.
Availability of the dissertation
An electronic version of the doctoral dissertation will be available in the University of Helsinki open repository Helda at
Printed copies will be available on request from Valter Uotila: