Transcript Another version - Scott Aaronson

Quantum Computing and the Limits
of the Efficiently Computable
Scott Aaronson (MIT)
Papers & slides at www.scottaaronson.com
Quantum Computing
A quantum superposition involving n particles can require
~2n complex numbers to specify:
x
x0,1n
Presents an obvious practical problem when using
conventional computers to simulate quantum mechanics
 

x
Feynman 1981: So then why not turn things around, and
build computers that themselves exploit superpositions?
Could such a machine get any advantage over a classical
computer with a random number generator? If so, it would
have to come from interference
Applications of Quantum
Computing:
Proving it’s possible at all!
Quantum simulation
NP-complete
Breaking public-key
cryptography
NP
Adiabatic optimization??
Machine learning??
BQP
Factoring
P
BosonSampling
Suppose we just want to demonstrate “quantum supremacy”
(i.e., a quantum system that’s hard to simulate classically)—
that’s all
A.-Arkhipov 2011, Bremner-Jozsa-Shepherd 2011: In that
case, we can plausibly improve both the hardware
We showed: if a fast, classical
requirements and the evidence for classicalExperimental
hardness,
exact
of algorithm
demonstration has now
compared
to simulation
Shor’s factoring
BosonSampling is possible,
been achieved with 6
Ourhierarchy
proposal: photons (by O’Brien group
then the polynomial
Identical
single
collapses to the third
level.
in Bristol)!
photons sent
through network of
interferometers,
then measured at
output modes
Quantum Money
Idea: Quantum states that can be created
by a bank, traded as currency, and
verified as legitimate, but can’t be cloned
by counterfeiters, because of quantum
mechanics’ No-Cloning Theorem

 
Wiesner ca. 1970: First quantum money scheme, but only
the bank could verify the bills. If anyone can verify a bill, then
computational assumptions clearly needed, in addition to QM
A.-Christiano 2012: First quantum money scheme where
anyone can verify a bill, and whose security is based on a
“conventional” crypto assumption
A Few Other Things I’ve Worked On
The limitations of quantum computers (e.g., for
finding collisions in hash functions); the possibility of
quantum-secure cryptography
What’s the largest possible quantum speedup? (The
Forrelation and k-fold Forrelation problems)
Quantum computing and the black-hole information
loss problem
Some Future Directions
The need for structure in quantum speedups
Quantum copy-protected software
Noisy BosonSampling (in dialogue with experimentalists)
Rise and fall of complexity in thermodynamic systems