Speaker: András Gilyén (Alfréd Rényi Institute of Mathematics)
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 show how Quantum Singular Value Transformation 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 this framework allows describing and unifying many quantum algorithms on a high level, and enables remarkably concise proofs for many prominent quantum algorithms, ranging from optimal Hamiltonian simulation to quantum linear equation solving (i.e., the HHL algorithm) and advanced amplitude amplification techniques. Finally, we also prove a quantum lower bound on spectral transformations.
