UBC Seminar: Niels Kornerup

Abstract: Time and space are the most important measures of cost in computation, even more so for quantum computation, where coherence times and logical qubit counts are critically constrained resources. Despite this, our tools for establishing unconditional tradeoff lower bounds between time and space in quantum computation are surprisingly limited. In this talk, we present an Omega(n^{4/3} (log log n)/(S^{1/3} log n)) non output oblivious quantum time-space tradeoff lower bound for sorting and an Omega(mn/S) output oblivious quantum time-space tradeoff lower bound for universal hashing from n bits to m bits. These new tradeoffs are proven with a novel method based off the noise operator that lets us upper bound the success probability of quantum query algorithms using a purely classical argument.