CS代写 MULT90063 Introduction to Quantum Computing

MULT90063 Introduction to Quantum Computing
Reversible computation, One qubit adder, the Deutsch-Josza algorithm
Two basic quantum algorithms: Bernstein-Vazirani and Simon’s Algorithms
Logical statements, Reversible logic, Adder, Deutsch-Josza algorithm

MULT90063 Introduction to Quantum Computing
Simple Quantum Algorithms: Simon
and Bernstein-Vazirani

MULT90063 Introduction to Quantum Computing
Bernstein-Vazirani Problem
Given a Boolean function, f:
f(x)=x·s mod2 find s.
Recall, bitwise product:
x · s = X xisi i

MULT90063 Introduction to Quantum Computing
Example: Linear Boolean function
f(x)=x·5 mod2 Remember, in binary, 5 = 101.
Given a black-box which calculates this function, find s=5.

MULT90063 Introduction to Quantum Computing
Solving BV Problem Classically
f(x)=x·5 mod2
Input one single digit “1” at a time.
Can determine s using n queries.

MULT90063 Introduction to Quantum Computing
Bernstein-Vazirani Problem
Given a Boolean function, f:
f(x)=x·s mod2 find s.
x · s = X xisi i
• Classical algorithm needs n queries
• Quantum algorithm needs just 1 query.
Recall: bitwise product:

MULT90063 Introduction to Quantum Computing
Bernstein-Vazirani algorithm
The circuit is the same as for the Deutsch-Josza algorithm:
The guarantees on f are different:
f(x)=x·s mod2
Recall: Deutsch-Josza algorithm required the function to either be constant or balanced.

MULT90063 Introduction to Quantum Computing
Implementing a Linear Boolean Function
For s = 5 = 1012 the function is evaluated using this circuit:
The bits of s determine the location of the CNOTs.
Every linear, Boolean function has a circuit of the same form.
|yx·s mod2i

MULT90063 Introduction to Quantum Computing
Full BV circuit for s=5
|0i |0i |0i
Uf – evaluates the function
Extra H here makes no difference to what’s measured

MULT90063 Introduction to Quantum Computing
Many gates square to identity
Compilation tips: Most physicists looking at quantum circuit diagrams aren’t multiplying matrices in their head. They’re identifying common patterns.
All of these combinations square to the identity (do nothing). You can check these on the QUI.

MULT90063 Introduction to Quantum Computing
BV circuit for s=5
|0i |0i |0i
Uf – evaluates the function

MULT90063 Introduction to Quantum Computing
Circuit identity: Inverted CNOT
Exercise: You can verify this by writing out the matrices and multiplying!

MULT90063 Introduction to Quantum Computing
Simple explanation of BV
Hadamard gates “conjugating” CNOT:
|0i |0i |0i
|0i |0i |0i |1i
Insert H2=I here
We can determine s with just one query, by making use of quantum superposition.

MULT90063 Introduction to Quantum Computing
Simplifying circuit
|0i |0i |0i |1i
Control is a 1, so these operations always happen
If in doubt, check using QUI

MULT90063 Introduction to Quantum Computing
BV Solution
This circuit will measure:
which is correct (s=5) A similar reduction would work for any s, but let us prove that formally.

MULT90063 Introduction to Quantum Computing
BV algorithm explained
State after the initial Hadamard gates:
1 X |0i|1i |i=pNx|xi⌦ p2
Sum of all computational basis states (again)

MULT90063 Introduction to Quantum Computing
Recall: General Function Phase Kickback
Using phase kickback, after the function has been applied:
| i=pN (1)
|0i|1i |xi⌦ p2
If the function evaluates to “1” then the target qubit is flipped, and we pick up a phase. Otherwise, there is no phase applied. This is a simple way to write that.

MULT90063 Introduction to Quantum Computing
Recall: Hadamard applied to a general state
Amplitude az -> how many times does the binary reXpresentation of z and x have 1’s in the same location?
H |xi=p az|zi
H⌦n |xi = p az |zi x0z0 +x1z1 +x2z2 +…+xnzn H N z=0
Shorthand for the bitwise dot product is: When 1’s in the same location, we get a sign change -> (1)x·z
Hadamards applied to a general state (n qubits, N = 2n):
H⌦n |xi = pN (1)x·z |zi

MULT90063 Introduction to Quantum Computing
BV algorithm explained
Considering the upper
register only: X
(1)x·s|xi N1
= N1 X X (1)x·(sz) |zi = N1 X X (1)x·(sz) |zi
x=0 z=0 z=0 x=0
x z = x0 + z0 mod 2, x1 + z1 mod 2, . . .
(1)x·s pN (1)x·z |zi H’s applied to basis state z=0
N1 N1 N1 N1
|xi = pN (1) |zi z=0

