Probability and Statistics Seminar: Separations between classical and quantum computational complexity through stochastic calculus

Friday, October 1 at 3:30pm to 4:30pm

This is a past event.
Virtual Event


Xinyu Wu, Carnegie Mellon University

Abstract:
The Forrelation problem is: given two random Boolean vectors x and y, decide if x and y are uniformly random or if x is uniformly random and y is the Walsh-Fourier transform of x. Variants of this problem show up as examples of functions hard for some classical complexity classes but easy for the corresponding quantum complexity classes. In this talk, I will present an approach to analyze the complexity of the Forrelation problem using techniques from stochastic calculus. Using this technique, I will give some simplified proofs of recent results by Raz-Tal and Girish-Raz-Zhan.

Dial-In Information

Please see your email to join via Zoom

NOTE: There will be a projector screen in KAP 414 for those who would like to gather and watch the talk. Note the speaker will not be present in KAP 414.

Event Type

Lecture / Talk / Workshop

Campus

University Park Campus

Department
Mathematics
Add this to your calendar

Recent Activity