7 votes
Accepted

How does Fourier sampling actually work (and solve the parity problem)?

Starting from the beginning (a very good place to start, after all), the state $\left| 0\right\rangle^{\otimes n}\left| -\right\rangle$ is input into $H^{\otimes n}\otimes I$ (here, called the '...
user avatar
  • 3,397
6 votes

Burnside Decomposition in Kuperberg's Hidden Shift

In the paper I called it the Burnside decomposition, but it looks like the standard name is the Wedderburn decomposition. That might simply have been a mistake in terminology on my part. Anyway, ...
user avatar
3 votes
Accepted

Why does Fourier sampling allow to efficiently recover hidden subgroups?

The question is whether taking the Fourier transform $\operatorname{QFT}|gH\rangle$ followed by sampling allows to efficiently recover generators of the hidden subgroup $H\leq G$. While the problem is ...
user avatar
3 votes
Accepted

Weak Fourier Sampling vs Strong Fourier Sampling?

Within the paper itself that you linked to, on page 4 section 1.2 "Nonabelian Fourier Transforms" and page 5 section 1.3 "Weak vs Strong Sampling and the Choice of Basis", they define what they mean ...
user avatar
3 votes
Accepted

Burnside Decomposition in Kuperberg's Hidden Shift

The second part of each tensor product serves as a multiplicity space. It might be more satisfying to write it as a full decomposition like your second one. So you have $\bigoplus V_\lambda \otimes ...
user avatar
  • 3,503
1 vote

Constructing arbitrary functions for the Abelian HSP

I am not sure if this anwers your question but I think this all boils down to whether one can we efficiently implement $QFT_{\mathbb{Z}_N}$ when $N$ is not a power of $2$. In this case we can no ...
user avatar
  • 1,447
1 vote

What is recursive Fourier sampling and how does it prove separations between BQP and NP in the black-box model?

Initially I'll admit that I find the linked papers to be dense as well. However, to make some headway, a complete problem in $\mathrm{NP}$ can be phrased as "given a $\mathsf{3SAT}$ instance, does ...
user avatar
  • 6,777

Only top scored, non community-wiki answers of a minimum length are eligible