A QUANTUM APPROXIMATION ALGORITHM FOR COVARIANCE OF RANDOM VARIABLES
Keywords:
amplitude amplification, quantum fourier transform, grover diffusion operator, data analysis, machine learningAbstract
Quantum computing is a promising emerging field in computational science, attracting significant international research interest. Data representation is crucial to the success of machine learning models, and covariance analysis to determine relationships between pairs of random variables is an essential step in exploratory data analysis. Here we introduce a novel quantum algorithm for covariance approximation and its circuit implementation for discrete-value vectors. The algorithm leverages vital components of quantum computing, including amplitude encoding, the Grover diffusion algorithm for amplitude amplification and the quantum Fourier transform. As a core innovation, we utilize two quantum states and their properties of superposition product states to estimate the covariance between input vectors. Evaluating the quantum algorithm’s performance over five discrete-value distributions, we found high levels of agreement between the classical and quantum computations, with maximum average errors averaging 0.153. Furthermore, the analysis revealed additional applications of the Grover diffusion operator to solve problems.
References
Alchieri, L., Badalotti, D., Bonardi, P., Bianco, S. (2021): An introduction to quantum machine learning: from quantum logic to quantum deep learning. – Quantum Machine Intelligence 3(2): 30p.
Behrens, J.T., Yu, C.H. (2003): Exploratory data analysis. – Handbook of Psychology 2: 33-64.
Benedetti, M., Lloyd, E., Sack, S., Fiorentini, M. (2019): Parameterized quantum circuits as machine learning models. – Quantum Science and Technology 4(4): 20p.
Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U. (1997): Strengths and weaknesses of quantum computing. – SIAM Journal on Computing 26(5): 1510-1523.
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., Lloyd, S. (2017): Quantum machine learning. – Nature 549(7671): 195-202.
Blank, C., Park, D.K., Rhee, J.K.K., Petruccione, F. (2020): Quantum classifier with tailored quantum kernel. – NPJ Quantum Information 6(1): 9p.
Bravo-Prieto, C. (2021): Quantum autoencoders with enhanced data encoding. – Machine Learning: Science and Technology 2(3): 11p.
Buffoni, L., Caruso, F. (2021): New trends in quantum machine learning (a). – Europhysics Letters 132(6): 8p.
Chatfield, C. (1986): Exploratory data analysis. – European Journal of Operational Research 23(1): 5-13.
Choi, J., Kim, J. (2019): A tutorial on quantum approximate optimization algorithm (QAOA): Fundamentals and applications. – In 2019 International Conference on Information and Communication Technology Convergence (ICTC), IEEE 5p.
Cleff, T. (2014): Exploratory data analysis in business and economics. – Exploratory Data Analysis in Business and Economics 215p.
Cleve, R., Watrous, J. (2000): Fast parallel circuits for the quantum Fourier transform. – In Proceedings 41st Annual Symposium on Foundations of Computer Science, IEEE 10p.
Cui, J., Fan, H. (2010): Correlations in the Grover search. Journal of Physics A: Mathematical and Theoretical 43(4): 18p.
Data, M.C., Komorowski, M., Marshall, D.C., Salciccioli, J.D., Crutain, Y. (2016): Exploratory data analysis. – Secondary Analysis of Electronic Health Records 18p.
Dilip, R., Liu, Y.J., Smith, A., Pollmann, F. (2022): Data compression for quantum machine learning. – Physical Review Research 4(4): 8p.
Farhi, E., Goldstone, J., Gutmann, S. (2014): A quantum approximate optimization algorithm. – ArXiv:1411.4028 16p.
Gelman, A. (2004): Exploratory data analysis for complex models. – Journal of Computational and Graphical Statistics 13(4): 755-779.
Hadfield, S., Wang, Z., O’gorman, B., Rieffel, E.G., Venturelli, D., Biswas, R. (2019): From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. – Algorithms 12(2): 45p.
Hales, L., Hallgren, S. (2000): An improved quantum Fourier transform algorithm and applications. – In Proceedings 41st Annual Symposium on Foundations of Computer Science, IEEE 10p.
Jang, K., Song, G., Kwon, H., Uhm, S., Kim, H., Lee, W.K., Seo, H. (2021): Grover on PIPO. – Electronics 10(10): 18p.
Jebb, A.T., Parrigon, S., Woo, S.E. (2017): Exploratory data analysis as a foundation of inductive research. – Human Resource Management Review 27(2): 265-276.
Karami, S., Saberi-Movahed, F., Tiwari, P., Marttinen, P., Vahdati, S. (2023): Unsupervised feature selection based on variance–covariance subspace distance. – Neural Networks 166: 188-203.
Koren, M., Peretz, O. (2024): Automated Data-Driven and Stochastic Imputation Method. – Intechopen 19p.
Koren, M., Peretz, O. (2024): A quantum procedure for estimating information gain in Boolean classification task. – Quantum Machine Intelligence 6(1): 8p.
Koren, M., Koren, O., Peretz, O. (2023a): A quantum “black box” for entropy calculation. – Quantum Machine Intelligence 5(2): 8p.
Koren, O., Koren, M., Peretz, O. (2023b): A procedure for anomaly detection and analysis. – Engineering Applications of Artificial Intelligence 117: 8p.
LaRose, R., Coyle, B. (2020): Robust data encodings for quantum classifiers. – Physical Review A 102(3): 24p.
Leinhardt, S., Wasserman, S.S. (1979): Exploratory data analysis: An introduction to selected methods. – Sociological Methodology 10: 311-365.
Li, G., Ye, R., Zhao, X., Wang, X. (2022): Concentration of data encoding in parameterized quantum circuits. – Advances in Neural Information Processing Systems 35: 19456-19469.
Majji, S.R., Chalumuri, A., Manoj, B.S. (2023): Quantum Approach to Image Data Encoding and Compression. – IEEE Sensors Letters 7(2): 1-4.
Mandal, S.B., Chakrabarti, A., Sur-Kolay, S. (2014): Synthesis of ternary Grover's algorithm. – In 2014 IEEE 44th International Symposium on Multiple-Valued Logic, IEEE 6p.
Mashhadi, S. (2019): General secret sharing based on quantum Fourier transform. – Quantum Information Processing 18(4): 15p.
Moore, C., Rockmore, D., Russell, A. (2006): Generic quantum Fourier transforms. – ACM Transactions on Algorithms (TALG) 2(4): 707-723.
Morgenthaler, S. (2009): Exploratory data analysis. – Wiley Interdisciplinary Reviews: Computational Statistics 1(1): 33-44.
Nachman, B., Urbanek, M., de Jong, W.A., Bauer, C.W. (2020): Unfolding quantum computer readout noise. – NPJ Quantum Information 13p.
Nakamura, S. (1995): Numerical analysis and graphic visualization with MATLAB. – Prentice-Hall, Inc. 519p.
Nam, Y., Su, Y., Maslov, D. (2020): Approximate quantum Fourier transform with O (n log (n)) T gates. – NPJ Quantum Information 6(1): 6p.
Peretz, O., Koren, M. (2024): A parameterized quantum circuit for estimating distribution measures. – Quantum Machine Intelligence 6(1): 1-9.
Piattini, M., Peterssen, G., Pérez-Castillo, R. (2021): Quantum computing: A new software engineering golden age. – ACM SIGSOFT Software Engineering Notes 45(3): 12-14.
Romero, J., Olson, J.P., Aspuru-Guzik, A. (2017): Quantum autoencoders for efficient compression of quantum data. – Quantum Science and Technology 2(4): 13p.
Ruiz-Perez, L., Garcia-Escartin, J.C. (2017): Quantum arithmetic with the quantum Fourier transform. – Quantum Information Processing 16: 1-14.
Self, C.N., Khosla, K.E., Smith, A.W., Sauvage, F., Haynes, P.D., Knolle, J., Mintert, F., Kim, M.S. (2021): Variational quantum algorithm with information sharing. – NPJ Quantum Information 7(1): 10p.
Shi, H.L., Liu, S.Y., Wang, X.H., Yang, W.L., Yang, Z.Y., Fan, H. (2017): Coherence depletion in the Grover quantum search algorithm. – Physical Review A 95(3): 9p.
Shin, S., Teo, Y.S., Jeong, H. (2023): Exponential data encoding for quantum supervised learning. – Physical Review A 107(1): 21p.
Sierra-Sosa, D., Pal, S., Telahun, M. (2023): Data rotation and its influence on quantum encoding. – Quantum Information Processing 22(1): 89p.
Tukey, J.W. (1977): Exploratory data analysis. – Reading, MA: Addison-Wesley 2: 29p.
Tulsi, A. (2015): Faster quantum searching with almost any diffusion operator. – Physical Review A 91(5): 3p.
Vigni, M.L., Durante, C., Cocchi, M. (2013): Exploratory data analysis. – In Data Handling in Science and Technology, Elsevier 28: 55-126
Vorobyov, V., Zaiser, S., Abt, N., Meinel, J., Dasari, D., Neumann, P., Wrachtrup, J. (2021): Quantum Fourier transform for nanoscale quantum sensing. – NPJ Quantum Information 7(1): 8p.
Wang, G., Zhao, B., Wu, B., Zhang, C., Liu, W. (2023): Intelligent prediction of slope stability based on visual exploratory data analysis of 77 in situ cases. – International Journal of Mining Science and Technology 33(1): 47-59.
Weigold, M., Barzen, J., Leymann, F., Salm, M. (2021): Encoding patterns for quantum algorithms. – IET Quantum Communication 2(4): 141-152.
Weigold, M., Barzen, J., Leymann, F., Salm, M. (2020): Data encoding patterns for quantum computing. – In Proceedings of the 27th Conference on Pattern Languages of Programs 11p.
Weinstein, Y.S., Pravia, M.A., Fortunato, E.M., Lloyd, S., Cory, D.G. (2001): Implementation of the quantum Fourier transform. – Physical Review Letters 86(9): 6p.
Wiebe, N. (2020): Key questions for the quantum machine learner to ask themselves. – New Journal of Physics 22(9): 14p.
Willsch, M., Willsch, D., Jin, F., De Raedt, H., Michielsen, K. (2020): Benchmarking the quantum approximate optimization algorithm. – Quantum Information Processing 19: 1-24.
Wongsuphasawat, K., Liu, Y., Heer, J. (2019): Goals, process, and challenges of exploratory data analysis: An interview study. – ArXiv Preprint 10p.
Xu, B., Heidari, A.A., Cai, Z., Chen, H. (2023): Dimensional decision covariance colony predation algorithm: global optimization and high−dimensional feature selection. – Artificial Intelligence Review 56(10): 11415-11471.
Ying, M. (2010): Quantum computation, quantum theory and AI. – Artificial Intelligence 174(2): 162-176.
Zhandry, M. (2012): How to construct quantum random functions. – In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, IEEE 9p.
Zhang, B., Sone, A., Zhuang, Q. (2022): Quantum computational phase transition in combinatorial problems. – NPJ Quantum Information 8(1): 11p.
Zhang, J., Chen, X. (2019): Robust sufficient dimension reduction via ball covariance. – Computational Statistics & Data Analysis 140: 144-154.
Zhou, S., Loke, T., Izaac, J.A., Wang, J.B. (2017): Quantum Fourier transform in computational basis. – Quantum Information Processing 16(3): 19p.