Quantum discriminative canonical correlation analysis. (English) Zbl 1542.81239
Summary: Discriminative canonical correlation analysis (DCCA) is a powerful supervised feature extraction technique for two sets of multivariate data, which has wide applications in pattern recognition. DCCA consists of two parts: (i) mean-centering that subtracts the sample mean from the sample and (ii) solving the generalized eigenvalue problem. The cost of DCCA is expensive when dealing with a large number of high-dimensional samples. To solve this problem, here we propose a quantum DCCA algorithm. Specifically, we devise an efficient method to compute the mean of all samples and then use block-Hamiltonian simulation and quantum phase estimation to solve the generalized eigenvalue problem. Our algorithm achieves a polynomial speedup in the dimension of samples under certain conditions over its classical counterpart.
Keywords:
quantum computing; quantum algorithm; discriminative canonical correlation analysis; feature extractionReferences:
| [1] | Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124-134 (1994) |
| [2] | Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC’ 96, pp. 212-219 (1996) · Zbl 0922.68044 |
| [3] | Rebentrost, P.; Mohseni, M.; Lloyd, S., Quantum support vector machine for big data classification, Phys. Rev. Lett., 113, 13, 130503 (2014) · doi:10.1103/PhysRevLett.113.130503 |
| [4] | Pérez-Salinas, A.; Cervera-Lierta, A.; Gil-Fuster, E.; Latorre, JI, Data re-uploading for a universal quantum classifier, Quantum, 4, 226 (2020) · doi:10.22331/q-2020-02-06-226 |
| [5] | Du, Y.; Hsieh, MH; Liu, T.; Tao, D., A grover-search based quantum learning scheme for classification, New J. Phys., 23, 2, 023020 (2021) · doi:10.1088/1367-2630/abdefa |
| [6] | Huang, R.; Tan, XQ; Xu, QS, Variational quantum tensor networks classifiers, Neurocomputing, 452, 89-98 (2021) · doi:10.1016/j.neucom.2021.04.074 |
| [7] | Wang, G., Quantum algorithm for linear regression, Phys. Rev. A, 96, 012335 (2017) · doi:10.1103/PhysRevA.96.012335 |
| [8] | Yu, CH; Gao, F.; Wen, QY, An improved quantum algorithm for ridge regression, IEEE Trans. Knowl. Data Eng., 33, 858-866 (2021) |
| [9] | Yu, CH; Gao, F.; Liu, C.; Huynh, D.; Reynolds, M.; Wang, J., Quantum algorithm for visual tracking, Phys. Rev. A, 99, 022301 (2019) · doi:10.1103/PhysRevA.99.022301 |
| [10] | Lloyd, S.; Mohseni, M.; Rebentrost, P., Quantum principal component analysis, Nat. Phys., 10, 9, 631-633 (2014) · doi:10.1038/nphys3029 |
| [11] | Cong, I.; Duan, L., Quantum discriminant analysis for dimensionality reduction and classification, New J. Phys., 18, 7, 073011 (2016) · Zbl 1456.81136 · doi:10.1088/1367-2630/18/7/073011 |
| [12] | Duan, B.; Yuan, J.; Xu, J.; Li, D., Quantum algorithm and quantum circuit for a-optimal projection: Dimensionality reduction, Phys. Rev. A, 99, 3, 032311 (2019) · doi:10.1103/PhysRevA.99.032311 |
| [13] | Pan, SJ; Wan, LC; Liu, HL; Wu, YS; Qin, SJ; Wen, QY; Gao, F., Quantum algorithm for neighborhood preserving embedding, Chinese Phys. B, 31, 216-227 (2022) · doi:10.1088/1674-1056/ac523a |
| [14] | Harrow, AW; Hassidim, A.; Lloyd, S., Quantum algorithm for linear systems of equations, Phys. Rev. Lett., 103, 15, 150502 (2009) · doi:10.1103/PhysRevLett.103.150502 |
| [15] | Wossnig, L.; Zhao, Z.; Prakash, A., Quantum linear system algorithm for dense matrices, Phys. Rev. Lett., 120, 050502 (2018) · doi:10.1103/PhysRevLett.120.050502 |
| [16] | Wan, LC; Yu, CH; Pan, SJ; Gao, F.; Wen, QY; Qin, SJ, Asymptotic quantum algorithm for the toeplitz systems, Phys. Rev. A, 97, 062322 (2018) · doi:10.1103/PhysRevA.97.062322 |
| [17] | Liu, H.L., Qin, S.J., Wan, L.C., Yu, C.H., Pan, S.J., Gao, F., Wen, Q.Y.: A quantum algorithm for solving eigenproblem of the laplacian matrix of a fully connected graph. arXiv:2203.14451v1 (2022) |
| [18] | Sun, T.K., Chen, S.C., Yang, J.Y., Shi, P.F.: A novel method of combined feature extraction for recognition. In: 2008 Eighth IEEE International Conference on Data Mining, pp. 1043-1048 (2008) |
| [19] | Yang, XH; Liu, WF; Liu, W.; Tao, DC, A survey on canonical correlation analysis, IEEE Trans. Knowl. Data Eng., 33, 6, 2349-2368 (2021) · doi:10.1109/TKDE.2019.2958342 |
| [20] | Sargin, M.E., Erzin, E., Yemez, Y., Tekalp, A.M.: Multimodal speaker identification using canonical correlation analysis. 2006 IEEE International Conference on Acoustics Speech and Signal Processing Proceedings 1, I-I (2006) |
| [21] | Sun, QS; Zeng, SG; Liu, Y.; Heng, PA; Xia, DS, A new method of feature fusion and its application in image recognition, Pattern Recogn., 38, 12, 2437-2448 (2005) · doi:10.1016/j.patcog.2004.12.013 |
| [22] | Wegelin, J.: A survey of partial least squares (pls) methods, with emphasis on the two-block case. Technical report (2000) |
| [23] | Koide-Majima, N.; Majima, K., Quantum-inspired canonical correlation analysis for exponentially large dimensional data, Neural Netw, 135, 55-67 (2021) · Zbl 1521.68131 · doi:10.1016/j.neunet.2020.11.019 |
| [24] | Hou, YY; Li, J.; Chen, XB; Tian, Y., Quantum partial least squares regression algorithm for multiple correlation problem, Chinese Phys. B, 31, 198-207 (2021) |
| [25] | Kerenidis, I.; Landman, J.; Luongo, A.; Prakash, A.; Wallach, H.; Larochelle, H.; Beygelzimer, A.; Alche-Buc, F.; Fox, E.; Garnett, R., q-means: A quantum algorithm for unsupervised machine learning, Advances in Neural Information Processing Systems (2019), Red Hook, NY: Curran Associates Inc., Red Hook, NY |
| [26] | Brassard, G.; Hoyer, P.; Mosca, M.; Tapp, A., Quantum amplitude amplification and estimation, Contemp. Math., 305, 53-74 (2002) · Zbl 1063.81024 · doi:10.1090/conm/305/05215 |
| [27] | Wiebe, N.; Kapoor, A.; Svore, KM, Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning, Quantum Info. Comput., 15, 3-4, 316-356 (2015) |
| [28] | Zhou, SS; Loke, T.; Izaac, JA; Wang, JB, Quantum fourier transform in computational basis, Quantum Inform. Process., 16, 3, 82 (2017) · Zbl 1373.81161 · doi:10.1007/s11128-017-1515-0 |
| [29] | Ruiz-Perez, L.; Garcia-Escartin, JC, Quantum arithmetic with the quantum fourier transform, Quantum Inform. Process., 16, 17, 152 (2017) · Zbl 1373.81150 · doi:10.1007/s11128-017-1603-1 |
| [30] | Shao, C.P., Liu, J.P.: Quantum algorithms for the polynomial eigenvalue problems. arXiv:2010.15027v1 quant-ph (2020) |
| [31] | Chakraborty, S., Gilyén, A., Jeffery, S.: The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 33:1-33:14 (2019) · Zbl 07561526 |
| [32] | Gilyén, A., Su, Y., Low, G.H., Wiebe, N.: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 193-204 (2019) · Zbl 1433.68147 |
| [33] | Chakraborty, S., Gilyén, A., Jeffery, S.: The power of block-encoded matrix powers: improved regression techniques via faster hamiltonian simulation. arXiv: 1804.01973v2 (2018) |
| [34] | Giovannetti, V.; Lloyd, S.; Maccone, L., Quantum random access memory, Phys. Rev. Lett., 100, 160501 (2008) · Zbl 1228.81125 · doi:10.1103/PhysRevLett.100.160501 |
| [35] | Asaka, R.; Sakai, K.; Yahagi, R., Quantum random access memory via quantum walk, Quantum Sci. Technol, 6, 035004 (2020) · doi:10.1088/2058-9565/abf484 |
| [36] | Hann, CT; Lee, G.; Girvin, S.; Jiang, L., Resilience of quantum random access memory to generic noise, PRX Quantum, 2, 020311 (2021) · doi:10.1103/PRXQuantum.2.020311 |
| [37] | Arunachalam, S.; Gheorghiu, V.; Jochym-O’Connor, T.; Mosca, M.; Srinivasan, PV, On the robustness of bucket brigade quantum ram, New J. Phys., 17, 123010 (2015) · Zbl 1452.81061 · doi:10.1088/1367-2630/17/12/123010 |
| [38] | Paler, A.; Oumarou, O.; Basmadjian, R., Parallelizing the queries in a bucket-brigade quantum random access memory, Phys. Rev. A, 102, 032608 (2020) · doi:10.1103/PhysRevA.102.032608 |
| [39] | Phalak, K., Li, J., Ghosh, S.: Approximate quantum random access memory architectures. arXiv: 2210.14804 (2022) |
| [40] | Mitarai, K.; Kitagawa, M.; Fujii, K., Quantum analog-digital conversion, Phys. Rev. A, 99, 012301 (2019) · doi:10.1103/PhysRevA.99.012301 |
| [41] | Grover, LK, Fixed-point quantum search, Phys. Rev. Lett., 95, 150501 (2005) · Zbl 1255.81106 · doi:10.1103/PhysRevLett.95.150501 |
| [42] | Yoder, TJ; Low, GH; Chuang, IL, Fixed-point quantum search with an optimal number of queries, Phys. Rev. Lett., 113, 210501 (2014) · doi:10.1103/PhysRevLett.113.210501 |
| [43] | Chakraborty, S., Gilyén, A., Jeffery, S.: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. arXiv: 1806.01838v1 (2018) |
| [44] | Ahuja, A., Kapoor, S.: A quantum algorithm for finding the maximum. arXiv: quant-ph/9911082 (1999) |
| [45] | Han, JW; Kamber, M.; Pei, J.; Han, JW; Kamber, M.; Pei, J., 3-data preprocessing, Data Mining (Third Edition), The Morgan Kaufmann Series in Data Management Systems, 83-124 (2012), Boston: Morgan Kaufmann, Boston · Zbl 1230.68018 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
