University takes unfortunate stance on existence of quantum algorithm
The homepage of Bristol University now prominently features a photograph with the words “NP ⊂ BQP, but the proof is too small to fit on this blackboard.” Hat tip to Aram Harrow, who’s also the apparent culprit behind this embarrassment to his employer.
Follow
Comment #1 October 26th, 2007 at 11:17 am
to me it looks like it says, “but the photograph” and then i cant read any more. is there a bigger version somewhere?
Comment #2 October 26th, 2007 at 11:21 am
Aram?
Comment #3 October 26th, 2007 at 12:40 pm
Aram’s non response is clearly an indication that the equation is indeed true, and that Aram has been abducted by the British intelligence services.
Comment #4 October 26th, 2007 at 12:53 pm
It may be just ‘NPC’ and ‘BQP’ written next to each other. I do not clearly identify the 3rd symbol as \in.
Comment #5 October 26th, 2007 at 1:00 pm
This is a weaker corollary of a result known since the 1970s. In the famous picture of Rivest, Shamir and Adelman, the blackboard in the background clearly states “therefore [three dots], P=NP.”
Comment #6 October 26th, 2007 at 1:09 pm
I thought that the blackboard was just part of the site’s Halloween theme decoration.
Comment #7 October 26th, 2007 at 6:00 pm
Any crime scene investigators read this blog?
Comment #8 October 27th, 2007 at 3:14 pm
I love it that Bristol U is confident enough to say on its home page: “Yes, that’s what we do for a living: we stand in front of blackboards filled with equations and we are proud of that.”
Comment #9 October 27th, 2007 at 9:52 pm
At the risk of spreading the doofosity virus (and/or being added to the FAQ Of Death):
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.
Comment #10 October 27th, 2007 at 10:18 pm
is it conceivable that they might have had a use for solving NP problems (nothing comes to mind really)? i would imagine, even if faced with NP problems, approximate solutions would have been more than adequate in nature. though i have no credentials so id really love to hear other peoples opinions. and wait a minute, since we have no clear link that NP is in BQP, even if the brain were a quantum computer (my money on no), it wouldnt really imply that it had evolved from a desire to solve NP-complete problems, right?
Comment #11 October 27th, 2007 at 10:32 pm
Harrison:
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! NPPSPACE = BQPPSPACE = 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!)
Comment #12 October 28th, 2007 at 2:18 am
“For example, suppose tomorrow someone found an oracle relative to which NP \in BQP”
That’s impossible 🙂
Comment #13 October 28th, 2007 at 6:08 pm
Being officially a representative of the University of Bristol, it seems I have to go for my first post here…
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?
Comment #14 October 29th, 2007 at 1:02 pm
Whoa! I had been using the wrong RSS feed for Shtetl-Optimised (as it’s called over here) and missed seeing my name in print.
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.
Comment #15 October 29th, 2007 at 1:06 pm
and that ? is meant to be a \subset
Comment #16 November 1st, 2007 at 10:59 am
I recently figured out another prover of NP \subset BQP standing next to aram…
Comment #17 November 6th, 2007 at 2:29 pm
When a video crew came to film people at my workplace in connection with a paper which had been published in Science, I wrote a “proof” on a blackboard which began with supersymmetric quantum mechanics and proceeded, via several very pretty category-theoretic diagrams, to P != NP.