Cardinality-Aware Quantum Retrieval for Large-Scale Predicate Matching in Big Data Systems
Main article
Abstract
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.
