Xinyu Wu: Separations between classical and quantum computational complexity through stocha... (CMU)

Separations between classical and quantum computational complexity through stochastic calculus. 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.