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

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

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

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

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

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

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

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

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

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

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

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

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