Class Description

FH: Fourier Hierarchy

FHk 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

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

Defined in [Shi03].

Linked From

No class.