I **am** proud of what I wrote on the board. My hope is that hundreds of years of research will eventually vindicate me and that future scientists will speculate endlessly about what proof I could have had using only 21st century techniques.

Well, I can at least clarify some of the facts. First, Scott’s reading is indeed correct: “NP \subset BQP but the proof is too small to fit on this blackboard…” That’s what we (or at least one of our number) wrote on that day on the board, no dispute about that. Second, I wouldn’t say the author (or anyone here) is particulary proud of the silly joke (Aram? ;-). But then, what we, or indeed most people, write on blackboards during discussions is not meant to reflect eternal mathematical truth – any trespasser on such a discussion reads, believes and photographs at their own risk. Rather, those marks of chalk are the like waymarks on our quest for said truth. Third, it is undisputed that we (i.e., the University of Bristol) _did_ after all, even after reviewing the pictures and spotting the glaring gap in the proof on the board, published the cursed witness to our ineptness – which begs the real question: why? This (as most things here in the Southwest of England) is kind of hard to answer – at least in official function. My personal view is that of indomitable inventor Wallace (of Wallace and Gromit, hailing from Bristol’s Aardman animation studios): try, try, and try – and if you still don’t succeed, at least you’ll have a jolly good afternoon crowned with a nice hot cuppa with scones.

Oh, and about Aram – did I mention that this is England? where else do you think people “disappear” to on a weekend as this, than to London?

]]>That’s impossible ðŸ™‚

]]>*For example, suppose tomorrow someone found an oracle relative to which NP \in BQP. Would you think that the unrelativized case was any more likely?*

No, since I can already give you such an oracle today! NP^{PSPACE} = BQP^{PSPACE} = PSPACE. ðŸ™‚

*What if they showed NP \in BQP relative to a random oracle?*

That’s impossible. We already know NP ⊄ BQP relative to a random oracle, though I don’t take that as grounds for belief.

*what if neurobiologists found that the human brain is, in fact, a quantum computer?*

That would be an incredible and unlikely discovery that might cause me to reconsider my beliefs about all sorts of things — it’s hard to say.

*what new information would significantly change the Bayesian probability, for you, of Bristolâ€™s homepage being correct?*

OK, I’ll give you a few examples:

* If someone showed that Graph Isomorphism and Approximate Shortest Vector were in BQP (or better yet, that SZK⊆BQP).

* If someone found an efficient quantum algorithm to invert any one-way function (or even any trapdoor one-way function).

* If someone showed coNP⊆QMA.

* If someone built a scalable quantum computer, ran the adiabatic algorithm to search for proofs of the Riemann Hypothesis with at most 10 million symbols, and quickly converged to the ground state (i.e. proof).

(My next suggestion: use the quantum computer to search for a proof that NP⊆BQP!)

OK, Scott, we’re all familiar with your views on NP \in BQP. What I want to know is, what evidence, if any, would make you reconsider your position?

For example, suppose tomorrow someone found an oracle relative to which NP \in BQP. Would you think that the unrelativized case was any more likely? What if they showed NP \in BQP relative to a random oracle?

And (I’ll admit it, this is my favorite) what if neurobiologists found that the human brain is, in fact, a quantum computer? As you point out, our distant ancestors didn’t need to factor large integers or solve the discrete log problem or do searches in O(\sqrt{n}) time…but it’s conceivable that they mighta had a use for solving NP-complete problems! Short of someone actually finding a BQP algorithm for 3SAT (or proving the lower bound in the other direction), what new information would significantly change the Bayesian probability, for you, of Bristol’s homepage being correct?

Apologies for the off-topic-ness.

]]>