Transcript The Learnability of Quantum States

‫עדויות חדשות שקשה לדמות את‬
‫מכניקת הקוונטים עם מחשבים‬
‫קלאסיים‬
)New Evidence That Quantum Mechanics Is
Hard to Simulate on Classical Computers(
‫סקוט אהרונסון‬
)Scott Aaronson(
MIT
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: Disadvantages:
Based on “generic” complexity
assumptions, rather than the
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)—testable before I’m
dead?
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” (?)
Results (from arXiv:0910.4698)
There exist black-box sampling and relational problems in
BQP that are not in BPPPH
Assuming the “Generalized Linial-Nisan Conjecture,” there
exists a black-box 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 a black-box decision problem
that requires (N) queries classically ((N1/4) even using
postselection), but only O(1) queries quantumly
Results (from recent 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 approximate the permanent of a matrix of
independent N(0,1) Gaussians.
Conjecture: The above problem is #P-complete.
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!
Fourier Sampling 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 SAMPLING 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 SAMPLING Is Not In PH
Key Idea: Show that, if we had a constant-depth 2poly(n)-size
circuit C for FOURIER SAMPLING, then we could violate a known
AC0 lower bound, by “sneaking a MAJORITY problem” into the
estimation of some random Fourier coefficient fˆ s 
Obvious problem: How do we know C will output the
particular s we’re interested in, thereby revealing anything
about fˆ s  ?
We don’t! (Indeed, there’s only a ~1/2n chance it will)
But we have a long time to wait, since our reduction can be
nondeterministic!
That just adds more layers to the AC0 circuit
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
Intuition: FOURIER CHECKING
Shouldn’t Be In PH
Why?
• For any individual s, computing the Fourier
coefficient fˆ s  is a #P-complete problem
• f and g being forrelated is an extremely “global”
property: no polynomial number of f(x) and g(y) values
should reveal much of anything about it
But how to formalize and prove that?
A k-term is a product of k literals of the form xi or 1-xi
A distribution D over {0,1}N is k-wise independent if for all
k-terms C,
1
PrD C   PrU C  
2
k
Key Definition: A distribution D is -almost k-wise
independent if for all k-terms C,
PrD C 
1  
 1 
PrU C 
Approximation is
multiplicative, not additive
… that’s important!
Theorem: For all k, the forrelated distribution F is
O(k2/2n/2)-almost k-wise independent
Proof: A few pages of Gaussian integrals, then a
discretization step
Linial-Nisan Conjecture (1990) with weaker parameters that suffice for us:
n o 1 
Let f:{0,1}n{0,1} be computed by a circuit of size 2 and
depth O(1). Then for all n(1)-wise independent distributions D,
Pr  f x   Pr n  f x   o1.
x~ D
x0 ,1
Razborov’08
Finally,Bazzi’07
Braverman’09
dramatically
Alas,
proved
we need
proved
the
simplified
depth-2
the…
the whole
Bazzi’s
case thing
proof
“Generalized Linial-Nisan
Conjecture”: Let f be computed
o 1 
by a circuit of size 2n and depth O(1). Then for all
1/n(1)-almost n(1)-wise independent distributions D,
Pr  f x   Pr n  f x   o1.
x~ D
x0 ,1
Coming back to our result for relational problems: what was
surprising was that we showed hardness of a BQP sampling
problem, 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)
Related to my result that
PostBQP=PP
Claim 2: Suppose
QSAMPLINGBPP. Then we
could estimate p in BPPNP
Proof: Let M be a classical
algorithm for QSAMPLING, and
Proof: If we can estimate p,
let r be its randomness. Use
then we can also compute
approximate counting to
xf(x) using binary search
2 M r  outputs 0 n
estimate
Pr
and padding
r
1 

  f  x 
2n 

n
2
Conclusion: Suppose QSAMPLING
 x0,1BPP. Then P#P=BPPNP
p :

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
Our Result: Take a system of n identical photons, with
m=O(n2) modes (basis states) each. Put each photon in a
known mode, then apply a random mm scattering matrix U:
U
Conjecture: This
problem is #P-complete
Let D be the distribution that results from measuring the
photons. Suppose there’s an efficient classical algorithm that
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
,
The Permanent of Gaussians Conjecture (PGC)
Given a matrix X of i.i.d, N(0,1) complex Gaussians, it is
#P-complete to approximate Per(X) to within  n! ,
polyn 
with 1-1/poly(n) probability over X
“But isn’t the permanent easy to approximate, by JerrumSinclair-Vigoda?”
Yes—for nonnegative matrices. For general matrices, can get huge
cancellations between positive and negative terms, and indeed even
approximating the permanent is #P-complete in the worst case
Intuition for PGC: We know computing the permanent of a
random matrix is #P-complete—over finite fields. “Merely”
need to extend that result to the reals or complex numbers!
Basic difficulty: When doing LFKN-style interpolation, errors
in the permanent estimates can blow up exponentially
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) bosons
Useful fact we rely on: given a Haar-random mm unitary matrix,
an nn submatrix looks approximately Gaussian
Suppose that initially, modes 1,…,n contain one boson each
while modes n+1,…,m are unoccupied. Then after applying
U, we observe a configuration (list of occupation numbers)
s1,…,sm, with probability
pS :
Per U S 
2
s1! sm !
Neat Fact: The pS’s sum to 1
where US is an nn matrix
containing si copies of the
ith row of U (first n columns
only)
Problem: Bosons like to pile on top of each other!
Call a configuration S=(s1,…,sm) good if every si is 0 or 1 (i.e.,
there are no collisions between bosons), and bad otherwise
If bad configurations dominated, then our sampling
algorithm might “work,” without ever having to solve a hard
PERMANENT instance
Furthermore, the “bosonic birthday paradox” is even worse
than the classical one!
2
Prboth particles land in the same box   ,
3
rather than ½ as with classical particles
Fortunately, we show that with n bosons and mkn2 boxes,
the probability of a collision is still at most (say) ½
Experimental Prospects
What would it take to implement the
requisite experiment with photonics?
• Reliable phase-shifters and
beamsplitters, to implement a Haarrandom unitary on m photon modes
• Reliable single-photon sources
• 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 Generalized L-N even for the special case of DNFs.
$100
Yields an oracle A such that BQPAAMA
Prove the Permanent of Gaussians Conjecture!
Would imply that even approximate classical simulation of NIS500
linear-optics circuits would collapse PH
More Open Problems (no prizes)
Can we “instantiate” FOURIER CHECKING by an explicit
(unrelativized) problem?
Can we use BOSONSAMPLING to solve any decision problem
outside BPP?
Can you convince a skeptic (who isn’t a BPPNP machine) that
your QC is indeed doing BOSONSAMPLING?
Can we get unlikely classical complexity consequences from
P=BQP or PromiseP=PromiseBQP?
Summary
I like to say that we have three choices: either
(1) The Extended Church-Turing Thesis is false,
(2) Textbook quantum mechanics is false, or
(3) QCs can be efficiently simulated classically.
For all intents and purposes?