The quantum low-rank approximation problem

In the presence of noise, a quantum system is described by a density matrix often labeled ρ. Intuitively, noise creates uncertainty in our knowledge of the exact state, and ρ is the average state across many identical experiments. Under thermal noise, for example, the state of a system with hamiltonian H relaxes to a thermal state, ρth, which weighs the eigenstates of H with a Gibbs weight. In principal, ρ_th therefore consists of a convex combination of an exponential number of pure states, but for small temperatures, it's a good approximation to truncate to a small low-energy subspace. We make this truncation rigorous by defining and solving the quantum analog of the famous "low-rank approximation problem" which asks for the matrix B closest to A satisfying rank(B) <= R. The solution is intuitive: B is the truncation of A to the eigenspace with R largest eigenvalues which are known as the principal values. In the quantum case, A and B become quantum states ρ and σ which must be normalized, i.e. Tr[ρ] = Tr[σ] = 1, so simple truncation alone cannot work. A reasonable guess is that the quantum solution is just the classical one with renormalization. We show that this is correct, but by an additive renormalization and not a multiplicative one. Further, this additive renormalization solution is unique for any Schatten p-norm with p >= 2, but highly degenerate for p = 1 which the trace distance. We then develop a hybrid quantum-classical variational algorithm to solve the quantum low-rank approximation problem for p = 2. In particular, we show how to either learn a rank-constrained approximation of ρ by finding a circuit which prepares an approximate purification or by probabilistically sampling states generated from a fixed unitary acting on different computational basis states. This algorithm--which we call "quantum mixed state compiling," therefore provides a means to (i) learn a mixed state, (ii) learn a lower-rank approximation of a mixed state, (iii) perform principal components analysis, and more.