OPEN SOURCE SOFTWARE
OPEN SOURCE SOFTWARE CSCI 4967
Popular in Course
Popular in ComputerScienence
This 77 page Class Notes was uploaded by Santos Fadel on Monday October 19, 2015. The Class Notes belongs to CSCI 4967 at Rensselaer Polytechnic Institute taught by Staff in Fall. Since its upload, it has received 24 views. For similar materials see /class/224851/csci-4967-rensselaer-polytechnic-institute in ComputerScienence at Rensselaer Polytechnic Institute.
Reviews for OPEN SOURCE SOFTWARE
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/19/15
Quantum Computation Lecture 6 Quantum Computation and Computer Science 11 Notes taken by Kevin Barlett August 2007 Summary This continues the discussion of how computation using Quantum means relates to the body of more traditional Computer Science 1 Computational Complexity Cont 11 Quick Review As discussed in the previous lecture there are different classes of problems in traditional Computer Science and the two we are most focused on are P and NP P being the class of all problems such that there is a deterministic algorithm that can solve a problem in polynomial time in relation to the size of the input NP is the class of problems such that there is a nondeterministic algorithm that can solve the problem in polynomial time Note While it is true that P Q NP since from every deterministic polynomial algorithm a non deterministic polynomial algorithm can be created in common usage when referring to NP we are re ferring to those problems known to be in NP but are not known to be in P Traditional Computer Science has regarded those problems in P to be considered easy however those problems in NP are considered hard because for most reasonably sized input it is intractable to actually nd a solution While the problems in class NP are much more dif cult to solve they are still very important questions to have solutions to Some of those problems are 1 Traveling Salesman Problem TSP Given a graph GVE where each e E E has a weight associated with it w e 2 0 the goal is nd the shortest cycle such that each vertex city is visited atleast once N Satis ability of 3Clauses 3SAT Given clauses of the form 11 V12 V13 where each xi is going to be either vj or v7These clauses are thenjoined together to create sequences of the form 11ng V13 I4VI5V15 A H The goal of this problem is to nd an assignment of the variables used vj s to either True or False such that the entire sequence is True or that each clause is evaluated to True 3 Hamiltonian Cycle Given a graph G V7 E nd a cycle a path that starts and ends at the same node such that each vertex is touched once and only once 12 Witnesses While problems in NP have no known solving deterministic polynomial time algorithm we can solve simpler problems with deterministic polynomial time algorithmsTake for instance the BSAT problem if I were to give you an assignment of the variables it is relatively simple read deterministic polynomial time to see if that assignment is a solution to Lecture Notes for a course given by Stephen F Bush at RPI this BSAT sequence or not We just check each of the clauses to see if it evaluates to true and if any doesn t then we know it isn t a valid solution to 3SAT We can consider this simpler deterministic polynomial time algorithm to be a witness for the BSAT problemSimilarly a witness for the Hamiltonial Cycle Problem would take the cycle and con rm that it is indeed a cycle and that every vertex is touched exactly once De nition 1 For each of the problems in NP there exists atleast one witness that will con rm a solution is a valid solution 13 P NP As discussed earlier is is easy to show that every problem in P is also in NH however there is a question that remainsAre those problems in NP that aren t known to be in P that way because there isn t a deterministic polynomial time algorithm that solves them or have we just not found a deterministic polynomial time algorithm yet and one does exist Put another way we know P Q NP and we don t known if NP Q P Is is expected that it will be discovered P y NP but this has not been provenThis intuition is largely based upon the fact that many very intelligent people have spent quite a bit of time attempting to nd deterministic polynomial time algorithms for various problems in NP and none of them have had signi cant success However lack of a determinisic polynomial time algorithm is not a proof that one does no exist and so the search continues for either a deterministic polynomial time algorithm or a proof that one does not exist 14 Reducibility Reducibility allows the complexity of one problem to be tied to another by saying If we can solve problem A in deterministic polynomial time then we know we can also solve problem B in deterministic polynomial time The proccess works by creating the following procedure Take Input for problem B N Convert Input for problem B into an input for problem A This must be done in deterministic polynomial time Squot Solve problem A gt Convert solution from problem A into a solution for problem B This must be done in deterministic polyno mial time 5 Return solution for problem B By using this setup we have guaranteed that if B is not in R this can only happen if there is no deterministic polynomial time algorithm solving A and similarly if there is not a deterministic polynomial time algorithm solving A there is no deterministic polynomial time algorithm solving B 15 NPCompleteness De nition 2 A problem A is said to be NP Complete if the following requirements are met 1 A E NP 2 V n 6 NE A lt17 11 every problem in NP can be reduced to A The existance of some problems being NPComplete was rst shown by Cook and Levin when they proved that BSAT was NPComplete Now many other problems are known to be NP Complete reducch m A aHNPpmhlaus have the same du39 mmy anl39 some Wham harder 1mm mhcxs Fxgwci mmummmmw Dmi nn 3 Ldner39s my mm m dung Ladm NPrOamplc c gamma mung be mm solvc hasc pmbkms m NP 2 Cilulit Model of Ccmpllm on 21 Introduction 1 Wins arc ma m owned we aim oumpuncmx wrung as mm of cmpuzary smug ax luminary Untpmvalucs m on sunny was 3 Ancilla are used to give wires preprepared values 4 Fanout which allows the value of one wire to me split into many wires carrying the same information Note Recall that quantum computation works differently than normal computation so each of the pieces in traditional circuitry may or may not have an analogue in quantum circuitry In traditional computation we can not create a circuit to run a nondeterministic algorithm however we can create a circuit to run a deterministic algorithm Similarly the number of elements in the circuit can be considered as the complexity of the circuit so that if a circuit exists such that it has a number of elements that has a polynomial relation to the size of the input we can say that there exists a deterministic polynomial time algorithm that solves the given problem This direct relation polynomial number of components vs polynomial number of operations can be quite convenient when considering the complexity of a problem 3 Maxwell s Demon Entropy and the Reversibility of Circuits 31 Maxwell s Demon and Entropy James Maxwell created a thought experiment during the 1860 s that went as follows Assume we have a system consisting of a rectangular box and a uniform gas inside Assume also a partion exists dividing the box into two halves and let there be a door in this partion that can be opened and closed by some demon Now as the gas exists in the system some of the particles will be more exicited than others and will have more energy Let us say that the demon attempts to and succeeds in opening and closing the door allowing all of the highly energetic molecules to move to one side of the parition and stay there and keeping all of the nonenergetic particles on the other side This would seem to be a system where the second law of thermodynamics which states that the entropy of any system not in equillibrium will increase over time is violated This demon perplexed some physicists as they attemptted to nd a aw in this senario One of the general objec tions was that given that the system is closed and since the system is at thermal equilibrium the only light will be the result of thermal noise and the noise is random to the point where it wouldn t be enough to allow the demon to know when to open the door and which particles to let through A different objection was raised by Leo Szilard who argued that the demon would expend energy in obtaining the information necessary to decide if the door should be opened at a particular time or not And since the demon is impacting the system the demon itself is inside the system and so in the end any entropy lossed by the gas in the box will be equivalent to or less than the entropy gained by the demon 32 Reversibility of Circuits In general the second law of thermodynamics states that the entropy of a closed system can never decrease So if we consider a quantum circuit if we ever decrease the possible number of logical states of a computation then we would be decreasing the entropy of the system this can not be and so the entropy that is lost must be given off in some other form such as heat A good measure of if the number of logical states are decreasing is if the circuit can be reversed and given the output be able to obtain the exact input that was given Consider an ORgate if the output of an ORGate was 1 there is no way to determine if the two inputs were 0 1 or 1 O or 1 1 and so an ORgate is not reversible and so would be accompanied by the release of energy in some form or another 33 CNot and Toffoli gates A ControlledNot gate or CNot for short works as follows it takes two inputs say a b and retunis a b where H7 E ifa1 T b ifaO 1 ms way Wc g1 the mum xelamm 1 am Wc wam q a N m M Taffohg cs and have the same c ectbangahlc m mud anycmu wuh hcsc buddu gblacks 34 Reversibility of Circuit Revisiud mkangd m 07 X 7 rm f X Pix F 39Lx Ans a i Garbage gure 2 Haww ammmhc mug of reversxhlc Cmn 4 Mmllmment some yy au sme spat 30 than on beg the quesme can cva39y observable be measurch 0 pm mama Waye cumpmcx a meanmng an absmahlc cancspundmgw he halhng pmhlcm of Tmmg Machmc Mm mm be e m Quantum Computation Lecture 5 Quantum Computation and Computer Science 1 Notes taken by Robert Stevens October 2007 Summary This class helps to integrate the big picture ideas of Computer Science with Quantum Com putation These ideas include Turing Machine Halting Problem Computational Complexity Theory Polynomial Time and the Strong ChurchTuring Thesis 1 Turing Machine The Turing Machine is an idealized and rigorously de ned mathematical model of computing device In our case we will be using a model slightly different The programs input and output for this case a Universal Computer can be represented using a pair of uniquely encoded pair of positive integers l Kolomogorov Complexity can be described using as follows 0 6 represents a universal Turing machine 0 p represents a program 0 x represents a string Proof W lt W 1 2 Universal Turing Machine 0 Turing was the rst person to create a Universal Turing Machine 0 Marvin Minksy in the early 1960s created a 7 state TM 0 Sequences that have small complexity tend to have regular patterns Proof KW olt Olog n D 0 Sequences that have large complexity typically have random patterns a Typically these patterns are incompressible b A fair coin being ipped can be represented as Lecture Notes for a course given by Stephen F Bush at RPI Proof KW olt n 01 1 3 Direct Relationship between computer science and information theory 0 Programs can be encoded based on probability distribution of their bitsequence o The program length is then related to the probability distribution 4 Minimum Description Length and Sophistication 0 Compression only occurs in nonrandom portion of the bitstrings that represents the program 0 Anything that is too complex must be left verbatim 2 The Halting Problem The primary question Does a program number x halt on input x 7 0 ifzhalts MI 7 l othETwise o Is there an algorithm to solve the halting problem that is to compute Mr 0 Let T be the Turing Number 0 There s a contradiction because if the program has an output 0 but the Turing halts then the program has an output of l which is impossible 0 Relationship between halting problem and Hilbert s Problem There is no program that exists which can prove the halting problem This relates to many natural mathematical conjectures that cannot be decided algorithmically To do this would require to solve the halting problem 3 Computational Complexity Theory General theory of the resources needed to solve computational problems 1 Type of resources 0 Time 0 Space 0 Energy 2 Type of computational problems 0 Composing a poem 0 Sorting a database 0 Decision problem 3 Decision Problems 0 A decision problem is a computational problem with a yes or no answer 0 Decision problems are simple which makes it easier to create rigorous mathematical theory 0 These are relatively general usually in terms of another problem 0 Such problems include Multiplication Decision Problem Is the H bit of the product In and 11 one Factoring Decision Problem Does 11 have a nontrivial factor smaller than k 0 Time required to solve one of these problems is the same as the time required to solve the basic mathemat ical version o Ef ciency Easy 2 tractable ef ciency computable A problem is easy if there is a Turing Machine to solve the problem that runs in polynomial time related to the size of the problem input Hard 2 intractable not ef ciently computable A problem that is hard is one that does not run in polynomial time by a Turing Machine 4 Polynomial Time Polynomial Time is a program that executes a number of operations running time proportional to the size of its input 11 0 Problems with polynomialtime solutions are usually found to be easily soluble o Superpolynomial algorithm whose running time as a function of the input size n is nl09 is likely preferable to a polynomialtime algorithm taking time nlooooo De nition 1 The set of all decision problems soluble in polynomial time on a Turing Machine is denoted P o Terminology Multiplication is in P means The Multiplication decision problem is in P o Turing Machines can be used to help simulate P Allow the Turing Machine to do random coin ips The set of all decision problems soluble is denoted BPP bounded probability of error polynomial time For now BPP and P will be equivalent 5 Strong ChurchTuring Thesis Any physically reasonable algorithmic process can be simulated on a Turing Machine with at most a polynomial slowdown in the number of steps required to do the simulation 0 ChurchTuring Thesis Any algorithmic process can be simulated on a Turing machine 0 The Strong ChurchTuring Thesis lmplies that the problems in P are precisely those for which a polynomialtime solution is the best possible in any physically reasonable model of computation Kolomogorov Complexity requirement of a universal Turing Machine still polynomial in time complexity Serves as the basis for a useful theory of computational complexity Quantum Computationquot Lecture 4 Quantum Mechanics 11 Notes taken by Max Schnur August 2007 Summary This lecture went over Telelportation the Spectral Theorem Dirac Notation and the Trace Operator An explanation of Schroedinger s Equation brings us back to Postulate 2 1 Teleportation Given Alice and Bob we want to nd a way for Alice to transfer her quantum state without altering it to Bob It s important to note however that a quantum state itself cannot be transferred because then it would necessarily need to be read Rather Alice and Bob agree on a system beforehand for recreating a quantum state while two classical bits are actually transferred 11 The Paper s Example Alice s quantum state is de ned as 15 alO bll Of course she doesn t know the values of a or b but she wants to send the whole state to Bob To do this Alice and Bob must both posses one qubit of an entangled pair 1b For example 1 imam M The starting state for everyone is 15 1 the combination of Alice s state with the EPR Pair The result is follow al011 bl100 14111 This makes sure all the bits are entangled Alice controls controls means that Alice can measure the qubit and therefore affect its state the rst two bits Bob controls the last one Alice then applies a series of gates to the entangled qubits a Cnot gate and a WalshHadamard Alice measures the rst two qubits and treats them as two classical bits These two bits can be treated as a return value 03 During this measurement Bob s quantum state has been projected to any of alO bll all bl0 alO 7 bl l or all 7 blO Alice can now send her two classical bits to Bob Before any of this happened Alice and Bob had agreed on transformations that correspond to the possible return values 03 When the right transformation is applied to Bob s quantum state Alice s original state is reconstructe Lecture Notes for a course given by Stephen F Bush at RPI Note that this is teleportation and not cloning When Alice measured her bits she essentially destroyed them for herself but Bob was able to recreate them This is how the No Cloning Principle is preserved 12 The Class Example The inclass example is similar to the paper s method but instead uses Bell States as transformation gates Instead of Cnot and HadamardWalsh gates it uses simple L X Y and Z gates for transforming Alice s classical bits 13 Communication Faster Than Light At rst glance teleportation seems like it can let you communicate at faster than light speeds But in reality there s no way for Alice to send a pure unknown quantum state to anyone She needs to build it herself get an imprin of it and transmit the imprint Then Bob can rebuild it himself So teleportation is slower than the speed of light but it lets you transmit an in nite amount of data in just two classical bits 2 Outer Product Notation It s my understanding that 0 will yield a horizontal vector 10 O is the outer value while 1 will yield a vertical vector 01 l is the outer value Using this notation allows for some macroscopic properties that can be exploited The lecture notes shows how the result of an inner product can be used as an outer product and gives examples of outer product notation It is also useful in describing projectors A projector acts as a variable that chooses a result of aje1gt j 2gt yje3gt from the result of aje1gt j 2gt That means P je1gtlte1j je2gtlte2j in this case It can be generalized as a projection of orthonormal vectors on any subspace ie more states to E jejgtltejj 3 Spectral Theorem Theorem 1 There is an orthonormal basis of V consisting of Eigenvectors A Each eigenvalue is real Proo s for this are available here ht tp en wikipedi a orgwild Spectra litheorem You can apply the spectral theorem easily by taking a Matrix M and transposing it 90 degrees Take the eigenvalues of M and MT separately For the eigenvalues that match take the 1 These are the output of the spectral theorem This is apparently useful in many places especially for eigenvalue decomposition but we have yet to see how it is used in quantum computing 4 Trace Operator The trace operation is simply de ned as the sum of the diagonals topleft to bottomright of a Matrix It can be used to ef ciently nd cycles in a graph supposing the graph represents an adjacency matrix Note that if parts of a graph can be extracted to form a subgraph then the trace operator can be used on the subgraph to nd subcycles As implied above the trace operator is cyclic so tTAB tTBA We have not yet seen how this will be used 5 Postulate 2 Revisited Postulate 2 The evolution of a closed quantum system is described by a unitary transformation In other words 1W can be described as a function of 1b But in practice quantum dynamics occurs in continuous time not discrete steps The evolution of a closed quantum system should be described in time using Schroedinger s equation d 2 HW H is a constant Hermitian Matrix known as the Hamiltonian of the system Schroedinger s equation can be solved for us just broken down so that it is usable in quantum computing Wt erpthl 0gt U ezpthl1gt WW This is the form we recognize as Postulate 27it is accurate but now you know where it comes from Quantum Computation Stephen F Bush Lecture 2 QM Basics 11 Notes taken by Matt Edman September 5 2007 Summary This lecture continued the previous week s introduction to the basics of quantum mechanics as it applies to quantum computing We brie y reviewed the mathematical notation used in the course introduced last week as well as introduced the remaining two postulates The lecture concluded with a discussion of the concept of quantum entanglement and a summary of all four postulates 1 Introduction Relation Among Matrix Types The following table gives relationships for four types of matrices Recall that Al AT is the Hermitian conjugate or adjoint of the matrix A For example a b T 7 a 0 c d 7 b d where 2 is the complex conjugate of the complex number 2 The complex conjugate of a complex number simply means changing the sign of the imaginary part 2 Measuring a Qubit Quantum mechanics does not allow one to precisely determine the values of a and B in a qubit l gt 040 5 Measurement disturbs the system and leaves it in either a 0 or ll state Instead we read limited information about a and B by looking at the probability of the system being left in a particular state as a result of the measurement Measuring in the computational basis is then described as 130 W2 131 W2 Lecture Notes for a course given by Stephen F Bush at RPI Since the measurement either results in system in a 0 or ll state with probability 1 then the equality P 0 Pl lal2 W2 1 must hold Students are encouraged to work through the exercise given in the slides to determine which of the given states of a qubit are valid as well as the probabilities of state 0 and ll for each valid state We can also extend this concept of measurement to an arbitrary state space Cd Let in m lag be an orthonormal basis for Cd A measurement of the qudit l gt in this basis gives results j with probability PU ll jgt WV where we recall the complex inner product of two vectors is computed as W lil WW The more general approach allows us to consider measurement under a different orthonormal basis Consider a gt qubit W and the orthonormal basis lgt io l if M W i Computing the probability of each state results in 2 M J 2 la l2 2 lamm 137 r We will discuss examples of situations in which one would need to change the basis used in a future lecture Inner products and duals The inner product of vector spaces multiplies vectors together with the result being a scalar value 122 it reduces dimensionality to a single number Inner product spaces of an in nite dimension are know as Hilbert spaces The inner product can also be used to de ne the dual sometimes written ab of a vector 1b More formally the dual M of a vector l gt in state space Cquotl is a function M Cquotl A C de ned in terms of the inner product as WWW W l gt Here s an example 1 a lt0lal0gt l1gt 0 l l B l a Two useful properties of inner products are ltalbgt ltblagt since lat lb w lagt Albgt H WAT since AM we mum s WNW The vector dual ltal can also be considered as row vectors For example suppose al Ej ajltjl and bl Ej bj ltj Applying the de nition of the dual above we see that b1 ltalbgt at W Za j ma a a 52 3 Postulate 3 With the de nition of a vector dual from the previous section we can now state Postulate 3 If we measure l gt in an orthonormal basis le1gtui led then we obtain the result j with probability Pj lltejl gtl2 The measurement disturbs the system leaving it in a state lejgt determined by the outcome We also showed that a global phase factor is unmeasurable and irrelevant Say we measure ei9l gt in the orthonor mal basis le1gtp i i led Here ei is a global phase factor or overall multiplicative constant We would compute the probability of each state lejgt as PU llt jl i9l gtl2 ll jgt39 i9l gtl2 ll jgt 39 WV llt jl gtl2 The last two steps in the above equation hold since the complex conjugate of e is e49 and ewe 1 Thus the global phase factor cancels out and is unimportant 4 Poly Qubit Systems We can represent a multiplequbit system as a00l00gt a01l01gt a10l10gt Quill The probability of resulting in a bit string 1 y is then de ned similar to before as Pz7 y lawle The promise of quantum computing comes from the fact that we can represent the state of n qubits as a superpo sition 216ml aim corresponding to every possible nbit string Classical systems would require 02 bits to describe the quantum state instead of only n qubits in a quantum system 5 Postulate 4 The fourth and nal postulate posits The state space of a composite physical system is the tensor product of state spaces of the component systems A tensor product such as 0 0 can also be written as o l0gtl0gt be careful to distinguish from 0 l0 0 l0 0 or o l00gt The computational basis states de ned in terms of tensor products are 0 0 0 8 ll ll 8 Depending on the context the tensor product is also referred to as an outer product direct product cardinal product or Kronecker product As an example the Kronecker product of two rectangular arrays is b1 aibi 12121 Wu 7 a1172 a2172 a3172 b3 la1 a2 asl cle cng agbg 124 1114 a2114 a3114 The tensor product ja jb of the state of two systems ja and jb represents the state of the joint system Conversely if the joint state is ja jb then we can say the states of the individual systems are states ja and If a gate U is applied to to one system say ja in thejoint system ja jb then the tensor product U E I is applied to the joint system or 1 E U if U is applied to 12 Students should work through the example from the lecture slides of a NOT gate applied to a twoqubit system Some other properties of tensor products include 0 2010 M 2M M lVgt MM 0 lV1gtll2gt lwgt lV1gt lwgt lV2gt lwgt 0 M lw1gt W lVgt lw1gt M lw2gt W lbgt WW E wW 0 AG BMW M AM Blwgt The tensor product is also related to graphs The tensor product G X H of two graphs G and H is the Cartesian product of the two vertex sets and any two vertices u7 u and v7 1 are adjacent in G X H iff u is adjacent with v and u is adjacent with 1 Showing the relationship between the tensor and graph product is left as an exercise for the student 6 Entanglement The last topic covered in this lecture was that of quantum entanglement a topic once described by Schrodinger as the characteristic trait of quantum mechanics We introduced quantum entanglement with an example of two entangled qubits and proved how they cannot be reduced to separate states and represented as a tensor product of those states Theorem 1 j gt W cannot be written as a tensor product Proof The proof is by contradiction Assume that j gt can be written as a tensor product W al0gt l1gt7l0gt 6W aw00gt vl10gt a6l01gt mm The only way the statement above can be true is if either 5 0 or 7 0 driving the second coef cient to zero In such a case though either the rst or the last coef cient would also vanish resulting in an impossible state Thus by contradiction we have proven that 1 cannot be written as a tensor product 7 Summary To summarize the four postulates of quantum mechanics are Postulate 1 A closed quantum system is described by a unit vector in a complex inner product space known as a state space Postulate 2 The evolution of a closed quantum system is described by a unitary transformation That is Wgt UM Postulate 3 If we measure j gt in an orthonormal basis je i i i jedgt then we obtain the resultsj with probability PU Hem1W The measurement inevitably disturbs the system leaving it in a state jejgt determined by the outcome Postulate 4 The state space of a composite physical system is the tensor product of the state spaces of the component systems Students were reminded to continue doing the exercises given in the lecture slides on their own The next lecture Will continue With quantum mechanics and also introduce superdense coding Quantum Computationquot Lecture 9 Quantum Noise 1 Notes taken by Jason Lawrence August 2007 Summary These are the notes for Quantum Noise 1 1 Density Matrix The density matrix is a tool that can be used to describe noise in quantum systems The lecture provided examples of quantum noise processes and the mathematical tools that can describe quantum noise The density matrix generalizes the notion of a quantum state for a noisy quantum system It is a mathematical convenience as it is much easier to work with a density matrix than a quantum state 11 Simplicity Density matrices are a much more simple way to look at quantum states The following state probabilities can be represented by the matrix on the right logt p 01 m p 0 1 1 2 0 flag p0il5 A 3 g 12 log p 0 15 OHfi D p 0 25 2 L3 p 0 25 2 Ensemble Point of View 0 De nition The density matrix for systems in the state lzbj with probability pj is p ijjl jgtlt jl 0 Dynamics p A p UpUl 0 Measurement A measurement described by projection Pk gives result k with probability tTltPk p and the post measurement density matrix is pk 0 Characterization t rp l and p is a positive matrix Conversely given a matrix satisfying these properties there must exist a set of of states lzbj and probabilities pj such that p Ep za W Lecture Notes for a course given by Stephen F Bush at RPI 21 Qubit Examples 0 0 ii 0 1 Z i3 i M 0 Suppose W 39D With probability 1 Then p 0gti1gti0gt ilgt 12 1 7239 12 fl 0 Suppose W 0 With probability 1 Then p i0gtlt0i 1 0 1 0 0 Suppose W 1 With probability 1 Then p i1gtlt1i f f 1 22 2 Qubit Example Suppose we have M 00 With probability p and W w With probability 1 7 p o pp00gtlt00lt17p lt01gt10gtgtltlt01lt10gt 1 0 pg1000i0110 0 0 D H ON N O u u D H ON N O u u COCO P 0 0 0 3 Dynamics and the Density Matrix We have a quantum system in the state Mg With probability pj Here is What happens When a unitary matrix U is applied to the system 0 The initial state is zbj and the nal state is WW 0 The initial density matrix is p Epji jgtlt ji and the nal matrix is p ijUi jgtlt jiUl o p UpUJr 31 Qubit Examples We have M 0 With probability p and W 1 With probability 1 7 p P 0 39 p i0 17p 0 Apply theX gate p XpX 16p Note Xir X o If our state is completely mixed W i0 and W 1 With probability 12 then p Will not change for any U 4 Terms These terms were mentioned in the lecture repeated verbatim from the lecture here 0 Pure state A quantum system whose state l16gt is known exactly Note that tr p2 g l with equality if and only if a state is pure 0 Mixed state A system whose state is not pure 0 Puri cation Given a mixed system A and its density pA a reference system R can be introduced such that a pure state lAR exists for the joint system AR and pA tTRlARgtltARl R is mathematical convenience and has no direct physical signigicance 5 Bloch Sphere A qubit can be represented as a point on a sphere Unitary operations can be de ned in terms of rotations of the Bloch sphere Density matrices correspond to the inside of the Bloch Sphere The interior of the Bloch sphere represents the mixed states of a single qubit 0 An arbitrary qubit density matrix can be decomposed as W o The Bloch vector in Euclidean form I sin 26 96 cos 15 y sin 26 96 sin 15 z cos 26 0 Pure states correspond to the surface of the Bloch Sphere l16gt cos glO e sin gll o The I y 2 coordinates of a state represent the expectation values of the 07 operators respectively TjO39j o This is expressed by p I x E where I is the 2 X 2 identity matrix and x E 2122 0 A convex combination of pure states T7 with weights pj gives a mixed state with Bloch vector Ej pjTj Quantum Computationquot Lecture 1 Introduction to Quantum Mechanics by Stephen F Bush Notes taken by Briggs Thompson August 2007 Summary This document summarizes the rst lecture of the course Intro to Quantum Computing The topics include the course layout an introduction to quantum mechanics postulate 1 and 2 and logic gates 1 Description of Quantum Mechanics Quantum Mechanics is the backbone for creating theories relating to the physical universe It consists of four postulates which describe the laws of describing the universe 1 How to describe quantum states of a closed system State vectors and State space 2 How to describe quantum dynamics unitary evolution 3 How to describe measurements of a quantum system projective measurements 4 How to describe quantum state of a composite system tensor products A qubit is a two level quantum system Two states can be described as a vector around the circle in the lecture slide 2 Postulate 1 Associated to any quantum system is a complex vector space known as a state space The state of a closed quantum system is a unit vector in a state space Quantum mechanics does not prescribe the state spaces of speci c systems or those of electrons This basically means that the mechanics does NOT show where the electrons are 3 Logic Gates General dynamics of a closed quantum system Including logic gates can be represented as a unitary matrix The NOT gate ips the state of the qubit it applies the opposite to the matrix matrixlinear operatorlinear transformation 2 linear map Quantum gate modulo unitary Lecture Notes for a course given by Stephen F Bush at RPI 4 Lecture 2 Quantum mechanics does not allow us to determine alpha and beta We can read out limited information about alpha and beta meaning we can measure them as probabilities However measuring the system unavoidably disturbs the system leaving it in a O or 1 state determined by the outcome This means that the original position is lost and and new position is formed Quantum Computationquot Lecture 11 Quantum Information Theory 1 Notes taken by Robert Stevens November 2007 Summary This class helps to bring together the broad topic of information theory not only in a classical sense but also how it is incorporated in the realm of quantum computing data compression is explained along with properties of entropy more importantly Shannon s entropy communication and how it is affect by noise and lastly how data compression can be brought into the quantum realm 1 Information Information itself is very much an openended question as to it s explanation Still thought as in some respects as a research topic the main idea of information is to have a model that can be applied to realistic situations In general though information applies not only to randomness but also information must be capable of being compressed The model that will be used for this class is Discrete iid sources lid refers to independent and identically dis tributed or the fact that each output from the source is not dependent on other outputs they all have the same distri bution 0 Each output comes from a nite set 0 The alphabet will consists of O and 1 with no loss in generalization 0 Most sources of what we know as information is not discrete iid 1 Correlations prevent this from happening 2 Example in English literature there are letter combinations that occur more frequently than if they were separated 3 Certain frequently used text is not separated o 7W1 logpX A HX iid source X k random variable X distribution px o ShannonMcMillanBreiman Theory PT7 m logPTX H 1 naoo o Quantifying the rate at which information is being produced be a source Lecture Notes for a course given by Stephen F Bush at RPI Axiomatic ApproachDesireable axioms in which a measure of information should obey plus nd such a measurement Operation Approach Based on the fundamental program of information science with the main question being how many bits are needed to store the output of the source so the output can be readily recovered 2 Data Compression The main idea of data compression is one of two things one is to nd the minimum size that some piece of information can be stored and still be recoverable Second is to de ne the minimal value of stored information is the information content of the source 0 Shannon s noiseless channel coding theorem HX E Hp E 7 p logp o This minimum value of R number of bits for compression is given by the Shannon entropy of the source distribution this logarithm is base 2 o Flipping Coins Example Suppose we are getting p for heads and 1p for tails By ipping an arbitrarily large number of times this will become np heads and n1p tails This will also become np1 7 e and np1 e Doing the math will lead to a typical sequence m 2 H1 gt1 p This sequence is typical with probability approaching 1 This means that one could create a table that contains an indexed list of all the typical sequences Thus we have the following algorithm Algorithm 1 Let y be the source output If y is atypical Send the bit 0 n1 bits and then the bit string y Else Send 1 and the index of y nHp 1p 1 bits in the lookup table 96 Using the algorithm mentioned before on average only Hp1p bits were required to store the com pressed string per use of the source 96 This such an algorithm is used for large 11 applications 96 The algorithm never makes an error recovery Achieves Shannon s entropy on average FixedLength Compression Algorithm 2 Let y be the source output Ify is atypical then send nHp 1p 1 0 s else send 1 and the index of y in the lookup table 96 Errors always occur 96 Probability does approach 1 96 Only able to distinguish between 2 possible source outputs yet a source can have more than this number of outputs while still having an entropy lower than R Impossible to compress less than the Shannon rate 3 Properties of Entropy Entropy is HX E Hp E 7ng logp The probability Hp lp of this outcome looks just like a bell curve that starts at O and ends at l The highest outcome of Hp lp is 1 at 5 p o Recalling Kolmogorov Complexity The minimum obtained is When the source is outputting a single string over and over again Because of this the string contains no information but its length thus there s no compressibility The maximum is obtained When the input distribution is completely uniform everything is unknown about the source 0 Shannon entropy can be broken down into 4 real world components 1 Identify a physical resource 2 Identify an information processing task 3 Identify a criterion for success 4 How much of 1 do lneed to achieve 2 While satisfying 3 4 Communication and Noise In many topics communicating classical bits and qubits across a channel is very important More important if the affect of realworld noise like analog interference and how it affects the communication of this information o Reliable communication in the presence of noise Using a binary symmetric channel A bit is sent through the channel One of the transmission Will be correct probability of lp The other transmission Will be incorrect probability p Thus this channel is broken down to conditional probabilities p040lp p14Jp p071p plillp 0 Channel Capacity Maximal number of message bits that can be reliably sent over the number of uses of the channel High mutual information means one can recover the original material 0 Shannon s noisy channel coding theorem 2 The capacity of a noisy channel is given by the expression capacity H X 39 Y 0 Quantum Information Source Semiclassical Coin Toss l0gtPT 9 llgtPT Quantum Coin Toss 9 l0gtPT 0 1 7 1 95 PT 7 E Quantum information sources produces states hay with probabilities pj 5 Quantum Data Compression Quantum Data Compression has an input that is compressed and a probability that has to be decompressed In the end though we will nd that quantum data compression will actually be able to surpass or in this case be lower than than Shannon Entropy 39 J E jimjn 0 p E pjlzmzpjn 0 WW E WANWM F EPJFOWLPJ 0 FE lt JlPJl Jgt o F H1 Semiclassical Coin Toss 9 l0gtPT 9 llgtPT 6 Answer 1 Quantum Coin Toss 9 l0gtPT 01 9 igt igtPT 6 Answer y 1 L Answer m 06 6 We can do better than Shannon s rate Hpj z m kampmiLal ijm Md Hmmmdmm m 135 Cmgmm Lamxunns Q15 gang an 7 Stephen F Bush GE Global Research September 17 2008 WM e p quot muk i awe MEL Instructor Dr Stephen F Bush7 GE Global Researc Phone 387 6827 Email bushszresearchgecom Of ce Hours Thu 750 PM and by appointment Textbook None Course Website http www cs rpi edu bushs I am 4 1m WA lavnail 5am 3W Notes QM Basics 11 Measuring a Qubit Postuiates 3 3c 4 Entanglement Mechanics I Superdense Coding O n c an m Computer Science 11 The Size of P NP The Circuit Model Midterm Exam I Win t WLMJ WA nail Ema 315 I antum Operators Zero Error Information Theory Graph Entropy Quantum Circui s s of Quantum Computation Universality Quantum Complexity Classes A Stochastic Quantum Computer Quantum oise Density matrices Fidelity Measures ise II m point of view Quantum Information Theory I pression s at Compression Quantum Information Theory II Quantum Entropy Fidelity and Reliability Entanglement Local Operations and Classical Communication Student Project Presentations Final Exam and Vacation Notes Project proposals olue L M WI 1mm am 4 Component Weight Total Grade Midterm nal 30 each 60 Final Project 20 80 Assignments 0 80 Scribe Notes 10 90 igtClicker quizes Participation 10 100 I mm is at mm mth am 545 Scribe 1 Scribe 2 Scribe 3 1 2 Adam H Comella 3 Keith Emmanuel 4 Kyle G Gancarz 5 og E Moseley 6 Jason D Sanchez 7 Adam Co ela 8 Keith Emm nuel 9 KyleG ancarz 10 Logan E Moseley 11 la D Sanchez 12 Adam H Comella 13 Keith Emmanuel I Irma mum WA nail EM 551 0 I ve obtained a quantum math package and begun playing with it A Yes B No I Wm WL 1m LN mm 7mm 3245 0 I ve decided upon a nal project A Yes B No I Em WL 1m 4amp7 Mail swan W51 0 ln linear algebra a roW Vector or roW matrix is a 1 X 71 matrix that is7 a matrix consisting of a single roW x x1 x2 xm 0 The transpose of a roW Vector is a column Vector 1 2 T o The dot product of tWo Vectors a and b is equivalent to multiplying the roW Vector representation of a by the column Vector representation of b 171 Oaba1 a2 as 172 ltalbgt b3 I Wug WLMJ WA I fume WLMJ WA 0 Matrix multiplication involves the action of multiplying each roW Vector of one matrix by each column Vector of another matrix 102 31 7131X21 10 1X30gtlt22gtlt1 1gtlt10gtlt12gtlt0 71X33gtlt21gtlt1 71X13gtlt11gtlt0 a Note that its an inner product dot product of all rows of one matrix With all columns of the other a So the order of matrix operations is extremely important 0 The transpose of an Whyn matrix A is the n by m matrix AT also sometimes Written as Aquot formed by turning roWs into columns and columns into rows7 ie A Lj AU for all indices 139 andj o A BT AT BT and ABT BTAT i am WM 0 Special condition in Which A A o A is the eigenvalue of A o 1 is the eigenvector of A o For example7 all an I A I 7 Where the juxtaposition of a21 a22 y 9 matrices means matrix multiplication o How to solve use simple algebra and obtain detA 7 AI 07 solve for A I 171m Wt 11d WA Jamal a v Hm A Z has determinant detA ad 7 0 abc Fora3x3matrixA d e f g 2 Using the cofactor expansion on the rst row of the matrix we 5 f d f d e ah i g i g h aeiiafhibdibfgcdhiceg aei bfg cdh 7 956 hfa idb 71 0 I THREE WLMJ Wlmln ham ua m 0 Find the eigenvalue of A 53 2 10 5 3 1 0 odetA7Iidet 2 10 7A 0 1 7 5 3 0 57A d5tl2 iol lo All d5tl 2 107A 7 57A10776 271544 0 Solving for 7 57A10776 A2715A44 0 a A71174 0 Thus7 11 and 4 so this matrix has two eigenvalues I Trim Wt 11a WA Jawmil awe lm 0 o Dirac delta function7 6z 007 m 07 m 7 0 7 1 in j o Kronecker delta7 6W 7 07 ifi j I Trim Wt 11a WA may amt mm Rce aitim 11j Normal AAT 2 ATA Hermitian A 2 AT Unitary AAT I Positive 11 Al 11gt 2 0 0000 Normal H ermitian S F Bush wwwresearchgecombushsf Thug 55 2501 WM VGZ 13M ms um unmst udznslly 1 Tn 522 3 me cummands cumamed m ma package ODENSIWQdeIIS V sham EIT mssv Ker my yx xcsRevlslan Szgmaz xb Adj Cam EncmpY Ker Racqb sngmaa Eta Eamp easuxeKe Fldehty KecV e mian Rm sy xd Eta EampPT had Km PaxmalTxace Ran Bunker Rm swap gtltd am Eancmlledx Had Ker PaxclalTxaceEven Randamuublcl Razz Tensaxanduc ZexaT hian Eancxalled l Hadamaxd ea uxeKe ijEv Randamu 12 5 Thxee w lian Eancxalledz my HulclejEEasls m Randamuubldl Slgma Taffal p EncleTlmes cums mm Hulmquj Pu y r Sigma Naup x gmal ecuxns the mu szgma x macxlx mm 5mm U l me SqllmstqlmlhlenLily Wm J 1 u mpm Signal luma W792 SignaZ may a 39 u in WEquot 1 E Mm Smmazjmmaz 1 u wan11 sigma MW E J 1 u Manor I J mpns sxgmajmmaa 1 n W ssgmLngmz WW u 1 n u my D 7 mahlzsmn 1 u am Mr mm mm u x n n OutJUZF D in w r I Wm 83 r rough and rea l gtal0gt l1gt 0 Quantum mechanics DOES NOT allow us to determine Oz and B We can7 however7 read out limited information about 04 and B 0 Measuring in the computational basis77 0 P0 lalZ 131 W2 0 Measurement unavoidably disturbs the system7 leaving it in a state 0 or 1 determined by the outcome I Rm 4 1m WA lavnail 2mm mm Measuring a qubif 1 p0 pm Figure Projecting onto our multidimensional ruler Which of the following are possible states of a qubit at H 9 g l1gt e l0gt 07 0 03 1 9 08 0 06 1 Q cos0 0 isin0 l1 9 cos20 l0 7 sin20 l1 9 0 What are the probabilities of state 0 and 1 for each valid state WW W WL ME WWW I Valid 5mm 1 mm Ilnm mm mp1 2 1 MW 1 mm Ivar 4 Kztlrhtn1 MISWF 1 ms Ilnm1lzlo 3Kzun 2 MMSF n7sls77 u ements 0 Let 51 led be an orthonormal basis for Cd 0 A measurement of hp in the basis 51 led gives results j with probability Pj Haj l gtl27 0 Reminderl a5 6 0 Measurement unavoidably disturbs the system7 leaving it in a state lei determined by the outcome 1Inner product or is just the usual inner product Note that some mathematicians use the reverse convention Where the complex conjugate is applied to the components of the second vector in quantum information science the complex conjugate is invariably applied to the components of the rst vector mm W mum WA 334mb gta0gt 1gt 0 Introduce orthonormal basis H OH D and 7 Mim 2 04H V WNW M l 6 2 o Pm 0 o Pr I Trim ni Wt 11a WA 32mm Ema o The inner product is used to de ne the dual of a vector W1 0 If W1 lives in Cd then dual of W1 is a function W 3 Cd H 0 de ned bYlt ii gtgt1Jgt i gt 0 Simpli ed notation WM 0 Example 01a0gtmigt 1 J 2 J 04 0 Properties aib May7 since a 7 7 a AW H 1417 Since Ai MC 7141 it 141 i0gt I Trim as Wt 1w W1 1mm 234mm 0 Suppose a Z Li and b Z bj Then b1 ltaibgt WWW Ziafba39 Maii 2 o This suggests the very useful identi cation of ai with the row vector a a I Trim Wt 11a WA 12mm awe o If we measure W1 in an orthonormal basis l51gt led then we obtain the result j with probability Pj l 57 W1 2 o The measurement disturbs the system7 leaving it in a state lei determined by the outcome I Trim Wt Ila WA Jawnail 234mm 3amp933 o The measurement apparatus and the system to be measures form a large closed system Thus7 do Postulates 1 and 2 1gt Postulate 3 0 Research problem solve the measurement problem 0 best minds in physics have spent a long time thinking about this problem7 and they have not succeeded F Bush wwwresearchgecombushsf Quan ru m sys re m Measuring appara rus Rest of The Universe Thur S c W65 0 Film VG J Quintin g k 217 O O O 0 Suppose we measure W1 in the orthonormal basis l51gt led Then PM l lt61 W l2 Suppose we measure 5 W1 in the orthonormal basis l51gt led Then PM lltej l 6 lwgt l2 He W l2 lt5739 l 6 W lt l 6 9 W Complex conjugate of a is given by e 9 Whose product is The global phase factor a is thus unobservable and we may identify the states W1 and 5 W1 Global versus relative phase factor or amplitude which is important I Rm 4 1m WA lavnail 5am EM 0 Associated to any quantum system is a complex inner product space known as state space 0 The state of a closed quantum systems is a unit vector in state space 0 Note These inner product spaces are often called Hilbert spaces I Trim Wt Ila WA Jamal awe 3M o 0400 00 a01l01 a10l10 all 11 0 Measurement in the computation basis Pmy lam 2 probability for getting the bit string z 0 We now get BIT STRINGS General state of n qubits Zidmw 04m state of n qubits can be written as a superposition over computational basis states corresponding to every possible n bit string 0 Classically7 requires 02 bits to describe the state Perhaps we need a mathematical theory of quantum automata the quantum state space has far greater capacity than the classical one in the quantum case we get the exponential growth the quantum behavior ofthe system might be much more complex than its classical simulation gtgt 7 Yu Manin 1930 I Wm WLMK VWAQ o The intuition it takes a lot more classical information to describe a quantum state than it does qubits o This intuition was one of the bases for the idea that quantum computers might be more powerful than classical o The state space of a composite physical system is the tensor product of the state spaces of the component systems 0 Example two qubit state space is CZ X CZ C4 0 Computational basis states 0 X l0gtgl0gt X 1 1 X 1 0 Alternative notations l0 l0gtgl0 0gtl00gt 0 Properties 2010 W llW8 lwgt lVgt 2W 0 ll1gt lV2gt liq lV2gt lVgt lW1gtlW2gt lVgt lW1gtlVgt lW2gt I Trim 4 11a WA Jamal was 3M Alice Bob o The tensor product 2 may be applied in different contexts to vectors matrices tensors vector spaces algebras topological vector spaces and modules also referred to as the outer product 0 A representative case is the Kronecker product of any two rectangular arrays considered as matrices 0 Example 1 11121 12121 Wu 2 l 11 a2 as l 13 33 33 b4 11124 12124 13124 I Trim ni L 1w WA 1mm was A vector tensor product7 which we use for quantum states7 is of theform 1x2 1 2 7 1x3 2 3 2x2 2x3 I Trim ni L 1w WA 32mm am 0 kn 1m 1122 bu m nummms n a 3111311 3111312 alell 3121312 3121322 azzmz 22 o The tensor product G x H of graphs G and H is a graph such that Q The vertex set of G X H is the Cartesian product VG gtlt VH and 9 Any two vertices u 1 and 11 are adjacent in G X H if and only if u is adjacent With 1 and u is adjacent With 1 o The tensor product is also called the direct product categorical product cardinal product or Kronecker product 0 It is also equivalent to the Kronecker product of the adjacency matrices of the graphs 0 The notation G x H is also sometimes used to refer to the Cartesian product of graphs but more commonly refers to the tensor product I Wm E ME MI vWA mm EMA m Tensor 6 a CO PT VGG S mth f31hid gm sim 39 i in Postulate 4 o If Alice prepares her system in state la and Bob prepares is in state lb then the joint state is la X o Conversely7 if the joint state is la X lb then we say that Alice s system is in the state la and Bob s system is in the state M 59 W 6 M 59 W9 W 0 Alice applies the gate U to her system77 means that U X I is applied to the joint system I leaves Bob unchanged 0 A Blzxgt lwgtAlzgt Blwgt I mm Wt m WA mm ems 9M3 0 Suppose a NOT gate is applied to the second qubit of the state mm ml01gt ml10gt min 0 The resulting state is I amp lm ml01gt mm mun mm mm mm mm 0 Note I keeps rst qubit constant and X applies the NOT to the second qubit Suppose a two qubit system is in the state 08 00 06 11 A NOT gate is applied to the second qubit7 and a measurement performed in the computational basis What are the probabilities for the possible measurement outcomes l I Trim Wt MI wi mam 7mm mm 0 Given Alice s state is la Oz 0 B 1 and Bob s state is W vl0gt5l1gt o W 0011 W 739 MW 0 W a l0gt Bl1gtv l0gt 5 W aleO Byl10gt a6l01gt B6l11gt gt B 0 or 39y 0 V 39 ll 1 would not call entanglement one but rather the characteristic trait of quantum mechanics7 the one that enforces its entire departure from classical lines of thought77 I Trim L 1w WA 2mm saws The proof of this fact is trivial o 1 can be written as a tensor product of such states 0 Multiplying out7 we see that the state must be of the form on 00 Byl10gt a6l01gt B6l11gt The only way this can be equal to W1 is if this second co e icient is zero7 that is7 either 3 0 or 39y 0 O 0 But in the rst case the last co e icient would vanish7 and in the second case the rst co e icient would vanish7 so this must be impossible O From this we conclude that 1 cannot be written as a tensor product I Rm 4 1m WA lavnail 2am QM A closed quantum system is described by a unit vector in a complex inner product space nown as state space The evolution of a closed quantum system is described by a unitary transformation Wgt UN e measure mm in an orthonormal basis E Jew then we obtain the results 739 with probability Pj ME l w l2 The me sur ement disturbs the system leaving it in a state leygt determined by the outcome The state space of a composite physical system is the tensor product of the state spaces ofthe component systems ME mm 0 Which of the following is most true and important about Postulate 3 A Quantum measurement often returns incorrect values B We can never know the qubit amplitudes C We must project a measurement onto an orthogonal space D A unitary operation is required for measurement I Mugs WPLMK 4amp1 0 What is the tensor product of Y 62 and Z 31 namely Y Z 1 7i A i 1 0 0 7i 0 0 0 0 i B 2 0 0 0 0 7i 0 0 0 71 0 0 z 0 0 2 C 2 0 0 0 0 7i 0 0 I Wm r w L m m mm aims 45m o What is the interpretation of the inner product of A and B in two dimensional Euclidean Space A Length of the projection of vector A on to vector B B Length of the projection of vector B on to vector A C Length of A B I imam WL M Jan mum aw game 0 Which of the following states has a relative phase factor A 5w 0 5w 1 B ei9l0gt1 l1gt c ewlogtewm l1gt I Trim WL 1m LNaA will aim 0 Which of the following is the best reason for entanglement as we have discussed thus far A There are hidden variables controlling quantum systems that we have not yet discovered B Tensor products of systems cannot be factored cleanly into component systems starts are inter mixed C Quantum states of distinct systems happen to collapse during measurement in a correlated manner for no apparent reason I m s w L m m mm aw 931433 Read the paper An Introduction to Quantum Computing for Non Physicists77 by Eleanor Rieffel and Wolfgang Polak 1 found in the Announcement page of the course website http www cs rpi edubushscsci4967announc ement html 0 Apply the principles introduced in the last lecture to some illustrative examples superdense coding and a simpli ed quantum cryptography example 0 Visit reVised form of postulates 2 dynamics and 3 measurement I Rm 4 1m WA lavnail Edwina mm o 5 U is is normalized if U is unitary Consider de nition of unitarity7 UUT I so 5 U is and 1UT 89 1W 0 Or take 5 of both sides7 so 3 5 ltS U sgt I Trim Wt Ila WA Jawnail 234m E Rieffel and W Polak Introduction to quantum computing for non physicists Technical Report TR 98 0447 FX Palo Alto Laboratory7 Aug 1998