detailed explanation

A more detailed view of Shor’s and Grover’s algorithms still focuses on a few core ideas:
superposition, interference, and how each algorithm structures these to “steer”
probability toward the right answer. Below is a conceptual, math-light but technically
accurate walkthrough.

Shor’s algorithm: big picture

Shor’s algorithm solves integer factorization: given a large N , find non-trivial factors p , q
such that N= pq . Classically, the best-known algorithms are sub-exponential but still very
slow for cryptographic sizes, while Shor’s runs in polynomial time in log ⁡N . The key trick
is to turn factoring into a period-finding problem and then use a quantum subroutine to
find that period efficiently.

High-level flow:

1. Classical pre-processing: pick a random integer a with 1<a< N , compute gcd (a , N ).

o If gcd (a , N )≠ 1, you already have a non-trivial factor.

o Otherwise, continue.

2. Reduce factoring to period-finding: define the function

x
f (x)=a mod N

This function is periodic: there exists some smallest positive integer r (the order of
a mod N ) such that

r
a ≡ 1(mod N ) .

If r is even and a r /2 ≢−1(mod N ), then

r /2 r/2
gcd (a −1 , N ) , gcd (a +1 , N )

give non-trivial factors of N .

 3. Quantum core: efficiently find the period r of f (x) .
This is the part that uses qubits, superposition, and the Quantum Fourier Transform
(QFT).

4. Classical post-processing: from the measured value related to r , use continued

fractions to recover r , then compute the gcds above to get the factors.

The quantum speedup sits entirely in step 3.

Shor’s algorithm: quantum subroutine in detail

The quantum subroutine solves: “Given f ( x)=a x mod N , find its period r .”

1. Register setup and superposition

Use two registers:

 First register (input): large enough to represent integers from 0 up to some Q−1 ,
where Q is typically a power of 2 with N 2 ≤Q<2 N 2.

 Second register (output): large enough to hold values of f (x)=a x mod N .

Steps:

1. Initialize state ¿ 0 ⟩∨0 ⟩.

2. Apply Hadamard gates to all qubits in the first register to create a uniform
Q−1
1
superposition: ∑ ❑∨x ⟩∨0 ⟩ .
√Q x=0
This means the input register now simultaneously holds all possible exponents x .

2. Compute f (x) in superposition

Implement a reversible modular exponentiation circuit that maps

x
¿ x ⟩∨0 ⟩ ↦∨ x ⟩∨f ( x )⟩=¿ x ⟩∨a mod N ⟩ .

After this:

Q−1
1
∑
√Q x=0
❑∨x ⟩∨ax mod N ⟩ .
Now, each possible exponent x is entangled with its output f (x) .

3. Measure the second register

Measure the second register (the function value). Suppose the outcome is some value y .
Because many different x values yield the same y due to periodicity, the first register
collapses to a superposition of those x ’s that satisfy a x mod N= y .

If the period is r , these x ’s differ by multiples of r : something like

x=x 0 ,

So after this measurement, the state of the first register is (unnormalized)

¿ x 0 ⟩+ ¿ x 0 +r ⟩+¿ x 0 +2 r ⟩+ …

This is now a periodic superposition with period r .

4. Apply the Quantum Fourier Transform (QFT)

Apply the QFT over ZQ to the first register. The QFT maps a periodic superposition in the
“time domain” to a superposition peaked at integer multiples of Q/r in the “frequency
domain.”

Concretely, the QFT of a periodic state with period r produces large amplitudes at basis
states ¿ k ⟩ such that

jQ
k≈
r

for integer j . After QFT, measuring the first register yields some k that encodes
information about the fraction k /Q ≈ j/r .

5. Extract the period via classical post-processing

Given the measurement result k , compute the rational approximation of k /Q using

continued fractions. This yields a candidate fraction j /r . From this, extract r , then check
whether a r ≡ 1(mod N ). If valid (and with additional constraints like r even and a r /2 ≢−1),
use gcd operations to get the factors of N . If not successful, repeat the algorithm with
another a or another run.
So in essence:

 Superposition lets the algorithm evaluate a x mod N for many x simultaneously.

 Measurement plus QFT converts periodic structure in x into peaks in the frequency
domain.

 Classical number theory recovers the period and factors N .

Grover’s algorithm: big picture

Grover’s algorithm solves the unstructured search problem: given a function (oracle)
n
f :{0 , 1} →{0 ,1 } that marks some “good” inputs with 1, find an input x with f (x)=1.

 Classical search: expected O(N ) queries for N=2n possible inputs.

 Grover: finds a marked item in O( √ N ) queries, which is a quadratic speedup.

The main concept is amplitude amplification: start with a uniform superposition over all
candidates and repeatedly apply operations that increase the probability amplitude of
marked states and decrease that of unmarked states.

Grover’s algorithm: step-by-step logic

Assume there is exactly one marked item for clarity.

1. Initialize uniform superposition

Use n qubits, each initialized to ¿ 0 ⟩, then apply Hadamard gates to create:

N −1
1
¿ ψ 0 ⟩=
√N
∑ ❑∨x ⟩ .
x=0

Every candidate has equal amplitude 1/ √ N .

2. Oracle operation

The oracle O f is a black-box unitary that flips the phase of the marked state:

This does not change which basis vector is correct; it only alters the sign (phase) of its
amplitude.
3. Diffusion (inversion about the mean)

The diffusion operator (sometimes called the Grover diffusion operator) reflects
amplitude values about their average. In matrix form:

D=2∨ψ 0 ⟩ ⟨ ψ 0∨−I .

Applied to the state after the oracle, it increases the amplitude of the marked state and
slightly decreases the amplitudes of all others. Geometrically, the algorithm can be seen
as repeated rotations in a 2D subspace spanned by:

 ¿ w ⟩: the marked state .

 ¿ r ⟩: the uniform superposition of all unmarked states.

The combination “oracle + diffusion” is one such rotation step.

4. Grover iteration and optimal number of steps

Each Grover iteration is:

G=D ⋅O f .

Starting from ¿ ψ 0 ⟩ , applying G once slightly increases the amplitude of . Repeating this
process causes the amplitude of the marked state to grow approximately linearly with
the number of iterations, while the total probability remains normalized.

π
 After about √ N iterations, the probability of measuring is very close to 1.
4
 If you over-iterate, the amplitude starts to rotate past the optimum and decreases
again.

So the algorithm is:

1. Prepare uniform superposition.

2. Repeat O( √ N ) times:

o Apply oracle to flip phase of marked state(s).

o Apply diffusion to amplify their amplitudes.

3. Measure the state; with high probability, obtain .

For multiple marked items (say M marked entries):

 The optimal number of iterations scales as O( √ N / M ) .

 The same amplitude amplification geometry holds but with a slightly modified angle.

Conceptual contrast: Shor vs Grover

 Shor’s algorithm:

o Problem: structured (number-theoretic) — factoring via period-finding.

o Technique: use QFT to exploit periodicity in a function evaluated in

superposition.

o Speedup: exponential (polynomial-time vs sub-exponential/classical).

 Grover’s algorithm:

o Problem: unstructured search (no exploitable algebraic structure in the

function).

o Technique: amplitude amplification (oracle + diffusion) to maximize the

marked state’s probability.

o Speedup: quadratic (O( √ N ) vs O(N )).

If you want, the next step can be a very small, worked toy example for each (e.g., Shor
factoring 15 or Grover searching among 4 elements) to make the mechanics concrete.