Demonstration of Quantum Sparse Matrix inversion with Quantum Singular Value Transformation

Quantum singular value transformation (QSVT) is a powerful framework that generalizes several quantum algorithms, including quantum linear system solver. Although the QSVT-based linear solvers have attracted significant amount of attention due to their potential exponential speed-up over the classical counterparts, their explicit gate complexities have not been sufficiently discussed. In this work, we focused on the linear systems with Toeplitz matrix and evaluated the gate complexity of the QSVT-based linear solvers, by explicitly implementing the block encoding of the matrix and addressing instability in calculating the rotation angles in the QSVT. The results numerically confirmed that the Toffoli-gate counts scale linearly with respect to the matrix size.