Quantum Worst-case to Average-case reductions for all linear problems

Add to your list(s) Download to your calendar using vCal

• Sathyawageeswar Subramanian, University of Warwick
• Thursday 03 November 2022, 14:15-15:30
• MR15.

If you have a question about this talk, please contact Sergii Strelchuk.

Given an algorithm that has a small non-zero probability of answering correctly on an average input, can we use it to design another algorithm that has non-zero probability of answering correctly even on worst-case inputs? In this talk, I will focus on quantum algorithms for linear problems, and describe an explicit and efficient transformation that turns algorithms which 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. Along the way I will also present a tight Omega(n^2) lower bound on the average-case quantum query complexity of the Matrix-vector Multiplication problem.

The techniques used in this work build on the recently introduced additive combinatorics framework for classical worst-case to average-case reductions (STOC 2022). The key quantum ingredients are subroutines based on quantum singular value transformations for approximate verification of the output of noisy quantum algorithms, and a learner for the heavy Fourier characters of indicator functions with imperfect quantum implementations. I will discuss how these tools can be combined to prove a quantum local correction lemma based on a probabilistic generalisation of Bogolyubov’s lemma in additive combinatorics, leading to our worst-case to average-case transformation for linear problems.

This talk is based on joint work with Vahid Asadi, Alexander Golovnev, Tom Gur, and Igor Shinkar.

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR15
• bld31

Note that ex-directory lists are not shown.