Transcription
The past, present, and future history of quantumcomputingAshley Montanaroashley.montanaro@bristol.ac.ukSchool of Mathematics, University of BristolBristol, UK25 November 2015Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 1/29
Quantum computingA quantum computer is a machine designed to use the principles ofquantum mechanics to do things which are fundamentally impossible forany computer which only uses classical physics.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 2/29
Quantum computingA quantum computer is a machine designed to use the principles ofquantum mechanics to do things which are fundamentally impossible forany computer which only uses classical physics.This lecture will discuss the history of quantum computing, including:1. The basic concepts behind quantum mechanics2. How we can use these concepts for teleportation and cryptography3. Quantum algorithms outperforming classical algorithms4. Experimental implementations of quantum computing5. Commercialisation of quantum technologiesAshley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 2/29
The Solvay conference 1927Pic: Wikipedia/Solvay conferenceAshley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 3/29
The Solvay conference 1927Erwin Schrödinger Werner HeisenbergPaul DiracMax PlanckMarie CurieAlbert EinsteinPic: Wikipedia/Solvay conferenceAshley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 3/29
Key ingredients of quantum mechanicsQuantum mechanics has certain bizarre features which do not occur instandard, or “classical” physics, such as:Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 4/29
Key ingredients of quantum mechanicsQuantum mechanics has certain bizarre features which do not occur instandard, or “classical” physics, such as:1. Superposition. If a system can be in state A or state B, it can also bein a “mixture” of the two states. If we measure it, we see either A or B,probabilistically.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 4/29
Key ingredients of quantum mechanicsQuantum mechanics has certain bizarre features which do not occur instandard, or “classical” physics, such as:1. Superposition. If a system can be in state A or state B, it can also bein a “mixture” of the two states. If we measure it, we see either A or B,probabilistically.2. Collapse. Any further measurements will give the same result.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 4/29
Key ingredients of quantum mechanicsQuantum mechanics has certain bizarre features which do not occur instandard, or “classical” physics, such as:1. Superposition. If a system can be in state A or state B, it can also bein a “mixture” of the two states. If we measure it, we see either A or B,probabilistically.2. Collapse. Any further measurements will give the same result.3. Entanglement. There exist systems of multiple parts which cannot bedescribed only in terms of their constituent parts.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 4/29
Key ingredients of quantum mechanicsQuantum mechanics has certain bizarre features which do not occur instandard, or “classical” physics, such as:1. Superposition. If a system can be in state A or state B, it can also bein a “mixture” of the two states. If we measure it, we see either A or B,probabilistically.2. Collapse. Any further measurements will give the same result.3. Entanglement. There exist systems of multiple parts which cannot bedescribed only in terms of their constituent parts.4. Uncertainty. There are pairs of measurements where greater certaintyof the outcome of one measurement implies greater uncertainty of theoutcome of the other measurement.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 4/29
Key ingredients of quantum mechanicsQuantum mechanics has certain bizarre features which do not occur instandard, or “classical” physics, such as:1. Superposition. If a system can be in state A or state B, it can also bein a “mixture” of the two states. If we measure it, we see either A or B,probabilistically.2. Collapse. Any further measurements will give the same result.3. Entanglement. There exist systems of multiple parts which cannot bedescribed only in terms of their constituent parts.4. Uncertainty. There are pairs of measurements where greater certaintyof the outcome of one measurement implies greater uncertainty of theoutcome of the other measurement.The basic idea behind quantum computing is to use these effects to ouradvantage.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 4/29
Schrödinger’s catPic: Wikipedia/Schrodinger’s catAshley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 5/29
The qubit: the basic building-block of quantumcomputersIQuantum mechanics deals with very small systems, like atoms orphotons (“particles of light”).IA quantum system which has two distinct states is called a qubit.IJust as classical computers operate on bits, quantum computersoperate on qubits.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 6/29
The qubit: the basic building-block of quantumcomputersIQuantum mechanics deals with very small systems, like atoms orphotons (“particles of light”).IA quantum system which has two distinct states is called a qubit.IJust as classical computers operate on bits, quantum computersoperate on qubits.For example, one property of a photon is polarisation: a photon can beeither vertically or horizontally polarised ( or ), so this gives us a qubit.vs.01Pic: coins-of-the-uk.co.ukAshley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 6/29
Non-locality and entanglementImagine we have a pair of entangled qubits:Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 7/29
Non-locality and entanglementIEven if we move one of the qubits to the Moon, the global state of thetwo qubits cannot be described solely in terms of the individual stateof each of them!IIn particular, if we measure one of the qubits, this apparentlyinstantaneously affects the other one.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 7/29
Quantum cryptographyI1984: Bennett and Brassard propose to use quantum mechanics forsecure distribution of cryptographic keysI1989: Quantum key distribution demonstrated experimentallyAshley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 8/29
Quantum cryptographyI1984: Bennett and Brassard propose to use quantum mechanics forsecure distribution of cryptographic keysI1989: Quantum key distribution demonstrated experimentally &% && AliceIBobThe basic idea is to use the principles of uncertainty and collapse todetect an eavesdropper.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 8/29
Quantum cryptographyI1984: Bennett and Brassard propose to use quantum mechanics forsecure distribution of cryptographic keysI1989: Quantum key distribution demonstrated experimentally &% && AliceEveBobIThe basic idea is to use the principles of uncertainty and collapse todetect an eavesdropper.IIf Eve wants to read Alice’s message to Bob, she has to measure it –and that can be detected.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 8/29
Teleportation: using entanglement to our advantageII1993: Quantum teleportation is proposed1997-8: Quantum teleportation demonstrated experimentallyRichard Jozsa, Bill Wootters, Charlie Bennett,Gilles Brassard, Claude Crépeau, Asher Peres,cat.Pic: www.cs.mcgill.ca/ crepeau/tele.htmlAshley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 9/29
AliceBobThe teleportation protocol proceeds as follows:1. Alice and Bob start by sharing a pair of entangled qubits.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 10/29
mAliceBobThe teleportation protocol proceeds as follows:1. Alice and Bob start by sharing a pair of entangled qubits.2. Alice performs a measurement involving both her half of the pair, andthe qubit she wants to send.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 10/29
mmAliceBobThe teleportation protocol proceeds as follows:1. Alice and Bob start by sharing a pair of entangled qubits.2. Alice performs a measurement involving both her half of the pair, andthe qubit she wants to send.3. She sends the measurement result m to Bob.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 10/29
mmAliceBobThe teleportation protocol proceeds as follows:1. Alice and Bob start by sharing a pair of entangled qubits.2. Alice performs a measurement involving both her half of the pair, andthe qubit she wants to send.3. She sends the measurement result m to Bob.4. Bob performs a correction based on the measurement result.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 10/29
mmAliceBobThe teleportation protocol proceeds as follows:1. Alice and Bob start by sharing a pair of entangled qubits.2. Alice performs a measurement involving both her half of the pair, andthe qubit she wants to send.3. She sends the measurement result m to Bob.4. Bob performs a correction based on the measurement result.At the end of the protocol, the state of Alice’s qubit has been transferred toBob’s qubit.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 10/29
The dawn of quantum computingThere is no efficient general-purpose method known to simulate quantumphysics on a standard computer.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 11/29
The dawn of quantum computingThere is no efficient general-purpose method known to simulate quantumphysics on a standard computer.I1982: Nobel Laureate Richard Feynman asked whether quantumphysics could be simulated efficiently using a quantum computer.“If you want to make a simulation ofnature, you’d better make it quantummechanical, and by golly it’s a wonderful problem, because it doesn’tlook so easy.”Pic: Wikipedia/Richard FeynmanAshley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 11/29
The dawn of quantum computingBut nobody knew what such a quantum computer would look like. . .Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 12/29
The dawn of quantum computingBut nobody knew what such a quantum computer would look like. . .I1985: David Deutsch proposes the mathematical concept of thequantum Turing machine to model quantum computation.“Computing devices resembling theuniversal quantum computer can, inprinciple, be built and would havemany remarkable properties not reproducible by any Turing machine.”Pic: www.physics.ox.ac.uk/al/people/Deutsch.htmThis put the concept of quantum computing on a sound theoretical footingfor the first time.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 12/29
The dawn of quantum computingBut could a quantum computer actually outperform a classical computer?Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 13/29
The dawn of quantum computingBut could a quantum computer actually outperform a classical computer?I1992: David Deutsch and Richard Jozsa give the first such example.“The quantum computation solvesthe problem with certainty in exponentially less time than any classicaldeterministic computation.”Pic: www.damtp.cam.ac.uk/people/r.jozsaAshley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 13/29
The dawn of quantum computingBut could a quantum computer actually outperform a classical computer?I1992: David Deutsch and Richard Jozsa give the first such example.“The quantum computation solvesthe problem with certainty in exponentially less time than any classicaldeterministic computation.”Pic: www.damtp.cam.ac.uk/people/r.jozsaI1993: Ethan Bernstein and Umesh Vazirani show that quantumcomputers can be significantly faster than classical computers, even ifthe classical computer is allowed a small probability of error.I1994: Dan Simon shows that quantum computers can beexponentially faster.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 13/29
The dawn of quantum computingBut could a quantum computer actually outperform a classical computer?I1992: David Deutsch and Richard Jozsa give the first such example.“The quantum computation solvesthe problem with certainty in exponentially less time than any classicaldeterministic computation.”Pic: www.damtp.cam.ac.uk/people/r.jozsaI1993: Ethan Bernstein and Umesh Vazirani show that quantumcomputers can be significantly faster than classical computers, even ifthe classical computer is allowed a small probability of error.I1994: Dan Simon shows that quantum computers can beexponentially faster.These problems were all somewhat contrived. . .Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 13/29
Shor’s algorithmBut could a quantum computer solve a problem which people actually careabout?Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 14/29
Shor’s algorithmBut could a quantum computer solve a problem which people actually careabout?I1994: Peter Shor shows that quantum computers can factorise largeintegers efficiently.Given an integer N p q for primenumbers p and q, Shor’s algorithmoutputs p and q.No efficient classical algorithm for thistask is known.Pic: physik.uni-graz.atAshley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 14/29
Shor’s algorithmBut could a quantum computer solve a problem which people actually careabout?I1994: Peter Shor shows that quantum computers can factorise largeintegers efficiently.Given an integer N p q for primenumbers p and q, Shor’s algorithmoutputs p and q.No efficient classical algorithm for thistask is known.Pic: physik.uni-graz.atShor’s algorithm breaks the RSA public-key cryptosystem on whichInternet security is based.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 14/29
Grover’s algorithmOne of the most basic problems in computer science: unstructured search.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 15/29
Grover’s algorithmOne of the most basic problems in computer science: unstructured search.IImagine we have n boxes, each containing a 0 or a 1. We can lookinside a box at a cost of one query.0Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum Computing010001Slide 15/290
Grover’s algorithmOne of the most basic problems in computer science: unstructured search.IImagine we have n boxes, each containing a 0 or a 1. We can lookinside a box at a cost of one query.0I0100010We want to find a box containing a 1. On a classical computer, thistask could require n queries in the worst case.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 15/29
Grover’s algorithmOne of the most basic problems in computer science: unstructured search.IImagine we have n boxes, each containing a 0 or a 1. We can lookinside a box at a cost of one query.0II0100010We want to find a box containing a 1. On a classical computer, thistask could require n queries in the worst case.1996: Lov Grover gives a quantum algorithm which solves thisproblem using about n queries.The square-root speedup of Grover’salgorithm finds many applications tosearch and optimisation problems.Pic: Bell LabsAshley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 15/29
Quantum simulationThe third important algorithmic development in the late 90’s was theresolution of Feynman’s conjecture.I1996: Seth Lloyd proposes a quantum algorithm which can simulatequantum-mechanical systems.“A quantum computer with a few tens ofquantum bits could perform in a few tens ofsteps simulations that would require Avogadro’s number [6 1023 ] of memory sitesand operations on a classical computer.”Pic: MITAshley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 16/29
Quantum simulationThe third important algorithmic development in the late 90’s was theresolution of Feynman’s conjecture.I1996: Seth Lloyd proposes a quantum algorithm which can simulatequantum-mechanical systems.“A quantum computer with a few tens ofquantum bits could perform in a few tens ofsteps simulations that would require Avogadro’s number [6 1023 ] of memory sitesand operations on a classical computer.”Pic: MITSimulating quantum mechanics has applications to drug design, materialsscience, high-energy physics, . . .Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 16/29
The rise of quantum computingFollowing the publication of these algorithms, there was an explosion ofinterest in quantum 0052010No. of published papers using phrase “quantum computer” per year (Google Scholar)Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 17/29
But can we actually build one?Building a large-scale quantum computer is extremely challengingbecause of decoherence.If a quantum computer interacts with the outside world and is subject tonoise, it can lose its “quantumness” and behave like a classical computer.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 18/29
But can we actually build one?Building a large-scale quantum computer is extremely challengingbecause of decoherence.If a quantum computer interacts with the outside world and is subject tonoise, it can lose its “quantumness” and behave like a classical computer.I1995-6: Peter Shor and Andrew Steane devise quantumerror-correcting codes which can be used to fight decoherence.The most optimistic current estimates are that a fault-tolerant quantumcomputer could be built from components which have an error rate of up toabout 1%.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 18/29
Quantum computing technologiesIt isn’t clear yet which technology will be used to build a large-scalequantum computer. Some examples:Photonic circuitsSuperconducting electronicsTrapped ionsPics: University of Bristol, UCSB, NISTAshley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 19/29
Some experimental progress1997-8Quantum teleportation demonstrated [Innsbruck, Rome, Caltech, . . . ]1998Quantum error-correction demonstrated [MIT]2001Shor’s algorithm factorises 15 3 5 using NMR [IBM]20058 qubits controlled in ion trap [Innsbruck]2008Photonic waveguide quantum circuits demonstrated [Bristol]2010Entangled states of 14 qubits created in ion trap [Innsbruck]201221 3 7 factorised using quantum optics [Bristol]2012100µs coherence for superconducting electronic qubits [IBM]2013First publicly-accessible “quantum cloud” [Bristol]2014Superconducting qubits at fault-tolerant threshold [UCSB]Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 20/29
Quantum technologies you can buy todayQuantum random number generators:Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 21/29
Quantum technologies you can buy todayQuantum random number generators:Quantum key distribution solutions:Both of these products marketed by ID Quantique.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 21/29
Quantum technologies you can buy todayThe D-Wave Two “quantum computer”:Pic: NASAAshley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 22/29
The D-Wave Two deviceD-Wave Systems, Inc. claims that their system is the world’s firstlarge-scale quantum computer, with up to 512 qubits.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 23/29
The D-Wave Two deviceD-Wave Systems, Inc. claims that their system is the world’s firstlarge-scale quantum computer, with up to 512 qubits.However, their claims are controversial:Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 23/29
The D-Wave Two deviceD-Wave Systems, Inc. claims that their system is the world’s firstlarge-scale quantum computer, with up to 512 qubits.However, their claims are controversial:ITheir machine isn’t a general-purpose quantum computer, but canonly be used to run one optimisation algorithm.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 23/29
The D-Wave Two deviceD-Wave Systems, Inc. claims that their system is the world’s firstlarge-scale quantum computer, with up to 512 qubits.However, their claims are controversial:ITheir machine isn’t a general-purpose quantum computer, but canonly be used to run one optimisation algorithm.ITheir qubits are “noisy”, and do not operate below the fault-tolerantthreshold.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 23/29
The D-Wave Two deviceD-Wave Systems, Inc. claims that their system is the world’s firstlarge-scale quantum computer, with up to 512 qubits.However, their claims are controversial:ITheir machine isn’t a general-purpose quantum computer, but canonly be used to run one optimisation algorithm.ITheir qubits are “noisy”, and do not operate below the fault-tolerantthreshold.IThey have not demonstrated large-scale quantum entanglement.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 23/29
The D-Wave Two deviceD-Wave Systems, Inc. claims that their system is the world’s firstlarge-scale quantum computer, with up to 512 qubits.However, their claims are controversial:ITheir machine isn’t a general-purpose quantum computer, but canonly be used to run one optimisation algorithm.ITheir qubits are “noisy”, and do not operate below the fault-tolerantthreshold.IThey have not demonstrated large-scale quantum entanglement.IRecent research suggests that fine-tuned classical optimisationalgorithms can sometimes outperform their machine.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 23/29
The D-Wave Two deviceD-Wave Systems, Inc. claims that their system is the world’s firstlarge-scale quantum computer, with up to 512 qubits.However, their claims are controversial:ITheir machine isn’t a general-purpose quantum computer, but canonly be used to run one optimisation algorithm.ITheir qubits are “noisy”, and do not operate below the fault-tolerantthreshold.IThey have not demonstrated large-scale quantum entanglement.IRecent research suggests that fine-tuned classical optimisationalgorithms can sometimes outperform their machine.Characterising the power and potential of the D-Wave approach iscurrently an active area of research.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 23/29
The commercial future of quantum computingCan quantum computing make money?Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 24/29
The commercial future of quantum computingCan quantum computing make money?ISeveral major technology companies now have their own quantumcomputing research efforts, e.g. IBM, Microsoft (two groups!), Google.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 24/29
The commercial future of quantum computingCan quantum computing make money?ISeveral major technology companies now have their own quantumcomputing research efforts, e.g. IBM, Microsoft (two groups!), Google.I2002: ID Quantique is first commercial company to demonstratequantum key distribution.I2013: Mike Lazaridis (founder of BlackBerry) announces 100Mventure capital fund to invest in quantum computing.I2014: The UK government announces 270M funding for researchinto, and commercialisation of, quantum technologies.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 24/29
The commercial future of quantum computingCan quantum computing make money?ISeveral major technology companies now have their own quantumcomputing research efforts, e.g. IBM, Microsoft (two groups!), Google.I2002: ID Quantique is first commercial company to demonstratequantum key distribution.I2013: Mike Lazaridis (founder of BlackBerry) announces 100Mventure capital fund to invest in quantum computing.I2014: The UK government announces 270M funding for researchinto, and commercialisation of, quantum technologies.Estimates (perhaps not reliable) for the value of the quantum computingmarket are into the 10’s of billions by 2020.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 24/29
Challenges for quantum computingAlthough there has been significant progress in quantum computing, thefield faces a number of challenges:IThe difficulty of building a large-scale quantum computer;IThe difficulty of designing new quantum algorithms;IThe difficulty of applying existing quantum algorithms to practicalproblems;The difficulty of proving limitations on quantum computers.ISo there is still much to be done. . .Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 25/29
SummaryIQuantum computers can solve certain problems more efficiently thanclassical computers.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 26/29
SummaryIQuantum computers can solve certain problems more efficiently thanclassical computers.IWe don’t have large-scale, general-purpose quantum computersyet. . .Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 26/29
SummaryIQuantum computers can solve certain problems more efficiently thanclassical computers.IWe don’t have large-scale, general-purpose quantum computersyet. . .I. . . but physicists and engineers are working on it!Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 26/29
SummaryIQuantum computers can solve certain problems more efficiently thanclassical computers.IWe don’t have large-scale, general-purpose quantum computersyet. . .I. . . but physicists and engineers are working on it!IThe most important application of a large-scale quantum computer islikely to be simulating quantum-mechanical systems.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 26/29
SummaryIQuantum computers can solve certain problems more efficiently thanclassical computers.IWe don’t have large-scale, general-purpose quantum computersyet. . .I. . . but physicists and engineers are working on it!IThe most important application of a large-scale quantum computer islikely to be simulating quantum-mechanical systems.IThere are still many interesting open questions about the power andpotential of quantum computing to be explored.Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 26/29
Further readingIWinning a Game Show with a Quantum ComputerAshley Montanarohttp://www.cs.bris.ac.uk/ montanar/gameshow.pdfIQuantum Computing Since DemocritusScott ntroduction to Quantum Computing, University of WaterlooJohn Watroushttps://cs.uwaterloo.ca/ watrous/LectureNotes.htmlIQuantum Computation and Quantum InformationMichael Nielsen and Isaac ChuangCambridge University PressAshley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 27/29
Partial timeline: Theory of quantum computing1984.Quantum cryptographic key distribution invented [Bennett Brassard]1985General quantum computational model proposed [Deutsch]1992First exponential quantum speed-up discovered [Deutsch and Jozsa]1993Quantum teleportation invented [Bennett et al.]1994Shor’s algorithm rewrites the rulebook of classical cryptography1995Quantum error-correcting codes invented [Shor]1996Quantum simulation algorithm proposed [Lloyd]1996Quantum speed-up for unstructured search problems [Grover]1998Efficient quantum communication protocols [Buhrman et al.]2003Exponential speed-ups by quantum walks invented [Childs et al.].Ashley Montanaroashley.montanaro@bristol.ac.ukQuantum ComputingSlide 28/29
quantum mechanics to do things which arefundamentally impossiblefor any computer which only uses classical physics. This lecture will discuss the history of quantum computing, including: 1.The basic concepts behind quantum mechanics 2.How we can use these concepts for teleportation and cryptography 3.Quantum algorithms outperforming classical .
