Class Description

FH: Fourier Hierarchy

FH_{${\displaystyle k}$} is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with at most ${\displaystyle k}$ Fourier transforms (for ${\displaystyle k\in \mathbb {Z} ^{+}}$), 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_{${\displaystyle k}$} is strictly contained in FH_{${\displaystyle k+1}$}).

It is known that FH₂ ${\displaystyle \subseteq }$ BQP

Defined in [Shi03].

Linked From 0 Classes

No class.