Quantum Worst-Case to Average-Case Reductions for All Linear Problems
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian · Society for Industrial and Applied Mathematics eBooks · 2024
We study the problem of constructing worst-case algorithms from average-case algorithms. Prior to this work, such reductions were only known for a small number of specific problems or restricted computational models. In contrast, we show that for quantum computation, all linear problems admit worst-case to average-case reductions. Specifically, 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. En route, we obtain a tight Ω(n2) lower bound on the average-case quantum query complexity of the Matrix-Vector Multiplication problem.