Shor’s Algorithm

Anita S. V.

Freeman Dyson

For me, the important thing about quantum mechanics is the equations, the mathematics. If you want to understand quantum mechanics, just do the math. All the words that are spun around it don’t mean very much. It’s like playing the violin. If violinists were judged on how they spoke, it wouldn’t make much sense.

Church-Turing Thesis

Every computing machine is necessarily within polynomial reductions from Turing machine.

But that was assuming classical physics, with quantum mechanics we believe this is broken. Many classically hard problems like factoring of a number is polynomial on a quantum computer when best known classical algorithms are exponential on number of bits.

There is also reasonable evidence probabilistic algorithms can be faster but a proof seems elusive. Discovery of AKS primality has cast doubt on this.

Quantum Mechanics - Informally

Superposition Principle: Any two valid state can be simultaneously possible. (With varying complex weights). The combined state will “behave” in some sense between those two components.

Correspondence Principle: Any classically understood state “behaves” classically. (Similar to Transfer principle)

1. Polarization of light, intensity argument -> photon probability -> statistics -> quantum.
2. Electron spin -> need for complex phase -> quantum.

Hilbert Space

It is a vector space over complex number field, together with an inner product definition. Inner product can be thought of as something that expresses separation between the vector. (Similar to dot product for real vectors)

||a||² = (a, a) ≥0 for all vectors. And linear on second operator.

(a, b) = (b, a)*

(a, λb) = λ(a, b)

(a, b+c) = (a, b) + (a, c)

​

Dual Space

We can observe, the space of linear functionals f : X -> C as a hilbert space. (trivially has same dimension).

Define, dual (a) = f_a, such that f_a(b) = (a, b). We now have a dual hilbert space by defining its inner product as (f_a,f_b) = (b, a)

The elements of our main space will be denoted as |a⟩, ket-vector. and its dual will be written as ⟨a|, bra-vector, then we can conveniently define (a, b) = ⟨a|b⟩

Outer Product, |a⟩⟨b| is defined as linear operator X->X, (|a⟩⟨b|) |x⟩ = |a⟩(⟨b|x⟩)

​

Concretely speaking

Complex column vectors of size n, is an n-dimensional complex vector space. We augment an inner product as follows to make it a Hilbert Space:

(a, b) = a^†b

Realization: ⟨a| is simply a^†. We will reserve dagger for linear operators from now.

Note: Every hilbert space can be converted to a column matrix using a basis.

​

​

Definitions.

Note that, (a, A b) = (A^†a, b)

Hermitian operator if self adjoint. (H^† = H).

Unitary operator if preserves inner product. (U^†U = UU^† = I)

Normal operator if (A^†A= AA^†). Trivially both unitary and hermitian are normal operators.

If A|a⟩ = λ|a⟩ then, |a⟩ is an eigenvector of A, and λ is an eigenvalue of A.

Positive operator if A satisfies ⟨a|A|a⟩ ≥0 for all |a⟩. Positive definite if equality only for 0 vector.

Quantum Mechanics - Formally.

1. State of any system is a unit element of Hilbert Space.
2. State transitions is a function of time, and the transformation is unitary.
3. A measurement gives you one of the eigenvalues of a hermitian, A, with probability equal to ||(inner product of state into the corresponding eigenvectors)||², with resultant state as a corresponding eigenvector.

Qubit

Irrelevance of global phase!

Pauli Matrices - Basic Gates

If n is a real unit vector on 3D space, that represents n · 𝜎 = n_xX + n_yY + n_zZ

Define: R_n(θ) = exp(iθ(n · 𝜎)/2) = cos(θ/2) I + i sin(θ/2) (n · 𝜎)

​

Hadamard, Phase and T gates.

T is also called 𝜋/8 gate.

​

Important Results.

If A is hermitian, its eigenvalues are real, and eigenvectors are orthogonal (for unequal eigenvalue). The space generated by eigenvectors with nonzero eigenvalues is called support of the hermitian.

Definition: Diagonalizable if A can be written as sum of a|a⟩⟨a|, where a is eigenvalue and |a⟩ is corresponding eigenvector. And each of {|a⟩} must be orthonormal to each other.

Spectral Decomposition Theorem: An operator is normal if and only if diagonalizable.

AA^† is a positive operator. All positive operators are hermitian. And hence all eigenvalues are non-negative for a positive operator.

​

Function of Hermitian.

If f is analytic at eigenvalues, we can easily see f(A) = 𝝨f(a)|a⟩⟨a|

In case f is defined on eigenvalues of A, we can still use it from a “definition” perspective, but may not “carry” algebraic features from complex space to hilbert space.

