Quantum Singular Value Transformation & Its Algorithmic Applications

In this dissertation we study how efficiently quantum computers can solve various problems, and how large speedups can be achieved compared to classical computers. In particular we develop a generic quantum 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 quantum singular value transformation unifies a large number of prominent quantum algorithms, and show several problems where it leads to new quantum algorithms or improves earlier approaches. We develop an improved version of Jordan's quantum algorithm for gradient computation that can speed up the training of variational quantum optimization, and prove an essentially matching lower bound on quantum gradient computation. We also show that a quantum 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 quantum SDP-solvers, introducing several new techniques, and improve on all prior quantum algorithms for SDP-solving. Finally we study the variable version of the Lovász Local Lemma (LLL) and its quantum generalization. We improve on the previous constructive quantum 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.