The complexity of the one clean qubit model, the aBc problem, and quantum online optimization

Abstract

In the first part of the thesis, we study the one clean qubit model in the communication complexity setting. We show that classically simulating the one clean qubit model with polynomially small additive error is hard. In addition, we conjecture that, even with constant additive error, classical simulation of the one clean qubit model is hard as well. We also study a vector-matrix-vector multiplication problem in its decision and approximation form, both in the communication and streaming model.

In the second part of the thesis, we study how quantum computing can be used to improve the time complexity of algorithms in the fault-tolerant regime. In the online setting, we propose quantum algorithms that obtain a quadratic improvement in the problem size for both portfolio optimization and robust optimization problems. The speedup is due to techniques such as quantum state preparation, quantum inner and norm estimation and quantum multi-sampling.