中国物理B ›› 2023, Vol. 32 ›› Issue (10): 100309-100309.doi: 10.1088/1674-1056/acb914

• • 上一篇    下一篇

A quantum algorithm for Toeplitz matrix-vector multiplication

Shang Gao(高尚) and Yu-Guang Yang(杨宇光)†   

  1. Faculty of Information Technology, Beijing University of Technology, Beijing 100124, China
  • 收稿日期:2022-11-03 修回日期:2023-01-18 接受日期:2023-02-06 出版日期:2023-09-21 发布日期:2023-09-27
  • 通讯作者: Yu-Guang Yang E-mail:yangyang7357@bjut.edu.cn
  • 基金资助:
    This work was supported by the National Natural Science Foundation of China (Grant Nos. 62071015 and 62171264).

A quantum algorithm for Toeplitz matrix-vector multiplication

Shang Gao(高尚) and Yu-Guang Yang(杨宇光)†   

  1. Faculty of Information Technology, Beijing University of Technology, Beijing 100124, China
  • Received:2022-11-03 Revised:2023-01-18 Accepted:2023-02-06 Online:2023-09-21 Published:2023-09-27
  • Contact: Yu-Guang Yang E-mail:yangyang7357@bjut.edu.cn
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (Grant Nos. 62071015 and 62171264).

RichHTML

0

PDF (PC)

69

赞

摘要： 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.

关键词: quantum algorithm, Toeplitz matrix-vector multiplication, circulant matrix

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.

Key words: quantum algorithm, Toeplitz matrix-vector multiplication, circulant matrix

中图分类号:  (Quantum computation architectures and implementations)

  • 03.67.Lx
03.67.Ac (Quantum algorithms, protocols, and simulations) 03.65.Fd (Algebraic methods)