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.
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.
The new Quantum Machine Learning (QML) paradigm for highly efficient query execution in high-dimensional SQL data systems and Conventional database query execution is plagued by performance bottlenecks because of the explosive nature of structured data and intricate query optimization issues. The new QML-based methodology uses quantum algorithms to accelerate query processing by exploiting parallel computation, quantum-aided indexing, and probabilistic data access. With the incorporation of quantum-enhanced optimization methods, the framework achieves remarkable query execution time reduction, enhanced system scalability, and increased efficiency in managing relational databases at scale. The work compares the framework's performance against traditional SQL query optimizers and shows better performance in terms of execution speed, accuracy in retrieving data, and utilization of computational resources. The results also point to the promise of QML in revolutionizing DBMS and bringing in next-generation data analytics solutions.
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 Natural Language Processing (QNLP) is an emerging interdisciplinary field at the intersection of quantum computing, natural language understanding, and formal linguistic theory. As advances in quantum hardware and algorithms accelerate, QNLP promises new paradigms for representation learning, semantic modeling, and efficient computation. However, existing literature remains fragmented, with no unified synthesis across modeling, encoding, and evaluation dimensions.In this work, we present the first systematic and taxonomy driven survey of QNLP that holistically organizes research spanning three core dimensions: computational models, encoding paradigms, and evaluation frameworks. First, we analyze foundational approaches that map linguistic structures into quantum formalism, including categorical compositional models, variational quantum circuits, and hybrid quantum classical architectures. Second, we introduce a unified taxonomy of encoding strategies, ranging from quantum tokenization and state preparation to embedding based encodings, highlighting tradeoffs in scalability, noise resilience, and expressiveness. Third, we provide the first comparative synthesis of evaluation methodologies, benchmark datasets, and performance metrics, while identifying reproducibility and standardization gaps.We further contrast quantum inspired NLP methods with fully quantum implemented systems, offering insights into resource efficiency, hardware feasibility, and real world applicability. Finally, we outline open challenges such as integration with LLMs and unified benchmark design, and propose a research agenda for advancing QNLP as a scalable and reliable discipline.
[EN] Quantum computing is widely regarded as one of the scientific fields with the greatest transformative potential. Its applications are already being explored in areas such as cybersecurity, chemistry, and machine learning. Within the domain of quantum machine learning, one emerging subfield is quantum natural language processing (QNLP), which seeks to leverage quantum algorithms to address complex language-related tasks more efficiently than classical counterparts. This thesis begins with a systematic literature review of the current landscape of quantum machine learning, focusing particularly on the design, development, and deployment of QNLP models on real quantum hardware. The SLR identifies 94 relevant articles that utilize quantum machine learning techniques and algorithms, highlighting their implementation via computational quantum circuits, or ansatzes. The main types of algorithms found include quantum adaptations of classical models such as support vector machines and k-nearest neighbors, as well as quantum neural networks, one of the most prominent applications being image classification. In addition, this work offers both quantitative and qualitative analyses, integrating a comprehensive set of experiments conducted on quantum simulators and real quantum devices. A significant contribution of this work lies in the design and evaluation of these new quantum circuit architectures, tailored to optimize expressibility, entanglement, and trainability. Empirical analysis shows that model accuracy tends to exhibit an inverse relationship with ansatz expressibility and a direct correlation with entanglement capability. In parallel, it contributes to the field by proposing novel ansatz architectures and applying circuit knitting techniques to overcome current hardware limitations. Ultimately, this thesis demonstrates the feasibility of hybrid quantum-classical approaches in QNLP and highlights their potential to be extended to support more complex and scalable real-world language applications.
Quantum Natural Language Processing (QNLP) is an emerging interdisciplinary field at the intersection of quantum computing, natural language understanding, and formal linguistic theory. As advances in quantum hardware and algorithms accelerate, QNLP promises new paradigms for representation learning, semantic modeling, and efficient computation. However, existing literature remains fragmented, with no unified synthesis across modeling, encoding, and evaluation dimensions.In this work, we present the first systematic and taxonomy driven survey of QNLP that holistically organizes research spanning three core dimensions: computational models, encoding paradigms, and evaluation frameworks. First, we analyze foundational approaches that map linguistic structures into quantum formalism, including categorical compositional models, variational quantum circuits, and hybrid quantum classical architectures. Second, we introduce a unified taxonomy of encoding strategies, ranging from quantum tokenization and state preparation to embedding based encodings, highlighting tradeoffs in scalability, noise resilience, and expressiveness. Third, we provide the first comparative synthesis of evaluation methodologies, benchmark datasets, and performance metrics, while identifying reproducibility and standardization gaps.We further contrast quantum inspired NLP methods with fully quantum implemented systems, offering insights into resource efficiency, hardware feasibility, and real world applicability. Finally, we outline open challenges such as integration with LLMs and unified benchmark design, and propose a research agenda for advancing QNLP as a scalable and reliable discipline.