QIP '10 Liveblogging - Day 4.5
Loïck
on Friday, January 22 2010, 14:48
Live-blogging
New evidence that quantum mechanics is hard to simulate on classical computers
Scott Aaronson
“Experiments can prove whatever you like, so who cares?”
Quantum simulation is not in BPP unless factorization is. “I think that factoring is not in P, I would not bet my life on that as would bet that P ≠ NP”
« "foo-bar is true => PH collapse at a finite level" is almost as insane as "foo-bar is true => P = NP" »
Suppose the output distribution of an linear-optics circuit can be efficiently sampled classically, then P#P = BPPNP and hence PH collapses at the 3d level.Suppose the output distribution of an linear-optics circuit can be approximately efficiently sampled classically, then a BPPNP machine can additively approximate the permanent of X, where the entries of X are i.i.d. N(01) Gaussians. (Permanent is #P-complete, Gaussian permanent is also conjectured to be #P-complete)
"I heard that there is some kind of Fourier transform defined on the real… In computer science, it is on the Boolean hypercube!"
Fourier Fishing: We are given oracle access to n Boolean functions f1,…, fn, which are chosen uniformly and independently at random. The task is to output n strings,
z1,...,zn ∈ {0,1}n, at least 75% of which satisfy |fi(zi)|≥1 and at least 25% grater or equal than 2.
Fourier Fishing is in BQP but not in PH. (it is not a decision problem)
Fourier Checking is in BQP but there are evidences that it is not in PH. (by supposing the "Generalized Linial-Nisan Conjecure")
Quantum sampling is hard. (if it is in BPP, PH collapses at the third level)
PostBQP = PostIQP = PP
For a computer scientist point of view, Bosons are associated with Permanent, and Fermions with determinant.
Let's do linear optics for dummies (=computer scientists) and try to make it computer scientist by citing simulations of bosonic polynomial circuits by Seth LLoyd and the (wonderful) paper that is [KLM01].
And now, he's speaking too fast because he doesn't have enough time. (Gaussian, permanent, simulation, 30 squeezed states)
Prize problems:
- 200$ — Solve the generalized Linial-Nisan Conjecure
- 140 CHF — Solve the Permanent of Gaussian state conjecture (Hummm. What is that?)
- Big prize — Does linear optics contradict the generalized Church-Türing thesis?
Anthony, you're famous! One of your comments on my own blog has been ask to Scott: "Why are hardcore computer scientists interested with continuous variables?" Scott answer: "I don't know what is 'continuous variables, squeezing and homodyne measurement"
Comments
Friday, January 22 2010, 15:08
so what is PH again?
Friday, January 22 2010, 15:13
at the 3d level.??
no way!
Friday, January 22 2010, 15:52
actually, I asked the very same question on Scott's blog a few days ago, and he said he would explain everything in his 2nd QIP talk.
Friday, January 22 2010, 15:55
PH is the polynomial hierarchy PH = NP U NPNP U NPNPNP U …
Actually, this was Scott's third talk…
Friday, January 22 2010, 15:58
Anthony - it was on Scott's blog that I saw your question, and was interested. I did say that on his blog he'd said he was going to tell us in this talk. Actually, linear optics doesn't necessarily imply continuous variable computing - a lot of the time the physical systems are continuous variable but the logical elements are qubit/qudit logic.
Friday, January 22 2010, 16:07
@Loïck.
ok, and I gather that A^B means A with an oracle for B (cf @qudit's tweet).
So that does it mean if the hierarchy collapses? Any intuition about this?
@Clare
so which is it here? Does he want to linear optics with qubit logic, or with genuine continuous variables (squeezing, homodyne detection and all that)?
Friday, January 22 2010, 16:50
@Anthony - it's real continuous variables, using fock states for the number of photons that he wants to count. I'm still pondering things further.
Friday, January 22 2010, 17:03
Regarding Scott's interest in "squeezing, homodyne detection, and all that", these ideas are useful in experimentally realizing (using linear optics only) analog estimates of the permanent.
A good starting reference is Stefan Scheel's <i>Permanents in linear optical networks</i> (quant-ph/0406127).
It appears that Scott has made considerable progress toward linking-up a "compatible triple" of:
(1) QIP theorems that prove certain quantities *can't* be efficiently simulated;
(2) quantum simulation algorithms that establish what *can* be simulated (with classical resources); and
(3) experiments (perhaps even feasible experiments) that establish what *can* be computed with (continuous variable) quantum scattering experiments.
This is exciting work ... it represents a very serious attempt to establish a tighter link-up of QIP theory, simulation capability, and (feasible?) quantum experiments.
That is why I very much hope that someone will live-blog about this work, and/or Scott will post a presentation and/or even a preprint.
Friday, January 22 2010, 17:24
@John
OK, thanks for the explanation.
You can find Scott's slides on his webpage:
http://www.scottaaronson.com/talks/...
Friday, January 22 2010, 18:54
Thanks for the pointer to Scott's slides, Anthony!
The part of Scott's talk that we in Seattle are most interested in is encoded in the phrase (on Slide 22) "so we deal with it".
This phrase occurs precisely where several issues come into play that are mighty challenging for experimentalists and simulationists alike ... was there any verbal commentary that went with this slide?
Tuesday, January 26 2010, 01:21
With regard to the above questions relating to linear optical scattering, on Scott Aaronson's blot I posted a brief discussion of guessed-at methods for "dealing with it" ...
URL: "http://scottaaronson.com/blog/?p=43..."
It will be very interesting to read the (hoped-for) preprint, given that even the ultra-weak version of the Church-Turing thesis has not (yet) been experimentally disproved: "A classical Turing machine can simulate any quantum experiment in polynomial time."