Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Review A

Comment on “Asymptotic quantum algorithm for the Toeplitz systems”

Jesús Gutiérrez-Gutiérrez, Bruno Sunsundegi, Marta Zárraga-Rodríguez, Xabier Insausti

Published Aug 27, 2024• 0 citations
Publisher

Abstract

In their recent paper [], Wan proposed a quantum algorithm to solve systems of linear equations A x = b , where A is an n × n Toeplitz matrix generated by the Fourier coefficients of a continuous, 2 π -periodic, and positive function f . For large enough n , they claimed that the algorithm is valid for all b . In this Comment we prove that, in general, this is not true. Published by the American Physical Society 2024

DOI
10.1103/physreva.110.026401

Related papers

Asymptotic quantum algorithm for the Toeplitz systems

Lin‐Chun Wan, Chao‐Hua Yu, Shi‐Jie Pan +3 more

Solving the Toeplitz systems, which involves finding the vector $x$ such that ${T}_{n}x=b$ given an $n\ifmmode\times\else\texttimes\fi{}n$ Toeplitz matrix ${T}_{n}$ and a vector $b$, has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the linear equations of Toeplitz matrices, in which the Toeplitz matrices are generated by discretizing a continuous function. It is shown that our algorithm's complexity is nearly $O(\ensuremath{\kappa}\mathrm{poly}(logn))$, where $\ensuremath{\kappa}$ and $n$ are the condition number and the dimension of ${T}_{n}$, respectively. This implies our algorithm is exponentially faster than its classical counterpart if $\ensuremath{\kappa}=O(\mathrm{poly}(logn))$. Since no assumption on the sparseness of ${T}_{n}$ is demanded in our algorithm, it can serve as an example of quantum algorithms for solving nonsparse linear systems.

arXiv:1608.02184•Physical Review A•Jun 15, 2018•57 citations

Quantum Algorithm for the Toeplitz Systems

Lin‐Chun Wan, Chao‐Hua Yu, Shi‐Jie Pan +2 more

Solving the Toeplitz systems, which is to find the vector $x$ such that $T_nx = b$ given a $n\times n$ Toeplitz matrix $T_n$ and a vector $b$, has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the Toeplitz systems, in which a quantum state encoding the solution with error $\epsilon$ is generated. It is shown that our algorithm's complexity is nearly linear in the condition number, and polylog in the dimensions $n$ and in the inverse error $\epsilon^{-1}$. This implies our algorithm is exponentially faster than the best classical algorithm for the same problem if the condition number of $T_n$ is $O(\textrm{poly}(\textrm{log}\,n))$. Since no assumption on the sparseness of $T_n$ is demanded in our algorithm, the algorithm can serve as an example of quantum algorithms for solving non-sparse linear systems.

•Aug 7, 2016•1 citation

A quantum algorithm for Toeplitz matrix-vector multiplication

Shang Gao, Yu-Guang 宇光 Yang 杨

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 O ( κ polylog n ) , where κ 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 ρ 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.

Chinese Physics B•Feb 6, 2023•4 citations

A variational quantum algorithm for the Poisson equation based on the banded Toeplitz systems

Xiaoqi Liu, Yue-Di Qu, Ming Li +1 more

Abstract To solve the Poisson equation it is usually possible to discretize it into solving the corresponding linear system Ax = b. Variational quantum algorithms (VQAs) for the discretized Poisson equation have been studied before. We present a VQA based on the banded Toeplitz systems for solving the Poisson equation with respect to the structural features of matrix A. In detail, we decompose the matrices A and A 2 into a linear combination of the corresponding banded Toeplitz matrix and sparse matrices with only a few non-zero elements. For the one-dimensional Poisson equation with different boundary conditions and the d-dimensional Poisson equation with Dirichlet boundary conditions, the number of decomposition terms is less than that reported in [Phys. Rev. A 2023 108, 032 418 ]. Based on the decomposition of the matrix, we design quantum circuits that efficiently evaluate the cost function. Additionally, numerical simulation verifies the feasibility of the proposed algorithm. Finally, the VQAs for linear systems of equations and matrix-vector multiplications with the K-banded Toeplitz matrix T n K are given, where T n K ∈ R n × n and K ∈ O ( ploylog n ) .

