Oracle Separations in the Fourier Hierarchy

• URL: http://arxiv.org/abs/2609.11830v1
• Date: Thu, 10 Sep 2026 17:23:35 GMT
• Title: Oracle Separations in the Fourier Hierarchy
• Abstract summary: We prove that for every constant $kge2$ there is an oracle relative to which $mathrmFH_ksubsetneqmathrmFH_k+1$.<n>This holds for both of the usual ways of giving a circuit access to an oracle, the phase oracle and the standard oracle.<n>We also separate the union of all the levels from $mathrmBQP$ relative to an oracle.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 a first step, for oracle separations between consecutive levels. To our knowledge, the question was open at every level $k\ge2$. We prove that for every constant $k\ge2$ there is an oracle relative to which $\mathrm{FH}_k\subsetneq\mathrm{FH}_{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 $\mathrm{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 papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory [65.64123585249297]
  We prove two lower bounds for the first order complexity of minimizing a $d$-dimensional $1$-Lipschitz convex function over the unit ball with $m$ bits of memory.<n>We first show that any such (possibly randomized) algorithm must make $tilde(fracd2sqrtm)$ oracle queries.<n>For deterministic optimization algorithms, we show that $tilde(mind1.6,fracd8/3m2/3)$ queries are required.
  arXiv  Detail & Related papers  (2026-07-21T00:40:59Z)
• A Relativizing MIP for BQP [2.060642030400714]
  We show that the containment $mathsfBQP subseteq mathsfMIP$ holds with respect to any classical oracle.<n>We propose relativization as a proxy for prover efficiency, and hope that progress towards an $mathsfIP$ for $mathsfBQP$ in the oracle world will lead to a non-cryptographic interactive protocol.
  arXiv  Detail & Related papers  (2026-04-13T18:45:12Z)
• Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
  A Multinomial Logit (MNL) model is composed of a finite universe of items $[n]=1,..., n$, each assigned a positive weight.<n>A query specifies an admissible subset -- called a slate -- and the model chooses one item from that slate with probability proportional to its weight.<n>This query model is also known as the Plackett-Luce model or conditional sampling oracle in the literature.
  arXiv  Detail & Related papers  (2026-01-07T22:07:44Z)
• Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
  We provide evidence that existing learning algorithms, such as multiplicative weights update, are close to optimal. Our results are obtained in the algorithmic framework put forward by Kothari and Mehta.
  arXiv  Detail & Related papers  (2024-11-04T00:39:52Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  We present a time analogue quantum algorithm making a single query (in superposition) to a classical oracle. We prove that every $n$-qubit state can be constructed to within 0.01 error by an $On/n)$-size circuit over an appropriate finite gate set.
  arXiv  Detail & Related papers  (2023-06-02T17:49:35Z)
• Quantum Algorithms for Identifying Hidden Strings with Applications to Matroid Problems [8.347058637480506]
  We present a quantum algorithm consuming $O(1)$ queries to the max inner product oracle for identifying the pair $s, s'$. Also, we present a quantum algorithm consuming $fracn2+O(sqrtn)$ queries to the subset oracle, and prove that any classical algorithm requires at least $n+Omega(1)$ queries.
  arXiv  Detail & Related papers  (2022-11-19T11:14:19Z)
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
  We study the fundamental open question of finding the optimal high-order algorithm for solving smooth convex minimization problems. The reason for this is that these algorithms require performing a complex binary procedure, which makes them neither optimal nor practical. We fix this fundamental issue by providing the first algorithm with $mathcalOleft(epsilon-2/(p+1)right) $pth order oracle complexity.
  arXiv  Detail & Related papers  (2022-05-19T16:04:40Z)
• An optimal oracle separation of classical and quantum hybrid schemes [0.0]
  We show that for any depth parameter $d$, there exists an oracle that separates quantum depth $d$ and $2d+1$, when computation-time classical is allowed. This gives an optimal oracle separation of classical and quantum hybrid schemes.
  arXiv  Detail & Related papers  (2022-05-10T02:31:19Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Simplified Quantum Algorithm for the Oracle Identification Problem [0.0]
  oracle access to bits of an unknown string $x$ of length $n$, with the promise that it belongs to a known set $Csubseteq0,1n$. The goal is to identify $x$ using as few queries to the oracle as possible. We develop a quantum query algorithm for this problem with query complexity $Oleft(sqrtfracnlog M log(n/log M)+1right)$, where $M$ is the size of $C$.
  arXiv  Detail & Related papers  (2021-09-08T19:48:27Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.