Questions tagged [period-finding-algorithm]
The period-finding-algorithm tag has no usage guidance.
9
questions
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 ...
- 123
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}$$
...
- 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$?
- 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 ...
- 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 ...
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)
...
- 35
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 ...
- 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 ...
- 83
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 ...
