Quantum algorithms Andrew Childs Pawel Wocjan University of Waterloo University of Central Florida 10th Canadian Summer School on Quantum Information 17–19 July 2010 Outline I. Quantum circuits II. Elementary quantum algorithms III. The QFT and phase estimation IV. Factoring V. Quantum search VI. Quantum walk Part I Quantum circuits Quantum circuit model Quantum circuits are generalizations of Boolean circuits input transformation output (probabilistic) |1〉 U1 U3 U6 NM 0 |1〉 U2 U5 NM 1 |0〉 U6 NM 0 |1〉 U3 U4 U7 NM 1 |0〉 NM 1 Classical bit Classical bit (bit): B := {0, 1} I Basis state: either 0 or 1 I General state: a probability distribution p = (p0, p1) on B Classical register Classical register: Bn := B× B× . . .× B︸ ︷︷ ︸ n I Basis state: a binary string x ∈ Bn I General state: a probability distribution p = (px : x ∈ Bn) on Bn (written as a column vector) Remark: Note that p is a vector with positive entries that is normalized with respect to the `1-norm (the sum of the absolute values of the entries) Classical transformation Transformations on the classical register B are described by stochastic matrices Stochastic matrices preserve the `1-norm, i.e., probability distributions are mapped on probability distributions Let p be the state of the register. The state after the transformation P is given by the matrix-vector-product Pp Qubit Quantum bit (qubit): two-dimensional complex Hilbert space C2 I Computational basis states (classical states): |0〉 := ( 1 0 ) and |1〉 := ( 0 1 ) I General states: superpositions |ψ〉 = ( α0 α1 ) = α0|0〉+ α1|1〉 , |α0|2 + |α1|2 = 1 the coefficients α0, α1 ∈ C are called probability amplitudes Quantum register Quantum register: 2n-dimensional complex Hilbert space (C2)⊗n with tensor product structure (C2)⊗n := C2 ⊗ C2 ⊗ · · · ⊗ C2︸ ︷︷ ︸ n I Computational basis states (classical states): |x〉 = |x1〉 ⊗ |x2〉 ⊗ · · · ⊗ |xn〉 , x ∈ Bn I General state: |ψ〉 = ∑ x∈Bn αx |x〉 , ∑ x |αx |2 = 1 Remark: Note that |ψ〉 is a column vector (ket) that is normalized with respect to the `2-norm (Euclidean norm) Quantum transformations Transformations on the quantum register H := (C2)⊗n are described by unitary matrices U ∈ U(H) Unitary matrices preserve the `2-norm Let |ψ〉 ∈ H be the state of the quantum register; the state after the transformation U is given by the matrix-vector product U |ψ〉 Quantum circuit Each transformations U has to be implemented by a quantum circuit, i.e., a sequence of elementary gates Quantum circuit model = Quantum mechanics + Notion of complexity Single qubit gate on two qubits single-qubit gate U on first qubit U action on basis states of C2 ⊗ C2 |0〉 ⊗ |0〉 7→ (U|0〉)⊗ |0〉 |0〉 ⊗ |1〉 7→ (U|0〉)⊗ |1〉 |1〉 ⊗ |0〉 7→ (U|1〉)⊗ |0〉 |1〉 ⊗ |1〉 7→ (U|1〉)⊗ |1〉 corresponding matrix U ⊗ I = ( u00 · I u01 · I u10 · I u11 · I ) = u00 0 u01 0 0 u00 0 u01 u10 0 u11 0 0 u10 0 u11 Single qubit gate on two qubits single-qubit gate U on second qubit U action on basis states of C2 ⊗ C2 |0〉 ⊗ |0〉 7→ |0〉 ⊗ U|0〉 |0〉 ⊗ |1〉 7→ |0〉 ⊗ U|1〉 |1〉 ⊗ |0〉 7→ |1〉 ⊗ U|0〉 |1〉 ⊗ |1〉 7→ |1〉 ⊗ U|1〉 corresponding matrix I ⊗ U = ( 1 · U 0 · U 0 · U 1 · U ) = u00 u01 0 0 u10 u11 0 0 0 0 u00 u01 0 0 u10 u11 Controlled-NOT gate control: first qubit; target: second qubit • action on basis states of C2 ⊗ C2 |c〉 ⊗ |t〉 7→ |c〉 ⊗ |c ⊕ t〉 corresponding matrix 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 = |0〉〈0| ⊗ I2 + |1〉〈1| ⊗ X where I2 = |0〉〈0|+ |1〉〈1| and X = |0〉〈1|+ |1〉〈0| Controlled U gate control: qubit; target: m-qubit register • / U let U be a unitary acting on the m-qubit register action on basis states of C2 ⊗ (C2)⊗m |c〉 ⊗ |t〉 7→ |c〉 ⊗ Uc |t〉 where b ∈ B, t ∈ Bm corresponding matrix( I 0 0 U ) = |0〉〈0| ⊗ I + |1〉〈1| ⊗ U Toffoli gate control: first and second qubits; target: third qubit • • action on basis states of C2 ⊗ C2 ⊗ C2 |c1〉 ⊗ |c2〉 ⊗ |t〉 7→ |c1〉 ⊗ |c2〉 ⊗ |(c1 ∧ c2)⊕ t〉 corresponding matrix 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 = (I4−|11〉〈11|)⊗ I2 + |11〉〈11|⊗X Simulating irreversible gates with Toffoli gate The classical AND gate is irreversible because if the output is 0 then we cannot determine which of the three possible pairs was the actual input x1 x2 x1 ∧ x2 0 0 0 0 1 0 1 0 0 1 1 1 But it is easy to simulate the AND gate with one Toffoli gate |x1〉 • |x1〉|x2〉 • |x2〉 |0〉 |x1 ∧ x2〉 Problem of garbage To simulate irreversible circuits with Toffoli gates, we keep the input and intermediary results to make everything reversible Consider the function y = x1 ∧ x2 ∧ x3 |x1〉 • |x1〉|x2〉 • |x2〉|x3〉 • |x3〉 |0〉 |x1 ∧ x2 ∧ x3〉 |0〉 • |x1 ∧ x2〉 garbage It is important to not leave any garbage; otherwise, we could not make use of quantum parallelism and constructive interference effects Reversible garbage removal It is always possible to reversibly remove (uncompute) the garbage In the case y = x1 ∧ x2 ∧ x3, this can be done with the circuit |x1〉 • • |x1〉|x2〉 • • |x2〉|x3〉 • |x3〉 |0〉 |x1 ∧ x2 ∧ x3〉 |0〉 • |0〉 garbage uncomputed Simulating irreversible circuits with Toffoli gates Let f : {0, 1}n → {0, 1} be any boolean function Assume this function can be computed classically using only t classical elementary gates such as AND, OR, NAND We can implement a unitary Uf on (C2)⊗n ⊗ C2 ⊗ (C2)⊗w such that Uf (|x〉in ⊗ |y〉out ⊗ |0〉⊗wwork) = |x〉 ⊗ |y ⊕ f (x)〉 ⊗ |0〉⊗w Uf is built from polynomially many in t Toffoli gates and the size w of the workspace register is polynomial in t During the computation the qubits of the workspace register are changed, but at the end they reversibly reset to |0〉⊗w Universal gate set – exact implementation Each unitary U ∈ U(H) can be implemented exactly by quantum circuits using only: I CNOT gates (acting on adjacent qubits) I arbitrary single qubit gates Gate complexity of unitaries – exact implementation The gate complexity κ(U) of a unitary U ∈ U(H) is minimal number of elementary gates needed to implement U For example, quantum Fourier Transform has complexity O(n2) =⇒ Shor’s factorization algorithm Universal gate set – approximate implementation For each ∈ (0, 1) and each unitary U ∈ U(H), there is a unitary V such that ‖U − V ‖ ≤ where ‖U − V ‖ = sup |ψ〉 ‖(U − V )|ψ〉‖ and V is implemented by quantum circuits using only: I CNOT gates (acting on adjacent qubits) I the single qubit gates H = 1√ 2 ( 1 1 1 −1 ) R(θ) = ( 1 0 0 e iθ ) , with θ = pi 4 There are other universal gate sets Gate complexity of unitaries – approximate implementation The gate complexity κ(U) of a unitary U is the minimal number of gates (from a universal gate set) need to implement a unitary V with ‖U − V ‖ ≤ The Solovay-Kitaev theorem implies that κ(U) = O ( κ(U) · logc (κ(U)/)) for some small constant c Counting arguments show that most n-qubit unitaries have gate complexity exponential in n. Quantum measurement A general measurement is described by a collection P0,. . . ,Pm−1 of orthogonal projectors such that m−1∑ i=0 Pi = IH where H denotes the identity on H Let |ψ〉 be the state of the quantum register. The probability of obtaining the outcome i is given by Pr(i) = ‖Pi |ψ〉‖2 The post-measurement state (collapse of the wavefunction) is Pi |ψ〉 ‖Pi |ψ〉‖ Elementary quantum measurements A measurement has to be realized by first applying a suitable quantum circuit followed by an elementary measurement An elementary measurement on the n-qubit quantum register H consists of measuring the first (w.l.o.g.) m qubits (m ≤ n) with respect to the computational basis The 2m orthogonal projectors Pb are labeled by m-bit strings b ∈ Bm and are defined by Pb = |b1〉〈b1| ⊗ |b2〉〈b2| ⊗ · · · ⊗ |bm〉〈bm| ⊗ I2n−m The probability of obtaining outcome b is given by Pr(b) = ‖Pb|ψ〉‖2 = ∑ xm+1,...,xn∈B |αb1,...,bm,xm+1,...,xn |2 Structure of quantum algorithms A quantum algorithm consists of I preparing the initial state |x〉 with x ∈ Bn, I applying a quantum circuit of polynomially many in n gates from some universal gate set, and I performing an elementary measurement These steps are repeated polynomially many times to collect enough samples and followed by classical post-processing =⇒ solution of the problem Hadamard test |0〉 H • H NM |ψ〉 / U The probabilities of obtaining the outcomes 0 and 1 are: Pr(0) = 1 2 (1 + Re〈ψ|U|ψ〉) Pr(1) = 1 2 (1− Re〈ψ|U|ψ〉) Hadamard test |0〉 H • H NM |ψ〉 / U |0〉 ⊗ |ψ〉 7→ 1√ 2 (|0〉+ |1〉)⊗ |ψ〉 = 1√ 2 |0〉 ⊗ |ψ〉+ 1√ 2 |1〉 ⊗ |ψ〉 7→ 1√ 2 |0〉 ⊗ |ψ〉+ 1√ 2 |1〉 ⊗ U|ψ〉 7→ 1 2 (|0〉+ |1〉)⊗ |ψ〉+ 1 2 (|0〉 − |1〉)⊗ U|ψ〉 = 1 2 |0〉 ⊗ (|ψ〉+ U|ψ〉) + 1 2 |1〉 ⊗ (|ψ〉 − U|ψ〉) =: |Φ〉 Hadamard test Pr(0) = ‖P|Φ〉‖2 with P = |0〉〈0| ⊗ I = ‖(|0〉〈0| ⊗ I) (1 2 |0〉 ⊗ (|ψ〉+ U|ψ〉) + 1 2 |1〉 ⊗ (|ψ〉 − U|ψ〉) ) ‖2 = ‖1 2 |0〉 ⊗ (|ψ〉+ U|ψ〉)‖2 = 1 4 ‖|0〉‖2 · ‖|ψ〉+ U|ψ〉‖2 = 1 4 (〈ψ|+ 〈ψ|U†) (|ψ〉+ U|ψ〉) = 1 4 (〈ψ|ψ〉+ 〈ψ|U|ψ〉+ 〈ψ|U†|ψ〉+ 〈ψ|U†U|ψ〉) = 1 4 ( 2 + 〈ψ|U|ψ〉+ 〈ψ|U|ψ〉) = 1 2 ( 1 + Re〈ψ|U|ψ〉) Hadamard test – Figure it out yourself How can you estimate the imaginary part of 〈ψ|U|ψ〉? Hint: Add a simple gate on the control register before the measurement. SWAP test – Figure it out yourself Let S denote the swap gate acting on two qubits S = |00〉〈00|+ |01〉〈10|+ |10〉〈01|+ |11〉〈11| Determine the matrix representation of S with respect to the computational basis Consider the Hadamard test where the controlled operation is |0〉〈0| ⊗ I4 + |1〉〈1| ⊗ S and the state of the target register |ψ〉 = |ψ1〉 ⊗ |ψ2〉 Determine the probability of obtaining 0 and 1 for the cases: I arbitrary |ψ1〉 and |ψ2〉, I 〈ψ1|ψ2〉 = 0 (orthogonal), and I 〈ψ1|ψ2〉 = 1 (the same). Part II Elementary quantum algorithms Black box problems Standard computational problem: determine a property of some input data I Example: Find the prime factors of N Alternate model: Input is provided by a black box (or oracle) I Query: On input x , black box returns f (x) I Determine a property of f using as few queries as possible I The minimum number of queries is the query complexity I Example: Given a black box for f : {1, 2, . . . ,N} → {0, 1}, is there some x such that f (x) = 1? I Why black boxes? I Facilitates proving lower bounds I Can lead to algorithms for standard problems Black boxes for reversible/quantum computing Black box x f f (x) is not reversible Reversible version: x f x z z ⊕ f (x) Given a circuit that computes f non-reversibly, we can implement the reversible version with little overhead Quantum version: |x〉 f |x〉 |z〉 |z ⊕ f (x)〉 A reversible circuit is a quantum circuit Deutsch’s problem Problem I Given: a black-box function f : {0, 1} → {0, 1} I Task: determine whether f is constant or balanced x f1(x) 0 0 1 0 x f2(x) 0 1 1 1 x f3(x) 0 0 1 1 x f4(x) 0 1 1 0︸ ︷︷ ︸ constant: f (0) = f (1) ︸ ︷︷ ︸ balanced: f (0) 6= f (1) How many queries are needed? I Classically: 2 queries are necessary and sufficient I Quantumly: ? Toward a quantum algorithm for Deutsch’s problem Quantum black box for f : |x〉 f |x〉 |z〉 |z ⊕ f (x)〉 Compute f in superposition: |0〉 H f|0〉 |0〉 ⊗ |0〉 7→ |0〉+ |1〉√ 2 ⊗ |0〉 7→ 1√ 2 (|0〉 ⊗ |f (0)〉+ |1〉 ⊗ |f (1)〉) Can’t extract more than one bit of information about f Phase kickback Quantum black box for f : |x〉 f |x〉 |z〉 |z ⊕ f (x)〉 Phase kickback: |x〉 f (−1)f (x)|x〉 |0〉−|1〉√ 2 |0〉−|1〉√ 2 |x〉 ⊗ 1√ 2 (|0〉 − |1〉) = 1√ 2 (|x〉 ⊗ |0〉 − |x〉 ⊗ |1〉) 7→ 1√ 2 (|x〉 ⊗ |f (x)〉 − |x〉 ⊗ |1⊕ f (x)〉) = |x〉 ⊗ 1√ 2 (|f (x)〉 − |f (x)〉) = (−1)f (x)︸ ︷︷ ︸ not necessarily global |x〉 ⊗ 1√ 2 (|0〉 − |1〉) (−1)f (x)︸ ︷︷ ︸ not necessarily global Quantum algorithm for Deutsch’s problem |0〉 H f H NM f (0)⊕ f (1)|0〉−|1〉√ 2 |0〉 ⊗ |0〉 − |1〉√ 2 7→ |0〉+ |1〉√ 2 ⊗ |0〉 − |1〉√ 2 7→ (−1) f (0)|0〉+ (−1)f (1)|1〉√ 2 ⊗ |0〉 − |1〉√ 2 = (−1)f (0) |0〉+ (−1) f (0)⊕f (1)|1〉√ 2 ⊗ |0〉 − |1〉√ 2 7→ (−1)f (0)|f (0)⊕ f (1)〉 ⊗ |0〉 − |1〉√ 2 1 quantum query vs. 2 classical queries! The Deutsch-Jozsa problem Problem I Given: a black-box function f : {0, 1}n → {0, 1} I Promise: f is either constant (f (x) is independent of x) or balanced (f (x) = 0 for exactly half the values of x) I Task: determine whether f is constant or balanced How many queries are needed? I Classically: 2n/2 + 1 queries to answer with certainty I Quantumly: ? Phase kickback for a Boolean function of n bits Black box function: |x1〉 f |x1〉 ... ... |xn〉 |xn〉 |z〉 |z ⊕ f (x)〉 Phase kickback: |x1〉 ⊗ · · · ⊗ |xn〉 ⊗ |0〉 − |1〉√ 2 7→ (−1)f (x)|x1〉 ⊗ · · · ⊗ |xn〉 ⊗ |0〉 − |1〉√ 2 Quantum algorithm for the Deutsch-Jozsa problem |0〉 H f H NM ... ... ... |0〉 H H NM |0〉−|1〉√ 2 |0〉⊗n ⊗ |0〉 − |1〉√ 2 7→ ( |0〉+ |1〉√ 2 )⊗n ⊗ |0〉 − |1〉√ 2 = 1√ 2n ∑ x∈{0,1}n |x〉 ⊗ |0〉 − |1〉√ 2 7→ 1√ 2n ∑ x∈{0,1}n (−1)f (x)|x〉 ⊗ |0〉 − |1〉√ 2 Hadamard transform What do the final Hadamard gates do? H|x〉 = 1√ 2 (|0〉+ (−1)x |1〉) = 1√ 2 ∑ y∈{0,1} (−1)xy |y〉 H⊗n(|x1〉 ⊗ · · · ⊗ |xn〉) = n⊗ i=1 1√ 2 ∑ yi∈{0,1} (−1)xiyi |yi 〉 = 1√ 2n ∑ y∈{0,1}n (−1)x ·y |y〉 Quantum D-J algorithm: Finishing up 1√ 2n ∑ x∈{0,1}n (−1)f (x)|x〉 H⊗n7→ 1 2n ∑ x ,y∈{0,1}n (−1)f (x)(−1)x ·y |y〉 I If f is constant, the amplitude of |y〉 is ± 1 2n ∑ x∈{0,1}n (−1)x ·y = ± { 1 if y = 0 . . . 0 0 otherwise so we definitely measure 0 . . . 0 I If f is balanced, the amplitude of |0 . . . 0〉 is∑ x∈{0,1}n (−1)f (x) = 0 so we measure some nonzero string The Deutsch-Jozsa problem: Quantum vs. classical Above quantum algorithm uses only one query. Need 2n/2 + 1 classical queries to answer with certainty. What about randomized algorithms? Success probability arbitrarily close to 1 with a constant number of queries. Can we get a separation between randomized and quantum computation? Simon’s problem Problem I Given: a black-box function f : {0, 1}n → {0, 1}m I Promise: there is some s ∈ {0, 1}n such that f (x) = f (y) if and only if x = y or x = y ⊕ s I Task: determine s One classical strategy: I query a random x I repeat until we find xi 6= xj such that f (xi ) = f (xj) I output xi ⊕ xj By the birthday problem, this uses about √ 2n queries. It can be shown that this strategy is essentially optimal. Quantum algorithm for Simon’s problem Quantum black box: |x〉 ⊗ |y〉 7→ |x〉 ⊗ |y ⊕ f (x)〉 (x ∈ {0, 1}n, y ∈ {0, 1}m) |0〉 H f H NM ... ... ... |0〉 H H NM |0〉 ... ... |0〉 Repeat many times and post-process the measurement outcomes Quantum algorithm for Simon’s problem: Analysis I |0〉 H f H NM ... ... ... |0〉 H H NM |0〉 ... ... |0〉 |0〉⊗n ⊗ |0〉⊗m 7→ 1√ 2n ∑ x∈{0,1}n |x〉 ⊗ |0〉⊗m 7→ 1√ 2n ∑ x∈{0,1}n |x〉 ⊗ |f (x)〉 = 1√ 2n−1 ∑ x∈R |x〉+ |x ⊕ s〉√ 2 ⊗ |f (x)〉 for some R ⊂ {0, 1}n Quantum algorithm for Simon’s problem: Analysis II Recall H⊗n|x〉 = ∑y∈{0,1}n(−1)x ·y |y〉 H⊗n ( |x〉+ |x ⊕ s〉√ 2 ) = 1√ 2n+1 ∑ y∈{0,1}n [(−1)x ·y + (−1)(x⊕s)·y ]|y〉 = 1√ 2n+1 ∑ y∈{0,1}n (−1)x ·y [1 + (−1)s·y ]|y〉 Two cases: I if s · y = 0 mod 2, 1 + (−1)s·y = 2 I if s · y = 1 mod 2, 1 + (−1)s·y = 0 Measuring gives a random y orthogonal to s (i.e., s · y = 0) Quantum algorithm for Simon’s problem: Post-processing Measuring gives a random y orthogonal to s (s · y = 0) Repeat k times, giving vectors y1, . . . , yk ∈ {0, 1}n; solve a system of k linear equations for s ∈ {0, 1}n: y1 · s = 0, y2 · s = 0, . . . , yk · s = 0 How big should k be to give a unique (nonzero) solution? I Clearly k ≥ n − 1 is necessary I It can be shown that k = O(n) suffices O(n) quantum queries, O(n3) quantum gates Compare to Ω(2n/2) classical queries (even for bounded error) Recap We have seen several examples of quantum algorithms that outperform classical computation: I Deutsch’s problem: 1 quantum query vs. 2 classical queries I Deutsch-Jozsa problem: 1 quantum query vs. 2Ω(n) classical queries (deterministic) I Simon’s problem: O(n) quantum queries vs. 2Ω(n) classical queries (randomized) Quantum algorithms for more interesting problems build on the tools used in these examples. Exercise: One-out-of-four search Let f : {0, 1}2 → {0, 1} be a black-box function taking the value 1 on exactly one input. The goal is to find the unique (x1, x2) ∈ {0, 1}2 such that f (x1, x2) = 1. I Write the truth tables of the four possible functions f . I How many classical queries are needed to solve the problem? I Suppose f is given as a quantum black box Uf acting as |x1, x2, y〉 7→ |x1, x2, y ⊕ f (x1, x2)〉. Determine the output of the following quantum circuit for each of the possible black-box functions f : |0〉 H f|0〉 H |1〉 H I Show that the four possible outputs obtained in the previous part are pairwise orthogonal. What can you conclude about the quantum query complexity of one-out-of-four search? Part III The QFT and phase estimation Quantum phase estimation Problem We are given a unitary U and an eigenvector |ψ〉 of U with unknown eigenvalue We seek to determine its eigenphase ϕ ∈ [0, 1) such that U|ψ〉 = e2piiϕ|ψ〉 More precisely, we want to obtain an estimate ϕ̂ such that Pr (|ϕ̂− ϕ| ≤ 1 2n ) ≥ 3 4 The deviation |ϕ̂− ϕ| is computed modulo 1 Phase kick back |+〉 • |ψ〉 U |0〉+ |1〉√ 2 ⊗ |ψ〉 = |0〉√ 2 ⊗ |ψ〉+ |1〉√ 2 ⊗ |ψ〉 7→ |0〉√ 2 ⊗ |ψ〉+ |1〉√ 2 ⊗ U|ψ〉 = |0〉√ 2 ⊗ |ψ〉+ |1〉√ 2 ⊗ e2piiϕ|ψ〉 = |0〉√ 2 ⊗ |ψ〉+ e 2piiϕ|1〉√ 2 ⊗ |ψ〉 = |0〉+ e2piiϕ|1〉√ 2 ⊗ |ψ〉 Phase kick back |+〉 • |ψ〉 U |0〉+ |1〉√ 2 ⊗ |ψ〉 7→ |0〉+ e 2piiϕ|1〉√ 2 ⊗ |ψ〉 The eigenstate |ψ〉 in the target register emerges unchanged ⇒ It suffices to focus on the control register The state |0〉+ |1〉 of the control qubit is changed to |0〉+ e2piiϕ|1〉 by phase kick back Hadamard test + phase kick back |0〉 H • H NM |ψ〉 / U |0〉+ e2piiϕ|1〉√ 2 7→ 1 2 ( (|0〉+ |1〉) + e2piiϕ(|0〉 − |1〉)) 7→ 1 2 ( (1 + e2piiϕ)|0〉+ (1− e2piiϕ)|1〉)) := |ϕ〉 Hadamard test + phase kick back |ϕ〉 = 1 2 ( (1 + e2piiϕ)|0〉+ (1− e2piiϕ)|1〉)) The probability of obtaining 0 is Pr(0) = ‖|0〉〈0| |ϕ〉‖2 = |1 2 (1 + e2piiϕ)|2 = 1 4 |epiiϕ + e−piiϕ)|2 = 1 4 |2 cos(piϕ)|2 = cos2(piϕ) = 1 2 ( 1 + cos(2piϕ) ) Phase kick back due to higher powers of U For arbitrary k , we obtain |0〉 H • 1√2 (|0〉+ e2pii2 kϕ|1〉) |ψ〉 / U2k |ψ〉 since U2 k |ψ〉 = e2pii2kϕ|ψ〉 Phase kick back part of phase estimation |0〉 H • |0〉+e2pii2 n−1ϕ|1〉√ 2 |0〉 H • |0〉+e2pii2 n−2ϕ|1〉√ 2... · · · ... |0〉 H • |0〉+e2pii2 0ϕ|1〉√ 2 |ψ〉 / U20 U21 U2n−1 |ψ〉 We set |ϕ〉 := |0〉+ e 2pii2n−1ϕ|1〉√ 2 ⊗|0〉+ e 2pii2n−2ϕ|1〉√ 2 ⊗· · ·⊗ |0〉+ e 2pii20ϕ|1〉√ 2 Binary fractions Assume that the eigenphase ϕ is an exact n-bit binary fraction, i.e., ϕ = 0.x1x2 . . . xn = n∑ i=1 xi 2i For arbitrary k ∈ {0, . . . , n − 1}, we have 2k ϕ = x1x2 . . . xk .xk+1 . . . xn e2pii2 kϕ = e2pii(x1x2...xk .xk+1...xn) = e2pii(x1x2...xk+0.xk+1...xn) = e2pii(x1x2...xk ) · e2pii(0.xk+1...xn) = e2pii(0.xk+1...xn) Phase kick back part of phase estimation |0〉 H • |0〉+e2pii0.xn |1〉√ 2 |0〉 H • |0〉+e2pii0.xn−1xn |1〉√ 2... · · · ... |0〉 H • |0〉+e2pii0.x1...xn−1xn |1〉√ 2 |ψ〉 / U20 U21 U2n−1 |ψ〉 Quantum Fourier transform The quantum Fourier transform F is defined by F (|xn〉 ⊗ |xn−1〉 ⊗ · · · ⊗ |x1〉) = |0〉+ e2pii0.xn |1〉√ 2 ⊗ |0〉+ e 2pii0.xn−1xn |1〉√ 2 ⊗· · ·⊗ |0〉+ e 2pii0.x1x2...xn |1〉√ 2 We use inverse quantum Fourier transform F † to obtain the bits of the eigenphase Note: QFT is defined by F |x1〉 ⊗ |x2〉 ⊗ · · · ⊗ |xn〉 = |0.x1x2 . . . xn〉 in the literature; we use the above definition for the sake of notational simplicity (otherwise, we would have to include the so-called bit-reversal) Quantum circuit for phase estimation |0〉 H • F † |xn〉 |0〉 H • |xn−1〉 ... · · · |0〉 H • |x1〉 |ψ〉 / U20 U21 U2n−1 |ψ〉 Inverse quantum Fourier transform for 3 bits |0〉+e2pii0.x3 |1〉√ 2 H • • |x3〉 |0〉+e2pii0.x2x3 |1〉√ 2 R†2 H • |x2〉 |0〉+e2pii0.x1x2x3 |1〉√ 2 R†3 R † 2 H |x1〉 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ The phase shift Rk is defined by Rk := [ 1 0 0 e2pii/2 k ] QPE: least significant bit – top qubit |0〉+e2pii0.x3 |1〉√ 2 H _ _ _ _ _ _ |0〉+ e2pii0.x3 |1〉√ 2 = |0〉+ (−1)x3 |1〉√ 2 H−→ |x3〉 QPE: second bit – middle qubit |x3〉 • |0〉+e2pii0.x2x3 |1〉√ 2 R†2 H _ _ _ _ _ _ _ _ _ _ _ _ |x3〉 ⊗ |0〉+ e 2pii0.x2x3 |1〉√ 2 ctrl R†2−−−−→ |x3〉 ⊗ |0〉+ e 2pii0.x20|1〉√ 2 I⊗H−−−→ |x3〉 ⊗ |x2〉 QPE: most significant bit – bottom qubit |x3〉 •|x2〉 • |0〉+e0.x1x2x3 |1〉√ 2 R†3 R † 2 H _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |x3〉 ⊗ |x2〉 ⊗ |0〉+ e 2pii0.x1x2x3 |1〉√ 2 ctrl R†3−−−−→ |x3〉 ⊗ |x2〉 ⊗ |0〉+ e 2pii0.x1x20|1〉√ 2 ctrl R†2−−−−→ |x3〉 ⊗ |x2〉 ⊗ |0〉+ e 2pii0.x100|1〉√ 2 I⊗I⊗H−−−−→ |x3〉 ⊗ |x2〉 ⊗ |x1〉 Summary of phase estimation circuit We use phase kick back due to the controlled U2 k gate to prepare the state |0〉+ e2pii0.xk+1xk+2...xn |1〉√ 2 Using the previously determined bits xk+2, . . . , xn, we change this state to |0〉+ e2pii0.xk+10...0|1〉√ 2 = |0〉+ (−1)xk |1〉√ 2 We apply the Hadamard gate to obtain |xk+1〉 The controlled phase shifts enable us to reduce the problem of determining each bit to distinguishing between |+〉 and |−〉 (deterministic Hadamard test) Special case: exact n-bit binary fraction Assume that ϕ is an exact n-bit binary fraction, i.e., ϕ = 0.x1 . . . xn−1xn |0〉 H • F † |xn〉 |0〉 H • |xn−1〉 ... · · · |0〉 H • |x1〉 |ψ〉 / U20 U21 U2n−1 |ψ〉 ⇒ The measurment of the qubits yields the bits xn, xn−1, . . . , x1 deterministically General case: arbitrary eigenphases Let ϕ be arbitrary Unless ϕ is an exact n-bit fraction, the application of the inverse quantum Fourier transform F †|ϕ〉 produces a superposition of n-bit strings Geometric summation Lemma We have N−1∑ y=0 e2piiθy = N for θ = 0 N−1∑ y=0 e2piiθy = 1− e2piiNθ 1− e2piiθ for θ ∈ (0, 1) Assume that θ = xN for some x ∈ [0,N − 1] ⇒ We have N−1∑ y=0 e2pii x N y = N δx ,0 Probability of obtaining a certain estimate Lemma Let x = ∑n k=1 xi2 n−i and ϕx := 0.x1x2 . . . xn = x2n be the corresponding n-bit fraction The probability of obtaining the estimate ϕx is Pr(x) = 1 22n sin2 ( 2n pi (ϕ− ϕx) ) sin2 ( pi (ϕ− ϕx) ) Examples of probability distributions for different ϕ Examples of probability distributions for different ϕ Examples of probability distributions for different ϕ Examples of probability distributions for different ϕ Examples of probability distributions for different ϕ Examples of probability distributions for different ϕ Examples of probability distributions for different ϕ Examples of probability distributions for different ϕ Examples of probability distributions for different ϕ Probability of obtaining a certain estimate Proof. The probability of obtaining the estimate ϕx is Pr(x) = |〈x |F †|ϕ〉|2 = |〈ϕx |ϕ〉|2 = 1 22n ∣∣ 2n−1∑ y=0 e2pii (ϕ−ϕx ) y ∣∣2 geometric summation = 1 22n ∣∣∣1− e2pii(2n(ϕ−ϕx )) 1− e2pii(ϕ−ϕx ) ∣∣∣2 |1− e i2θ| = |e−iθ − e iθ| = 2| sin θ| = 1 22n sin2(2n pi(ϕ− ϕx)) sin2(pi(ϕ− ϕx)) Lower bound on success probability Theorem Let x be such that x2n ≤ ϕ < x+12n The probability of returning one of the two closest n-bit fractions ϕx and ϕx+1 is at least 8 pi2 Proof of lower bound on success probability Pr(success) := Pr(x) + Pr(x + 1) = 1 22n ∣∣ 2n−1∑ y=0 e2pii(ϕ−ϕx )y ∣∣2 + ∣∣ 2n−1∑ y=0 e2pii(ϕ−ϕx )y ∣∣2 This function attains its minimum at ϕ = 12 (ϕx + ϕx+1) ⇒ Pr(success) ≥ 2 22n ∣∣ 2n−1∑ y=0 e2pii y 2n+1 ∣∣2 ≥ 2 22n 4 4 sin2( pi 2n+1 ) ≥ 8 pi2 The last inequality follows from 1| sin θ|2 ≥ 1|θ|2 Summary of phase estimation We are given a unitary U and an eigenvector |ψ〉 of U with unknown eigenphase ϕ We obtain an estimate ϕ̂ such that Pr (|ϕ̂− ϕ| ≤ 1 2n ) ≥ 8 pi2 To do this, we need invoke each of the controlled U, U2,. . . ,U2 n−1 gates once We can boost the success probability to 1− by repeating the above algorithm O(log(1/)) times and outputting the median of the outcomes Phase estimation applied to superpositions of eigenstates We are given a unitary U with eigenvectors |ψi 〉 and corresponding eigenphases ϕi Let |ψ〉 = ∑ i αi |ψi 〉 What happens if we apply phase estimation to |0〉⊗n ⊗ |ψ〉? After the n phase kick-backs due to U2 0 , U2 1 , . . . U2 n−1 , we obtain∑ i αi |ϕi 〉 ⊗ |ψi 〉 After applying the inverse quantum Fourier transform, we obtain∑ i αi |x̃i 〉 ⊗ |ψi 〉 where |x̃i 〉 denotes a superpositions of n-bit estimates of ϕi Part IV Factoring The fundamental theorem of arithmetic Theorem Every positive integer larger than 1 can be factored as a product of prime numbers, and this factorization is unique (up to the order of the factors). N = 2n2 × 3n3 × 5n5 × 7n7 × · · · Examples 15 = 3× 5 239815173914273 = 15485863× 15486071 3107418240490043721350750 0358885679300373460228427 2754572016194882320644051 8081504556346829671723286 7824379162728380334154710 7310850191954852900733772 4822783525742386454014691 736602477652346609 = 16347336458092538484 43133883865090859841 78367003309231218111 08523893331001045081 51212118167511579 × 19008712816648221131 26851573935413975471 89678996851549366663 85390880271038021044 98957191261465571 “The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length... Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.” – Carl Friedrich Gauss, Disquisitiones Arithmeticæ (1801) RSA Alice Eve Bob M message primes p, q n n n = pq e e e ∈ Z×(p−1)(q−1) encryption key d := e−1 mod (p − 1)(q − 1) decryption key C := Me mod n ciphertext C Cd = Med mod n = M Order finding Definition Given a,N ∈ Z with gcd(a,N) = 1, the order of a modulo N is the smallest positive integer r such that ar ≡ 1 (mod N). Problem I Given: a,N ∈ Z with gcd(a,N) = 1 I Task: find the order of a modulo N Spectrum of a cyclic shift Let P be a cyclic shift modulo r : P|x〉 = |x + 1 mod r〉 Claim. For any k ∈ Z, the state |uk〉 := 1√ r r−1∑ x=0 e−2piikx/r |x〉 is an eigenstate of P. Proof. U|uk〉 = 1√ r r−1∑ x=0 e−2piikx/r |x + 1 mod r〉 = 1√ r r−1∑ x=0 e2piik/re−2piik(x+1)/r |x + 1 mod r〉 = e2piik/r 1√ r r∑ x=1 e−2piikx/r |x mod r〉 = e2piik/r |uk〉 The multiplication-by-a map Define U by U|x〉 = |ax〉 for x ∈ ZN . Computing U: |x , 0〉 7→ |x , ax〉 (reversible multiplication by a) 7→ |ax , x〉 (swap) 7→ |ax , 0〉 (uncompute reversible division by a) High powers of U can be implemented efficiently using repeated squaring Spectrum of the multiplication-by-a map Define U by U|x〉 = |ax〉 for x ∈ ZN . Claim. Let r be the order of a modulo N. For any k ∈ Z, the state |uk〉 := 1√ r r−1∑ x=0 e−2piikx/r |ax mod N〉 is an eigenstate of U with eigenvalue e2piik/r . Proof. Same as for the cyclic shift, due to the isomorphism x mod r ↔ ax mod N Order finding and phase estimation U|uk〉 = e2piik/r |uk〉 Phase estimation of U on |uk〉 can be used to approximate k/r . Problems: I We don’t know r , so we can’t prepare |uk〉. I We only get an approximation of k/r . I Even if we knew k/r exactly, k and r could have common factors. Estimating k/r in superposition A useful identity: r−1∑ k=0 e2piikx/r = { r if x = 0 0 otherwise Consider 1√ r r−1∑ k=0 |uk〉 = 1 r r−1∑ k,x=0 e−2piikx/r |ax mod N〉 = |a0 mod N〉 = |1〉 Phase estimation: |0〉 ⊗ |1〉 = 1√ r r−1∑ k=0 |0〉 ⊗ |uk〉 7→ 1√ r r−1∑ k=0 |k̃/r〉 ⊗ |uk〉 Measurement gives an approximation of k/r for a random k Continued fractions Problem Given samples x of the form bk 2nr c, dk 2 n r e (k ∈ {0, 1, . . . , r − 1}), determine r . Continued fraction expansion: x 2n = 1 a1 + 1 a2+ 1 a3+··· Gives an efficiently computable sequence of rational approximations Theorem If 2n ≥ N2, then k/r is the closest convergent of the CFE to x/2n among those with denominator smaller than N. Since r < N, it suffices to take n = 2 log2 N Common factors If gcd(k , r) = 1, then the denominator of k/r is r Fact The probability that gcd(k, r) = 1 for a random k ∈ {0, 1, . . . , r − 1} is φ(r) r = Ω ( 1 log log r ) 0 200 400 600 800 1000 n 0.2 0.4 0.6 0.8 1.0 jHnLn Thus Ω(log log N) repetitions suffice to give r with constant probability Alternatively, find two (or more) denominators and take their least common multiple; then O(1) repetitions suffice Factoring → finding a nontrivial factor Suppose we want to factor the positive integer N. Since primality can be tested efficiently, it suffices to give a procedure for finding a nontrivial factor of N with constant probability. function factor(N) if N is prime output N else repeat x=find_nontrivial_factor(N) until success factor(x) factor(N/x) end if We can assume N is odd, since it is easy to find the factor 2. We can also assume that N contains at least two distinct prime powers, since it is easy to check if it is a power of some integer. Reduction of factoring to order finding Factoring N reduces to order finding in Z×N [Miller 1976]. Choose a ∈ {2, 3, . . . ,N − 1} uniformly at random. If gcd(a,N) 6= 1, then it is a nontrivial factor of N. If gcd(a,N) = 1, let r denote the order of a modulo N. Suppose r is even. Then ar = 1 mod N m (ar/2)2 − 1 = 0 mod N m (ar/2 − 1)(ar/2 + 1) = 0 mod N so we might hope that gcd(ar/2− 1,N) is a nontrivial factor of N. Miller’s reduction Question Given (ar/2 − 1)(ar/2 + 1) = 0 mod N, when does gcd(ar/2 − 1,N) give a nontrivial factor of N? Note that ar/2 − 1 6= 0 mod N (otherwise the order of a would be r/2, or smaller). So it suffices to ensure that ar/2 + 1 6= 0 mod N. Lemma Suppose a ∈ Z×N is chosen uniformly at random, where N is an odd integer with at least two distinct prime factors. Then with probability at least 1/2, the order r of a is even and ar/2 6= −1 mod N. Proof (part 1 of 2) Let N = pm11 × · · · × pmkk (pi distinct odd primes, k ≥ 2) a = ai mod p mi i ri = order of ai mod p mi i 2ci = largest power of 2 that divides ri Claim 1. If r is odd or ar/2 + 1 = 0 mod N, then c1 = · · · = ck . Since r = lcm(r1, . . . , rk), r is odd iff c1 = . . . = ck = 0. If r is even and ar/2 = −1 mod N, then ar/2 = −1 mod pmii for each i , so ri does not divide r/2; but notice that ri does divide r . Hence r/ri is an odd integer for each i , and every ri must contain the same number of powers of 2 as r . Proof (part 2 of 2) Claim 2. Pr(ci = any particular value) ≤ 1/2 (Then the lemma follows, since in particular Pr(c1 = c2) ≤ 1/2.) a ∈ Z×N uniformly at random ⇔ ai ∈ Z × p mi i uniformly at random Since Z× p mi i is cyclic and of even order, exactly half its elements have the maximal value of ci , so in particular the probability of any particular ci is at most 1/2. Shor’s algorithm Input: Integer N Output: A nontrivial factor of N 1. Choose a random a ∈ {2, 3, . . . ,N − 1} 2. Compute gcd(a,N); if it is not 1 then it is a nontrivial factor, and otherwise we continue 3. Perform phase estimation with the multiplication-by-a operator U on the state |1〉 using n = 2 log2 N bits of precision 4. Compute the continued fraction expansion of the estimated phase, and find the best approximation with denominator less than N; call the result r 5. Compute gcd(ar/2 − 1,N). If it is a nontrivial factor of N, we are done; if not, go back to step 1 Quantum vs. classical factoring algorithms Best known classical algorithm for factoring N I Proven running time: 2O((logN) 1/2(log logN)1/2) I With plausible heuristic assumptions: 2O((logN) 1/3(log logN)1/3) Shor’s quantum algorithm I QFT modulo 2n with n = O(log N): takes O(n2) steps I Modular exponentiation: compute ax for x < 2n. With repeated squaring, takes O(n3) steps I Running time of Shor’s algorithm: O(log3 N) Beyond factoring There are many fast quantum algorithms based on related ideas I Computing discrete logarithms I Decomposing abelian/solvable groups I Estimating Gauss sums I Counting points on algebraic curves I Computations in number fields (Pell’s equation, etc.) I Abelian hidden subgroup problem I Non-abelian hidden subgroup problem? Part V Quantum search Unstructured search Quantum computers can quadratically outperform classical computers at a very basic computational task, called unstructured search. There is a set X containing N items, some of which are marked We are given a Boolean black box f : X → {0, 1} that indicates whether a given item is marked The problem is to decide if any item is marked, or alternatively, to find a marked item given that one exists Applications of unstructured search Unstructured search can be thought of as a model for solving problems in NP by brute force search If a problem is in NP, then we can efficiently recognize a solution, so one way to find a solution is to solve unstructured search Of course, this may not be the best way to find a solution in general, even if the problem is NP-hard We don’t know if NP-hard problems are really “unstructured” Unstructured search It is obvious that even a randomized classical algorithm needs Ω(N) queries to decide if any item is marked On the other hand, a quantum algorithm can do much better! Phase oracle We assume that we a unitary operator U satisfying U|x〉 = (−1)f (x)|x〉 = { |x〉 x is not marked −|x〉 x is marked Target state We consider the case where there is exactly one x ∈ X element that is marked; call this element m Our goal is to prepare the state |m〉 Initial state We have no information about which item might be marked ⇒ We take |ψ〉 := 1√ N N∑ x=1 |x〉 as the initial state Rough idea behind Grover search We start with the initial state |ψ〉 We prepare the target state |m〉 by implementing a rotation that moves |ψ〉 toward |m〉 We realize the rotation with the help of two reflections Visualization of a reflection in R2 PIC 1 v PIC 1 v w ω 'w 2ω ω Visualization of a reflection in R2 PIC 1 v w ω 'w 2ω ω PIC 1 ω v w Visualization of a reflection in R2 PIC 1 v w ω 'w 2ω ω Reflections U = I − 2|m〉〈m| is a reflection about the target state |m〉 V = I − 2|ψ〉〈ψ| is the reflection around about the initial state |ψ〉: V |ψ〉 = − |ψ〉 V |ψ⊥〉 = |ψ⊥〉 for any state |ψ⊥〉 orthogonal to |ψ〉 Structure of Grover The algorithm is as follows: I start in |ψ〉, I apply the Grover iteration G := V U some number of times, I make a measurement, and hope that the outcome is m Invariant subspace Observe that span{|m〉, |ψ〉} is a U- and V -invariant subspace, and both the inital and target states belong to this subspace ⇒ It suffices to understand the restriction of VU to this subspace Consider an orthonormal basis {|m〉, |φ〉} for span{|m〉, |ψ〉} The Gram-Schmidt process yields |φ〉 = |ψ〉 − α|m〉√ 1− α2 where α := 〈m|ψ〉 = 1/√N Invariant subspace Now in the basis {|m〉, |φ〉}, we have |ψ〉 = sin θ|m〉+ cos θ|φ〉 where sin θ = 〈m|ψ〉 = 1/ √ N U = (−1 0 0 1 ) V = I − 2|ψ〉〈ψ| = ( 1 0 0 1 ) − 2 ( sin θ cos θ )( sin θ cos θ ) = ( 1− 2 sin2 θ −2 sin θ cos θ −2 sin θ cos θ 1− 2 cos2 θ ) = − (− cos 2θ sin 2θ sin 2θ cos 2θ ) Grover iteration within the invariant subspace ⇒ We find V U = − (− cos 2θ sin 2θ sin 2θ cos 2θ ) (−1 0 0 1 ) = − ( cos 2θ sin 2θ − sin 2θ cos 2θ ) This is a rotation up to a minus sign Visualization of first Grover iteration PIC 4 m φ ψ θ PIC 4 m φ ψ θ 2 π θ− 2 π θ− U ψ VU ψ π θ−2π θ− VU ψ−θ 3π θ− 3θ 3θθ 2θ Visualization of first Grover iteration PIC 4 m φ ψ θ 2 π θ− 2 π θ− U ψ PIC 4 m φ ψ U ψ VU ψ 2π θ−2π θ− VU ψ−θ 3π θ− 3θ 3θθ 2θ Visualization of first Grover iteration PIC 4 m φ ψ θ 2 π θ− 2 π θ− U ψ VU ψ π θ−2π θ− PIC 4 m φ ψ U ψ VU ψ VU ψ− 2π θ− θ 3π θ− 3θ 3θθ 2θ Visualization of first Grover iteration PIC 4 m φ ψ θ 2 π θ− 2 π θ− U ψ VU ψ π θ−2π θ− VU ψ−θ PIC 4 m φ ψ U ψ VU ψ VU ψ− 3π θ− 3θ 3θθ 2θ Visualization of first Grover iteration PIC 4 m φ ψ θ 2 π θ− 2 π θ− U ψ VU ψ π θ−2π θ− VU ψ−θ 3π θ− PIC 4 m φ ψ U ψ VU ψ VU ψ− 3θ 3π θ− 3θθ 2θ Visualization of first Grover iteration PIC 4 m φ ψ θ 2 π θ− 2 π θ− U ψ VU ψ π θ−2π θ− VU ψ−θ 3π θ− 3θ PIC 4 m φ ψ U ψ VU ψ VU ψ− 3θ 3θθ 2θ Visualization of first Grover iteration PIC 4 m φ ψ θ 2 π θ− 2 π θ− U ψ VU ψ π θ−2π θ− VU ψ−θ 3π θ− 3θ 3θ PIC 4 m φ ψ U ψ VU ψ VU ψ− θ 2θ Visualization of first Grover iteration PIC 4 m φ ψ θ 2 π θ− 2 π θ− U ψ VU ψ π θ−2π θ− VU ψ−θ 3π θ− 3θ 3θθ 2θ Grover search Geometrically, U is a reflection around the |m〉 axis and V is a reflection around the |ψ〉 axis, which is almost but not quite orthogonal to the |m〉 axis The product of these two reflections is a clockwise rotation by an angle 2θ, up to an overall minus sign From this geometric picture, or by explicit calculation using trig identities, it is easy to verify that (VU)k = (−1)k ( cos 2kθ sin 2kθ − sin 2kθ cos 2kθ ) Grover search Recall that our initial state is |ψ〉 = sin θ|m〉+ cos θ|φ〉 How large should k be before (VU)k |ψ〉 is close to |m〉? We start an angle θ from the |φ〉 axis and rotate toward |m〉 by an angle 2θ per iteration ⇒ To rotate by pi/2, we need θ + 2kθ = pi/2 k ≈ pi 4 θ−1 ≈ pi 4 √ N Grover search It is easy to calculate that |〈m|(VU)k |ψ〉|2 = sin2((2k + 1)θ) This is the probability that, after k steps of the algorithm, a measurement reveals the marked state We are solving a completely unstructured search problem with N possible solutions, yet we can find a unique solution in only O( √ N) queries! While this is only a polynomial separation, it is very generic, and it is surprising that we can obtain a speedup for a search in which we have so little information to go on Grover search It can also be shown that this quantum algorithm is optimal Any quantum algorithm needs at least Ω( √ N) queries to find a marked item (or even to decide if some item is marked) Multiple solutions Assume that there are t marked items ⇒ There is a two-dimensional invariant subspace spanned by span{|µ〉, |ψ〉} where |µ〉 = 1√ t ∑ x marked |x〉 is the uniform superposition of all solutions The Gram-Schmidt process yields the ONB {|µ〉, |φ〉} where |φ〉 = 1√ N − t ∑ x unmarked |x〉 is the uniform superposition of all non-solutions Invariant subspace Now in the basis {|µ〉, |φ〉}, we have |ψ〉 = sin θ|µ〉+ cos θ|φ〉 where sin θ = 〈µ|ψ〉 = √ t N VU = − ( cos 2θ sin 2θ − sin 2θ cos 2θ ) Overshooting The success probability is given by sin((2k + 1)θ) where sin θ = √ t N ⇒ We need to apply VU k ≈ pi 4 √ N t times Due to the oscillatory behaviour of the success probability it is important not to overshoot, i.e., to choose a number of iterations that it too large, so that the probability starts decreasing Quantum counting The eigenvalues of −VU = ( cos 2θ sin 2θ − sin 2θ cos 2θ ) are e i2θ and e−i2θ The initial state |ψ〉 is a superposition of the two eigenvectors corresponding to the above two eigenvalues ⇒ Using phase estimation, we can obtain an estimate θ̃ such that |θ − θ̃| ≤ by invoking the controlled version of −VU O(1/) times Quantum counting Using the estimate θ̃, we obtain an estimate t̃ satifying |t − t̃| ≤ (2 √ tN + ) Quantum counting We use the following two inequalities: | sin θ + sin θ̃| ≤ 2 sin θ + |θ − θ̃| ≤ 2 √ t N + | sin θ − sin θ̃| ≤ |θ − θ̃| ≤ We have ∣∣∣∣ tN − t̃N ∣∣∣∣ = | sin2 θ − sin2 θ̃| = | sin θ + sin θ̃| | sin θ − sin θ̃| ≤ ( 2 √ t N + ) Amplitude amplification Assume that there is a classical (randomized) algorithm that produces a solution to some problem with probability p Assume that we can recognized if the output produced by the algorithm is a valid solution or not ⇒ We repeat the algorithm until we obtain a solution The expected number of times we have to repeat is O(1/p) (geometric random variable) Quantum amplitude amplification makes it possible to reduce the complexity to O(1/ √ p) Part VI Quantum walk Randomized algorithms Randomness is an important tool in computer science Black-box problems I Huge speedups are possible (Deutsch-Jozsa: 2Ω(n) vs. O(1)) I Polynomial speedup for some total functions (game trees: Ω(n) vs. O(n0.754)) Natural problems I Majority view is that derandomization should be possible (P=BPP) I Randomness may give polynomial speedups (Schöning algorithm for k-SAT) I Can be useful for algorithm design Random walk Graph G = (V ,E ) u u u u u Q Q Q Q Two kinds of walks: I Discrete time I Continuous time Random walk algorithms Undirected s–t connectivity in log space I Problem: given an undirected graph G = (V ,E ) and s, t ∈ V , is there a path from s to t? I A random walk from s eventually reaches t iff there is a path I Taking a random walk only requires log space I Can be derandomized (Reingold 2004), but this is nontrivial Markov chain Monte Carlo I Problem: sample from some probability distribution (uniform distribution over some set of combinatorial objects, thermal equilibrium state of a physical system, etc.) I Create a Markov chain whose stationary distribution is the desired one I Run the chain until it converges Continuous-time quantum walk Graph G r r r r r Q QQ 1 2 3 4 5 A = 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 adjacency matrix L = −2 1 1 0 0 1 −3 0 1 1 1 0 −2 1 0 0 1 1 −3 1 0 1 0 1 −2 Laplacian Random walk on G I State: probability pv (t) of being at vertex v at time t I Dynamics: ddt~p(t) = −L~p(t) Quantum walk on G I State: amplitude qv (t) to be at vertex v at time t (i.e., |ψ(t)〉 = ∑v∈V qv (t)|v〉) I Dynamics: i ddt~q(t) = −L~q(t) Random vs. quantum walk on the line r r r r r r r r rff - -4 -3 -2 -1 0 1 2 3 4 Classical: -60 -40 -20 0 20 40 60 Quantum: -60 -40 -20 0 20 40 60 Random vs. quantum walk on the hypercube V = {0, 1}n E = {(x , y) ∈ V × V : x and y differ in exactly one bit} n = 3: s s s s s s s s 000 100 010 001 110 011 101 111 Classical random walk: reaching 11 . . . 1 from 00 . . . 0 is exponentially unlikely Quantum walk: with A = ∑n j=1 Xj , e−iAt = n∏ j=1 e−iXj t = n⊗ j=1 ( cos t −i sin t −i sin t cos t ) Glued trees problem in out Black-box description of a graph I Vertices have arbitrary labels I Label of ‘in’ vertex is known I Given a vertex label, black box returns labels of its neighbors I Restricts algorithms to explore the graph locally Glued trees problem: Classical query complexity in out Let n denote the height of one of the binary trees Classical random walk from ‘in’: probability of reaching ‘out’ is 2−Ω(n) at all times In fact, the classical query complexity is 2Ω(n) Glued trees problem: Exponential speedup in out ↓ col 0 col 1 col 2 col 3 col 4 col 5 col 6 col 7 col 8 col 9 √ 2 2 √ 2 √ 2 √ 2 √ 2 √ 2 √ 2 √ 2 Column subspace |col j〉 := 1√ Nj ∑ v∈column j |v〉 Nj := { 2j if j ∈ [0, n] 22n+1−j if j ∈ [n + 1, 2n + 1] Reduced adjacency matrix 〈col j |A|col j + 1〉 = √ 2 if j ∈ [0, n − 1]√ 2 if j ∈ [n + 1, 2n] 2 if j = n Discrete-time quantum walk: Need for a coin Quantum analog of discrete-time random walk? Unitary matrix U ∈ C|V |×|V | with Uvw 6= 0 iff (v ,w) ∈ E Consider the line:r r r r r r r r rff - -4 -3 -2 -1 0 1 2 3 4 Define walk by |x〉 7→ 1√ 2 (|x − 1〉+ |x + 1〉)? But then |x + 2〉 7→ 1√ 2 (|x + 1〉+ |x + 3〉), so this is not unitary! In general, we must enlarge the state space. Discrete-time quantum walk on a line r r r r r r r r rff - -4 -3 -2 -1 0 1 2 3 4 Add a “coin”: state space span{|x〉 ⊗ |←〉, |x〉 ⊗ |→〉 : x ∈ Z} Coin flip: C := I ⊗ H Shift: S |x〉 ⊗ |←〉 = |x − 1〉 ⊗ |←〉 S |x〉 ⊗ |→〉 = |x + 1〉 ⊗ |→〉 Walk step: SC -60 -40 -20 0 20 40 60 The Szegedy walk State space: span{|v〉 ⊗ |w〉, |w〉 ⊗ |v〉 : (v ,w) ∈ E} Let W be a stochastic matrix (a discrete-time random walk) Define |ψv 〉 := |v〉 ⊗ ∑ w∈V √ Wwv |w〉 (note 〈ψv |ψw 〉 = δv ,w ) R := 2 ∑ v∈V |ψv 〉〈ψv | − I S(|v〉 ⊗ |w〉) := |w〉 ⊗ |v〉 Then a step of the walk is the unitary operator U := SR Spectrum of the walk Let T := ∑ v∈V |ψv 〉〈v |, so R = 2TT † − I . Theorem (Szegedy) Let W be a stochastic matrix. Suppose the matrix∑ v ,w √ WvwWwv |w〉〈v | has an eigenvector |λ〉 with eigenvalue λ. Then I − e±i arccosλS√ 2(1− λ2) T |λ〉 are eigenvectors of U = SR with eigenvalues e±i arccosλ. Proof of Szegedy’s spectral theorem Proof sketch. Straightforward calculations give TT † = ∑ v∈V |ψv 〉〈ψv | T †T = I T †ST = ∑ v ,w∈V √ WvwWwv |w〉〈v | = ∑ λ |λ〉〈λ| which can be used to show U(T |λ〉) = ST |λ〉 U(ST |λ〉) = 2λST |λ〉 − T |λ〉. Diagonalizing within the subspace span{T |λ〉,ST |λ〉} gives the desired result. Exercise. Fill in the details Random walk search algorithm Given G = (V ,E ), let M ⊂ V be a set of marked vertices Start at a random unmarked vertex Walk until we reach a marked vertex: W ′vw := 1 w ∈ M and v = w 0 w ∈ M and v 6= w Wvw w /∈ M. = ( WM 0 V I ) (WM : delete marked rows and columns of W ) Question. How long does it take to reach a marked vertex? Classical hitting time Take t steps of the walk: (W ′)t = ( W tM 0 V (I + WM + · · ·+ W t−1M ) I ) = ( W tM 0 V I−W tM I−WM I ) Convergence time depends on how close ‖WM‖ is to 1, which depends on the spectrum of W Lemma Let W = W T be a symmetric Markov chain. Let the second largest eigenvalue of W be 1− δ, and let = |M|/|V | (the fraction of marked items). Then the probability of reaching a marked vertex is Ω(1) after t = O(1/δ) steps of the walk. Quantum walk search algorithm Start from the state 1√ N−|M| ∑ v 6∈M |ψv 〉 Consider the walk U corresponding to W ′:∑ v ,w∈V √ W ′v ,wW ′w ,v |w〉〈v | = ( WM 0 0 I ) Eigenvalues of U are e±i arccosλ where the λ are eigenvalues of WM Perform phase estimation on U with precision O( √ δ) I no marked items =⇒ estimated phase is 0 I fraction of marked items =⇒ nonzero phase with probability Ω(1) Further refinements give algorithms for finding a marked item Grover’s algorithm revisited Problem Given a black box f : X → {0, 1}, is there an x with f (x) = 1? Markov chain on N = |X | vertices: W := 1 N 1 · · · 1... . . . ... 1 · · · 1 = |ψ〉〈ψ|, |ψ〉 := 1√ N ∑ x∈X |x〉 Eigenvalues of W are 0, 1 =⇒ δ = 1 Hard case: one marked vertex, = 1/N Hitting times I Classical: O(1/δ) = O(N) I Quantum: O(1/ √ δ) = O( √ N) Element distinctness Problem Given a black box f : X → Y , are there distinct x , x ′ with f (x) = f (x ′)? Let N = |X |; classical query complexity is Ω(N) Consider a quantum walk on the Hamming graph H(N,M) I Vertices: {(x1, . . . , xM) : xi ∈ X} I Store the values (f (x1), . . . , f (xM)) at vertex (x1, . . . , xM) I Edges between vertices that differ in exactly one coordinate Element distinctness: Analysis Spectral gap: δ = O(1/M) Fraction of marked vertices: ≥ (N−2M−2)/(NM) = Θ(M2/N2) Quantum hitting time: O(1/ √ δ) = O(N/ √ M) Quantum query complexity: I M queries to prepare the initial state I 2 queries for each step of the walk (compute f , uncompute f ) I Overall: M + O(N/ √ M) Choose M = N2/3: query complexity is O(N2/3) (optimal!) Quantum walk algorithms Quantum walk search algorithms I Spatial search I Finding a triangle in a graph I Checking matrix multiplication I Testing if a black-box group is abelian Evaluating Boolean formulas Exponential speedup for a natural problem?
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- Canadian Summer School on Quantum Information (CSSQI) (10th : 2010) /
- Quantum Algorithms
Open Collections
Canadian Summer School on Quantum Information (CSSQI) (10th : 2010)
Quantum Algorithms Wocjan, Pawel; Childs, Andrew 2010-07-18
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Quantum Algorithms |
Creator |
Wocjan, Pawel Childs, Andrew |
Contributor |
Summer School on Quantum Information (10th : 2010 : Vancouver, B.C.) University of British Columbia. Department of Physics and Astronomy Pacific Institute for the Mathematical Sciences |
Date Issued | 2010-07-18 |
Description | Quantum information offers the possibility to solve certain problems dramatically faster than is possible with classical computers. In these lectures, we will give an introduction to quantum algorithms. We will begin with an overview of the quantum circuit model and some elementary examples of quantum speedup. Next, we will introduce the quantum Fourier transform and show how it can be used to estimate the eigenvalues of a unitary operator. Using phase estimation, we will describe Shor's algorithm for factoring integers. We will also describe Grover's search algorithm, and will conclude with a discussion of recent quantum algorithms based on quantum analogs of random walks. |
Type |
Moving Image |
Language | eng |
Date Available | 2016-11-22 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0040932 |
URI | http://hdl.handle.net/2429/29926 |
Affiliation |
Non UBC |
Peer Review Status | Unreviewed |
Scholarly Level | Other |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 59370-SS Algorithms 1.mp4 [ 191.1MB ]
- 59370-SS Algorithms 2.mp4 [ 214.39MB ]
- 59370-SS Algorithms 5.mp4 [ 207.21MB ]
- 59370-SS Algorithms 6.mp4 [ 233.33MB ]
- 59370-SS Algorithms 3.mp4 [ 214.95MB ]
- 59370-SS Algorithms 4.mp4 [ 206.82MB ]
- 59370-quantum_algorithms.pdf [ 1.47MB ]
- Metadata
- JSON: 59370-1.0040932.json
- JSON-LD: 59370-1.0040932-ld.json
- RDF/XML (Pretty): 59370-1.0040932-rdf.xml
- RDF/JSON: 59370-1.0040932-rdf.json
- Turtle: 59370-1.0040932-turtle.txt
- N-Triples: 59370-1.0040932-rdf-ntriples.txt
- Original Record: 59370-1.0040932-source.json
- Full Text
- 59370-1.0040932-fulltext.txt
- Citation
- 59370-1.0040932.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.59370.1-0040932/manifest