代写代考 MULT90063 Introduction to Quantum Computing

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

MULT90063 Introduction to Quantum Computing
In this lecture we will discuss reversible logic and our first quantum algorithm – the Deutsch-Josza algorithm,
1. Reversible (classical) logic
2. The Deutsch-Josza algorithm
3. Aside: Universality in quantum computing
Along the way we will encounter common patterns often turn up in quantum algorithms, and will highlight them because they will help make sense of what of future quantum circuits.
Kaye, 1.5, 6.1-6.4
Nielsen and Chuang, 1.4, 3.1 Reiffel, 6, 7.3-7.5

MULT90063 Introduction to Quantum Computing
Universality in classical logic
A set of (classical) gates is said to be functionally complete (or “universal”) if every possible truth table (ie. Boolean function) can be expressed using members of the set.
For example, in classical logic: {AND, OR, NOT} is functionally complete.
AND OR NOT
Every logical circuit can be made from combinations of these gates. In fact, the NAND gate alone is universal. However, we cannot implement these gates directly in a quantum computer. AND/OR are not reversible.

MULT90063 Introduction to Quantum Computing
Irreversible Functions
We cannot implement AND or OR because these functions are irreversible.
Irreversible functions are not unitary.
We cannot determine the inputs from the output.

MULT90063 Introduction to Quantum Computing
Reversible Logic
Classically, if we would like to calculate some Boolean function, f, we can construct a circuit out of AND, OR and NOT gates. However, AND and OR gates are not reversible, and so can’t be implemented in a quantum computer.
But by use of reversible circuits and additional bits/qubits, we can express everything in terms of reversible gates (such as Toffoli):

MULT90063 Introduction to Quantum Computing
Reversible Logic and the Toffoli Gate
a AND b a XOR b (NOT a) OR (NOT b)
|ai |ai |bi |bi
|0i |a ^ bi
|1i |1i |ai |ai
|bi |a bi
|ai |ai |bi |bi
|1i |¬a _ ¬bi
The Toffoli gate is universal and reversible. In principle every classical boolean function can be written in terms of reversible gates (such as Toffoli) which can be implemented on a quantum computer.

MULT90063 Introduction to Quantum Computing
One Bit Adder
We can, for example, implement a one bit adder using only reversible gates:
|carryi |a + bi
We will now explain this circuit and in the lab we will extend this to a two bit adder.

MULT90063 Introduction to Quantum Computing
1+1 Quantum Style
Here is what happens when we add together numbers in superposition:
|0i + |1i p2
|1i |0i + |1i
Let’s do the walkthrough…

MULT90063 Introduction to Quantum Computing
One Qubit adder – example
| i= p2 ⌦|1i⌦|0i⌦|0i
|0i + |1i p2

MULT90063 Introduction to Quantum Computing
One Qubit adder – example
| i= p2 ⌦|1i⌦|0i⌦|0i
|0i + |1i p2
|0100i + |1101i |i= p2

MULT90063 Introduction to Quantum Computing
One Qubit adder – example
|0i + |1i p2
| i= p2 ⌦|1i⌦|0i⌦|0i
|0101i + |1100i |i= p2
flip flip |0100i + |1101i

MULT90063 Introduction to Quantum Computing
One Qubit adder – example
|0i + |1i p2
⌦|1i⌦|0i⌦|0i
|0101i + |1110i flip
|0i + |1i p2
|0101i + |1100i | i= noflip p2
|0100i + |1101i

MULT90063 Introduction to Quantum Computing
One Qubit adder – example
|0i + |1i p2
Or, considering the last two registers as a two-qubit register (binary notation):
|0101i + |1110i
|0101i + |1110i |i= p2
|0i |1i |1i + |1i |1i |2i | i= p2
Note: this is an entangled state.

MULT90063 Introduction to Quantum Computing
Implementing irreversible functions
We cannot compute irreversible functions directly (not unitary). One strategy which you often see to make an irreversible function reversible is simply to propagate the input to the output:
Propagate inputs to output
|xi |f (x)i
Calculated f(x)

MULT90063 Introduction to Quantum Computing
One Bit Adder
The adder is an example. Given a + b, we can’t uniquely determine a and b So we used this trick:
Propagated inputs to output
Evaluated function

MULT90063 Introduction to Quantum Computing
Implementing irreversible functions
One strategy which you often see to make an irreversible function reversible is simply to propagate the inputs:
|y f(x)i
Must deal with all possible inputs, not just 0.
Add (bit-by-bit modulo 2) input and calculated f(x)
You will see this pattern in several of the quantum algorithms we will study.

