Cryptography from Quantum Pseudorandomness

CS/Math Seminar Featuring Luowen Qian, Boston University, QNC 1201 + ZOOM

In this talk, we study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quantum algorithms that are only correct on a small (even sub-constant) fraction of their inputs into ones that are correct on all inputs. This stands in contrast to the classical setting, where such results are only known for a small number of specific problems or restricted computational models. En route, we obtain a tight Ω(n^2) lower bound on the average-case quantum query complexity of the Matrix-Vector Multiplication problem.

Our techniques strengthen and generalise the recently introduced additive combinatorics framework for classical worst-case to average-case reductions (STOC 2022) to the quantum setting. We rely on quantum singular value transformations to construct quantum algorithms for linear verification in superposition and learning Bogolyubov subspaces from noisy quantum oracles. We use these tools to prove a quantum local correction lemma, which lies at the heart of our reductions, based on a noise-robust probabilistic generalisation of Bogolyubov's lemma from additive combinatorics.

Based on joint work with Alexander Golovnev, Tom Gur, Igor Shinkar, and Sathyawageeswar Subramanian.

Join Zoom Meeting

https://uwaterloo.zoom.us/j/91307405190?pwd=VDk4YTBoSXJkNHk5emxOSlp0R3ZsQT09

Meeting ID: 913 0740 5190

Passcode: 102090

Add event to calendar