{"id":"arxiv/2604.15248","url":"https://arxiv.org/abs/2604.15248","tags":["quant-ph","cs.CC"],"score":0,"title":"IQP circuits for 2-Forrelation","domain":"quant-ph","source":"arxiv","authors":["Quentin Buzet","André Chailloux"],"reviews":0,"subject":"quant-ph","summary":"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, signed $2$-Forrelation can be solved by a classical random choice between two one-query…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-04-16","reactions":{}}