As per comlexityzoo web, the definition of the k-th level of Fourier Hierarchy (FH) is:

$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.

I am confused about the definition, specifically the part "with k levels of Hadamard gates".

It asserts Factoring via (Kitaev) phase estimation technique implies it be in $FH_2$.

A closer look at the Phase estimation circuit reveals it contains a Hadamard layer at the beginning as $H^{\otimes n}$. Later, QFT (or $QFT^{\dagger}$) has $n$ layer of Hadamard gates (occurring in-between phase and rotation gates). (Please see the QFT wiki image here).

It seems the '$k$ levels of Hadamards' are not the same as the '$k$ layers of Hadamard gate'.

In Factoring (via Phase estimation), I can see that Hadamard is applied exactly twice to each qubit. Thus, Factoring is in $FH_2$.

Can someone confirm if it is the correct way to interpret the definition of the Fourier hierarchy?

  • 2
    $\begingroup$ I think factoring is in FH$_2$ because much as in Simon's algorithm one does the Hadamard gates initially, before the modular squaring, and then again after the modular squaring. Do you know what recursive Fourier sampling is? I think that's a natural version of the Fourier Hierarchy. It's an old problem going back all the way to Bernstein and Vazirani; I think that going $k$ recursive steps down solves a problem in FH$_k$... $\endgroup$ Mar 27 at 16:16
  • $\begingroup$ @Mark, I will think from Recursive Fourier Sampling (RFS) perspective. $\endgroup$ Mar 27 at 19:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.