93
Part Three · A · Foundations of quantum information

Classical computation, Turing machines, and complexity classes

Give someone a filled-in Sudoku and they can check it in a minute. Give them a blank one of size 100 × 100 and, as far as anyone knows, no method can fill it before the Sun burns out. Is there a fast method nobody has found? That is the P versus NP question, worth a million dollars and still open. Quantum computers live inside this landscape of hard and easy problems, and to say exactly what they can and cannot do, you need its map. Part Three begins with that map.

On the plate: a Turing machine, adding one to a binary number, one step at a time.

The simplest computer

Alan Turing in 1936 defined computation with a machine that reads and writes symbols on an endless tape, one cell at a time, following a finite table of rules: in state qq, reading symbol aa, write bb, move left or right, go to state q′q'. Every algorithm anyone has found can be run on such a machine; the Church–Turing thesis says every effective procedure can. or . It moves to the right end, then carries ones to zeros leftward until it can write a one. Established

How fast is fast?

Complexity theory counts steps as a function of input size nn. Polynomial time, nkn^k, is considered efficient; exponential, 2n2^n, is not. Set n=n = 40 and compare, at a billion steps a second. At 40, n3n^3 takes 64 microseconds; 2n2^n takes 18 minutes. At 100, 2n2^n takes 4×10134\times10^{13} years. No hardware improvement rescues an exponential.

The classes

P: problems solvable in polynomial time. NP: problems whose solutions can be checked in polynomial time. BPP: solvable in polynomial time by a randomized algorithm that is right with probability at least 2/3; repeating it and taking the majority makes the error exponentially small, by a Chernoff bound. PSPACE: solvable with polynomial memory, however long it takes. We know P⊆NP⊆PSPACE\text{P}\subseteq\text{NP}\subseteq\text{PSPACE} and P⊆BPP\text{P}\subseteq\text{BPP}, but not whether any of these inclusions is strict.

Its quantum counterpart, BQP, appears in Chapter 128. It contains factoring, which is believed not to be in P, and is believed not to contain the NP-complete problems. Choose a class to highlight: . Established as definitions and proven inclusions; the separations are open.

NP-completeness

In 1971 Stephen Cook and, independently, Leonid Levin showed that Boolean satisfiability (SAT) is as hard as anything in NP: any NP problem can be translated, in polynomial time, into a SAT instance. Such problems are NP-complete. Richard Karp then showed 21 classic problems are NP-complete by such reductions, for example turning 3-SAT into finding a clique in a graph. Thousands are known now, including protein folding on lattice models and many scheduling problems. A fast algorithm for any one gives fast algorithms for all. Established

The extended Church–Turing thesis

The strong form says that any physically reasonable computer can be simulated by a probabilistic Turing machine with at most polynomial slowdown. Quantum computers are the main challenge to it: if factoring is truly hard classically, Shor’s algorithm (Chapter 114) shows a physical device that beats every classical one exponentially. Whether large quantum computers can be built is the experimental question of Parts 3C–3E. Debated

What you now have

Turing machines and the Church–Turing thesis, polynomial versus exponential time, P, NP, BPP and PSPACE, NP-completeness and reductions, and the extended Church–Turing thesis that quantum computing challenges.

· · ·

Three questions to carry with you.

What does it mean for a problem to be in NP?tap
A proposed solution can be verified in polynomial time.
Why is BPP considered efficient despite errors?tap
Repetition and majority vote shrink the error exponentially.
Is factoring NP-complete?tap
It is in NP but not believed NP-complete; it is in BQP.

And one to work out. An algorithm takes 2n2^n steps at 10910^9 steps per second. For n=60n = 60, how many years?

time ≈years

Sources: A. M. Turing, Proc. London Math. Soc. 42, 230 (1936). S. A. Cook, Proc. 3rd ACM STOC, 151 (1971); L. Levin, Problems of Information Transmission 9, 265 (1973). R. M. Karp, in Complexity of Computer Computations (1972). M. Sipser, Introduction to the Theory of Computation. S. Arora and B. Barak, Computational Complexity. S. Aaronson, Quantum Computing Since Democritus. Checked by code: 2⁶⁰/10⁹ s = 36.6 years; binary-increment machine output verified on all 8-bit inputs.

Next · Chapter 94
Reversible computing and Landauer's principle

Erasing one bit must release heat. In 2012, physicists measured this with a single bead.

Turn the page