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, ...
Greg Kuperberg's user avatar
8 votes

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 '...
Mithrandir24601's user avatar
  • 3,686
4 votes

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 ...
Rajeev Oberai's user avatar
4 votes

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 ...
AHusain's user avatar
  • 3,633
3 votes

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 ...
MartinQuantum's user avatar
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 ...
Mark Spinelli's user avatar
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 ...
Craig Gidney's user avatar
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 ...
Condo's user avatar
  • 2,018

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