Randomness and Quantumness in Space-Bounded Computation

Abstract

In the field of computational complexity theory, we study the power and limits of different computational resources and the interplay between them. The constraints on space complexity provide a natural and interesting setting, that is often more tractable than the time-restricted counterparts. In this dissertation, we specifically study how randomness and quantumness interact with space complexity. Our results consist of two parts. In the first part, we present our algorithmic results. We show that randomness used for BPL algorithms can be reduced to logarithmic with the access to untrusted random bits. Consequentially, every BPL algorithm can be certifiably derandomized using presumably hard functions. For quantum computing, we show how to eliminate intermediate measurement in logspace quantum circuits, and simulate general quantum algorithms in BQL with only unitaries. In the second part, we present our lower bound results. For decision problems, we propose the coupon-collector model where one receives random coordinates of the input, and prove a quadratic time-space tradeoff lower bound in the model. For computing multi-output functions, we prove the first polynomial separation between randomized and deterministic oblivious computation for total functions. And for learning, we prove an exponential time lower bound against classical-quantum hybrid learners with sub-quadratic classical memory and sublinear quantum memory.