Abstract Toeplitz matrix-vector multiplication is widely used in various fields, including optimal control, systolic finite field multipliers, multidimensional convolution, etc. In this paper, we first present a non-asymptotic quantum algorithm for Toeplitz matrix-vector multiplication with time complexity , where and are the condition number and the dimension of the circulant matrix extended from the Toeplitz matrix, respectively. For the case with an unknown generating function, we also give a corresponding non-asymptotic quantum version that eliminates the dependency on the -norm of the displacement of the structured matrices. Due to the good use of the special properties of Toeplitz matrices, the proposed quantum algorithms are sufficiently accurate and efficient compared to the existing quantum algorithms under certain circumstances.
Fund: This work was supported by the National Natural Science Foundation of China (Grant Nos. 62071015 and 62171264).
Corresponding Authors:
Yu-Guang Yang
E-mail: yangyang7357@bjut.edu.cn
Cite this article:
Shang Gao(高尚) and Yu-Guang Yang(杨宇光) A quantum algorithm for Toeplitz matrix-vector multiplication 2023 Chin. Phys. B 32 100309
[1] Shor P W 1994 Proceedings of the 35th Annual Symposium on Foundations of Computer Science, November 20-22, 1994, Washington, USA, p. 124 [2] Gover L K 1996 Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, May 22-24, 1996, Philadelphia, USA, p. 212 [3] Brandao F G S L and Svore K M 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, October 15-17, 2017, California, USA, p. 415 [4] Harrow A W, Hassidim A and Lloyd S 2009 Phys. Rev. Lett.103 150502 [5] Kerenidis I and Landman J 2021 Phys. Rev. A103 042415 [6] Kerenidis I, Landman J, Luongo A and Prakash A 2019 33rd Conference on Neural Information Processing Systems, December, 8-14, 2019, Vancouver, Canada, p. 4134 [7] Lloyd S, Garnerone S and Zanardi P 2016 Nat. Phys.7 10138 [8] Lloyd S, Mohseni M and Rebentrost P 2014 Nat. Phys.10 631 [9] Yu C H, Gao F, Lin S and Wang J 2019 Quantum Inf. Process.18 249 [10] Rebentrost P, Mohseni M and Lloyd S 2014 Phys. Rev. Lett.113 130503 [11] Yu C H, Gao F, Wang Q L and Wen Q Y 2016 Phys. Rev. A94 042311 [12] Duan B, Yuan J, Xu J and Li D 2019 Phys. Rev. A99 032311 [13] Pan S J, Wan L C, Liu H L, Wang Q L, Qin S J, Wen Q Y and Gao F 2020 Phys. Rev. A102 052402 [14] Gao S and Yang Y G 2022 Phys. Scr.98 010001 [15] Yu C H, Gao F, Liu C, Huynh D, Reynolds M and Wang J B 2019 Phys. Rev. A99 022301 [16] Gao S, Pan S J and Yang Y G 2023 Sci. China Inf. Sci.66 129501 [17] Li Z Q, Cai B B, Sun H W, Wan L C, Qin S J, Wen Q Y and Gao F 2022 Sci. China-Phys. Mech. Astron.65 290311 [18] Baros S, Chang C Y, Colon-Reyes G E and Bernstein A 2022 Automatica138 109926 [19] Cariow A and Gliszczyński M 2012 Elec. Rev.88 166 [20] Cenk M, Negre C and Hasan M A 2012 IEEE T. Comput.62 1345 [21] Glentis G O and Jakobsson A 2011 IEEE T. Signal Proces.59 4154 [22] Hasan M A, Meloni N, Namin A H and Negre C 2010 IEEE T. Comput.61 151 [23] Hasan M A and Negre C 2012 IEEE T. Comput.62 1467 [24] Li S W, Jiang Q B, Zhao Q J, Lu L and Feng Z L 2020 Front. Inform. Technol. Electron. Eng.21 1467 [25] Medišauskas L, Saalmann U and Rost J M 2018 J. Phys. B: At. Mol. Opt. Phys.52 015602 [26] Pan J S, Lee C Y, Sghaier A, Zeghid M, and Xie J F 2019 IEEE T. VLSI Syst.27 1614 [27] Rakhuba M V and Oseledets I V 2015 SIAM J. Sci. Comput.37 A565 [28] Taşkin H K and Cenk M 2018 Proceedings of the Fifth Workshop on Cryptography and Security in Computing Systems, January 24, 2018, Manchester, UK, p. 1 [29] Ye K and Lim L H 2016 IEEE Information Theory Workshop (ITW) 310 [30] Wan L C, Yu C H, Pan S J, Gao F, Wen Q Y and Qin S J 2018 Phys. Rev. A97 062322 [31] Wan L C, Yu C H, Pan S J, Qian S J, Gao F and Wen Q Y 2021 Phys. Rev. A104 062414 [32] Gray R 1972 IEEE T. Inform. Theory18 725 [33] Serra S 1998 Linear Algebra Appl.270 109 [34] Russell D C, Grenander U and Szegö G 1959 Proceedings of the Edinburgh Mathematical Society (University of California Press, 1958) p. 246 [35] Chan R H and Ng M K 1996 SIAM Rev.38 427 [36] Gray R M 2006 Foundations and TrendsoledR in Communications and Information Theory2 155 [37] Nielsen M A and Chuang I 2002 Quantum Computation and Quantum Information 10th Ed. (Cambridge: Cambridge University Press) p. 216 [38] Giovannetti V, Lloyd S and Maccone L 2008 Phys. Rev. Lett.100 160501 [39] Kerenidis I and Prakash A 2016 arXiv preprint arXiv:1603.08675 [40] Brassard G, Hoyer P, Mosca M and Tapp A 2002 Contemporary Mathematics305 53 [41] Zhou S S and Wang J B 2017 Roy. Soc. Open Sci.4 160906
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
