Quantum Singular Value Transformation & Its Algorithmic Applications
András Gilyén · 2019
In this dissertation we study how efficiently computers can solve various problems, and how large speedups can be achieved compared to classical computers. In particular we develop a generic algorithmic framework that we call quantum singular value transformation, capable of working with exponentially large matrices, that can apply polynomial transformations to the singular values of a block of a unitary. We show how singular value transformation unifies a large number of prominent algorithms, and show several problems where it leads to new algorithms or improves earlier approaches. We develop an improved version of Jordan's algorithm for gradient computation that can speed up the training of variational optimization, and prove an essentially matching lower bound on gradient computation. We also show that a computer can very efficiently compute an approximate subgradient of a convex Lipschitz function. Combining this with some recent classical results we get improvements for black-box convex optimization problems. Then we take a new perspective on SDP-solvers, introducing several new techniques, and improve on all prior algorithms for SDP-solving. Finally we study the variable version of the Lovasz Local Lemma (LLL) and its generalization. We improve on the previous constructive results by designing an algorithm that works efficiently for non-commuting terms as well, assuming that the system is uniformly gapped. For the variable version of the classical LLL we find optimal bounds for the guaranteed-to-be-feasible probabilities on cyclic dependency graphs.