MULT90063 Introduction to Quantum Computing
Deutsch-Josza algorithm
• Given a boolean function, f, determine if:
f is constant (always gives the same result), or
f is balanced (gives equal numbers of 0s and 1s)
• Classical algorithm (worst case) needs 2n/2+1 queries
• Quantum algorithm needs just 1 query.

MULT90063 Introduction to Quantum Computing
Deutsch-Josza algorithm (2)
Let’s take the example with just one bit/qubit input. There are 4 choices of function:
|yi |y f(x)i
f1(0) = 0 f1(1) = 0 f2(0) = 1 f2(1) = 1 f3(0) = 0 f3(1) = 1 f4(0) = 1 f4(1) = 0

MULT90063 Introduction to Quantum Computing
Example of a constant function
f(0) = 1 f(1) = 1
The circuit always flips (ie. NOT) the second qubit, regardless of the input. This function is constant, since the output is always 1.

MULT90063 Introduction to Quantum Computing
Deutsch algorithm: constant function
The function, U, is implemented by the gates inside this box

MULT90063 Introduction to Quantum Computing
Deutsch algorithm: walkthrough
| i=|0i⌦|1i

MULT90063 Introduction to Quantum Computing
Deutsch algorithm: walkthrough
| i=H|0i⌦H|1i
|0i + |1i |0i |1i
= p2 ⌦ p2 = |+i ⌦ |i

MULT90063 Introduction to Quantum Computing
Deutsch algorithm: walkthrough
| i=|+i⌦X|i
|0i + |1i |0i |1i
= p2 ⌦X p2 |0i + |1i |1i |0i
= p2 ⌦ p2 = |+i ⌦ |i
Global phase is unmeasurable

MULT90063 Introduction to Quantum Computing
Deutsch algorithm: walkthrough
| i=H|+i⌦|i = |0i ⌦ |i

MULT90063 Introduction to Quantum Computing
Deutsch algorithm: walkthrough
|0i |1i | i=|0i⌦ p2
= |0i ⌦ |i
We will measure “0” with 100% probability. This indicates (with a single evaluation of the function) that the function is constant.

MULT90063 Introduction to Quantum Computing
Example of a balanced function
f(0) = 0 f(1) = 1
The circuit only flips (ie. NOT) the second qubit, if the input is a 1.
This function is balanced, since the output has equal numbers of 0 and 1 output.

MULT90063 Introduction to Quantum Computing
Deutsch algorithm: balanced function
The function, U, is implemented by the gates inside this box

MULT90063 Introduction to Quantum Computing
Deutsch algorithm: walkthrough
| i=|0i⌦|1i

MULT90063 Introduction to Quantum Computing
Deutsch algorithm: walkthrough
| i=H|0i⌦H|1i
|0i + |1i |0i |1i
= p2 ⌦ p2 = |+i ⌦ |i

MULT90063 Introduction to Quantum Computing
Deutsch algorithm: walkthrough
| i=CNOT|+i|i
This is a common pattern called “phase kickback”

MULT90063 Introduction to Quantum Computing
Phase kickback
Consider X applied to the output register:
|0i |1i X|i=X p2
|1i |0i = p2
If we were to apply an X gate to the target qubit we get a global phase change.
Otherwise the state is unchanged.
What would happen when apply
a control-X gate?

MULT90063 Introduction to Quantum Computing
Phase kickback
Now with a control-X gate:
CNOT |+i |i = CNOT
|0i+|1i|0i|1i p2 p2
|0i |0i|1i |1i |1i|0i = p2 p2 + p2 p2
If we were to apply a control-X gate then any control states which apply the X-gate receive a phase change. The “1” state receives the (relative) phase change in this case.
|0i |i |1i |i CNOT |+i|i = p2

MULT90063 Introduction to Quantum Computing
Phase kickback
|0i |i |1i |i CNOT |+i|i = p2
The state of the target qubit remains unchanged.
This causes the phase to be applied to the control qubit. This is known as phase kickback.

MULT90063 Introduction to Quantum Computing
Deutsch algorithm: walkthrough
| i = CNOT |+i|i = |i|i
Phase kickback changes the state of the control qubit.

MULT90063 Introduction to Quantum Computing
Deutsch algorithm: walkthrough
| i=H|i⌦|i = |1i ⌦ |i

