Presentation on theme: "Quantum Computation and Quantum Information – Lecture 3"— Presentation transcript:
1 Quantum Computation and Quantum Information – Lecture 3 Part 1 of CS406 – Research Directions in ComputingNick Papanikolaou
2 MotivationQuantum computers are built from wires and logic gates, just as classical computers areThe potential of such devices stems from the ability to manipulate superpositions of statesQuantum algorithms solve problems which are not known to be solvable classically!
3 Lecture 3 Topics Quantum logic gates Simple quantum circuits Quantum teleportation as a circuitDeutsch’s quantum algorithm
4 Quantum vs. classical gates The simplest boolean gate is NOT, with truth table:Quantum gates have to be defined not only on the equivalents of 0 and 1, but on their superpositions too!inout1
5 Quantum NOT gate: Linearity Suppose we define a quantum NOT gate as follows:The action of the quantum NOT gate on a superposition must then be:All quantum operations are linear
6 The NOT Gate as a MatrixBecause all quantum operations have to be linear, we can represent the action of a quantum gate by a matrixThe quantum NOT, or Pauli-X gate, is written:
7 Quantum State VectorsRemember that a quantum state is represented by a vectorNotation:
8 Quantum NOTWe can express the NOT operation on a general qubit as matrix multiplication:
9 Other Single Qubit Gates The Pauli-X gate works on only one qubitOther common single qubit gates are:Pauli-Z gate:Pauli-Y gate:Hadamard gate:ZYH
17 Features of Quantum Circuits No loops are allowed; quantum circuits are acyclicFan-in is not allowed:Fan-out is not allowed:
18 Generalised Control Gate Any quantum gate U can be converted into a controlled gate:One control qubitn target qubitsUIf the control qubit is “high,” U is applied to the targets. CNOT is the Controlled-X gate!
19 Quantum Measurement Measurement in a quantum circuit is drawn as: M (classical bit representing outcome of measurement)M = 0 with prob.orM = 1 with prob.Ifthen:
20 A Qubit Cloning Circuit? Using the XOR gate, it is possible to copy a classical bit:xyxÅyCan we build a quantum circuit that performs does this with qubits?
21 A Qubit Cloning Circuit? (2) OK hereentangled!!
22 A Qubit Cloning Circuit? (3) It is impossible to clone a qubit!Also note thatunwanted terms!
28 Quantum Teleportation Circuit (4) HM2XM2ZM100, 01, 10 or 11
29 Quantum Teleportation Circuit (5) If Alice obtainsThen Bob’s qubit is in stateSo Bob applies gateobtaining00I01X10Z11Y = ZX
30 What have we achieved?The teleportation process makes it possible to “reproduce” a qubit in a different locationBut the original qubit is destroyed!Next topic: Quantum Parallelism and Deutsch’s quantum algorithm
31 Quantum ParallelismQuantum parallelism is that feature of quantum computers which makes it possible to evaluate a function f(x) on many different values of x simultaneouslyWe will look at an example of quantum parallelism now – how to compute f(0) and f(1) for some function f all in one go!
32 Quantum Circuits for Boolean Functions It is known that, for any boolean functionit is possible to construct a quantum circuit Uf that computes itSpecifically, to each binary function f corresponds a quantum circuit:binary addition
33 Quantum Circuits for Boolean Functions (2) What can this circuit Uf do? Example:xyyÅf(x)
34 Quantum Circuits for Boolean Functions (3) But what if the input is a superposition?xyyÅf(x)amazing! we’ve computed f(0) and f(1) at the same time!
35 Quantum Parallelism Summary So, a superposition of inputs will give a superposition of outputs!We can perform many computations simultaneouslyThis is what makes famous quantum algorithms, such as Shor’s algorithm for factoring, or Grover’s algorithm for searchingSimple q. algorithm: Deutsch’s algorithm
36 Deutsch’s Algorithm David Deutsch: famous British physicist Deutsch’s algorithm allows us to compute, in only one step, the value ofTo do this classically, you would have to:compute f(0)compute f(1)add the two resultsRemember:
38 Circuit for Deutsch’s Algorithm (2) xyyÅf(x)HHH
39 Circuit for Deutsch’s Algorithm (3) xyyÅf(x)HHH...and so we have computed
40 End of Lecture 3Congratulations! If you are still awake, you have learned something about:quantum gates (X, Y, Z, H, CNOT)quantum circuits (swapping, no-cloning problem)teleportationquantum parallelismand Deutsch’s algorithm