Lower Bounds on Average-Case and Non-Local Quantum Computation
Candidate: Vahid Reza Asadi
Supervisors: Richard Cleve, Mohammad Hajiabadi
Location: QNC 2101
This thesis studies computational and information-theoretic limitations in both classical and quantum models of computation. It is organized into two parts, each addressing a different aspect of computational hardness. Despite their differences, both parts share a common goal: understanding how structural and physical constraints shape what classical and quantum algorithms can achieve.,,
In Part I, we present lower bounds on the average-case complexity of certain tasks in classical and quantum settings. We develop a general framework for constructing efficient worst-case to average-case reductions. Applying this framework, we obtain such reductions for fundamental problems in a variety of computational models; namely, algorithms for matrix multiplication, streaming algorithms for the online matrix-vector multiplication problem, and static data structures for all linear problems, as well as the multivariate polynomial evaluation problem. We further extend this framework to the setting of quantum algorithms, along the way obtaining a tight bound on the average-case quantum query complexity of the matrix-vector multiplication problem. Our techniques rely crucially on tools from additive combinatorics. In particular, we show local correction lemmas that rely on new probabilistic and noise-robust versions of the quasi-polynomial Bogolyubov-Ruzsa lemma.,,
In Part II, we give quantum gate and entanglement lower bounds on certain non-local tasks. A non-local quantum computation (NLQC) replaces direct interaction between two quantum systems with a single simultaneous round of communication and shared entanglement. We study two classes of NLQC, f-routing and f-BB84, which are of relevance to classical information theoretic cryptography and quantum position-verification. We give the first non-trivial lower bounds on entanglement in both settings, under the assumption of perfect correctness. Within this setting, we give a lower bound on the Schmidt rank of any entangled state that completes these tasks for a given function f(x,y) in terms of the rank of a matrix G_{xy} whose entries are zero when f(x,y)=0 and strictly positive otherwise. This also leads to a lower bound in terms of the non-deterministic quantum communication complexity of f. Due to a relationship between f-routing and the conditional disclosure of secrets (CDS) primitive studied in information theoretic cryptography, we obtain a new technique for lower bounding the randomness complexity of CDS. Finally, we show that the number of quantum gates plus single-qubit measurements required to implement a function f is at least linear in the entanglement-assisted simultaneous-message-passing communication complexity of f. As a consequence, we derive a linear lower bound for the inner-product function.