András Gilyén: Quantum singular value transformations & its algorithmic applications
0An invited talk by András Gilyén at the 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), Day 3. TQC 2019 was hosted June 3-5, 2019 by the Joint Center for Quantum Information and Computer Science at the University of Maryland (QuICS). More information about TQC can be found at https://www.tqcconference.org.
Abstract: An n-qubit quantum circuit performs a unitary operation on an exponentially large, 2^n-dimensional Hilbert space, which is a major source of quantum speed-ups. We develop a new “Quantum singular value transformation” algorithm that permits directly harnessing the advantages of exponential dimensionality by applying polynomial ransformations 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. \br The presented framework unifies a host of quantum algorithms ranging from linear equation solving to quantum simulation and quantum walks. Many prominent quantum algorithms become simple corollaries, when viewed from the right angle, and the new perspective also reveals hitherto unknown algorithms.