Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations

Qisheng Wang, Zhicheng Zhang

Since Harrow, Hassidim, and Lloyd (2009) showed that a system of linear equations with $N$ variables and condition number $\kappa$ can be solved on a quantum computer in $\operatorname{…