MULT90063 Introduction to Quantum Computing
Deutsch algorithm: walkthrough
| i=|1i⌦|i
We will measure “1” with 100% probability. This indicates (with a single evaluation of the function) that the function is balanced.

MULT90063 Introduction to Quantum Computing
Deutsch-Josza (3)
f2(0) = 1 f2(1) = 1
f3(0) = 0 f3(1) = 1
f4(0) = 1 f4(1) = 0
f1(0) = 0 f1(1) = 0
The Deutsch-Josza algorithm determines in just one query whether the function is constant or balanced.
Classically, this would require two queries.

MULT90063 Introduction to Quantum Computing
Phase kickback for balanced functions
Constant functions
The control qubit is unchanged by the constant functions.
The same phase kickback pattern that we just saw applies to both balanced functions
Balanced functions

MULT90063 Introduction to Quantum Computing
Multiple qubits: Deutsch-Josza
This means that there are multiple qubits in the register There are multiple Hadamard gates here
Only a single qubit here

MULT90063 Introduction to Quantum Computing
Example of multi-qubit constant function
|y f(x)i

MULT90063 Introduction to Quantum Computing
Example of multi-qubit balanced function
|y f(x)i

MULT90063 Introduction to Quantum Computing
Multiple qubits: Deutsch-Josza
Let’s walkthrough this circuit…

MULT90063 Introduction to Quantum Computing
Recap: binary and decimal representations
|0i |0i
shorthand notation
|0i+|1i |0i+|1i |0i+|1i |i= p2 ⌦ p2 …⌦ p2
| i = p2 (|00…0i + … + |11…1i)
i.e. even superposition over binary rep of integers: i = 0 to 2n – 1
In general we use two representations in the QUI (N = 2n): “binary”
| i = a0…00 |0…00i + a0…01 |0…01i + a0…10 |0…10i + … + a1…1 |1…1i
“decimal” | i = X a |i | i=a0|0i+a1|1i+a2|2i+…+aN1|N1i
e.g. a101 |101i
a = |a|ei✓

MULT90063 Introduction to Quantum Computing
After the initial Hadamard gates, the state is (n qubits, N = 2n):
1 X |0i|1i |i=pNx|xi⌦ p2
Equal (even) superposition of states

MULT90063 Introduction to Quantum Computing
General Function Phase Kickback
|xi |xi
|y f(x)i
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
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
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
e.g. Hadamard applied to a general state
x = 4 1 |0i |1i |0i + |1i |0i + |1i |100i = p23 p2 p2 p2
H⌦3 |000i =
|0i + |1i |0i + |1i |0i + |1i p2 p2 p2
1 z = 0 z = 1
|000i = p23 (|000i + |001i + … + |111i)
H⌦3 |x = 0i = p23
bitwise: x · z = 0 3
(1)x·z |zi
1 2 1 z=0
H |100i = p23 (|000i + |010i + |001i + |011i |100i |110i |101i |111i) x·z=0 x·z=1
H⌦3 |x = 4i = p23
(1)x·z |zi
H⌦3 |xi = p23
(1)x·z |zi
General for n=3

MULT90063 Introduction to Quantum Computing
Constant function
For a constant function (f(x) = 0 for all x, or f(x) = 1 for all x):
| i = N1 X(1)f(x) X(1)x·z |zi
x=0 z=0 N1N1
N1 X(1)x·z =
(1)f(0) X X x·z ! = N (1) |zi
So for a constant function “0” will always be measured (global phase is unimportant).
x=0 z=0 N1 N1
= (1)f(0) X X(1)x·z
N z=0 x=0 = (1)f(0) |z = 0i

MULT90063 Introduction to Quantum Computing
If 0 is measured, then the function is constant.
If any other value is measured, then the function is balanced.
The Deutsch-Josza algorithm evaluates if a function is constant or balanced with a single query. Classically we would require O(2n) queries.
Of course, there are classical probabilistic algorithms with establish with high probability in few queries, but only with high probability of success not with certainty.

MULT90063 Introduction to Quantum Computing
Deutsch-Josza algorithm
• Given a Boolean function, f, determine if:
– fisconstant(alwaysgivesthesameresult)
– fisbalanced(givesequalnumbersof0sand1s)
• Classical algorithm (worst case) needs 2n/2+1 queries
• Quantum algorithm needs just 1 query.

MULT90063 Introduction to Quantum Computing
Universality in 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

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

Related Posts