“On the other hand, on the basis of what has been proved so far, it remains possible that there may exist (and even be empirically discoverable) a theorem­ proving machine which in fact is equivalent to mathematical intuition, but cannot be proved to be so, nor even be proved to yield only correct theorems of finitary number theory.”

I read the Platonic Heaven post on this blog before getting to here.

http://www.newscientist.com/article/mg20527464.000-natures-hot-green-quantum-computers-revealed.html

Interesting?

Bob  Sure Alice! But first let me ask, how’s your permanent-measuring experiment working?

Alice  Pretty well from a technical point of view, Bob … yesterday we measured 10^6 outputs—of which no two were alike—and so we now have a set of 10^6 different scattering matrices whose permanents are supposed to be larger-than-average.

Bob  That’s interesting, Alice, because we’ve been running a forms-and-flow simulation on a tensor-network state-space, and we too have a set of 10^6 scattering matrices … and just like you, we’re not sure whether these matrices have larger-than average permanents or not.

Alice  Golly, that raises an interesting question, Bob: is there any way to distinguish between our two data sets? What if we just emailed them to a complexity theory group, asked them to apply any test—using polynomial resources, of course—that can distinguish them?

Bob  We simulationists have been watching for such a test, Alice, and it’s a pretty safe bet that ingenious new theoretical ideas are in the works; we’ll just have to wait while these new ideas develop.

But in the meantime, this theoretical work definitely is suggesting new insights into our quantum simulation codes.

Alice  Like what, Bob?

Bob  (sighs) Well, we simulationists have always taken granted that simulations can do something that experimentalists never can: simulate quantum post-selection experiments. But if we model the output measurement process too as a stochastic flow, the high-order photon statistics of simulated measurements are not those predicted by projection methods … and this deprives of our only efficient tool for efficiently simulating post-selection.

Alice  (laughs) But Bob, isn’t that good news? If forms-and-flow quantum simulations are weaker than QIP theorists generally supposed, that means the compatible triple of QIP illusions is safe!

Bob  (cheers up) Alice, you’re right. It appears that present knowledge allows: (1) QIP theorists to continue to believe that BQP is strictly stronger than BPP, (2) simulationists to continue to be believe that every experimental dataset can be simulated with polynomial resources (even from quantum experiments), and (3) experimentalist to continue to believe that new quantum physics is just around the corner in every experiment!

And what’s really striking, is that all three communities can show solid technical grounds for their growing confidence.

Alice  That’s a wonderful attitude, Bob!

But before we have a final discussion of whether QIP2010 changed the world—and if so, how?—why don’t you and I wait a couple of days, and see what turns up on Dick Lipton’s blog, Gödel’s lost letter and P=NP.

Dick’s topic this week is a very interesting one:  An Educational Extinction Event? Could Universities become extinct in the next twenty-five years?

Bob  That’s bound to be an interesting discussion, Alice. It’s pretty clear that the whole world is changing—not just the universities in it—and so the key question for you and me, and for theorists too, is whether QIP has a key role to play in that change.

Alice  (smiles again) I think we both agree that the answer is almost surely “yes” … and that QIP’s role is destined to be hugely positive.

Bob  Especially if our illusions all prosper!

Alice  Bob, I’ve been thinking some more about QIP2010 and whether it’s “a meeting that changed the world”.

Heck, Nature‘s list of six world-changing meetings describes pretty clearly what it takes to do the job!

Bob  Hmmmm … since you’re an experimentalist, Alice … and I’m an engineer … and the QIP attendees are mainly theorists and mathematicians … pretty clearly it’s no small challenge to change all our worlds.

Alice  That’s what I was thinking too, Bob, but it turns out that the Nature meetings didn’t actually change the world, but rather gathered together people who foresaw that the world was going to change, and decided to play an active role themselves in making that change happen.

Bob  Ho ho, Alice! Something tells me that you foresee that our world is going to change … and that you’re don’t intend to passively and watch it happen.

Alice  That’s absolutely right, Bob! For us experimentalists, a wonderfully exciting aspect of QIP2010 is the ideas presented for exploring physics beyond the standard model in benchtop-scale experiments.

Bob  But gosh … isn’t new physics nowadays to be found mainly at very small length-scales (high energy physics) or at very large length scales (cosmology)?

Alice  Yes, but QIP2010 points to another area of physics that is little-explored … classical datasets that are reproducibly measureable (with polynomial time and space resources) but not explicitly constructable (with polynomial computational resources).

