Cardinality estimation is an important part of query optimization in DBMS. We develop a Quantum Cardinality Estimation (QCardEst) approach using Quantum Machine Learning with a Hybrid Quantum-Classical Network. We define a compact encoding for turning SQL queries into a quantum state, which requires only qubits equal to the number of tables in the query. This allows the processing of a complete query with a single variational quantum circuit (VQC) on current hardware. In addition, we compare multiple classical post-processing layers to turn the probability vector output of VQC into a cardinality value. We introduce Quantum Cardinality Correction QCardCorr, which improves classical cardinality estimators by multiplying the output with a factor generated by a VQC to improve the cardinality estimation. With QCardCorr, we have an improvement over the standard PostgreSQL optimizer of 6.37 times for JOB-light and 8.66 times for STATS. For JOB-light we even outperform MSCN by a factor of 3.47.
Cardinality estimation is an important part of query optimization in DBMS. We develop a Quantum Cardinality Estimation (QCardEst) approach using Quantum Machine Learning with a Hybrid Quantum-Classical Network. We define a compact encoding for turning SQL queries into a quantum state, which requires only qubits equal to the number of tables in the query. This allows the processing of a complete query with a single variational quantum circuit (VQC) on current hardware. In addition, we compare multiple classical post-processing layers to turn the probability vector output of VQC into a cardinality value. We introduce Quantum Cardinality Correction QCardCorr, which improves classical cardinality estimators by multiplying the output with a factor generated by a VQC to improve the cardinality estimation. With QCardCorr, we have an improvement over the standard PostgreSQL optimizer of 6.37 times for JOB-light and 8.66 times for STATS. For JOB-light we even outperform MSCN by a factor of 3.47.
The optimization of queries speeds up query processing in databases. One of the most time-consuming tasks in query processing is the join operation, where the order of the joins plays a crucial role in determining the number of tuples to be processed for intermediate results, and hence, the overall processing costs. In this paper, we use a variational quantum circuit (VQC) to create a hybrid classical-quantum machine learning algorithm to predict efficient join orders by learning from past join orders. We develop an encoding of the join order problem using a low number of qubits. We show that VQCs with filtering of cross joins outperform the classical dynamic programming optimizer of PostgreSQL with a 2.7% faster execution time.
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.
Classical and learned query optimizers (LQOs) use cardinality estimations as one of the critical inputs for query planning. Thus, accurately predicting the cardinality of arbitrary queries plays a vital role in query optimization. A recent boom in novel deep learning methods stimulated not only the rise of LQOs but also contributed to the appearance of learned cardinality estimators (LCEs). However, the majority of them are based on classical neural networks, ignoring that multivariate correlations between attributes across different tables could be naturally represented via entanglements in quantum circuits.
Quantum annealers offer a promising sampling-based computing paradigm for large-scale combinatorial optimization. However, directly using them to solve database optimization problems in real-time scenarios remains challenging due to strict hardware constraints and the opacity of commercial hybrid solvers. To address these challenges, we present QDBO , a white-box quantum-augmented database optimizer that directly leverages low-level quantum sampling on a quantum annealer. It first performs an initial reduction to produce embeddable QUBO instances via multiple mapping strategies that trade off efficiency and quality. It then applies an online iterative relaxation correction procedure that uses sampling feedback to correct the reduced QUBO across iterations, enabling controllable quality improvements under varying time budgets. We integrate QDBO with the PostgreSQL query optimizer to construct Q 2 O-QDBO for join order optimization. Evaluations on the Join Order Benchmark (JOB) and the Cardinality Estimation Benchmark (CEB) show that Q 2 O-QDBO improves 62 out of 113 JOB queries, and achieves up to 49.36× execution-time speedup and 36.88× end-to-end speedup on the CEB workload. Evaluations on synthetic queries with up to 50 relations show that Q 2 O-QDBO achieves significantly less end-to-end latency while maintaining similar solution quality compared with black-box quantum solvers. To demonstrate generality, we further integrate QDBO with PostgreSQL for index selection on TPC-H, where QDBO achieves up to 2.64× workload speedup over the empty-index baseline and outperforms classical and black-box solver baselines. These results demonstrate that using QDBO to solve large-scale database optimization problems in real-time settings is promising.
Large-scale predicate matching in big data systems—identifying all records that satisfy complex multi-attribute query conditions—represents one of the most computationally intensive tasks in modern data analytics. Classical approaches based on full table scans or index lookups face prohibitive scalability constraints as datasets grow into the petabyte range. Quantum computing, and Grover's search algorithm in particular, offers a theoretically quadratic speedup for unstructured search; however, the efficiency of any quantum search procedure depends critically on an accurate estimate of the number of matching records, known as the query cardinality. Inaccurate cardinality estimates cause the quantum circuit to operate at a suboptimal number of iterations, increasing both failure rates and missed matches. This paper proposes the Cardinality-Aware Quantum Retrieval (CAQR) framework, which integrates quantum amplitude estimation for adaptive cardinality inference with a Bayesian posterior update mechanism that continuously refines the cardinality estimate during query execution. CAQR constructs efficient quantum oracles for conjunctive and disjunctive predicate conditions and dynamically adjusts Grover iteration counts to maintain near-optimal success probabilities throughout the retrieval process. Simulation experiments over synthetic datasets with search spaces ranging from 2¹² to 2²⁴ demonstrate that CAQR reduces the fraction of missed predicate matches from between 6.1% and 14.8% (baseline) to below 0.82% across all tested configurations, while also reducing total oracle calls by approximately 14–17% compared to fixed-cardinality quantum retrieval. The framework is evaluated against classical, naive quantum, and learned-cardinality baselines, and its theoretical time and space complexity are analysed. These results establish CAQR as a competitive and practically relevant approach for quantum-assisted big data query processing.