Seminars

View all Seminars  |  Download ICal for this event

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

Series: Bangalore Theory Seminars

Speaker: Sathyawageeswar Subramanian Universiry of Warwick

Date/Time: Jan 05 14:45:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Abstract:
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 Bogolyubovs 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 (Link


Speaker Website Link


Microsoft teams link:

Link



Acknowledging the support from the Kirani family for generously supporting the seminar series.



Hosts: Aditya Subramanian, Aditya Abhay Lonkar, Rahul Madhavan & Rameesh Paul