Bob  You mean … like permanents of optical scattering matrices?

Alice  Yes, that is the simplest example I know, but there are others, like factoring large integers.

Needless to say, we experimentalists are completely agnostic about the various possible outcomes, which include: (1) we measure the permanent, and the polynomial-time Church-Turing Thesis is thereby refuted (modulo plausible CT assumptions), (2) it turns out that we can’t measure permanents with present-day technology, but solely for technical reasons that (plausibly) are non-fundamental, (3) it turns out we can’t measure permanents, because the polynomial-time Church-Turing Thesis is true, for deep and general mathematical reasons that we don’t (yet) understand.

For us experimentalist, the most exciting alternative is the one that finds new physics: (4) it turns out we can’t measure permanents, because the physical state-space of QM experiments is *not* a Hilbert space, but rather a lower-dimensional manifold, such that (again) the polynomial-time Church-Turing Thesis is true, but for fundamental physical reasons that we can observe in the laboratory.

Bob  (smiles) We simulationist engineers prefer alternative (4) so strongly, that in our professional lives we behave as though it’s true!

And in this regard we engineers are much like mathematicians; just as mathematicians behave as though every theorem has a proof, engineers behave as though every classical dataset can be simulated.

Alice  (laughs) … and we experimentalists behave as though new physical laws are just around the corner in every experiment.

It’s pretty amazing, Bob, that throughout the whole 20th century, all three of our illusions have served the world so well!

Bob  Yes, surely *that* is a deep mystery that is shared by math, science, and engineering.

So, Alice, how will the 21st century be changed by these QIP-inspired insights … assuming that all three of our professions get to keep our cherished illusions?

Alice  We’ll have to have at least one more discussion about *that* … but it seems pretty safe to foresee that big changes are coming.

Bob  Now that’s a mighty sobering topic to contemplate … but it’s an exciting one too.

Registering interest…

Alice  So, Bob, was QIP2010 a “Meeting that changed the world?”

Bob  Well I thought so, Alice … but I would be interested to hear your opinion.

Alice  For me, the exciting thing about QIP2010 was the (numerous) suggestions for practical experiments whose outcome cannot be predicted—even in principle—with classical computational resources.

Bob  Yes, that kind of experiment has fundamental importance for scientists and engineers alike. So, which experiments are you going to try first?

Alice  Scott Aaronson’s talk gave the simplest example, and the clearest theoretical discussion too. So I stopped at the airport gift shop and bought a 30-photon source and a optical coupler having 30^2 ports and a random unitary transfer function U … and I’ve been measuring photon-count outputs A all week!

Bob  Wow! How’s that experiment going, Alice?

Alice  Well … estimating the low-order mements of the distribution A is easy and fun! But estimating the high-order moments is very slow; we’ve yet to measure the same output A more than once … there are just too many permutations of output channels.

Say … Bob … you’ve got one of those fancy tensor network simulation codes … can’t you simply predict the probability |⟨A|U|Ψ0⟩|^2? The QIP folks tell us this probability is related to that sexy quality, the permanent of an A-dependent subset of U!

Bob  We engineers are excited about that too, Alice, but our simulations run into a glitch that is rather like your experimental glitch. You see, whenever we feed number state inputs into our tensor network simulation of your experiment, the simulation keeps asking for more memory, and running slower-and-slower.

So it looks like both of us require classical resources that are exponential in the number of photons, in order to reliably estimate the permanent |⟨A|U|Ψ0⟩|^2 … at least, if we do our experiments and code our simulations the naive way.

Alice  Heck … can’t you adjust your simulation code to not use so much memory?

Bob  We’re thinking about it, but in all the schemes we’ve thought of so far, this amounts to simulating a noisy version of your optical scattering experiment—so noisy that you wouldn’t be able to measure a permanent.

Alice  Hmmmm … well … perhaps the QIP2011 theorists will suggest to us some trickier methods for estimating/simulating the permanent … and more broadly, suggest still more classes of real-world quantum experiments that can’t be simulated, even in principle.

For sure, we can be confident that the QIP theorists will keep coming up with new ideas!

Bob  And whatever those new QIP ideas are, Alice, it’s a pretty safe bet that we engineers will be able to adapt many of them to make our simulation codes run faster, and our devices function nearer to quantum limits.

Alice  Gosh, so it’s clear that QIP20XX ideas have *already* changed the world!

Bob  Absolutely!

I kinda liked that a lot.