Class Description

FH: Fourier Hierarchy

FH_k is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with k levels of Hadamard gates and all other gates preserving the computational basis. (Conditional phase flip gates are fine, for example.) Thus

• FH₀ = P
• FH₁ = BPP
• FH₂ contains factoring because of Kitaev's phase estimation algorithm

It is an open problem to show that the Fourier hierarchy is infinite relative to an oracle (that is, FH_k is strictly contained in FH_k+1).

Defined in [Shi03].

Linked From

No class.