2
$\begingroup$

Could someone help me to understand the concept behind period finding in Shor algorithm?. I'm a beginner in quantum computing.

I want to know why we use Shor's algorithm to find the period and what is the use of it.

$\endgroup$
1

2 Answers 2

4
$\begingroup$

It is helpful to first understand how to implement Shor's algorithm classically. Following this, let's take

$$ N = 314191$$


Step 1: Make a random guess

$$G = 127$$


Step 2: Compute the greatest common divisor using Euclid's algorithm

$$ gcd(127,314191) = 1$$

If the $gcd > 1$, then we will have factorized N by pure luck.


Step 3: Find a number X such that

$$ 127^X = 1 \mod{314191}$$

By classical search,

$$X = 17388$$


Step 4: This implies that

$$127^{17388} = 314191m + 1$$ $$127^{17388} - 1 = 314191m$$ $$(127^{\frac{17388}{2}} - 1)(127^{\frac{17388}{2}} + 1) = 314191m$$ $$(127^{8694} - 1)(127^{8694} + 1) = 314191m$$


Step 5: It can be shown that X being an even number, one or both of the LHS factors $(127^{8694} - 1)(127^{8694} + 1)$ likely share some common factors with $314191$ (instead of $m$), ie.

$$gcd(127^{8694} \pm 1, 314319) > 1$$

occurs with a rather high probability of nearly $ 40 \% $.

Indeed,

$$gcd(127^{8694} + 1, 314319) = 829$$

and

$$gcd(127^{8694} - 1, 314319) = 379$$

are the two factors of $N = 314319$.


Period finding is specific to the quantum implementation of Shor's algorithm, where X occurs as periodic bumps of interval X. The purpose of period finding is to find X faster than is classically possible.

$\endgroup$
0
$\begingroup$

Shor's algorithm is designed to work faster on a quantum computer since quantum computers run multiple steps simultaneously due to their ability to store qubits in superposition. We use period-finding in specific so we can apply QPE (quantum phase estimation). If you have not watched the Veritasium video on it, I would recommend watching that to understand the algorithm and understand a bit of why it works faster. In general, quantum algorithms are designed in a completely different way than classical algorithms. Hope that helps!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.