Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

An n-qubit quantum circuit performs a unitary operation on an exponentially large, 2n-dimensional, Hilbert space, which is a major source of quantum speed-ups. We develop a new “Quantum singular value transformation” algorithm that can directly harness the advantages of exponential dimensionality by applying polynomial transformations to the singular values of a block of a unitary operator. The transformations are realized by quantum circuits with a very simple structure - typically using only a constant number of ancilla qubits - leading to optimal algorithms with appealing constant factors. We show that our framework allows describing many quantum algorithms on a high level, and enables remarkably concise…

• NS
  National Science Foundation

  Awards: 1526380, grant 1526380
• UD
  U.S. Department of Energy
• Q
  QuantERA

  Award: QuantAlgo 680-91-034
• OO
  Office of Science
• MU
  Multidisciplinary University Research Initiative

  Award: W911NF-16-1-0349
• AS
  Advanced Scientific Computing Research
• AR
  Army Research Office

  Awards: W911NF-16-1-0349, W911NF-16-1, MURI award W911NF-16-1-0349, W911NF-16-1-, W911NF