Quantum Computing leverages the quantum properties of subatomic matter to enable algorithms 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 problems that process massive amounts of data, raising the natural question of how quantum computers may be leveraged to solve these faster. This dissertation proposal presents some encouraging results on the design of quantum algorithms for machine learning and optimization.

We show a quantum speedup for convex optimization by extending quantum gradient estimation algorithms to efficiently compute subgradients of non-differentiable functions. We also developed a quantum framework for simulated annealing algorithms which is used to show a quantum speedup in estimating the volumes of convex bodies. We designed 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 l-2 margin SVMs. Finally, we formulate a model of quantum Wasserstein GANs in order to facilitate the robust generative learning of quantum states.

I will present plans for extending this work to new areas on the intersection of learning and quantum computing, including developing quantum algorithms for submodular optimization and logconcave sampling, and showing a theoretical separation between the representational properties of parameterized quantum circuits (quantum neural networks) and classical neural networks.

Examining Committee: 

 

                          Chair:               Dr. Xiaodi Wu         
                          Dept rep:         Dr. Furong Huang
                          Members:        Dr. Andrew Childs
                                                     Dr. Soheil Feizi