Manuel Kauers Shor’s Factorisation Algorithm for Quantum Computers

Quantum Information

• Classical Information Unit: The Bits; b ∈ {0, 1}

• Quantum Information Unit: The Qubit; |q⟩ ∈ ℂ^{2} with ||q|| = 1.

• Classical Information: Bit Strings; B ∈ {0, 1} × ⋯ × {0, 1}.

• Quantum Information: Qubit Tensors; |Q⟩ ∈ ℂ^{2} ⊗ ⋯ ⊗ ℂ^{2}. |Q⟩ = |q⟩_{1} ⊗ ⋯ ⊗ |q⟩_{n} with ||q_{i}|| = 1

• Notation:

– |x⟩: Ket-Notation of vectors

– {|0⟩, |1⟩} ONB of ℂ^{2}

– |1⟩ ⊗ |0⟩ ⊗ |1⟩ =: |1⟩|0⟩|1⟩ =: |101⟩ =: |5⟩

– ⟨x| := |x⟩^{T}

Physical Background

• Why?

• Quantum states can be superpositions of states.

• Example 1: Interferometer

• Example 2: Schrödinger’s cat is both dead and alive:

|cat⟩ = \frac{1}{\sqrt{2}}(|dead⟩ + |alive⟩)

• Measurement: Open the box and find out. Then |cat⟩ = |dead⟩ or |cat⟩ = |alive⟩.

Classical Computation

• Classical Computation: The Circuit Model

• Functions f: {0, 1}^{n} → {0, 1}^{m} are implemented in circuits.

• Example: Addition modulo 2

• AND, OR, and NOT build a uniform set of gates.

• Functions f: ℕ → ℕ are encoded by a family of circuits.

Quantum Computation

• Computational Model: Quantum Circuit

• Quantum gates are unitary operators

• Examples:

Hadamard Transform \frac{1}{\sqrt{2}} (\begin{matrix}1 & 1 \\ 1 & −1 \end{matrix}) epsfigfile=hadamard.eps
Controlled NOT  (\begin{matrix}1 \\ & 1 \\ & & & 1 \\ & & 1 \end{matrix}) epsfigfile=controlledNot.eps

• Uniform set of gates: all unitary operators ℂ^{2} → ℂ^{2} plus the Controlled NOT.

Example: Deutsch-Josza Algorithm

• Suppose f: {0, 1} → {0, 1} can be computed by a black box.

• Decide whether f(0) = f(1) with computing f only once!

• Let U_{f}: ℂ^{2} ⊗ ℂ^{2} be defined by

U_{f}|xy⟩ := |x, y ⊕ f(x)⟩ (x, y ∈ {0, 1})

where ⊕ denotes the boolean XOR.

• Consider the quantum circuit

• The circuit computes

(H ⊗ I) · U_{f} · (H ⊗ H) · |01⟩.

Example: Deutsch-Josza Algorithm II

• What is (H ⊗ I) · U_{f} · (H ⊗ H) · |01⟩?

• (H ⊗ H)|01⟩ = (|0⟩ + |1⟩)(|0⟩ − |1⟩) = |0⟩(|0⟩ − |1⟩) + |1⟩(|0⟩ − |1⟩)

• U_{f}(|0⟩(|0⟩ − |1⟩) + |1⟩(|0⟩ − |1⟩))

= |0⟩((|0⟩ − |1⟩) ⊕ |f(0)⟩) + |1⟩((|0⟩ − |1⟩) ⊕ |f(0)⟩) = ((−1)^{f(0)}|0⟩ + (−1)^{f(1)}|1⟩)(|0⟩ − |1⟩)

• H((−1)^{f(0)}|0⟩ + (−1)^{f(1)}|1⟩)

= (−1)^{f(0)}(|0⟩ + |1⟩) + (−1)^{f(1)}(|0⟩ − |1⟩)

= ((−1)^{f(0)} + (−1)^{f(1)})|0⟩ + ((−1)^{f(0)} − (−1)^{f(1)})|1⟩ • Note that (−1)^{f(0)} + (−1)^{f(1)} = 0 iff f(0) = f(1)

• Hence, a measurement yields |0⟩ iff f(0) ≠ f(1).

Quantum Fourier Transform

• Definition: Let q = 2^{l}, ω := exp(2πi/q). Then

QFT |a⟩ = \frac{1}{\sqrt{q}} ∑_{b=0}^{q−1} ω^{ab}|b⟩.

defines the quantum fourier transform on (C^{2})^{l}.

• Cooley-Tucky:

QFT_{nm} = (QFT_{m} ⊗I_{n}) · T · (I_{m} ⊗ QFT_{n}) · P

for a permutation P and a diagonal matrix T.

• Quantum Circuit for the QFT:

• Needs only O(l^{2}) quantum gates!

Shor’s Factoring Algorithm

• Let N be an L-digit number, a coprime to N.

• Let r be the order of a mod N.

• Suppose r is even. Then:

a^{r} = 1 mod N
a^{r} − 1^{2} = 0 mod N
(a^{r/2} − 1)(a^{r/2} + 1) = 0 mod N

• Suppose a^{r/2} ≠ ±1. Then gcd(N, a^{r/2} − 1) is a nontrivial factor of N.

• Problem: How to find the order of a.

Shor’s Factoring Algorithm

• Main step of Shor’s algorithm: Find the order of a.

• Let U(a, N) be the unitary map (x, y) ↦ (x, y ⊕ a^{x} (N)).

• Consider the following circuit

• The measurement will favor values of y with

\frac{y_{0}}{2^{2L}} ≈ \frac{k}{r}

for some integer k.

• y_{0} and 2^{2L} are known. Also, r < N, so k/r can be guessed to be the closest fraction to y_{0}/2^{2L} with denominator < N.

• This gives r (with reasonable probability) and we are done.