“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.

]]>