Communications in Theoretical Physics•Oct 28, 2024•2 citations

Publisher’s Note: Preconditioned Quantum Linear System Algorithm [Phys. Rev. Lett.110, 250504 (2013)]

B. D. Clader, B. C. Jacobs, C. Sprouse

Received 9 July 2013DOI:https://doi.org/10.1103/PhysRevLett.111.049903© 2013 American Physical Society

Physical Review Letters•Jul 23, 2013•4 citations

Comment on “Phase-Space Approach to Solving the Time-Independent Schrödinger Equation”

James Corgan Brown, Tucker Carrington

A Comment on the Letter by A. Shimshovitz and D. J. TannorPhys. Rev. Lett. 109, 070402 (2012).Received 25 June 2014DOI:https://doi.org/10.1103/PhysRevLett.114.058901© 2015 American Physical Society

Physical Review Letters•Feb 5, 2015•8 citations
In their recent paper [], Wan proposed a quantum algorithm to solve systems of linear equations A x = b , where A is an n × n Toeplitz matrix generated by the Fourier coefficients of a continuous, 2 π -periodic, and positive function f . For large enough n , they claimed that the algorithm is valid for all b . In this Comment we prove that, in general, this is not true. Published by the American Physical Society 2024
Solving the Toeplitz systems, which involves finding the vector xxx such that Tnx=b{T}_{n}x=bTn​x=b given an $n\ifmmode\times\else\texttimes\fi{}n$ Toeplitz matrix Tn{T}_{n}Tn​ and a vector bbb, has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the linear equations of Toeplitz matrices, in which the Toeplitz matrices are generated by discretizing a continuous function. It is shown that our algorithm's complexity is nearly $O(\ensuremath{\kappa}\mathrm{poly}(logn))$, where $\ensuremath{\kappa}$ and nnn are the condition number and the dimension of Tn{T}_{n}Tn​, respectively. This implies our algorithm is exponentially faster than its classical counterpart if $\ensuremath{\kappa}=O(\mathrm{poly}(logn))$. Since no assumption on the sparseness of Tn{T}_{n}Tn​ is demanded in our algorithm, it can serve as an example of quantum algorithms for solving nonsparse linear systems.
Solving the Toeplitz systems, which is to find the vector xxx such that Tnx=bT_nx = bTn​x=b given a n×nn\times nn×n Toeplitz matrix TnT_nTn​ and a vector bbb, has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the Toeplitz systems, in which a quantum state encoding the solution with error ϵ\epsilonϵ is generated. It is shown that our algorithm's complexity is nearly linear in the condition number, and polylog in the dimensions nnn and in the inverse error ϵ−1\epsilon^{-1}ϵ−1. This implies our algorithm is exponentially faster than the best classical algorithm for the same problem if the condition number of TnT_nTn​ is O(poly(log n))O(\textrm{poly}(\textrm{log}\,n))O(poly(logn)). Since no assumption on the sparseness of TnT_nTn​ is demanded in our algorithm, the algorithm can serve as an example of quantum algorithms for solving non-sparse linear systems.
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 O ( κ polylog n ) , where κ 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 ρ 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.
Abstract To solve the Poisson equation it is usually possible to discretize it into solving the corresponding linear system Ax = b. Variational quantum algorithms (VQAs) for the discretized Poisson equation have been studied before. We present a VQA based on the banded Toeplitz systems for solving the Poisson equation with respect to the structural features of matrix A. In detail, we decompose the matrices A and A 2 into a linear combination of the corresponding banded Toeplitz matrix and sparse matrices with only a few non-zero elements. For the one-dimensional Poisson equation with different boundary conditions and the d-dimensional Poisson equation with Dirichlet boundary conditions, the number of decomposition terms is less than that reported in [Phys. Rev. A 2023 108, 032 418 ]. Based on the decomposition of the matrix, we design quantum circuits that efficiently evaluate the cost function. Additionally, numerical simulation verifies the feasibility of the proposed algorithm. Finally, the VQAs for linear systems of equations and matrix-vector multiplications with the K-banded Toeplitz matrix T n K are given, where T n K ∈ R n × n and K ∈ O ( ploylog n ) .