log in  |  register  |  feedback?  |  help  |  web accessibility
Quantum Computing for Optimization and Machine Learning
Shouvanik Chakrabarti
Thursday, March 31, 2022, 8:30-11:30 am Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Quantum Computing leverages the quantum properties of subatomic matter to enable computations faster than those possible on a regular computer. Quantum Computers have become increasingly practical in recent years, with some small-scale machines becoming available for public use. The rising importance of machine learning has highlighted a large class of computing and optimization problems that process massive amounts of data and incur correspondingly large computational costs. This raises the natural question of how quantum computers may be leveraged to solve these problems more efficiently. This dissertation presents some encouraging results on the design of quantum algorithms for machine learning and optimization.

We first focus on tasks with provably more efficient quantum algorithms. We show a quantum speedup for convex optimization by extending quantum gradient estimation algorithms to efficiently compute subgradients of non-differentiable functions. We also develop a quantum framework for simulated annealing algorithms which is used to show a quantum speedup in estimating the volumes of convex bodies. Finally, we demonstrate a quantum algorithm for the solving matrix games, which can be applied to a variety of learning problems such as linear classification, minimum enclosing ball, and $\ell-2$ margin SVMs.

We then shift our focus to variational quantum algorithms, which describe a family of heuristic algorithms that use parameterized quantum circuits as function models that can be fit for various learning and optimization tasks. We seek to analyze the properties of these algorithms including their efficient formulation and training, expressivity, and the convergence of the associated optimization problems. We formulate a model of quantum Wasserstein GANs in order to facilitate the robust and scalable generative learning of quantum states. We also investigate the expressivity of so called Quantum Neural Networks compared to classical ReLU networks and investigate both theoretical and empirical separations. Finally, we leverage the theory of over-parameterization in variational systems to give sufficient conditions on the convergence of Variational Quantum Eigensolvers. We use these conditions to design principles to study and evaluate the design of these systems

Examining Committee:
Dean's Representative:
Dr. Xiaodi Wu    
Dr. Alexander Barg    
Dr. Andrew M. Childs    
Dr. Soheil Feizi    
Dr. Furong Huang

Shouvanik Chakrabarti is a PhD student in the Department of Computer Science advised by Dr. Xiaodi Wu. His research focusses mainly on provable and variational quantum algorithms for important applications in optimization, machine learning, and finance. He is also interested in classical machine learning and theoretical computer science in general.

This talk is organized by Tom Hurst