Transcript The Learnability of Quantum States

New Evidence That Quantum Mechanics Is
Hard to Simulate on Classical Computers

Scott Aaronson
Parts based on joint work with Alex Arkhipov
In 1994, something big happened in the
foundations of computer science, whose meaning
is still debated today…
Why exactly was Shor’s algorithm important?
Boosters: Because it means we’ll build QCs!
Skeptics: Because it means we won’t build QCs!
Me: For reasons having nothing to do with building QCs!
Shor’s algorithm was a hardness result for
one of the central computational problems
of modern science: QUANTUM SIMULATION
Use of DoE supercomputers by area
(from a talk by Alán Aspuru-Guzik)
Shor’s Theorem:
QUANTUM SIMULATION is
not in probabilistic
polynomial time,
unless FACTORING is also
Today: New kinds of hardness results for
simulating quantum mechanics
Advantages of the new
results:
Based on more “generic”
complexity assumptions than
classical hardness of FACTORING
Give evidence that QCs have
capabilities outside the entire
polynomial hierarchy
Use only extremely weak kinds
of QC (e.g. nonadaptive linear
optics)
Disadvantages:
Most apply to sampling
problems (or problems with
many possible valid
outputs), rather than
decision problems
Harder to convince a skeptic
that your QC is indeed
solving the relevant hard
problem
Problems not “useful” (?)
What Is The Polynomial Hierarchy?
NP  NP
NP
 NP
NP NP

Example of a PH problem:
“For all n-bit strings x, does there exist an n-bit string y
such that for all n-bit strings z, (x,y,z) holds?”
“such-and-such is true  PH collapses to a finite level”
is complexity-ese for
“such-and-such would be almost as insane as P=NP”
BQP vs. PH: A Timeline
Bernstein and Vazirani define BQP
They construct an oracle problem, RECURSIVE FOURIER
SAMPLING, that has quantum query complexity n but
classical query complexity n(log n)
First example where quantum is superpolynomially better!
A simple extension yields RFSMA
Natural conjecture: RFSPH
Alas, we can’t even prove RFSAM!
Results In The Oracle World
From arXiv:0910.4698
There exist oracle sampling and relational problems in
BQP that are not in BPPPH
Assuming the “Generalized Linial-Nisan Conjecture,”
there exists an oracle decision problem in BQP but not in
PH
Original Linial-Nisan Conjecture was recently proved by
Braverman, after being open for 20 years
Unconditionally, there exists an oracle decision problem that
requires (N1/4) queries classically (even using postselection),
but only 1 query quantumly
Results In The “Real” World
From not-yet-arXived joint work with Alex Arkhipov
Suppose the output distribution of any linear-optics circuit
can be efficiently sampled classically (e.g., by Monte Carlo).
Then P#P=BPPNP, and hence PH collapses.
Indeed, even if such a distribution can be sampled in BPPPH,
still PH collapses.
Suppose the output distribution of any linear-optics circuit
can even be approximately sampled in BPP. Then a BPPNP
machine can additively approximate Per(X), with high
probability over a matrix X of i.i.d. N(0,1) Gaussians.
“Permanent-of-Gaussians Conjecture”: The above problem is
#P-complete.
FOURIER FISHING Problem
Given oracle access to a random Boolean function
f : 0,1  1,1
n
The Task:
Output strings z1,…,zn, at least 75% of which satisfy
and at least 25% of which satisfy
where
ˆf z  : 1
n/2
2
fˆ zi   2
 1
z x
x0,1n
f x 
fˆ zi   1
FOURIER FISHING Is In BQP
|0
Algorithm:
H
|0
H
|0
H
H
f
H
H
Repeat n times;
output whatever
you see
Distribution over Fourier coefficients
Distribution over Fourier coefficients
output by quantum algorithm
FOURIER FISHING Is Not In PH
Basic Strategy: Suppose an oracle problem is in PH. Then by
reinterpreting every  quantifier as an OR gate, and every 
quantifier as an AND gate, we can get an AC0 (constant-depth,
unbounded-fanin, quasipolynomial-size) circuit for an “exponentiallyscaled down” version of the problem
And AC0 circuits are one of the few things in complexity theory that
we can actually lower-bound! In particular, it was proved in the
1980s that any AC0 circuit for MAJORITY (or for computing a Fourier
coefficient) must have exponential size
Problem: In our case, the AC0 circuit C doesn’t have to compute the
Fourier coefficients—it just has to sample from some probability
distribution defined in terms of them!
To deal with that, we use a nondeterministic reduction (which adds
more layers to the circuit), to show that C would nevertheless lead to
an AC0 circuit for MAJORITY
Decision Version: FOURIER CHECKING
Given oracle access to two Boolean functions
f , g : 0,1  1,1
n
Decide whether
(i) f,g are drawn from the uniform distribution U, or
(ii) f,g are drawn from the following “forrelated”
n
2
distribution F: pick a random unit vector v   ,
then let
f x : sgn vx , g x : sgn vˆx 
FOURIER CHECKING Is In BQP
|0
H
|0
H
|0
H
H
f
H
H
H
g
H
H
Probability of observing |0n:
2
n



2
if f,g are random
1 
x y

f x  1 g  y   
3n  

2  x , y0,1n
 1 if f,g are forrelated
