Quantum Linear System Algorithm for General Matrices in System Identification

Abstract

'Chen Dong' 'Shao-Ming Fei' 'Ming Li' 'Shunlong Luo'] Solving linear systems of equations is one of the most common and basic problems in classical identification systems. Given a coefficient matrix A and a vector b, the ultimate task is to find the solution x such that $Ax=b$. Based on the technique of the singular value estimation, the paper proposes a modified quantum scheme to obtain the quantum state $|x〉$ corresponding to the solution of the linear system of equations in $O(κ2r$poly $(log(mn)/ϵ))$ time for a general $m\timesn$ dimensional A, which is superior to existing quantum algorithms, where $κ$ is the condition number, r is the rank of matrix A and $ϵ$ is the precision parameter. Meanwhile, we also design a quantum circuit for the homogeneous linear equations and achieve an exponential improvement. The coefficient matrix A in our scheme is a sparsity-independent and non-square matrix, which can be applied in more general situations. Our research provides a universal quantum linear system solver and can enrich the research scope of quantum computation.