程序代写 MULT90063 Introduction to Quantum Computing

MULT90063 Introduction to Quantum Computing
Quantum search – introduction to Grover’s algorithm for amplitude amplification, geometric interpretation
Lecture 10
Optimality, Succeeding with Certainty, Quantum Counting

Copyright By PowCoder代写 加微信 powcoder

Grover’s algorithm

MULT90063 Introduction to Quantum Computing
Grover’s Algorithm Lecture 9

MULT90063 Introduction to Quantum Computing
Introduction to Grover’s algorithm
• This lecture: Grover’s search algorithm – Grover’s algorithm
– Worked Example
– Geometric interpretation
References:
Reiffel, Chapter 9.1-9.2
Kaye, Chapter 8.1-8.2
Nielsen and Chuang, Chapter 6.1-6.2

MULT90063 Introduction to Quantum Computing
Reminder: Outer Product
Fortwoquantumstates | i= ab , |i= dc We can define an outer product between them:
|ih|=ab⌦⇥c⇤ d⇤⇤ =ac⇤ ad⇤
26 0 0 0 0 37 64 0 0 1 0 75
For number basis states, this specifies a matrix with a single “1” in the location 1,2. In general:
|rowi hcolumn|

MULT90063 Introduction to Quantum Computing
Unordered Search
Grover’s algorithm performs a similar* problem to this: You are given a telephone book
And a phone number: 23675
Your task:
Find the name which goes with that number…
Part of Norfolk Island’s telephone book, with people listed by nickname (Photo: Wikicommons)
* Not all that similar, better examples later….

MULT90063 Introduction to Quantum Computing
Quantum search – Grover’s problem
Given an black box (oracle), Uf, which computes the function: f:{0,1}n à{0,1}
Find an x s.t. f(x) = 1

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 Two basic steps in Grover’s algorithm 1X Quantum database: |i = pN i |ii (i.e. all integers 0 to N-1) |0i |0i |0i |0i The “oracle” Identifies a particular marked state, m I 2 |i h| “Inversion about the mean” Repeat these two operations O(√N) times Inversion (I-2|0><0|) MULT90063 Introduction to Quantum Computing The Oracle The task of recognizing the correct solution goes to the “oracle”. Designed to flip the last bit if the input, i, is a solution MULT90063 Introduction to Quantum Computing Phase kickback for Boolean function |yi |y f(x)i Binary function, or “oracle” After the function has been applied: | i = pN (1)f (i) |ii ⌦ Target qubit remains the same If the oracle function evaluates to “1” then the target qubit is flipped, and we pick up a phase (associated with the control qubit state). Otherwise, there is no phase applied. This is a simple way to write that. | 0 i | 1 i p2 MULT90063 Introduction to Quantum Computing Example: Oracle recognizing the state “2 = |10>”
|0i |1i p2
Phase kickback
|00i ! |00i |01i ! |01i |10i ! |10i |11i ! |11i
The effect on each of the 4 states in the 2-qubit control register, x:
26 1 0 0 0 37
640 1 0 075=I2|10ih10|
0 0 1 0 0001

MULT90063 Introduction to Quantum Computing
The marked state
Initially in Grover’s algorithm, we will be searching for a single (integer) solution, m. In that case the effect of the oracle on the control register is:
I 2 |mi hm| 26 1 0 0 0 37
64 0 1 0 0 75 0 0 1 0
Here, as in future slides, we are only writing out the control qubits (in this case 2 qubits only).
As a matrix:
(in decimal ket notation)
-1inthemth position

MULT90063 Introduction to Quantum Computing
Example: Oracle recognizing the state “2 = |10>”
|0i |1i p2
In practice we can implement
the oracle without the check
qubit using a controlled-Z gate
(ex. Show the circuit right marks the state |10>, i.e. |m=2>).
Phase kickback
|00i ! |00i |01i ! |01i |10i ! |10i |11i ! |11i

