DOC PREVIEW
UW CSEP 590 - Lecture Notes

This preview shows page 1-2-3-4-28-29-30-31-57-58-59-60 out of 60 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 60 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 60 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 60 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 60 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 60 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 60 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 60 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 60 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 60 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 60 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 60 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 60 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 60 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60CSEP 590tv: Quantum ComputingDave BaconAug 3, 2005Today’s MenuPublic Key CryptographyShor’s AlgorithmGrover’s AlgorithmAdministriviaQuantum Mysteries: EntanglementAdministriviaHand in HW #5.Pick up HW solutions.Pick up the Take Home Final! Two weeks to complete. No collaboration. Extra credit problem based on next week’s lectureon entanglement.ReviewDavidDeutschRichardJozsa1992: Deutsch-Jozsa Algorithm Exact classical q. complexity:Bounded error classical q. complexity:Exact quantum q. complexity:1993: Bernstein-Vazirani Algorithm(non-recursive)UmeshVaziraniEthanBernsteinExact classical q. complexity:Bounded error classical q. complexity:Exact quantum q. complexity:Reviewn qubitsDeutsch-Jozsa AlgorithmBernsetein-Vazirani AlgorithmReviewDanSimon1994: Simon’s AlgorithmBounded error classical q. complexity:Bounded error quantum q. complexity:(first exponential separation)Given: A function with n bit strings as input and one bit asoutputPromise: The function is guaranteed to satisfyProblem: Find the n bit stringReview n qubits n qubitsSimon’s algorithmMultiple runs to find sToday:FactoringOne Time PadsAliceBob0010101111010001Random n bit string0110110011100101Alice’s message001010111101000101000111001101000110110011100101secretkeysecretkeyEvecannot learn messagePublic Key CryptographyInteresting history:1st schemes “known in public” where put forth byDiffie and Hellman in 1976 (key exchange) andRivest, Shamir and Adleman in 1978 (encryption algorithm)(based on work by Merkle in 1974, published 1978)However, it now appears that the British researchers working forBritish intelligence (GCHQ) were actually the first to discover these protocols, but their work was classified at the time!Clifford Cooks in 1973 (encryption algorithm)Malcolm Williamson in ~1973 (key exchange)(based on work by James Ellis in the late 1960s.)Computational ComplexityP : decision problems which can be solved without error inpolynomial time on a deterministic classical Turing machine.Decision problems: problem with a yes/no answer.Polynomial time: worst case bounded by a polynomial in the size of the problem.Examples of problems in P:Perfect matching: does a given graph have a perfect matching?Primes: is a given number a prime number?Linear Equalities: Given an integer n x d matrix A and an integer n x 1 vector b, does there exists a rational d x 1 vector x>0 such that Ax=b?Computational ComplexityNP : decision problems which can be solved without error ina polynomial time on a classical nondeterministic Turing machine. Shorthand, decision problems which, given a solution, you can verify this solution in polynomial time on a deterministic classical Turing machine.Examples of problems in NP:Perfect matching: does a given graph have a perfect matching?Satisfaction: does a given boolean function have a satisfyingassignment? Given f(x1,x2,…,xn), does there existx={0,1}n such that f(x)=1?Minesweeper: Given a partially solved Minesweeper board, doesthere exist an assignment of mines which can give riseto this board?One Million Dollars NP PNP=PORNP – Hard: Problems which have the property that for every problem in NP there is a polynomial time reductionto this problem.NP – Complete (NPC): NP – Hard and in NP. NPC PNP=NPC=POR NPPublic Key Cryptography1. There probably exist computational problems that are HARD.2. Can we use these to perform secure cryptography by basingthe security of the problem on the difficulty of the hard problem?If we make the hard problem big enough, baring a breakthroughin the computational complexity of the problem, or in computerhardware technology, the cryptography will be securePublic Key Cryptography RoughlyAliceBobInstructions for howto make her lock.Bob’s secretdocumentsThis is (very roughly) what happens in public key cryptographyAssume: very hard to design key from instructions to make lockPublic Key Encryption RSAAliceBob1. Alice generates two random large primes, and 2. Alice chooses a number which is coprime with . 3. Alice computes such that Public Key: Private Key:Public Key Encryption: RSAAliceBobPublic Key: Private Key: Public Key: Bob’s message: (FLT)(CRT)Public Key Encryption: RSAAliceBobPublic Key: Private Key: Bob’s message: Bob, using public key can encryptmessage.But decrypting without the privatekey is (thought) to becomputationally hardAlice, using private key, candecrypt the messagePublic Key Encryption: RSAAliceBobPublic Key: Private Key: Bob’s message: If we could factor, then we could compute from which you could use to find Then we just use the standard decryption: Factoring can be used to break RSAFactoring NPC P NPFactoring: Is one of the factors less than k?Difficulty?Probably: P NP coNP NPC coNPCcoNP: efficiently verifiable that NO solution to problem exists.Shor’s Algorithm188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059472772146107435302536223071973048224632914695302097116459852171130520711256363590397527398075086424064937397125500550386491199064362342526708406385189575946388957261768583317Best classical algorithmtakes timeShor’s quantum algorithm takes timePeterShor1994Shor’s AlgorithmWhat were the key insights which Shor used?Simon’s problem work’s because the function has a symmetry:In this case the symmetry is a symmetry Shor became interested in different symmetries and in particular symmetries of “the place where we do addition modulo N”Period FindingGiven: A function from 0,1,…,N-1 to some n bit numbersPromise: The function is guaranteed to satisfyProblem: Find the hidden period periodShor’s AlgorithmWhat were the key insights which Shor used?1. Period finding2. Period finding can be perform efficiently on a quantum computer.3. Period finding can be used to factor integersOrder-Finding and FactoringFactor Nchoose x coprime to N (Euclid’s algorithm for gcd)Order


View Full Document

UW CSEP 590 - Lecture Notes

Documents in this Course
Sequitur

Sequitur

56 pages

Sequitur

Sequitur

56 pages

Protocols

Protocols

106 pages

Spyware

Spyware

31 pages

Sequitur

Sequitur

10 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?