Friday, October 1 at 3:30pm to 4:30pm
Xinyu Wu, Carnegie Mellon University
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.
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.