Classical and quantum computation for principal component analysis of multi-dimensional datasets

Abstract

Classical and quantum computational systems and methods for principal component analysis of multi-dimensional datasets are presented. A dataset is encoded in a tensor of rank p, where p is a positive integer that may be greater than 2. The classical methods are based on linear algebra. The quantum methods achieve a quartic speedup while using exponentially smaller space than the fastest classical algorithm, and a super-polynomial speedup over classical algorithms that use only polynomial space. In particular, an improved threshold for recovery is achieved. The presented classical and quantum methods work for both even and odd ranked tensors. Accordingly, quantum computation may be applied to large-scale inference problems, e.g., machine learning applications or other applications that involve highly-dimensional datasets.