Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

Questions tagged [period-finding-algorithm]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
36 views

Eigenvalues of a unitary U that implements a periodic function [closed]

What can be said about the eigenvalues of a unitary quantum gate $U$ which implements $f(x)=f(x+r) \forall x$, as in $U|x\rangle|0\rangle\rightarrow|x\rangle|f(x)\rangle$ ? The reason I'm asking is ...
user27293's user avatar
4 votes
2 answers
1k views

A necessary and sufficient condition for the existence of a nontrivial square root in Shor's algorithm

A nontrivial square root of $N$ is a number $x$ such that $x^2 = 1\pmod{N}$ where $x$ isn't $1$ or $-1$. Shor's algorithm consists of finding such a number in order to find a nontrivial factor of $N$. ...
Omeglac's user avatar
  • 155
2 votes
1 answer
52 views

How to use the output of the DFT to compute the period of a function?

Have been trying to understand how I use the output of DFT to compute the period of a periodic function. Specifically, this is my code: ...
GRK's user avatar
  • 21
2 votes
1 answer
58 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
76 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
  • 491
1 vote
1 answer
38 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
67 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
98 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
179 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
153 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
  • 821
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