{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreieabqiknhhuvoion3ssqhd7nbsmpwtustr7geq35tcx5slvwtfy4e",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mjqijqmajwb2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.15248v1",
  "publishedAt": "2026-04-17T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Quentin Buzet",
    "André Chailloux"
  ],
  "textContent": "**Authors:** Quentin Buzet, André Chailloux\n\nThe 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 \\not\\subseteq \\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_ix_j$ that allows extracting inner-product phases within an $\\mathsf{IQP}$ circuit.",
  "title": "IQP circuits for 2-Forrelation"
}