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