For a positive operator A, define √A = 𝝨√a|a⟩⟨a|, verify that √A √A = A. (Note this doesn’t not mean X²=A has only one or even 2ⁿ solutions, Note that it is has even an entire space when A = I for example.)

Verify that exp(iH) = U, where H is hermitian, and U is unitary, and this is the Schrodinger’s equation.

No-Cloning Theorem

• It is not possible to clone state of a sub-system into two. (Because some part of sub-system need to necessarily lose its information. That would mean it would be not reversible, but unitary transformation always have inverse -- its adjoint)

​

Controlled NOT = CNOT (XORish)

Swap using CNOT

Control and Target reversal

Tensor Product

z(|a⟩⊗|b⟩) = (z|a⟩)⊗|b⟩ = |a⟩⊗(z|b⟩)

(|a⟩+|b⟩)⊗|c⟩ = |a⟩⊗|c⟩ + |b⟩⊗|c⟩

|c⟩⊗(|a⟩+|b⟩) = |c⟩⊗|a⟩ + |c⟩⊗|b⟩

(A⊗B)(|a⟩⊗|b⟩) = A|a⟩⊗B|b⟩

​

Controlled Unitary.

Every unitary matrix for a single qubit can be written as U = e^iαAXBXC, where A,B,C are unitary, α real, such that ABC = I.

Proof:

1. U = e^iαR_n(θ)
2. U = e^iαR_z(𝜷)R_y(𝛄)R_z(𝜹)
3. XYX = -Y ⇒ XR_y(𝛄)X = R_y(-𝛄)
4. Verify A=R_z(𝜷)R_y(𝛄/2), B=R_y(𝛄/2)R_z((𝜹+𝜷)/2), C=R_z((𝜹-𝜷)/2)
5. Explain phase move.

​

Controlled Unitary cont’d

C

X

B

X

A

1 0

0 e^iɑ

Toffoli Gate (NANDish)

Implementing Toffoli using H, T and S.

Bell States (Entangled states)

|𝛽₀₀⟩ = (|00⟩ + |11⟩)/√2

|𝛽₀₁⟩ = (|01⟩ + |10⟩)/√2

|𝛽₁₀⟩ = (|00⟩ - |11⟩)/√2

|𝛽₁₁⟩ = (|01⟩ - |10⟩)/√2

​

Quantum Computation Theorems.

Universality of CNOT: Every n-qubit unitary operator can be implemented by CNOT gate and all single qubit gates.

Approximation Theorem: Every n-qubit unitary operator can be approximated arbitrarily by CNOT gate and H,T (or Toffoli), and S gates.

​

Quantum Fourier Transform

Quantum Phase Estimation

Order Finding

Where r is order of x, least r such that x^r ≡ 1 (mod N).

Application: Order finding

But, the big problem is preparing eigenstate, which is impossible owing to fact we don’t know r. So we note (1/√r) Σ|u_s⟩ =|1⟩. as the second register. Now with 1/r probability we will get an eigenstate. So phase will be s/r with probability (1-ε)/r. Now to find actual r, we note that at sufficiently high accuracy, s/r is a continued fraction of estimate. (Non trivial theorem).

Application: Factoring

If x² ≡ 1 (mod N), such that x is not 1 or N-1. gcd(x-1, N) or gcd(x+1, N) is a non trivial factor of N. If N is odd composite non prime power, a random coprime a, will have an even order with high probability. So we will get a^x/2 as a solution. Retry until we get a solution. So factoring reduces to order finding. (For even N, power of prime, we got trivial mechanisms, especially owing to factor primality is polynomial in time).

Hidden Subgroup Problem

Let f be a function from a finitely generated group G to a finite set X such that f is constant on the cosets of a subgroup K, and distinct on each coset. Given a quantum black box for performing the unitary transform U|g⟩|h⟩ = |g⟩|h+f(g)⟩, for g ∊ G, h ∊ X, and + an appropriately chosen binary operation on X, find a generating set for K.

Most important Quantum Algorithms

1. Shor’s Algorithm (1994)
2. Grover’s Algorithm (1996)
3. Quantum Simulation (1980)
4. Linear Systems (2009)

Important from technical perspective (no application): Deutsch Jozsa Algorithm, Simon’s Algorithm.

References - Papers

1. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer - Peter M. Shor. link
2. An approximate Fourier transform useful in quantum factoring - D. Coppersmith. link
3. Quantum Algorithms Revisited - R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. link
4. Semi-classical Fourier transform for quantum computation. - R. B. Griffiths, C.S. Niu. link

References - Books

1. Quantum computation and quantum information - Michael A. Nielsen, and Isaac L. Chuang
2. The Principles of Quantum Mechanics - P.A.M. Dirac
3. Introduction to Quantum Mechanics - David J. Griffiths