Questions tagged [period-finding-algorithm]
The period-finding-algorithm tag has no usage guidance.
5
questions
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 ...
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)
...
- 23
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 ...
- 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 ...
- 83
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 ...
