Cardinality-Aware Quantum Retrieval for Large-Scale Predicate Matching in Big Data Systems
DOI:
https://doi.org/10.63646/IBMY3458Keywords:
Quantum retrieval; cardinality estimation; predicate matching; big data query; Grover's algorithm; quantum amplitude estimationAbstract
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.
How to Cite
References
Aaronson, S., & Rall, P. (2020). Quantum approximate counting, simplified. In Proceedings of the Symposium on Simplicity in Algorithms (pp. 24–32). SIAM. https://doi.org/10.1137/1.9781611976014.5
Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., … Martinis, J. M. (2019). Quantum supremacy using a programmable superconducting processor. Nature, 574(7779), 505–510. https://doi.org/10.1038/s41586-019-1666-5
Assunção, M. D., Calheiros, R. N., Bianchi, S., Netto, M. A. S., & Buyya, R. (2015). Big Data computing and clouds: Trends and future directions. Journal of Parallel and Distributed Computing, 79–80, 3–15. https://doi.org/10.1016/j.jpdc.2014.08.003
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., … Aspuru-Guzik, A. (2022). Noisy intermediate-scale quantum algorithms. Reviews of Modern Physics, 94(1), 015004. https://doi.org/10.1103/RevModPhys.94.015004
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., & Lloyd, S. (2017). Quantum machine learning. Nature, 549(7671), 195–202. https://doi.org/10.1038/nature23474
Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002). Quantum amplitude amplification and estimation. Contemporary Mathematics, 305, 53–74. https://doi.org/10.1090/conm/305/05215
Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., … Coles, P. J. (2021). Variational quantum algorithms. Nature Reviews Physics, 3(9), 625–644. https://doi.org/10.1038/s42254-021-00348-9
Chen, C. L. P., & Zhang, C. Y. (2014). Data-intensive applications, challenges, techniques and technologies: A survey on big data. Information Sciences, 275, 314–347. https://doi.org/10.1016/j.ins.2014.01.015
Dunjko, V., & Briegel, H. J. (2018). Machine learning and artificial intelligence in the quantum domain: A review of recent progress. Reports on Progress in Physics, 81(7), 074001. https://doi.org/10.1088/1361- 6633/aab406
Egger, D. J., Gambella, C., Marecek, J., McFaddin, S., Mevissen, M., Raymond, R., … Woerner, S. (2020). Quantum computing for finance: State-of-the-art and future prospects. IEEE Transactions on Quantum Engineering, 1, 3101724. https://doi.org/10.1109/TQE.2020.3030314
Giovannetti, V., Lloyd, S., & Maccone, L. (2008). Quantum random access memory. Physical Review Letters, 100(16), 160501. https://doi.org/10.1103/PhysRevLett.100.160501
Gyongyosi, L., & Imre, S. (2019). A survey on quantum computing technology. Computer Science Review, 31, 51–71. https://doi.org/10.1016/j.cosrev.2018.11.002
Han, Y., Wu, Z., Wu, P., Zhu, R., Yang, J., Tan, L. W. P., … Ioannidis, Y. (2021). Cardinality estimation in DBMS: A comprehensive benchmark evaluation. Proceedings of the VLDB Endowment, 15(4), 752– 765. https://doi.org/10.14778/3503585.3503586
Harrow, A. W., & Napp, J. C. (2021). Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms. Physical Review Letters, 126(14), 140502. https://doi.org/10.1103/PhysRevLett.126.140502
Hashem, I. A. T., Yaqoob, I., Anuar, N. B., Mokhtar, S., Gani, A., & Khan, S. U. (2015). The rise of 'big data' on cloud computing: Review and open research issues. Information Systems, 47, 98–115. https://doi.org/10.1016/j.is.2014.07.006
Hilprecht, B., Schmidt, A., Kulessa, M., Molina, A., Kersting, K., & Binnig, C. (2020). DeepDB: Learn from data, not from queries! Proceedings of the VLDB Endowment, 13(7), 992–1005. https://doi.org/10.14778/3384345.3384349
Huang, H. Y., Kueng, R., & Preskill, J. (2021). Information-theoretic bounds on quantum advantage in machine learning. Physical Review Letters, 126(19), 190505. https://doi.org/10.1103/PhysRevLett.126.190505
Kim, Y., Eddins, A., Anand, S., Wei, K. X., van den Berg, E., Rosenblatt, S., … Kandala, A. (2023). evidence for the utility of quantum computing before fault tolerance. Nature, 618(7965), 500–505. https://doi.org/10.1038/s41586-023-06096-3
Kipf, A., Kipf, T., Radke, B., Leis, V., Boncz, P., & Kemper, A. (2019). Learned cardinalities: Estimating correlated joins with deep learning. In Proceedings of CIDR 2019.
Kraska, T., Beutel, A., Chi, E. H., Dean, J., & Polyzotis, N. (2018). The case for learned index structures. In Proceedings of the ACM International Conference on Management of Data (pp. 489–504). https://doi.org/10.1145/3183713.3196909
Leis, V., Gubichev, A., Mirchev, A., Boncz, P., Kemper, A., & Neumann, T. (2015). How good are query optimizers, really? Proceedings of the VLDB Endowment, 9(3), 204–215. https://doi.org/10.14778/2850583.2850594
Liu, Y., Arunachalam, S., & Temme, K. (2021). A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics, 17(9), 1013–1017. https://doi.org/10.1038/s41567-021-01287-z
Lloyd, S., Garnerone, S., & Zanardi, P. (2016). Quantum algorithms for topological and geometric analysis of data. Nature Communications, 7, 10138. https://doi.org/10.1038/ncomms10138
Lu, W., Lu, Y., Li, J., Sigov, A., Ratkin, L., & Ivanov, L. A. (2024). Quantum machine learning: Classifications, challenges, and solutions. Journal of Industrial Information Integration, 42, 100736. https://doi.org/10.1016/j.jii.2024.100736
Lu, Y. (2019). Artificial intelligence: A survey on evolution, models, applications and future trends. Journal of Management Analytics, 6(1), 1–29. https://doi.org/10.1080/23270012.2019.1570365
Lu, Y., & Yang, J. (2024). Quantum financing system: A survey on quantum algorithms, potential scenarios and open research issues. Journal of Industrial Information Integration, 41, 100663. https://doi.org/10.1016/j.jii.2024.100663
Lu, Y., Sigov, A. S., Ratkin, L., Ivanov, L. A., & Zuo, M. (2023). Quantum computing and industrial information integration: A review. Journal of Industrial Information Integration, 35, 100511. https://doi.org/10.1016/j.jii.2023.100511
Marcus, R., & Papaemmanouil, O. (2019). Plan-structured deep neural network models for query performance prediction. Proceedings of the VLDB Endowment, 12(11), 1733–1746. https://doi.org/10.14778/3342263.3342341
Marcus, R., Negi, P., Mao, H., Zhang, C., Alizadeh, M., Kraska, T., … Papaemmanouil, O. (2019). Neo: A learned query optimizer. Proceedings of the VLDB Endowment, 12(11), 1705–1718. https://doi.org/10.14778/3342263.3342364
McClean, J. R., Romero, J., Babbush, R., & Aspuru-Guzik, A. (2016). The theory of variational hybrid quantum-classical algorithms. New Journal of Physics, 18(2), 023023. https://doi.org/10.1088/1367- 2630/18/2/023023
Mitarai, K., Negoro, M., Kitagawa, M., & Fujii, K. (2018). Quantum circuit learning. Physical Review A, 98(3), 032309. https://doi.org/10.1103/PhysRevA.98.032309
Montanaro, A. (2016). Quantum algorithms: An overview. npj Quantum Information, 2, 15023. https://doi.org/10.1038/npjqi.2015.23
Nielsen, M. A., & Chuang, I. L. (2010). Quantum computation and quantum information: 10th anniversary edition. Cambridge University Press.
Orüs, R., Mugel, S., & Lizaso, E. (2019). Quantum computing for finance: Overview and prospects. Reviews in Physics, 4, 100028. https://doi.org/10.1016/j.revip.2019.100028
Oussous, A., Benjelloun, F. Z., Lahcen, A. A., & Belfkih, S. (2018). Big Data technologies: A survey. Journal of King Saud University – Computer and Information Sciences, 30(4), 431–448. https://doi.org/10.1016/j.jksuci.2017.06.001
Preskill, J. (2018). Quantum computing in the NISQ era and beyond. Quantum, 2, 79. https://doi.org/10.22331/q-2018-08-06-79
Rebentrost, P., Mohseni, M., & Lloyd, S. (2014). Quantum support vector machine for big data classification. Physical Review Letters, 113(13), 130503. https://doi.org/10.1103/PhysRevLett.113.130503
Schuld, M., Bocharov, A., Svore, K. M., & Wiebe, N. (2020). Circuit-centric quantum classifiers. Physical Review A, 101(3), 032308. https://doi.org/10.1103/PhysRevA.101.032308
Schuld, M., & Killoran, N. (2019). Quantum machine learning in feature Hilbert spaces. Physical Review
Letters, 122(4), 040504. https://doi.org/10.1103/PhysRevLett.122.040504
Suzuki, Y., Uno, S., Raymond, R., Tanaka, T., Onodera, T., & Yamamoto, N. (2020). Amplitude estimation without phase estimation. Quantum Information Processing, 19(2), 75. https://doi.org/10.1007/s11128- 019-2565-2
Tang, E. (2019). A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (pp. 217–228). https://doi.org/10.1145/3313276.3316310
Wang, J., Trummer, I., & Basu, D. (2021). Are we ready for learned cardinality estimation? Proceedings of the VLDB Endowment, 14(9), 1530–1542. https://doi.org/10.14778/3461535.3461539
Woerner, S., & Egger, D. J. (2019). Quantum risk analysis. npj Quantum Information, 5(1), 15. https://doi.org/10.1038/s41534-019-0130-6
Yang, Z., Kamsetty, A., Luan, S., Liang, E., Gong, Y., & Stoica, I. (2020). NeuroCard: One cardinality estimator for all tables. Proceedings of the VLDB Endowment, 14(1), 61–73. https://doi.org/10.14778/3421424.3421432
Ye, Z., & Lu, Y. (2022). Quantum science: A review and current research trends. Journal of Management Analytics, 9(3), 383–402. https://doi.org/10.1080/23270012.2022.2089064
Zaharia, M., Xin, R. S., Wendell, P., Das, T., Armbrust, M., Dave, A., … Stoica, I. (2016). Apache Spark: A unified analytics engine for large-scale data processing. Communications of the ACM, 59(11), 56–65. https://doi.org/10.1145/2934664
Zhang, C., & Lu, Y. (2021). Study on artificial intelligence: The state ofthe art and future prospects. Journal of Industrial Information Integration, 23, 100224. https://doi.org/10.1016/j.jii.2021.100224
Zhu, R., Wu, Z., Han, Y., Zeng, K., Pfadler, A., Qian, Z., … Cui, B. (2021). FLAT: Fast, lightweight and accurate method for cardinality estimation. Proceedings of the VLDB Endowment, 14(9), 1489–1502. https://doi.org/10.14778/3461535.3461536
