代写代考 MULT90063 Introduction to Quantum Computing

MULT90063 Introduction to Quantum Computing
Introduction to Grover’s algorithm for amplitude amplification, geometric interpretation
Lecture 10
Amplitude Amplification, Succeeding with Certainty, Quantum Counting

Copyright By PowCoder代写 加微信 powcoder

Grover’s algorithm

MULT90063 Introduction to Quantum Computing
Amplitude Amplification
MULT90063 Introduction to Quantum Computing Lecture 10

MULT90063 Introduction to Quantum Computing
Amplitude Amplification
• This lecture: Amplitude amplificaiton – Amplitude Amplification
– Succeeding with certainty
– Quantum Counting
References:
Rieffel, Chapter 9.1-9.2
Kaye, Chapter 8.1-8.2
Nielsen and Chuang, Chapter 6.1-6.2

MULT90063 Introduction to Quantum Computing
Grover’s Algorithm (1996)
• Unordered search, find one marked item among many
• Classically, this requires N/2 queries to the oracle
• Quantum mechanically, requires only O(√N) queries.
Simple problem = search for one integer marked by the oracle. High level structure:
|0i |0i |0i |0i
Lov Grover
Inversion (I-2|0><0|) MULT90063 Introduction to Quantum Computing Some notation |0i |0i |0i |0i SG =I2|mihm| S0 =I2|0ih0| Inversion (I-2|0><0|) MULT90063 Introduction to Quantum Computing Some notation |0i |0i |0i |0i n is the number of input qubits. N is the total dimension (N=2n). M is the number of solutions. Inversion (I-2|0><0|) MULT90063 Introduction to Quantum Computing Oracles for NP-problems The phone book isn’t a great example: Adding in all the names would take O(N) time. In general though, many problems (specifically those in the class NP) can have easily checkable solutions even if it is hard to solve the problem originally. Examples: • Factoring • Travelling Salesman with route less than distance d • Hamiltonian cycle Straightforward application of Grover’s algorithm provides a polynomial improvement over random guessing... and potentially a better (but still polynomial speedup) known as amplitude amplication. Part of Norfolk Island’s telephone book, with people listed by nickname (Photo: Wikicommons) MULT90063 Introduction to Quantum Computing Oracle for a hash function A hash function whose output is hard to predict based on the input. “Uncompute” the hash function – ensures the input register remains unchanged. The oracle recognises the ‘correct’ solution, but does not know in advance which input leads to the correct solution MULT90063 Introduction to Quantum Computing Amplitude amplification What happens if we replace the Hadamard gates with some other U? Perhaps, for example, we can create a U which gives the correct outcome with probability greater than 1/N. Can we get any advantage? Inversion about the mean Apply general U instead of H MULT90063 Introduction to Quantum Computing New inversion step Apply general U instead of H |i = U |0i Then we can break this up as: |i = g0 |gi + b0 |bi Good: In the subspace spanned by all solutions Bad: Not in the subspace spanned by all solutions MULT90063 Introduction to Quantum Computing Maths of the Geometric Interpretation US0U†| i=U(I2|0ih0|)U†| i =| i2h0|U†| iU|0i =| i2h |U|0i⇤U|0i where |i = U |0i |i = g0 |gi + b0 |bi Q |ig = US0U†SG |gi = US0U† |gi = | g i 2 g 0⇤ U | 0 i =|i2gg| i2gb| i = | g i 2 g 0g | g i 2 g 0b | b i g000g000b pp =(1(12t2)t|)|ii22 t(t1(1t)t|)|ii gg bb MULT90063 Introduction to Quantum Computing Maths of Amplitude Amplification S i m i l a r l y, Q | b i = ( 1 2 t ) | b i + 2 p t ( 1 t ) | g i Andfrompreviousslide: Q|gi=(12t)|gi2pt(1t)|bi Q recursive step: pp (12t) 2 t(1t) Compare to a rotation matrix: 2 t(1t) (12t) sin ✓ = pt = g0 R(2✓) =  cos2✓ sin 2✓ sin2✓ cos 2✓ MULT90063 Introduction to Quantum Computing Grover vs Amplitude Amplification Amplification Angle of rotation: p Angle of rotation: p M sin✓= t=g0 If you can construct a U with a higher probability of success than random guessing 1/N, then amplitude amplificaton can help. MULT90063 Introduction to Quantum Computing How to achieve 100% Success The optimal, 100% probability of measuring marked can be missed. Can we modify the algorithm to obtain 100% probability of success? |ai solutions |bi Non-solutions pM sin✓= pN MULT90063 Introduction to Quantum Computing Grover with 100% success Using amplitude amplification This step gives 100% probability of finding the marked state Idea: reduce the size of each step (intentionally) so that a whole number of steps is required. |bi Non-solutions |ai solutions MULT90063 Introduction to Quantum Computing Reducing the angle We want to reduce the angle of rotation in Grover’s algorithm/amplitude amplification so that we require a whole number of steps to achieve 100% probability of success. Trick: Introduce a new qubit. MULT90063 Introduction to Quantum Computing How much reduction? Previously: U |0i = g0 |gi + b0 |bi With new qubit: V ⌦U|0i=V |0i⌦(g0|gi+b0|bi) If we arrange so that: V |0i = s1 g0 |0i + g0 |1i e.g. Y-rotation by an angle: cos ↵ = g0 2g MULT90063 Introduction to Quantum Computing New rotation angle V ⌦U|0i=sV |0i⌦(g0|gi+b0|bi) ✓g0 ◆2 g0 V |0i = 1 g0 |0i + g0 |1i Our new “good” states, but now have a preceding “1” on the extra qubit we added V ⌦U|0i=g |1i| g i+... We can choose the initial amplitude to be anything value less than the original Chooseg0’s.t. i= ⇡ 1 isawholenumber 4✓0 2 MULT90063 Introduction to Quantum Computing 100% success The ith step gives 100% probability of finding the marked state Using amplitude amplification sin✓0 =g0 i=⇡1 |bi Non-solutions |ai solutions MULT90063 Introduction to Quantum Computing Example: Three qubit Grover |0i |0i |0i |0i |0i |0i |0i Extra qubit! Inversion (I-2|0><0|) Inversion (I-2|0><0|) MULT90063 Introduction to Quantum Computing Example: Searching for 5 (101) Added an extra qubit Extra rotations (e.g. around Y) to ensure that we obtain the answer with certainty Oracle selects for “1” on the Oracle selects for “101” in main register Inversion: similar to Grover’s algorithm MULT90063 Introduction to Quantum Computing Example: Searching for 5 (101) MULT90063 Introduction to Quantum Computing Example: Searching for 5 (101) MULT90063 Introduction to Quantum Computing Example: Searching for 5 (101) MULT90063 Introduction to Quantum Computing Example: Searching for 5 (101) MULT90063 Introduction to Quantum Computing Example: Searching for 5 (101) MULT90063 Introduction to Quantum Computing Example: Searching for 5 (101) MULT90063 Introduction to Quantum Computing Amplitude Amplification Given an black box (oracle), Uf, which computes the function f:{0,1}n à{0,1} Find an x s.t. f(x) = 1 • Unordered search, generalisation of Grover’s algorithm • Classically, this requires N/2 uses of the oracle • Quantum mechanically, requires only O(√N). |0i |0i |0i |0i Inversion (I-2|0><0|) MULT90063 Introduction to Quantum Computing Amplitude Amplification is optimal Proof in your textbooks. Grover’s algorithm is optimal in terms of the number of applications of the oracle. For many oracle problems the required number of uses of the oracle scales like: This means that for a broad range of problems the best speedup we can achieve using a quantum computer is not exponential, but polynomial (which can be quite significant). For problems with identifiable structure, we might hope for more speedup. More on this next week. MULT90063 Introduction to Quantum Computing Quantum Counting Will show you this algorithm now, but will leave some of the details until after next week’s lectures/lab. Given an black box (oracle), Uf, which computes the function f:{0,1}n à{0,1} How many x s.t. f(x) = 1? MULT90063 Introduction to Quantum Computing Equivalent question What angle rotation does Q make? Oracle, M solutions MULT90063 Introduction to Quantum Computing Plotting amplitude as function of step number After k steps: ✓k = (2k + 1)✓ pM sin✓= pN Number of solutions is reflected in the period/frequency Incorrect solutions would follow cosine, rather than sin Amplitude at step ‘k’ is: gk = sin(2k + 1)✓ MULT90063 Introduction to Quantum Computing Finding the period of a periodic function | i=pN x |xi⌦Q |0i Control register, x x steps of Grover’s algorithm Quantum Fourier Transform (next week) MULT90063 Introduction to Quantum Computing Finding the period of a periodic function | i=pN |xi⌦Q |0i |xi⌦(sin(2x+1)✓| gi+cos(2x+1)✓| bi) If we measure the second register MULT90063 Introduction to Quantum Computing After measurement of the second register | i = X sin(2x + 1)✓ |xi ⌦ | gi (not normalized) x Next step: Use Quantum Fourier Transformation to find the period MULT90063 Introduction to Quantum Computing After the Fourier transformation Dimension: N’ Dimension: N After Fourier transforming a periodic function, we get a good approximation to theta. If we measure value “j”: pM ✓ = N0 sin✓ = pN Which we can solve to obtain the number of solutions, M MULT90063 Introduction to Quantum Computing Phase Estimation and HSP Problems The Hadamard and Fourier transform part is a known as phase estimation, and extremely useful for period functions (and eigenvalues which are periodic). As we will see in the next lecture, this pattern is often repeated. MULT90063 Introduction to Quantum Computing Introduction to Grover’s algorithm for amplitude amplification, geometric interpretation Lecture 10 Amplitude Amplification, Succeeding with Certainty, Quantum Counting Grover’s algorithm 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com