IQP circuits for 2-Forrelation

The 2-Forrelation problem provides an optimal separation between classical and quantum query complexity and is also the problem used for separating mathsf{BQP} and mathsf{PH} relative to an oracle. A natural question is therefore to ask what are the minimal quantum resources needed to solve this problem. We show that 2-Forrelation can be solved using Instantaneous Quantum Polynomial-time $mathsf{IQP}$ circuits, a restricted model of quantum computation in which all gates commute. Concretely, two mathsf{IQP} circuits with two quantum queries and efficient classical processing suffice. For the signed variant of 2-Forrelation, even a single mathsf{IQP} circuit and query suffices. This answers a recent open question of Girish (arXiv:2510.06385) on the power of commuting quantum computations. We use this to show that \(mathsf{BPP}^{mathsf{IQP}}\)^O notsubseteq mathsf{PH}^O relative to an oracle O, strengthening the result of Raz and Tal (STOC 2019). Our results show that mathsf{IQP} circuits can be used for classically hard decision problems, thus providing a new route for showing quantum advantage with mathsf{IQP} circuits, avoiding the verification difficulties associated with sampling tasks. We also prove Fourier growth bounds for mathsf{IQP} circuits in terms of the size of their accepting set. The key ingredient is an algebraic identity of the quadratic function Q(x) = sum_{i < j} x_ixj that allows extracting inner-product phases within an mathsf{IQP} circuit.