MULT90063 Introduction to Quantum Computing
Two steps to Grover’s algorithm
Set up “data base”
|0i |0i |0i |0i
I 2|mihm| The oracle
I 2|ih| “Inversion about the mean”
Repeat these two operations O(√N) times
1X One iteration of Grover where |i = pN i |ii
Inversion (I-2|0><0|) MULT90063 Introduction to Quantum Computing Unpicking the details: “Inversion” operation The “Inversion” part is just applying a phase to the zero state: 2 1 0 0 0 ... 3 6 0 1 0 0 ...7 |0i = B C 0 0 . . . 0 0 0 . . . 0 |0i h0| = B C ⌦ (1 0|0.i.h.00|)=B @.. A @. C ⌦ (1 0 . . . 0) = I = B A @ A 001...0 C @.A @ . A. . @ . A 1 0 0 0 ... 1 0 0 0 ... 100...0 10...0 6767 B01C00B... C 0100... 010...0 00...0 6767 C1 20B..I.2|0iCh0|= 0 001...0 . 0 1 0 ... 6767 I2|0ih0|= B 0 0 4 0 .0 0 1 ...5. 4 0 0 0 1 ...5 ... ... ... ... ... ... ... ... ... ... I2|0ih0|=6 0 0 1 0 ... 7 6 7 4 0 0 0 1 ...5 ... ... ... ... ... |ih|=ab⌦⇥c⇤ d⇤⇤ How?Recallouterproductetc: | ih|= a ⌦⇥ c⇤ d⇤ ⇤= ac⇤ ad⇤ b bc⇤bd⇤ 010101 1 01=101100...0 ad⇤ bc⇤ bd⇤ 10...0 10...0 BCBCBC B0C 0 010...0 B0C BCCBCBC Inversion (I-2|0><0|) MULT90063 Introduction to Quantum Computing Inversion about the mean |i = pN i |ii Set up “data base” |0i |0i |0i |0i I 2 |i h| “Inversion about the mean”...let’s see how that works. Inversion (I-2|0><0|) MULT90063 Introduction to Quantum Computing Apply inversion about the mean to general state Applying Hadamards both sides: I 2H⌦n |0i h0| H⌦n = I 2 |i h| 1X |i = p |ii X22222Ni3 1... |i=ai|ii i | i=Xai|ii!| 0i=(I2|ih|)Xai|ii General state superposition 6NNNN7 Equal 6 N2 1 N2 N2 N2 . . . 7 0 =62 2 12 2 ...7 |i= a|ii! ... ... ... ... ... i64N N N N 75 i N2 N2 N2 1N2 ... X1X1XXX ai |ii 2pN |ki pN hj| ai |ii Xaj1A ajA i k j Average = (ai 2A) |ii amplitude i instate| i MULT90063 Introduction to Quantum Computing Inversion about the mean Consider a general state. The resulting amplitude from the “Inversion about the mean” step is: X ai |ii ! X(ai 2A) |ii ii Original amplitude Average amplitude In practice on the QUI... MULT90063 Introduction to Quantum Computing Inversion about the mean Amplitudes of the state, before and after: ai A ai A ai A 2Aai When the state undergoes this transformation: X ai |ii ! X(2A ai) |ii ii MULT90063 Introduction to Quantum Computing Effect of inversion about the mean The marked state Increased amplitude of the marked state The mean State Inversion about the mean The mean State MULT90063 Introduction to Quantum Computing Interactive Example https://codepen.io/samtonetto/full/BVOGmW MULT90063 Introduction to Quantum Computing Worked example: finding 6 “Inversion about the mean” “Inversion about the mean” I 2|ih| I 2|ih| |0i |0i |0i I 2 |mi hm| The oracle I 2 |mi hm| The oracle Oracle = 6 Oracle = 6 MULT90063 Introduction to Quantum Computing Worked example: finding 6 |0i |0i |0i Oracle = 6 Oracle = 6 MULT90063 Introduction to Quantum Computing Worked example: finding 6 |0i |0i |0i Oracle = 6 Oracle = 6 MULT90063 Introduction to Quantum Computing Effect of the Oracle Apply the oracle The marked state MULT90063 Introduction to Quantum Computing Worked example: finding 6 |0i |0i |0i The mean(?) Phase of state 6 has changed to be negative Oracle = 6 Oracle = 6 MULT90063 Introduction to Quantum Computing Effect of inversion about the mean The marked state Increased amplitude of the marked state The mean State Inversion about the mean The mean State MULT90063 Introduction to Quantum Computing Worked example: finding 6 |0i |0i |0i After inversion about the mean: Oracle = 6 Oracle = 6 MULT90063 Introduction to Quantum Computing Effect of the Oracle Apply the oracle The marked state MULT90063 Introduction to Quantum Computing Worked example: finding 6 |0i |0i |0i After the second oracle: Oracle = 6 Oracle = 6 MULT90063 Introduction to Quantum Computing Effect of inversion about the mean The mean State Inversion about the mean The mean State MULT90063 Introduction to Quantum Computing Worked example: finding 6 |0i |0i |0i After the second oracle: Oracle = 6 Oracle = 6 MULT90063 Introduction to Quantum Computing Grover’s algorithm |0i |0i |0i 95% Success! Finally, we measure the marked state after 2 applications of the oracle, and find the marked state, 6 with 95% probability Oracle = 6 Oracle = 6 MULT90063 Introduction to Quantum Computing Geometric interpretation of Grover’s algorithm |0i |0i |0i A very useful basis: |bi = p 1 X |ii Solution! Non-solutions... N 1 i2/solutions We only need to consider the amplitude of these two states in Grover’s algorithm. Every operation is also real, so we can plot on a circle. MULT90063 Introduction to Quantum Computing Geometric Interpretation | i=↵|ai+|bi 1 Every state in Grover’s algorithm can be expressed as a superposition of these vectors |bi Non-solutions MULT90063 Introduction to Quantum Computing Equal superposition |0i |0i |0i Equal superposition state: |bi=p1 X |ii N 1 i/solutions 1X |i=pN i |ii = pN |ai+ pN |bi MULT90063 Introduction to Quantum Computing Equal Superposition Consider the equal superposition: 1 pN 1 |i= pN |ai+ pN |bi |ai solution Non-solutions 1 sin ✓ = pN MULT90063 Introduction to Quantum Computing Effect of the Oracle |0i |0i |0i Apply the oracle The marked state MULT90063 Introduction to Quantum Computing Geometric Effect of Oracle |ai solution Non-solutions MULT90063 Introduction to Quantum Computing Geometric Effect of Oracle ↵ |ai + |bi ! ↵ |ai + |bi |ai solution |bi Non-solutions MULT90063 Introduction to Quantum Computing Effect of inversion about the mean The mean State Inversion about the mean The mean State MULT90063 Introduction to Quantum Computing Inversion about the mean Similar to the oracle, inversion about the mean corresponds to a reflection. Now about equal superposition. |ai solution |bi Non-solutions MULT90063 Introduction to Quantum Computing Inversion about the mean Similar to the oracle, inversion about the mean corresponds to a reflection. Now about equal superposition. |ai solution |ih| i ✓ |bi Non-solutions MULT90063 Introduction to Quantum Computing Inversion about the mean |ai solution | i|ih| i |bi Non-solutions |ih| i ✓ MULT90063 Introduction to Quantum Computing Inversion about the mean | i(2| i2|ih| i) =(| i2|ih| i) |ai solution 2| i2|ih| i |bi Non-solutions Reflection about the mean reflects around the equal superposition state MULT90063 Introduction to Quantum Computing Geometric Effect of both Oracle and Inversion Combining both effects: |ai solution |bi Non-solutions MULT90063 Introduction to Quantum Computing Geometric Effect of both Oracle and Inversion Combining both effects: |ai solution |bi Non-solutions MULT90063 Introduction to Quantum Computing Geometric Effect of both Oracle and Inversion Combining both effects: |ai solution |bi Non-solutions MULT90063 Introduction to Quantum Computing Total effect of one Grover iteration Product of two reflections is a rotation. |ai solution |bi Non-solutions 1 sin ✓ = pN MULT90063 Introduction to Quantum Computing Many Grover iterations Product of two reflections is a rotation. |ai solution |bi Non-solutions 1 sin ✓ = pN MULT90063 Introduction to Quantum Computing How many iterations required? For small angles, 1 sin ✓ = pN After n iterations, we rotate to have only marked solutions: (2n + 1)✓ = ⇡2 n ⇡ ⇡4 p N The number of steps, n, required scales as O(√N), and not with N as it would classically. This is a “polynomial” rather than an “exponential” speedup. MULT90063 Introduction to Quantum Computing Multiple Solutions There can be more than one solution to a problem. Apply the oracle The M=2 marked states MULT90063 Introduction to Quantum Computing Geometric interpretation of Grover’s algorithm |0i |0i |0i A very useful basis: |ai = pM i2soXlutions |ii |bi=p 1 |ii N M i2/solutions We only need to consider the amplitude of these two states in Grover’s algorithm. Every operation is also real, so we can plot on a circle. Solutions! Non-solutions... MULT90063 Introduction to Quantum Computing Geometric Interpretation | i=↵|ai+|bi 1 Every state in Grover’s algorithm can be expressed as a superposition of these vectors |bi Non-solutions MULT90063 Introduction to Quantum Computing Equal superposition |0i |0i |0i Equal superposition state: 1X |i=pN i |ii |i=pN|ai+ pN |bi 1 |ai = pM i2solutions |bi=p 1 X |ii N M i2/solutions MULT90063 Introduction to Quantum Computing Equal Superposition Consider the equal superposition: pM pN M |i= pN |ai+ pN |bi |ai solutions |bi Non-solutions pM sin✓= pN MULT90063 Introduction to Quantum Computing Effect of the Oracle |0i |0i |0i Apply the oracle The marked state MULT90063 Introduction to Quantum Computing Geometric Effect of Oracle |ai solutions pM sin✓= pN Non-solutions MULT90063 Introduction to Quantum Computing Geometric Effect of both Oracle and Inversion Combining both effects: |ai solutions pM sin✓= pN |bi Non-solutions MULT90063 Introduction to Quantum Computing Geometric Effect of both Oracle and Inversion Combining both effects: |ai solutions pM sin✓= pN |bi Non-solutions MULT90063 Introduction to Quantum Computing Total effect of one Grover iteration Product of two reflections is a rotation. |ai solutions pM sin✓= pN |bi Non-solutions MULT90063 Introduction to Quantum Computing Many Grover iterations Product of two reflections is a rotation. |ai solutions |bi Non-solutions pM sin✓= pN MULT90063 Introduction to Quantum Computing How many iterations required? For small angles, pM sin✓= pN After n iterations, we rotate to have only marked solutions: (2n + 1)✓ = ⇡2p ⇡N Having multiple solutions is faster than searching for a single marked solution. MULT90063 Introduction to Quantum Computing Grover’s Algorithm • Unordered search, find one marked item among many • Classically, this requires N/2 uses of the oracle • Quantum mechanically, requires only O(√N). |0i |0i |0i |0i Lov Grover Inversion (I-2|0><0|) 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com