Slide1: David Evans http://www.cs.virginia.edu/evans CS150: Computer Science University of Virginia Computer Science Class 33: Computing with Photons From The Tinkertoy Computer and Other Machinations by A. K. Dewdney http://www.amazon.com/exec/obidos/tg/detail/-/071672491X/103-4408705-5367831?v=glance


Church-Turing Thesis: Church-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 power


Turing Machines and Complexity: Turing 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” is


Normal Steps: Normal 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 varies


Generalized Normal Steps: Generalized Normal Steps Require a constant amount of time Perform a fixed amount of work Localized Cannot scale (indefinitely) with input size


Abnormal Imaginary Computer: Abnormal 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?


Quantum Physics for Dummies: Quantum 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 box


Quantum Computing: Quantum 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 state


Qubit: Qubit 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!)


Quantum Computers Today: Quantum 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 hard 15 (= 5 * 3)


Complexity for Quantum Computer: Complexity 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 need Number of (nondeterministic) steps


Charge: Charge Exam 2 out Friday Covers through Monday All questions will assume only “normal” computers Links to example exams on the web Review session Wednesday, 7pm