{"id":"arxiv/2609.11830","url":"https://arxiv.org/abs/2609.11830","tags":["quant-ph","cs.CC"],"score":0,"title":"Oracle Separations in the Fourier Hierarchy","domain":"quant-ph","source":"arxiv","authors":["Atul Mantri"],"reviews":0,"subject":"quant-ph","summary":"The Fourier hierarchy $\\mathrm{FH}_0\\subseteq\\mathrm{FH}_1\\subseteq\\mathrm{FH}_2\\subseteq\\cdots$, introduced by Shi (TCS 2005), measures a quantum computation by the number of Hadamard layers it uses. Between two layers the circuit may permute basis states and attach phases, but it may not create superposition; the layers are its only source of interference. The first level is exactly $\\mathrm{BPP}$, while the second already solves Simon's problem and, through phase estimation, factors integers. Shi conjectured that every additional layer strictly increases computational power, and asked, as…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-10","reactions":{}}