Slide 1Church-Turing ThesisTuring Machines and ComplexityNormal StepsGeneralized Normal StepsAbnormal Imaginary ComputerQuantum Physics for DummiesQuantum ComputingQubitQuantum Computers TodayComplexity for Quantum ComputerChargeDavid Evanshttp://www.cs.virginia.edu/evansCS150: Computer ScienceUniversity of VirginiaComputer ScienceClass 33:Computing with PhotonsFrom The Tinkertoy Computer and Other Machinations by A. K. Dewdneyhttp://www.amazon.com/exec/obidos/tg/detail/-/071672491X/103-4408705-5367831?v=glance2CS150 Fall 2005: Lecture 33: Alternate Computing ModelsChurch-Turing Thesis•Church’s original (1935)–Lambda calculus is equivalent to real world computers (can compute any computable function)•Turing’s version –“Every function which would naturally be regarded as computable can be computed by a Turing machine.” •Generalized version:–Any computation that can be done by an algorithm can be done by a mechanical computer–All “normal” computers are equivalent in computing power3CS150 Fall 2005: Lecture 33: Alternate Computing ModelsTuring Machines and Complexity•Stronger version:–Complexity classes P, NP, and NP-complete are defined for Turing machine steps, but apply identically to all “normal” computers•Today: “Abnormal” Computers–Might change what is computable (probably don’t)–Do change what a normal “step” is4CS150 Fall 2005: Lecture 33: Alternate Computing ModelsNormal Steps•Turing machine:–Read one square on tape, follow one FSM transition rule, write one square on tape, move tape head one square•Lambda calculus:–One beta reduction•Your PC:–Execute one instruction (?)•What one instruction does varies5CS150 Fall 2005: Lecture 33: Alternate Computing ModelsGeneralized Normal Steps•Require a constant amount of time•Perform a fixed amount of work–Localized–Cannot scale (indefinitely) with input size6CS150 Fall 2005: Lecture 33: Alternate Computing ModelsAbnormal Imaginary Computer•“Accelerating” TM–Like a regular TM, except the first step takes 1 second, second step takes ½ second, third step takes ¼ second, ... nth step takes 1/2n second•Is our “Accelerating” TM more powerful than a regular TM?7CS150 Fall 2005: Lecture 33: Alternate Computing ModelsQuantum Physics for Dummies•Light behaves like both a wave and a particle at the same time•A single photon is in many states at once•Can’t observe its state without forcing it into one state•Schrödinger’s Cat–Put a live cat in a box with cyanide vial that opens depending on quantum state–Cat is both dead and alive at the same time until you open the box8CS150 Fall 2005: Lecture 33: Alternate Computing ModelsQuantum Computing•Feynman, 1982•Quantum particles are in all possible states•Can try lots of possible computations at once with the same particles•In theory, can test all possible factorizations/keys/paths/etc. and get the right one!•In practice, very hard to keep states entangled: once disturbed, must be in just one possible state9CS150 Fall 2005: Lecture 33: Alternate Computing ModelsQubit•Regular bit: either a 0 or a 1•Quantum bit: 0, 1 or in between–p% probability it is a 1•A single qubit is in 2 possible states at once•If you have 7 bits, you can represent any one of 27 different states•If you have 7 qubits, you have 27 different states (at once!)10CS150 Fall 2005: Lecture 33: Alternate Computing ModelsQuantum Computers Today•Several quantum algorithms–Shor’s algorithm: factoring using a quantum computer•Actual quantum computers–5-qubit computer built by IBM (2001)–Implemented Shor’s algorithm to factor:•“World’s most complex quantum computation” –Los Alamos has built a 7-qubit computer•To exceed practical normal computing need > 30 qubits–Adding another qubit is more than twice as hard15 (= 5 * 3)11CS150 Fall 2005: Lecture 33: Alternate Computing ModelsComplexity for Quantum Computer•Complexity classes are different than for regular computers, because a step is different•Quantum computer: each step can take both possible decisions at once–Means a quantum computer is a nondeterministic computer!–It can solve problems in class NP in polynomial time!•What matters?Number of qubits you needNumber of (nondeterministic) steps12CS150 Fall 2005: Lecture 33: Alternate Computing ModelsCharge•Exam 2 out Friday–Covers through Monday–All questions will assume only “normal” computers–Links to example exams on the web–Review session Wednesday,
View Full Document
Unlocking...