8
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,436
8
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,756
4
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 ...
4
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,683
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 ...
- 755
2
votes
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 ...
- 13.6k
1
vote
Why to evaluate a N period function we need to go up to N^2 and not just up to 2N
It's because the difference between fractions with denominators $\leq N$ can be as small as $1/N^2$, and the closest fractions always have different denominators, and your goal is to learn the ...
- 40.8k
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 ...
- 2,156
Only top scored, non community-wiki answers of a minimum length are eligible