For questions regarding quantum Fourier sampling. It's a method of efficiently approximating the distribution, sampled after a quantum Fourier transform over a system of qubits.
Questions tagged [fourier-sampling]
15 questions
13
votes
1 answer
How does Fourier sampling actually work (and solve the parity problem)?
I'm writing with respect to part I and part II of the Fourier sampling video lectures by Professor Umesh Vazirani.
In part I they start with:
In the Hadamard Transform:
$$|0...0\rangle \to \sum_{\{0,1\}^n}\frac{1}{2^{n/2}}|x\rangle$$
$$|u\rangle…
Sanchayan Dutta
- 17,945
- 8
- 50
- 112
10
votes
1 answer
What is recursive Fourier sampling and how does it prove separations between BQP and NP in the black-box model?
Context:
I was going through John Watrous' lecture Quantum Complexity Theory (Part 1) - CSSQI 2012. Around 48 minutes into the lecture, he presents the following:
No relationship is known between $\mathsf{BQP}$ and $\mathsf{NP}$...they are…
Sanchayan Dutta
- 17,945
- 8
- 50
- 112
7
votes
1 answer
Weak Fourier Sampling vs Strong Fourier Sampling?
I'm having trouble understanding the difference between weak fourier sampling and strong fourier sampling. From this paper:
...two important variants of the Fourier sampling paradigm have been
identified: the weak standard method, where only…
Raekye
- 307
- 1
- 4
6
votes
2 answers
Burnside Decomposition in Kuperberg's Hidden Shift
In "Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem" (arXiv), Kuperberg writes that $\mathbb{C}[G]$ has a "Burnside decomposition" of
$$\mathbb{C}[G]\cong \bigoplus_{V} V^*\otimes V$$
where each $V$ is an…
Sam Jaques
- 2,201
- 7
- 15
5
votes
1 answer
Why does Fourier sampling allow to efficiently recover hidden subgroups?
The hidden subgroup problem is often cited as a generalisation of many problems for which efficient quantum algorithms are known, such as factoring/period finding, the discrete logarithm problem, and Simon's problem.
The problem is the following:…
glS
- 27,510
- 7
- 37
- 125
4
votes
0 answers
Hidden subgroup problem
Let $H$ be a hidden subgroup of $G_1$ that is indistinguishable from subgroup $H^{\prime}$ by quantum Fourier sampling. Now take a larger group $G_2$ such that it contains $G_1$. Now if I do quantum Fourier sampling over $G_2$ instead of $G_1$ are…
Root
- 519
- 2
- 11
4
votes
0 answers
Fourier sampling in positive characteristic
Fourier sampling is used in the hidden subgroup problem in Shor's algorithm for $\mathbb{Z}/N\mathbb{Z}$ in the abelian case and the symmetric group $S_n$ for attempts at graph isomorphism in the nonabelian case.
Representations are over…
Jackson Walters
- 351
- 1
- 9
4
votes
0 answers
Abelian Hidden Subgroup Problem for arbitrary cyclic p-Groups
I had asked a question similar to this one here regarding how to handle the HSP for groups whose cyclic decomposition contains factors whose order is not a power of two. I also had some prior misunderstanding that I think I worked out. It was…
dylan7
- 334
- 1
- 9
3
votes
0 answers
Intuition for failure of strong Fourier sampling for the symmetric group
I am trying to read and understand the following two papers:
The Symmetric Group Defies Strong Fourier Sampling: Part I
The Symmetric Group Defies Strong Fourier Sampling: Part II
I have a pretty good understanding of representations of the…
Jackson Walters
- 351
- 1
- 9
3
votes
1 answer
Why to evaluate a N period function we need to go up to N^2 and not just up to 2N
I know about the answer of a similar question here:
Reason for evaluating $a^x \bmod N$ from $x = 0$ to $N^2$.
But the answer there seems to explain the reason in terms of real qubits (chance of them collapsing to some state or not) plus the…
Gustavo Mirapalheta
- 215
- 1
- 6
3
votes
1 answer
Constructing arbitrary functions for the Abelian HSP
My question might be similar to Hidden subgroup problem. However, I'm not exactly sure though. In addition, that question doesn't have an answer.
I'm trying to create some simple instances of the general abelian hidden subgroup problem to experiment…
dylan7
- 334
- 1
- 9
2
votes
0 answers
Is the QFT optimal in the quantum phase estimation algorithm?
We can concisely summarise the quantum phase estimation (QPE) algorithm as follows:
Generate the state $\sum_{k=0}^{2^n-1} \lambda^k |k\rangle$ efficiently using a series of controlled-unitary operations. Here $\lambda\equiv e^{2\pi i\phi}$, and…
glS
- 27,510
- 7
- 37
- 125
1
vote
0 answers
(Asymptotically) best known quantum algorithm for Graph isomorphism problem
Technically, Babai's (2016) (classical) quasi-polynomial algorithm can be counted as a quantum algorithm with a runtime of $\textrm{2}^{(\textrm{log(n)}^{c})}$. [Side remark: There is a claim that c=3 is sufficient, Helfgott (2017)]
Query:
What is…
108_mk
- 883
- 1
- 6
- 20
1
vote
0 answers
HHL phase estimation step
I have got an HHL circuit that looks as follows:
In the phase estimation part we are trying to find the eigenvalues of the matrix A. But what is the role of the piece of circuit hightlighted below?
As I understant, what are we doing here is to try…
Марина Лисниченко
- 409
- 2
- 10
1
vote
0 answers
Why is sampling considered difficult on a classical computer but easy on a quantum computer?
It is my understanding that classical computers have a hard time sampling results from an output from a quantum circuit, but quantum computers find it very easy to do so. Why is this?
chois3
- 187
- 1
- 4