# Questions tagged [fourier-sampling]

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.

14 questions
Filter by
Sorted by
Tagged with
32 views

### 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 ...
44 views

### 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 ...
78 views

### 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 ...
• 25.5k
1 vote
116 views

### 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? ...
98 views

### 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 ...
1 vote
94 views

### Why is sampling considered difficult on a classical computer but easy on a quantum computer? [closed]

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?
• 167
111 views

### 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 ...
• 324
180 views

### 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 ...
• 324
149 views

### 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 ...
• 509