The Quantum Low-Rank Approximation Problem
Nicholas Ezzell, University of Southern California
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