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 '...
- 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, ...
- 1,111
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 ...
- 615
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 ...
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 ...
- 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 ...
- 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 ...
- 6,777
Only top scored, non community-wiki answers of a minimum length are eligible