Forrelation: “the hardest problem in quantum computing”

1. Why Forrelation?

• “The hardest problem in quantum computing”
• Isolates complexity of doing fourier transform
• comes with a general technique called the “fourier growth technique”.
  • property of the forrelation problem can be used as a metric to understand the quantum resources required for a task, and to prove oracle separations.
  • classical vs quantum (BPP vs BQP, PH vs BQP)
  • weak models of quantum computing (DQC1, 1/2BQP, BQP)
  • rounds of adaptivity
• source of inspiration for related problems which also make a hierarchy of quantum resources (entanglement hierarchy, spectral forrelation)
• there is something for everyone in this problem.

1. What is the Problem?

• Definition, basic properties
• k-forrelation

1. Fourier Growth Framework

• Classical vs. quantum Fourier spectra; the Raz-Tal technique

1. Applications
   • Application to BQP vs BPP (?)
   • Application to BQP vs PH
   • Application to adaptivity
   • Application to DQC1, 1/2BQP, BQP
2. Quantum Crypto Implications

• P = NP but quantum crypto survives?
• acrobatics of BQP

1. Variations of the problem

• Entanglement version (communication complexity hierarchy)
• Spectral Forrelation → QMA vs. QCMA separation
• EQP variants (exact): bent functions, good candidate to initialize oracle, EQP vs. PH open problem

1. Whitebox Variants & Quantum Advantage

• Google/IBM experiments: bent functions, supremacy demonstrations
• Why is it good for verifiability (vs. sampling)

1. Takeaways & Open Questions

• Is every quantum algorithm “just” forrelation?
• Is it harder than factoring? Or is Shor’s the only true example of quantum advantage?
• Whitebox forrelation
• Other applications of the Fourier growth technique?
• k-spectral forrelation?

More to add? Email Kunal Marwaha kmarw@uchicago.edu or open an issue on GitHub.