  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 $\Omega(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.
