|
|
|
A quantum algorithm for Toeplitz matrix-vector multiplication |
| Shang Gao(高尚) and Yu-Guang Yang(杨宇光)† |
| Faculty of Information Technology, Beijing University of Technology, Beijing 100124, China |
|
|
|
|
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 ${\cal O}(\kappa \mathrm{polylog}n)$, where $\kappa $ and $2n$ 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 $L_{1}$-norm $\varrho $ 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.
|
Received: 03 November 2022
Revised: 18 January 2023
Accepted manuscript online: 06 February 2023
|
|
PACS:
|
03.67.Lx
|
(Quantum computation architectures and implementations)
|
| |
03.67.Ac
|
(Quantum algorithms, protocols, and simulations)
|
| |
03.65.Fd
|
(Algebraic methods)
|
|
| 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. A 103 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. A 94 042311
[12] Duan B, Yuan J, Xu J and Li D 2019 Phys. Rev. A 99 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. A 102 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. A 99 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 Automatica 138 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. A 97 062322
[31] Wan L C, Yu C H, Pan S J, Qian S J, Gao F and Wen Q Y 2021 Phys. Rev. A 104 062414
[32] Gray R 1972 IEEE T. Inform. Theory 18 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 Theory 2 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 Mathematics 305 53
[41] Zhou S S and Wang J B 2017 Roy. Soc. Open Sci. 4 160906 |
| No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
Altmetric
|
|
blogs
Facebook pages
Wikipedia page
Google+ users
|
Online attention
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.
View more on Altmetrics
|
|
|
