OPEN SOURCE SOFTWARE
OPEN SOURCE SOFTWARE CSCI 4967
Popular in Course
Popular in ComputerScienence
This 49 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 22 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.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/19/15
pdm i ezm m Qune m Ckwmpuiieaif quot kmmmjmwa m mph Stephen F Bush GE Global Research December 17 2008 I WM w L m 4amp1 with aw 11219 Cc use lnfm mat ion Instructor Dr Stephen F Bush7 GE Global Research Phone 387 6827 Email bushszresearchgecom Of ce Hours Thu 750 PM and by appointment Textbook None Course Website http www cs rpi edu bushs Notes Topics QM Basics I Postulates 1 8L 2 M Basics 11 Measuring a Qubit Postulates 3 amp 4 Entanglemen Quantum Mechanics I Superoiense Cooiin Revised Meas Quantum Mechanics II Te1eportation The Spectral Theorem Quantum Com utation and Computer Science I Computational Complexity Theory chr niring Thesis Quantum Computation and Computer Science 11 The Size of P NP The Circuit Model Mioiterm Exam g urement Postulate Week Topics Notes 8 Quantum Circuits I Models of Quantum Computation Deutsch s roblem 9 Quantum Circuits II Universality Quantum Complexity Classes A Stochastic Quantum omputer 10 Quan um oise Density matrices Fidelity Measures e II view m Information Theory I Nov 20 ata Compression ta Co pression Quantum Information Theory II No class Nov 27 OPY eliability r a R to Qua lation nt m Operators Zero Error Information Theory Graph Entropy Final Final Exam Dec 11 I l Component Weight Total Grade Midterm nal 30 each 60 Assignments 0 100 Scribe Notes 0 100 igtClicker quizes Participation 0 100 I WEsWM ire Outline e Schumacher Compression 9 Classical Error Coding 0 Linear Codes 9 Quantum Error Coding a Group Theory 0 Unitary Dynamics and Stabilizers 0 Gave de nitions of entropy both classical and quantum o Introduced data compression both classically and its connection with entropy o Introduced some of the basic properties of entropy which has application to entanglement quantum error correction and quantum communication I mm vi mm L M WA Maw ilz al Versi 1 0 Assume 71 bits m1 zn z 6 01 were sampled iid according to probabilities 190191 0 Then m1 mn may be compressed to nHp 0 1 Where Hp 7 2p logpi i0 0 For any 6 6 gt 0 and sufficiently large n for any n 2 6 n E 1 n 0 There exists a compression scheme compresses m1 ml to 3917 quot7 yAn And the m1 zn can be recovered from yl yWL with probability greater than 1 7 e I My m L Ml WA may O into the qubit domain Cenaa io 0 Assume a nite set of qubits S l111gt with underlying probabilities p pl7 pm 0 Thus7 57 p de nes an ensemble of states 0 Let la1gt la be compressed to 31 MAW 0 Note that the n 7 n qubits are discarded outside the typical sequence and assumed to be l00gt I mm as mm L In WA 11mm am 923 o First7 generate our sequence to be compressed7 log la 0 Transform to its compressed form 31 ngt 0 To uncompress7 rst tensor with the number of discarded qubits assumed to be zero7 31 ngt l00gt 0 Run the decompression algorithm on 31 ngt l00gt to obtain loluu l The delity l 0104L human 2 is the probability that we reconstruct the original sequence human 0 I my w L In WA mm am mg 0 Random choices in the original generation of the sequence to be compressed7 a1gtangt o Randomness from the measurement operation of oluam V 11 Neumquot 1111 entro Recall the 11139 tur r v f 0 Our random qubit sequences de ned by 57 p can be represented as a mixed state in a density matrix W P 219139 WW Ml 13971 5P polog 0 o Sp Hp with equality only when the states are mutually orthogonal o The maximum qubit compression that can be obtained for n qubits is nSp 0 Instead of a typical sequence7 think of a typical subspace A 0 We want a high probability of projecting our original sequence la1gt la onto A o Thus7 A is of dimension WSW o The compression algorithm needs to transpose the subspace A onto a smaller block of nSp qubits I My i mm L In WA mm a va 5313 0 Suppose S 17 LZJ2 where W11 0 and w 0gt1gtandp1p2 5 g i 4 ph MH H assuming bases 0 7 1 3 1 7r op 44tan8 1 10 7r inthenewbases 0 Ziltang o 0 Cosg 0sin l o 1 7sing 0cos l 0 Both states 111 and 112 have large overlap on the basis state 0 W O H COS 0 Both states 111 and 112 have small overlap on the orthogonal basis state 1 o llt il1 gtlsin o The 1 appears to be less important77 to the representation of the states I My m L Ml WA may a la Jo Conlpl ess 0 Consider all possible 71 qubit strings possible from S o lzn1z0gt lzn1gt lm0gt where zn1 m0 6 l0 gt l1 gt 0 Each lzn1z0gt can be interpreted as a binary number7 thus denoted as for z E 07 2 7 1 The overlap of with states in S is l m 5 l cosm sinn mg where m is the number of 0 s in the binary representation of z 0 0 Basis states with a large number of 1 s are relatively unimportant o Thus7 truncate to the typical subspace A comprised of all states such that the binary number x contains a proportion of 1 s less than Sp lt 0601 mm wtm WA may amt wag 0 0 O Consider to messages X and Y composed of symbols from the same alphabet The Hamming Distance between X and Y is de ned as the number of positions Where the symbol in X does not match the corresponding symbol in Y m A mic wilh pool dimw mpch by A and Wm gmd distance pmpcnica Error detection and correction require that valid code words valid messages have a large Hamming Distance otherwise a small error moves another to anther valid codeword and x cndlMirds o Mncn cmm s gecombushsf 6mm 33 c lm PM Smith g cdle 38429 Hamming example I 0 Notice how parity x is distributed 39 3 among the data 1 N 2 bits D Data bit P Parity bit 9 With a valid code7 1 parity in each circle is properly maintained Hannning example HI WHEN I I I 6 H 1 6 397BIT CODEWORD a An example with 11 1 0 EVENPARII Y Noml an erroneous bit LMHlmy39 dEVENPARII Y 0qu 0 1110 EVENPARITY Noml 1 Hamming example 1 a Hamming distance of three a Only 000 and 111 are valid codewords o The correct codeword is near any single erroneous bit ip 011 111 o Append n 7 k check bits that are functions of the k information bits 0 Example 71 771 4 000 1 w H HHO pow OOH OHO HOO Linear Codes Line or c Using 1d 39 ect error 0 Repeat the operation at the sender assume H is known Received data H b1 b2 syndrome 1011100b3 0 1101010b40 0111001b5 0 56 b 4 0 If not 0 then an error has occurred Ideally the precise location of the error can be found via 6 H18 0 Unfortunately H not invertible so work arounds are explained in the text 0 How could we make H invertible and What would be the implications F Bush wwwresearchgecombushsf 6 VXESQ FEM illCG ng lLi lD 244ng 1n Quantum E 39 39 ling I 1 rlheory Simplest coding 0 Assume our bisymmetric channel nq Example Binary symmetric channel 1 o 0 gt P 11 1 0 and simply repeat transmission until any error is overcome counting the majority of received bits as the correct one 0 So if we send three times then this scheme fails if we receive less than two correct bits 0 Fails with probability 1921 p p3 so probability of error is 3192 2193 F Bush wwwresearchgecombushsf Thu 6 750 Pl l V l l South Slide 2549 T Quantum version the three qubit bit ip 0 Starts With a similar concept to majority voting 0 a Ogt b 1gt is encoded as a 000gt b 111gt o Assign three qubits for one logical qubit subscript L for Logical W gt 0Lgt 3 low I1 gt 1Lgt 3 I111 input xllgt 0gt output Thu 6 Diagno 39 0 Measurement provides the error syndrome based upon the projection of the measurement 0 P0 E 1000 0001 1111 1111 no error 0 P1 E 1100 1001 1011 0111 bit ip on qubit one 6 P2 E 1010 0101 1101 1011 bit ip on qubit two 9 P3 E 1001 0011 1110 1101 bit ip on qubit three So measure 1 P to determine each syndrome above Measurement does not cause change to the transmitted state 0 Measurement does not reveal any information about the state only the type of error Simply use the information from the projection measurements to decide Which bit to ip in order to restore the qutrit Perfect error correction for up to one qubit error I l Phase ip 0 Quantum systems have more possible errors than just the bit ip7 X7 eg phase ip7 Z 0 So assume Z is applied with probability p 0 Thus state 1 0 M1 is corrupted to become 1 0 7 b 1 no classical equivalent 0 However7 it is easy to change the phase ip to a bit ip by changing basis Phase ip cont d 0 Move from computational basis 0gt 1gt to gt E 0gt 1gt a gt E 0gt 1gt 0 Then Z takes gt to gt and an analogous technique can be used F Bush wwwresearchgecombushsf Thu 6 750 Pl l VCC South Slide 2949 The Shor code o Combines the quantum bit ip and phase ip codes into one 0 First encode the qubit as per phase ip 0 a H gt7 W A if i gt o Next7 encode as per hit ip code H a 000 111gt and if a 000 7 111gt 0 Result is a nine qubit code a 0gt A 0Lgt E 000gt111gt000gt111gt000gt111gt 2 0007111 0007111 0007111 9 1gtH 1LgtE W 0 Example consider the state of tWo qubits 7 l00gtl11gt W 7 0 Notice that X1X2 W W Z1Z2 W W 0 Thus is stabilized by these operators 0 Reminder the subscript on the operator is the qubit being operated upon 0 Sometimes easier to Work With the operators that stabilize the state rather than the state itself 0 Requires cleVer use of group theory I l 0 Why Needed to understand stabilizers 0 Lots of de nitions to understand rst A group G7 is a non empty set C with a binary group multiplication operation such that 0 91 92 E G closure 0 V91792 6 G7 91 92 93 91 92 93 associativity o V91792793 G7356Gst VgEGgeegg identity 0 VgEG7396G73971 Gst gg 1eandg 1ge inverses 0 We may write 91 92 simply as 9192 mmswmmlgm swims massagesm we 392 it 39 011s cont 1 De39finitign Order Qf group The order of a nite group is simply the number of elements it contains id39n lled Ab I mwmm ian group o The set of integers modulo n or Zn7 with the multiplication operation of modular addition is an Abelian group a Satis es example using 71 3 Closure 2 3 l associativity 1 2 3 2 1 2 3 identity I 0 z mod n z inverse n 7 1 since VI 6 G I n 7 z 0 mod n 0000 De n it ion Or d r of anelement The order of an element 9 E G is the smallest positive integer r such that 97 g is multiplied with itself r times using the group de ned multiplication operator equals the identity element 5 A subgroup H of G is a subset of G which forms a group under the same group multiplication operation as G I m If 91 and 92 are elements of G7 the conjugate of 92 with respect to 91 is the element gflgggl 3919 If H is a subgroup of G7 then it is known as a normal subgroup if g ng H for all g E G De nitibn 39Conjug V Class The conjugacy class Gm of an element x in a group G is de ned by GE Eg 1mglg E G I MEL o The Pauli matrices with factors i1 and ii G1 E iL ii iX iiX iY iiY iZ iiZ 0 Forms a group under matrix multiplication for a single qubit o For n quloits7 the group consists of all n fold tensor products of Pauli matrices o Simpli es the study of groups by providing a compact representation 0 a la Kolmogorov Complexity7 the more compactly one can describe something7 the better one understands it A set of elements 91 quot791 in group G is said to generate the group G if every element of G can be written as a product of possible repeated elements from the list 91 quot791 written as G Elt 917 quot791 gt I mbwwwmzsm am as g Cau vgugt U G1 lt X7 ZJI gt since every element in G can be written as a product of X7 Z7 and i 0 Every group has a set of log GD generating elements I Pmquot 8 pieiyaxy memng D ug viaa up A cyclic group contains an element a such that any element 9 E G can be expressed as a for some integer n a is known as a generator of G Thus7 G lt a gt De nition C 39 1C subgroup A cyclic subgroup H generated by g E G is the group formed by 579792 quot797 1 where r is the order of g In other words7 H lt 9 gt I WEsWM o A matrix group is a set of matrices in Mn7 where each matrix is n x n that satisfy the properties of a group under matrix multiplication A representation p of a group G is de ned as a function that maps G to a matrix group7 preserVing group multiplication g E G is mapped to pg 6 Mn such that 9192 93 Many to one mapping is a homomorphism7 one to one is an isomorphism I T151133 WW Elm 333iquot n in n A representation p that maps into Mn has dimension dp n 0 These are matrix representations though there are more general types of representations I F 3 group de ned by My 257697 for g E G The character has the following properties 9 xI n G lX9l S n G lxgl 71 implies g 5w 9 X is constant on any given conjugacy class of G gt494 y 9 xg is an algebraic number for all g I mbwwwmzsm 3am gr g Two matrix groups are equivalent if they are isomorphic and corresponding elements under the isomorphism have the same character I Fmquot 5 De nitions 0 Suppose S is a subgroup of Gn7 the 71 fold Pauli matrix group V5 will be the set of n qubit states that are xed by every element of S V5 is the vector space stabilized by S and S is the stabilizer of the space V5 V5 is a subspace of the n qubit state space V5 is the intersection of the subspaces xed by each operator in S iguangrguza we Ewim i 35wm 39 w Assume n 3 qubits and S L Z1Z27 Z2Z37 Z1Z3 o Subspace xed by Z1Z2 is spanned by i0007 i0017 1107 111 o Subspace xed by Z2Z3 is spanned by i0007 1007 i0117 111 0 V5 is the subspace spanned by OOO and 111 I F o In the previous example7 the generator for S I7 Z1Z27 Z2Z37 Z1Z3 can be written S lt Z1Z27 Z2Z3 gt 0 because Z1Z3 Z1Z2Z2Z3 and I Z1Z22 u quotagain compact representation 1mm m a w mus Wimp 0 Suppose unitary U is applied to vector space V5 stabilized by the group S o Then7 for any element 9 E S U W1 Ug W1 UgUlU W1 0 Thus7 UVS is stabilized by USUf o If 91 quot791 generate S7 then UglUl7 UglUJr generates USUT o Bottom line To compute the change in the stabilizer7 one can compute how the generators of the stabilizers are affected Consider that HXHT z HYHT 71 and HZHT X Then it should be clear that after a Hadamard gate is applied to the state stabilized by Zl07 the resulting state will be stabilized by Tm 111 um w MAM Elma Finale 0 Final exam VCC South Thu Dec 11 6 8PM 0 Final projects code7 writeup7 and results due on that day 9 It s been fun
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'