Questions tagged [period-finding-algorithm]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
47 views

Why is the following exponential ignored (or equals 1) in the probability amplitude?

I'm reading Ronald de Wolf's lecture notes and when explaining Shor's algorithm on page 40 after applying a QFT to $$ \frac{1}{\sqrt{m}} \sum_{j=0}^{m-1} |jr+s\rangle $$ the following expression is ...
user4676310's user avatar
1 vote
2 answers
54 views

A concrete 4-qubit circuit that computes $ a^j \mod{15}$?

As a follow up to a previous question on period finding and factoring, could anyone give a real construction of a 4-qubit circuit that can output (in the same 4-qubit binary format) $$ a^j \mod{15}$$ ...
James's user avatar
  • 445
1 vote
1 answer
27 views

Can period-finding algorithm obtain more-than-one period?

For instance, let $f$ be a function with two co-prime periods $p$ and $q$. Can we find both $p$ and $q$ with several quantum queries to $f$?
Henry's user avatar
  • 117
0 votes
0 answers
54 views

Period finding for amplitude encoding of function

In quantum Fourier transform, amplitude encoding is used to represent function $f(x)$ such that $|\psi\rangle = \sum_x f(x)|x\rangle$, with $f(x)$ being amplitude. In Shor's algorithm, it is not this ...
Felipe's user avatar
  • 41
3 votes
1 answer
90 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
1 answer
139 views

Qiskit textbook: mod 15 multiplication circuit

The Qiskit textbook shows a circuit for mod 15 multiplication by "a", which for a==2 does the following operations: U.swap(0,1) U.swap(1,2) U.swap(2,3) ...
antonantal's user avatar
1 vote
1 answer
122 views

DFT like operation in the third step of Period finding and Discrete Logarithm algorithm

In the third step of the algorithm for discrete logarithm, the state $$ |\hat{f}(l_1,l_2)\rangle=\frac{1}{\sqrt{r}}\sum_{j=0}^{r-1}e^{-2\pi il_2j/r}|{f}(0,j)\rangle $$ is introduced which is stated to ...
Sooraj S's user avatar
  • 771
8 votes
2 answers
2k views

Why doesn't Shor's algorithm output a solution for some numbers?

I've been trying to mess around with Qiskit's implementation of Shor's algorithm, and while trying I've noticed that Shor(33), for example, would not output a solution (even with an absurd number of ...
Nuno Costa's user avatar
2 votes
0 answers
32 views

How to obtain an expression of the complexity of the period-finding algorithm with respect to the period length?

Intro. Nielsen and Chuang in Quantum computation and quantum information on section 5.4.1 state that the period-finding algorithm has a runtime of $U + O(L^2)$ operations where $L$ is the size of the ...
CuriousGeorge's user avatar