MULT90063 Introduction to Quantum Computing
BV algorithm explained
Simplifying the sum: N1 N1
| i = 1 X X (1)x·(sz)
N 1 8< N , b = 0 X(1)x·b =: x=0 0, b6=0 This sum (over x) is zero unless That is, z and s are bitwise identical, ie. N z=0 x=0 1 N1 = N (1)0 |si z=0 We will therefore measure s with certainty – the aim of the algorithm. MULT90063 Introduction to Quantum Computing Bernstein-Vazirani Algorithm Given a Boolean function, f: f(x)=x·s mod2 find s. x · s = X xisi i • Classical algorithm needs n queries • Quantum algorithm needs just 1 query. MULT90063 Introduction to Quantum Computing Third Quantum Algorithm: Simon’s algorithm MULT90063 Introduction to Quantum Computing Simon’s Problem Given a 2-to-1 function, f, such that f(x) = f(x a) Unlike the previous two examples, here the range of f(x) is Z, integers. Simon’s algorithm is an example of a “Hidden (Abelian) subgroup problem” (HSP) and was the inspiration for Shor’s factoring algorithm. MULT90063 Introduction to Quantum Computing Example of a hidden a f(001) = f(111) We would like to find the hidden ‘a’ s.t. f(x) = f(x a) In this case: MULT90063 Introduction to Quantum Computing Solving Simon’s problem classically Just try different inputs until you see a collision: f(000) = 0 f(011) = 3 f(111) = 1 f(010) = 2 f(001) = 1 Actually this is equivalent to the famous “birthday” problem, and takes fewer queries than you might expect. Probabilistically, if there are N different inputs we need p Evaluations of the function before we find a collision. Simon’s algorithm does the same with O(n) queries. MULT90063 Introduction to Quantum Computing Simon’s algorithm circuit Randomly measure a result of the function. Collapse to a superposition of inputs which give that value. Send these through Hadamard gates, and measure: |xi |xi |0i |0f(x)i Measure to find a f(x0),f(x0 a) MULT90063 Introduction to Quantum Computing Simon’s algorithm After the initial Hadamard gates: | i=pN x |xi|0i MULT90063 Introduction to Quantum Computing Simon’s algorithm After evaluation of the function: Uf|xi|0i |xi|f(x)i |xi |xi |0i |0f(x)i MULT90063 Introduction to Quantum Computing Simon’s algorithm It’s easiest to consider that the bottom register is measured first. Before measurement the state is: X | i=pN x |xi|f(x)i Some value, f(x0) will be measured at random, and the top register collapses |x0i+|x0 ai |i= p2 MULT90063 Introduction to Quantum Computing Example: Measuring function | i=pN x |xi|f(x)i = p8(|0i|0i+|1i|1i+|2i|2i+|3i|3i+|4i|2i+|5i|3i+|6i|0i+|7i|1i) If we measure the second register, and measure obtain “3”, the state collapses to only those states compatible with this measurement: Firstregister: 0 |3i |3i + |5i |3i |i= p2 |x0i+|x0 ai | i= p2 MULT90063 Introduction to Quantum Computing Simon’s algorithm We now apply Hadamard to the top register: ⌦n|x0i+|x0 ai | i=H p2 MULT90063 Introduction to Quantum Computing Hadamard applied to a general state Amplitude ay -> how many times does the binary reXpresentation of y and x have 1’s in the same location?
H |xi=p az|zi
ay |yi x0y0 +x1y1 +x2y2 +…+xnyn n
x · y = When 1’s in the same location, we get a sign change -> (1)x·y
Shorthand for the bitwise dot product is:
Hadamards applied to a general state (n qubits, N = 2n):
H⌦n |xi = pN (1)x·y |yi
(changed dummy index to y)

MULT90063 Introduction to Quantum Computing
Simon’s algorithm
| i=p1 X(1)x0·y|yi 2n1 a·y=0
Each time we measure, we randomly measure a “y” which is orthogonal to “a”: Obtain n random y’s this way and perform Gauss/Jordan elimination to obtain “a”
a·y=0 mod2

MULT90063 Introduction to Quantum Computing
Example of Simon’s algorithm
We would like to find the hidden ‘a’ s.t.
f(x) = f(x a) In this case, a=1102=6

MULT90063 Introduction to Quantum Computing
Running the circuit
a·y=0 mod2 We run the circuit, and at random, obtain measure the results:
We want to find, a=1102=6

MULT90063 Introduction to Quantum Computing
In matrix form
Weknowthat a·y=0 mod2
We have three values of ‘y’ for which this is true, so we can write a
system of linear equations for the bits of ‘a’:
24 0 0 1 0 35 1100 211103
Measured values
0010 ⇠411005
Solving for a Solution is degenerate. a=(0,0,0) or a1=a2=1 ie. a=(1,1,0)

MULT90063 Introduction to Quantum Computing
Simon’s Algorithm
Given a 2-to-1 function, f, such that
f(x) = f(x a)
Classical algorithm: O(pN)
Queries to the oracle (probabilistically)
Quantum algorithm:
O(n) Queries to the oracle

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts