A Simple Quantum Linear-System Solver via Dissipation

Abstract

Dissipation has been recently demonstrated as a powerful primitive for designing quantum algorithms. We apply this viewpoint directly to linear-system solving, $Ax=b$. We construct a simple purely dissipative Lindbladian whose unique fixed point encodes the linear-system solution. We prove dimension-independent trace-distance mixing in $\Theta(\kappa^2\log(1/\eps))$ time. We then show how to run this Lindbladian on digital quantum computers via collective block encoding and Lindbladian simulation, resulting in an $O\!\left(\kappa^2\log(1/\eps) \frac{\log(\kappa/\eps)}{\log\log(\kappa/\eps)}\right)$ query complexity for both $U_A$, the block encoding of $A$, and $U_b$, the $|b\rangle$ state preparation unitary.