Skip to main content

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.

Filter by
Sorted by
Tagged with
4 votes
0 answers
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 ...
Jackson Walters's user avatar
3 votes
0 answers
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 ...
Jackson Walters's user avatar
2 votes
0 answers
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 ...
glS's user avatar
  • 25.5k
1 vote
0 answers
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? ...
Марина Лисниченко's user avatar
3 votes
1 answer
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 ...
Gustavo Mirapalheta's user avatar
1 vote
0 answers
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?
chois3's user avatar
  • 167
4 votes
0 answers
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 ...
dylan7's user avatar
  • 324
3 votes
1 answer
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 ...
dylan7's user avatar
  • 324
4 votes
0 answers
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 ...
Root's user avatar
  • 509
5 votes
2 answers
173 views

Burnside Decomposition in Kuperberg's Hidden Shift

In "Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem", Kuperberg writes that $\mathbb{C}[G]$ has a "Burnside decomposition" of $$\mathbb{C}[G]\cong \bigoplus_{V}...
Sam Jaques's user avatar
  • 2,076
10 votes
1 answer
758 views

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 $\...
Sanchayan Dutta's user avatar
5 votes
1 answer
364 views

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 ...
glS's user avatar
  • 25.5k
7 votes
1 answer
227 views

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 ...
Raekye's user avatar
  • 307
13 votes
1 answer
1k views

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_{\{...
Sanchayan Dutta's user avatar