Transcript Another version - Scott Aaronson

Recent Progress in Computational Universality
a.k.a. What More Than Turing-Universality Do You
Want?
+?
Scott Aaronson (MIT)
Papers and slides at www.scottaaronson.com
The Pervasiveness of Universality
Almost any programming language or cellular automaton
you can think to invent, provided it’s “sufficiently
complicated,” will be able to simulate a Turing machine
For n large enough, almost any n-bit logic gate will be
capable of expressing all Boolean functions
Almost any 2-qubit unitary transformation can be used to
approximate any unitary transformation on any number
of qubits, to any desired precision
Yet precisely because universality is “common
as dirt,” it’s not useful for distinguishing
among candidate physical theories
versus
What We Could Ask of Physical Laws
“Beyond just Turing-universality”
Simplicity
Symmetry
Relativity (at least Galilean)
Quantum Mechanics (but why?)
Robustness (i.e., fault-tolerant universality)
Physical Universality
Interesting Structure Formation in “Generic” Cases
Symmetry
Classical Reversible Gates
Flip second bit iff first bit is 1
CNOT
Not universal (affine)
Flip third bit iff first two bits are both 1
Toffoli
Universal; can generate all permutations of nbit strings
Swap second and third bits iff first bit is 1
Fredkin
Computationally universal, but has a
symmetry (preserves Hamming weight)
A.-Grier-Schaefer 2015:
Classified all sets of
reversible gates in terms of
which n-bit reversible
transformations they
generate (assuming swaps and
ancilla bits are free)
Physical Universality
Schaeffer
2014: The first
known
“physicallyuniversal”
cellular
automaton
(able to implement
any transformation
in any bounded
region, by suitably
initializing the
complement of
that region)
Solved open
problem of
Janzing 2010
One of My Favorite Open Questions
For every n-qubit unitary transformation U, is there a
Boolean function f such that U can be realized by a
polynomial-time quantum algorithm with an oracle for f?
(I’m giving you any computational capability f you
could possibly want—but it’s still far from obvious
how to get the physical capability U!)
Can show: For every n-qubit state |, there’s a Boolean
function f such that | can be prepared by a
polynomial-time quantum algorithm with an oracle for f
Interesting Structure Formation
How to Measure Interesting Structure?
Many people have studied this (in the “other” complexity
theory); there are definitions in terms of predictability etc.
One simpleminded measure: the Kolmogorov complexity of
a coarse-grained description of our cellular automaton or
other system
Sean Carroll’s example:
The Coffee Automaton
A., Carroll, Mohan, Ouellette, Werness 2015: A probabilistic
nn reversible system that starts half “coffee” and half
“cream.” At each time step, we randomly “shear” half the
coffee cup horizontally or vertically (assuming a toroidal cup)
Compressed File Size
We prove that the apparent
complexity of this image has
a rising-falling pattern, with a
maximum of at least ~n1/6
500
450
400
350
300
250
200
150
100
50
0
-100
100
300
500
Time Steps
700
900
Interesting Computations Should Be Not
Merely Expressible, But Succinctly Expressible?
BB(n) = the maximum number of steps that a 1-tape, 2symbol, n-state Turing machine can take on an initially blank
tape before halting
BB(1)=1
BB(2)=6
BB(3)=21
BB(4)=107
BB(5)47,176,870
BB(6)7.41036534
Famously uncomputably-rapidly
growing function
Gödel  beyond some finite point, the
values of BB(n) are not even provable
in ZF set theory! (assuming ZF is consistent)
Yedidia 2015 (winner of MEng thesis prize)
Building on work of Harvey Friedman, constructed a
380,000-state Turing machine whose behavior is
independent of ZF set theory
Also an 8,000-state machine that tests Goldbach’s
Conjecture, and a 30,000-state machine that tests the
Riemann Hypothesis
Currently working on improving by an order of magnitude
(by switching from compiler to inline interpreter)
Difference from Minsky et al.’s “smallest universal Turing
machine” contest?