# Questions tagged [period-finding-algorithm]

The tag has no usage guidance.

9 questions
Filter by
Sorted by
Tagged with
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 ...
1 vote
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}$$ ...
1 vote
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$?
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 ...
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
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) ...
1 vote
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 ...
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 ...