Questions tagged [period-finding-algorithm]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer
64 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 ...
user avatar
1 vote
1 answer
40 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) ...
user avatar
1 vote
1 answer
70 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 ...
user avatar
  • 329
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 ...
user avatar
2 votes
0 answers
22 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 ...
user avatar