The Quantum Low-Rank Approximation Problem

Nicholas Ezzell, University of Southern California

Photo of Nicholas Ezzell

We define and solve a quantum version of the famous low-rank approximation problem. Specifically, we consider the task of minimizing the distance 𝐷(ρ,Οƒ) between two normalized quantum states ρ and Οƒ when ρ is fixed and the rank of sigma is constrained to be at most 𝑅. For both the trace distance and the Hilbert-Schmidt distance, we analytically solve for the optimal state sigma that minimizes the respective distance. For the Hilbert-Schmidt distance, the unique optimal state is Οƒβˆ— = τ𝑅 + 𝑁𝑅 where τ𝑅 = Π𝑅ρΠ𝑅 is given by projecting ρ onto its 𝑅 principle components with projector Π𝑅, and 𝑁𝑅 is an additive normalization factor given by 𝑁𝑅 = 1 βˆ’ π‘‡π‘Ÿ[τ𝑅]Π𝑅. For the trace distance, this state is also optimal but not uniquely optimal, and we provide the full set of states that are optimal. This suggests that in applications where the order of the principle components is important, one should prefer minimizing the Hilbert-Schmidt distance. As a natural follow up to this analytical work, we also propose and test a variational quantum algorithm (VQA) to find a low-depth quantum circuit which prepares Οƒβˆ— on quantum hardware. We consider two types of ansΓ€tze for the circuit: an ansatz which learns a purification of Οƒβˆ— and one which represents it as a convex combination of pure states. In both cases, the cost is efficiently computable on a quantum computer using a SWAP test (and slight variations), and we find in practice that the number of cost function evaluations needed to learn a state scales better than traditional methods to learn an unknown quantum state like full state tomography. By construction, a well learned convex combination ansatz also encodes the principle components of the target state with no additional processing, so our method doubles as a means of quantum PCA.

Abstract Author(s): Nic Ezzell, Elliott M. Ball, Aliza Siddiqui, ZoΓ« Holmes, Mark W. Wilde, Andrew T. Sornborger, Patrick J. Coles