Probabilistic quantum algorithm for Lyapunov equations and matrix inversion

Abstract

We present a probabilistic quantum algorithm for preparing mixed states which, in expectation, are proportional to the solutions of Lyapunov equations -- linear matrix equations ubiquitous in the analysis of classical and quantum dynamical systems. Building on previous results by Zhang et al., arXiv:2304.04526, at each step the algorithm can (i) return the current state, (ii) apply a trace nonincreasing completely positive map, or (iii) restart. We introduce a deterministic stopping rule, which leads to an efficient algorithm with a bounded expected number of calls to oracles representing the two input matrices of the Lyapunov equations. We also consider preparing a mixed state that approximates the normalized inverse of a positive definite matrix $A$. In its most general form, the algorithm generates mixed states, which approximate matrix-valued weighted sums and integrals. It can be shown that block encodings and states yield two incomparable computational resources even when they represent the same piece of data. While block encodings of functions have received much attention in the literature, our work takes a step toward the less explored problem of encoding functions into mixed states.