Quantum singular-value decomposition of nonsparse low-rank matrices

Patrick Rebentrost, Adrian Steffens, Iman Marvian, and Seth Lloyd
Phys. Rev. A 97, 012327 – Published 24 January 2018

Abstract

We present a method to exponentiate nonsparse indefinite low-rank matrices on a quantum computer. Given access to the elements of the matrix, our method allows one to determine the singular values and their associated singular vectors in time exponentially faster in the dimension of the matrix than known classical algorithms. The method extends to non-Hermitian and nonsquare matrices via matrix embedding. Moreover, our method preserves the phase relations between the singular spaces allowing for efficient algorithms that require operating on the entire singular-value decomposition of a matrix. As an example of such an algorithm, we discuss the Procrustes problem of finding a closest isometry to a given matrix.

  • Received 13 November 2017

DOI:https://doi.org/10.1103/PhysRevA.97.012327

©2018 American Physical Society

Physics Subject Headings (PhySH)

  1. Research Areas
Quantum Information, Science & Technology

Authors & Affiliations

Patrick Rebentrost1,2,*, Adrian Steffens1,3, Iman Marvian1, and Seth Lloyd1,4,†

  • 1Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
  • 2Xanadu, 372 Richmond St W, Toronto, Canada M5V 2L7
  • 3Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany
  • 4Department of Mechanical Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA

  • *patrick@xanadu.ai
  • slloyd@mit.edu

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 97, Iss. 1 — January 2018

Reuse & Permissions
Access Options
CHORUS

Article Available via CHORUS

Download Accepted Manuscript
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×