Quantum Worst-Case to Average-Case Reductions for All Linear Problems

CS/Math Seminar - Vahid Asadi, IQC 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/98879236191?pwd=cTh2cHZsa29xN2xocFdQdzFBZWY4dz09

Meeting ID: 988 7923 6191

Passcode: 761978