Evidence That FOURIER CHECKING  PH
We can prove that, even after you condition on any
setting for any polynomial number of f(x)’s and g(y)’s,
you still have “almost” no information about whether f
and g are independent or forrelated
We conjecture that this property, by itself, is enough to
imply an oracle problem is not in PH. We call this the
Generalized Linial-Nisan Conjecture
The original Linial-Nisan Conjecture—the same
statement, but without the “almost”—was proved last
year by Braverman, in a major breakthrough in
complexity theory (indirectly inspired by this work )
Coming back to the first result, what’s surprising is that we
showed hardness of a BQP sampling problem, by using a
nondeterministic reduction from MAJORITY—a “#P” problem!
This raises a question: is something similar possible in the
unrelativized (non-black-box) world?
Indeed it is. Consider the following problem:
QSAMPLING: Given a quantum circuit C, which acts on n
qubits initialized to the all-0 state. Sample from C’s
output distribution.
Result/Observation:
Suppose QSAMPLINGBPP. Then P#P=BPPNP
(so in particular, PH collapses to the third level)
Why QSAMPLING Is Hard
Let f:{0,1}n{-1,1} be any efficiently computable function.
Suppose we apply the following quantum circuit:
|0
H
|0
H
|0
H
H
f
H
H
Then the probability of observing the all-0 string is

1 
p : 2 n  f x 

2  x0,1n

2
Claim 1: p is #P-hard to
estimate (up to a constant factor)
Proof: If we can estimate p,
then we can also compute
xf(x) using binary search
and padding
Claim 2: Suppose
QSAMPLINGBPP. Then we
could estimate p in BPPNP
Proof: Let M be a classical
algorithm for QSAMPLING, and
let r be its randomness. Use
approximate counting to
2 M r  outputs 0 n
estimate Pr
r
1 

  f  x 
2n 

n
2
Conclusion: Suppose QSAMPLING
 x0,1BPP. Then P#P=BPPNP
p :

Related Results
A. 2004: PostBQP=PP
Bremner, Jozsa, Shepherd (poster #1): PostIQP=PP,
hence efficient simulation of IQP collapses PH
Fenner, Green, Homer, Pruim 1999: Determining
whether a quantum circuit accepts with nonzero
probability is hard for PH
Ideally, we want a simple, explicit quantum system Q,
such that any classical algorithm that even
approximately simulates Q would have dramatic
consequences for classical complexity theory
We believe this is possible, using non-interacting bosons
There
twosay
basic
of particle in the universe…
Allare
I can
is,types
the bosons
got the harder job…
BOSONS
FERMIONS
Their transition amplitudes are given respectively by…
Per A 
n
a  


S n i 1
i,
i
Det A 
 1


sgn  
S n
n
a  
i,
i 1
i
Linear Optics for Dummies (or computer scientists)
Computational basis states have the form |S=|s1,…,sm,
where s1,…,sm are nonnegative integers such that s1+…+sm=n
Theorem (Lloyd 1996 et al.): BosonP  BQP
n = # ofProof
photonsIdea:
m =Decompose
# of “modes” (boxes)
that
photon
U into
a each
product
ofcan be in
2) “elementary linear-optics gates”
O(m
Starting from a fixed basis state (like |=|1,…,1,0,…0), you
(beamsplitters
and
phase-shifters),
then
get to choose
an arbitrary
mm
unitary U to apply
simulate each
m  n gate
1  musing
 n  1standard qubit gates
  
 unitary V on n-photon
U induces an 

n
 
n



Milburn
U S ,T 2001):
states,Theorem
defined by(Knill, Laflamme,Per
SVT

Linear optics with
adaptive
measurements
1! sm !t1!t m !
can do all of sBQP
we’ll
use just of
a single
(nonadaptive)
whereBy
US,Tcontrast,
is an nn
submatrix
U indexed
by S,T
measurement
theofphoton
numbers
at the end
(containing
an sitjof
block
uij’s for each
i,j)
Then you get to measure V| in the computational basis
Our Result: Take a system of n identical photons with
m=O(n2) modes. Put each photon in a known mode, then
apply a Haar-random mm unitary transformation U:
U
Permanent-of-Gaussians
Conjecture: This problem
is #P-complete
Let D be the distribution that results from measuring the
photons. Suppose there’s a BPP algorithm that takes U as
input, and samples any distribution even 1/poly(n)-close to D
in variation distance. Then in BPPNP, one can estimate the
permanent of a matrix X of i.i.d. N(0,1) complex Gaussians,
to additive error
n! with high probability over X.
n
O 1
,
PGCHardness of BOSONSAMPLING
Idea: Given a Gaussian random matrix X, we’ll “smuggle” X
into the unitary transition matrix U for m=O(n2) photons—in
such a way that S|V|=Per(X), for some basis state |S
Useful fact we rely on: given a Haar-random mm unitary matrix,
an nn submatrix looks approximately Gaussian
Then the sampler has “no way of knowing” which submatrix
of U we care about—so even if it has 1/poly(n) error, with
high probability it will return |S with probability |Per(X)|2
Then, just like before, we can use approximate counting to
estimate Pr[|S]|Per(X)|2 in BPPNP, and thereby solve #P
Difficulty: The “bosonic birthday paradox”! Identical bosons
like to pile on top of each other, and that’s bad for us
SO WE DEAL WITH IT
Experimental Prospects
What would it take to implement the
requisite experiment?
• Reliable phase-shifters and
beamsplitters, to implement an
arbitrary unitary on m photon modes
• Reliable single-photon sources
Fock states, not coherent states
• Reliable photodetector arrays
But crucially, no nonlinear optics or
postselected measurements!
Our Proposal: Concentrate on (say) n=30 photons, so that
classical simulation is difficult but not impossible
Prize Problems
Prove the Generalized Linial-Nisan Conjecture!
$200
Yields an oracle A such that BQPAPHA
Prove the Permanent of Gaussians Conjecture!
Would imply that even approximate classical simulation of
linear-optics circuits would collapse PH
Do a linear optics experiment that overthrows the
Polynomial-Time Church-Turing Thesis
140Fr
?