Oracle Separations in the Fourier Hierarchy
Abstract
The Fourier hierarchy FH0⊆FH1⊆FH2⊆⋯, 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 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 a first step, for oracle separations between consecutive levels. To our knowledge, the question was open at every level k≥2. We prove that for every constant k≥2 there is an oracle relative to which FHksubsetneqFHk+1. The separating problem is built from Forrelation (Aaronson and Ambainis, STOC 2015): the level above solves it with a constant number of queries, whereas at level k it stays hard even for circuits making exponentially many queries. This holds for both of the usual ways of giving a circuit access to an oracle, the phase oracle and the standard oracle, which writes its answer into a register. The two are not interchangeable: relative to an oracle, the standard oracle is strictly more powerful at the same number of layers. We also separate the union of all the levels from BQP relative to an oracle. The lower bounds rest on a structural property of the hierarchy: the number of Hadamard layers limits how adaptively a circuit can query its oracle. With a phase oracle, a circuit with k layers is reproduced exactly by an algorithm making only k−1 rounds of parallel queries, which brings known lower bounds for such algorithms to bear. The standard oracle lets a circuit branch on earlier answers, and that case needs a separate argument.
Related
- A Separation Between Types of Quantum Oracle Separations
- EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity
- Improved Separations between Quantum and Classical Communication Complexity of Total Functions
- Memory Separations from a Collective-Spin Quantum Register
- Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
BibTeX
@misc{mantri2026oracle,
title = {{Oracle Separations in the Fourier Hierarchy}},
author = {Atul Mantri},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11830},
eprint = {2609.11830},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11830},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Oracle Separations in the Fourier Hierarchy
AU - Atul Mantri
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11830
UR - https://arxiv.org/abs/2609.11830
AB - The Fourier hierarchy FH_0⊆FH_1⊆FH_2⊆⋯, 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 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 a first step, for oracle separations between consecutive levels. To our knowledge, the question was open at every level k≥2. We prove that for every constant k≥2 there is an oracle relative to which FH_ksubsetneqFH_k+1. The separating problem is built from Forrelation (Aaronson and Ambainis, STOC 2015): the level above solves it with a constant number of queries, whereas at level k it stays hard even for circuits making exponentially many queries. This holds for both of the usual ways of giving a circuit access to an oracle, the phase oracle and the standard oracle, which writes its answer into a register. The two are not interchangeable: relative to an oracle, the standard oracle is strictly more powerful at the same number of layers. We also separate the union of all the levels from BQP relative to an oracle. The lower bounds rest on a structural property of the hierarchy: the number of Hadamard layers limits how adaptively a circuit can query its oracle. With a phase oracle, a circuit with k layers is reproduced exactly by an algorithm making only k−1 rounds of parallel queries, which brings known lower bounds for such algorithms to bear. The standard oracle lets a circuit branch on earlier answers, and that case needs a separate argument.
ER -