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 25Quantum ComputingJohn LavigneCOT 4810April 15, 2008History, Future, and AlgorithmsSummaryIntro to Quantum PhysicsIssues with Practical ApplicationQC HistoryQC LimitsDeutsch AlgorithmShor's AlgorithmGrover's AlgorithmQuantum Physics 101To understand how Quantum Computing works, we need to understand some things about atomsDon't worry, Quantum Physics isn't as hard as you think!Quantum Physics 101Quantum Mechanics - a theory of the mechanics of atoms, molecules, and other physical systems that are subject to the uncertainty principleQuantum Physics 101Bohr Model of the AtomElectrons spinning around a Proton and Neutron CoreQuantum Physics 101Spinning of atoms can represent bitsSpinning down represents 0Spinning up represents 1Spinning both ways is called a “super-position”These bits is called “qubits”Schrödinger's CatQuantum Physics 101These bits is called “qubits”Using several of these qubits together is the basis of a quantum computerKet NotationImmediate ProblemsHeisenburg Uncertainty PrincipleAny Interference will change the value of the qubit.This causes the information to become lost.This known as decoherenceTo solve this, we use a property known as “quantum entanglement”Two entangled particles will always have one particle spinning up and the other downBy taking advantage of this, it is possible to predict the value of a given atomWhat these Algorithms can doNo Magic SolutionsNP-Complete problems are still difficult. Don't try to find a single solutionMake assumptions about the entire set of solutionsThe Deutsch AlgorithmGiven a function f: {0,1} -> {0,1}Can be either constant or balancedCan determine which in only one stepFurther iterations developedComputationally InsignificantProved the advantages to QC techniques in certain situationsShor's Algorithm1994 – Peter Shor, Mathematician at MITUsed to factorize large numbers2001 – Algorithm “proved” on a 7-qubit machine15 factored in 5 and 315 = 1111 => 4 qubits requiredShor's AlgorithmPart 1set all Qubits to their superpositionShor's AlgorithmPart 2N is the number we want to factorize X is a random number, 1 < X < N-1X is raised to the power of Register A and divided by NThe remainder is placed into Register BShor's AlgorithmPart 2 - cont.Register A Register B0 11 22 43 84 15 26 47 8Register A Register B8 19 210 411 812 113 214 415 8Shor's AlgorithmPart 3Take the frequency of repitition, f, and use it in this equation:P = X^(f/2) -1The answer is not guaranteed to be correct, but it is easy to check the answer multiply it out againGrover's AlgorithmUsed to search databasesMany practical usesKnowing a phone number and no name, find the person in a phone bookAssumes a lack of knowledge about the order of itemsGrover's Algorithm“similar to dropping multiple pebbles in a pond so that the waves cross and interact in a particular way” (Maney)“undesired answers cancel out”Grover's AlgorithmClassical Computer: O(N)Average: N/2Quantum Computer: Average: sqrt(N)Averages for a DB of N=1,000,000Classical computer: 500,000 searchesQuantum computer: 1000 searchesGrover's AlgorithmSet all qubits to their super positionChecks all possible answers at onceMade possible through Quantum ParallelismWorks by “increasing the amplitude of the states that carry the desired result” (Lavor)Other ApproachesQutrits?|0>, |1>, and |2>Takes advantage of a base e systemUsing Photons instead of AtomsHistory1982 – First time Quantum Theory applied to computers1989 – First Quantum Algorithm (Deutsch)1994 – Shor's Algorithm developed1996 – Grover's Algorithm developed1998 – 2-Qubit register developed2001 – Shor's Algorithm ran on 7 bit QC at Los Alamos labsMay 2006 – Experimental 12-bit QC built byReferences, cont.Jonietz, Erika. "Quantum Calculation." Technology Review, July 2005. http://www.technologyreview.com/Infotech/14591 Aaronson, Scott, The Limits of Quantum, Scientific American, Mar2008, Vol. 298 Issue 3, p62-69, 8pCastelvecchi, Davide, 15 = 3 x 5, Science News, 12/8/2007, Vol. 172 Issue 23, p356-358, 3pBone, Simone and Matias Castro. "A Brief History of Quantum Computing." Imperial College, London, Department of Computing. 1997. http://www.doc.ic.ac.uk/~nd/surprise_97/journal/vol4/spb3/"12-qubits Reached In Quantum Information Quest." Science Daily, May 2006. http://www.sciencedaily.com/releases/2006/05/060508164700.htm Hagar, Amit “Quantum Computing” Stanford Encyclopedia of Philosophy, Feb 2007http://plato.stanford.edu/entries/qt-quantcomp/Lavor, C., Manssur, L.R.U, “Grover's Algorithm: Quantum Database Search*”, Universidade do Estado de Rio de Janeiro, Feb 2008, http://arxiv.org/PS_cache/quant-ph/0301/0301079v1.pdfAny Questions?Homework1. What are some possible applications of Quantum Computers?2. What are the names of the two Algorithms presented here?3. What are the three possible states of an
View Full Document
Unlocking...