A Simple Quantum Linear-System Solver via Dissipation

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 $\mathrm{\Theta }({\kappa }^2\log (1\mathrm{/}\text{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\text{\hspace{0.17em}⁣}({\kappa }^2\log (1\mathrm{/}\text{eps})\frac{\log (\kappa \mathrm{/}\text{eps})}{\log \log (\kappa \mathrm{/}\text{eps})})$ query complexity for both $U_A$, the block encoding of $A$, and $U_b$, the $\mathrm{\mid }b⟩$ state preparation unitary.