Everyone is welcome to attend the online lecture of Daniel Grier (University of Waterloo). Title: Classical Algorithms for Forrelation. Abstract:
This talk will feature the problem of forrelation: given two Boolean functions, estimate the correlation between one function and the Fourier transform of the other. There is a sense in which forrelation captures one of the hardest problems solvable by a quantum computer. For example, forrelation witnesses the largest possible separation between classical and quantum query complexity, and a natural generalization is BQP-complete. However, one can still ask the questions "What are the best classical algorithms for forrelation?" and "Are there interesting restricted settings in which forrelation becomes efficiently computable?" In this talk, I will focus on the latter question. I will introduce a family of Boolean functions defined over a graph and show that the forrelation can be computed efficiently whenever the graph is sufficiently structured (e.g. bipartite, planar). As an application, this will imply an efficient classical algorithm to compute level-2 variational energies in the Quantum Approximation Optimization Algorithm (QAOA) over similarly structured graphs.
Please contact Jop Briet or Suhasree Patro for the link to this seminar.
