Skip navigation
Please use this identifier to cite or link to this item:
Title: Randomness and Quantumness in Space-Bounded Computation
Authors: Zhan, Wei
Advisors: Raz, Ran
Contributors: Computer Science Department
Keywords: Quantum computing
Space-bounded computation
Subjects: Computer science
Issue Date: 2023
Publisher: Princeton, NJ : Princeton University
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.
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Computer Science

Files in This Item:
File Description SizeFormat 
Zhan_princeton_0181D_14695.pdf692.82 kBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.