IQP circuits for 2-Forrelation
The paper shows that 2-Forrelation, a problem separating classical and quantum query complexity, can be solved using Instantaneous Quantum Polynomial-time (IQP) circuits. This demonstrates that IQP circuits are powerful enough to solve classically hard problems, providing a new path for showing quantum advantage without the verification issues of sampling tasks.