Scott in Scotland
I’m in Edinburgh this week to visit my wonderful old friends Elham Kashefi and Rahul Santhanam, and to give a series of talks. It’s my first visit to my “ancestral homeland,” and as you can see above, I’ve enjoyed visiting my namesake monument and eating some freshly-ground haggis.
Earlier today, I was delighted to meet the matrix-multiplication-exponent-lowerer and unwilling Shtetl-Optimized celebrity Andrew Stothers, and to treat him to lunch. (I’d promised to buy Andrew a beer if I was ever in Edinburgh, to apologize for the blog-circus I somehow dragged him into, but he only wanted a diet Coke.) I’m now convinced that Andrew’s not publicizing his lowering of ω was mostly a very simple matter of his not being in contact with the theoretical computer science community. One factor might be that, here at U. of Edinburgh, the math and CS buildings are on different campuses two miles away from each other!
I apologize for the light-to-nonexistent blogging. To tide you over until I have time to post something real, here are some extremely-interesting quantum information papers that appeared on the arXiv just recently: A multi-prover interactive proof for NEXP sound against entangled provers by Tsuyoshi Ito and my postdoc Thomas Vidick, and Bell’s Theorem Without Free Will by Tobias Fritz.
Follow
Comment #1 July 12th, 2012 at 2:10 pm
I can’t quite decide how interesting Tobias Fritz’s paper is. Bell already emphasized that the decision as to what measurement is made on each system should come from sources that can be treated as effectively random, independent of each other, and independent of the systems we are measuring. Fritz seems to be pointing out that one way of generating this randomness is to measure half of an entangled state and then use the other half as a control variable that decides which measurement to make.
On the other hand, the idea that there can be a classical model for the joint probabilities obtained in an experiment, but that (subject to natural constraints) there is no classical model for the conditional probabilities, seems interesting. I just don’t know what to make of it yet.
Comment #2 July 12th, 2012 at 2:12 pm
Scott any comments on PRL 108 260501, “Quantum measurement occurrence is undecidable”?
Comment #3 July 12th, 2012 at 2:12 pm
Mathematician proves a theorem.
Earth-shattering result to computer scientists.
Just another Tuesday to mathematicians.
Comment #4 July 12th, 2012 at 2:49 pm
You’re in my city! If you want a lovely acai milkshake, visit the Brazilian cafe near the informatics building. I don’t know about other drinks.
Comment #5 July 13th, 2012 at 2:40 am
Hi Matt!
I’m happy to hear that my paper found a few readers. (Thanks, Scott!)
Then yes, the simple trick that you describe is how to translate a standard Bell scenario into the new formalism. My main point is that this leads to Bell-type theorems without the need for free will. Many people seem to take it as given that “nonlocality” can only exist in scenarios with measurement choices available; I would like to point this out as a misconception (which I had myself until less than a year ago). If you want so, my main point is educational.
The control-variable-trick is just one way to prove such Bell-type theorems; I hope that others will be found! Which highlights the second main point: besides incoporating standard Bell scenarios, thanks to the trick, the new formalism contains many other scenarios which are not of that form (see e.g. Thms 2.21, 3.8). The fact that some of these new scenarios have been considered before by mathematicians in a completely different context should be an indication for being on the right track. Given that standard Bell scenarios have found several information-processing applications, I want to ask: could the new scenarios also have such applications?
Finally, I think it’s natural that some people disagree about the importance of this stuff. The discovery of water on Mars was completely stunning to me, but probably expected by many experts. The only thing that one can objectively say is that water on Mars is infinitely more interesting than my paper!
Comment #6 July 13th, 2012 at 4:05 am
Did Elham take you to the Whisky Society? It’s worth a visit.
Comment #7 July 13th, 2012 at 4:24 am
Paul #2: I liked that paper! Cute, simple, something many other people could have thought of but didn’t. Once you have something that looks so much like the Matrix Mortality Problem, it’s not at all surprising that you could get undecidability — but the fact that the corresponding problem with nonnegative matrices is decidable is what really makes it interesting.
Comment #8 July 13th, 2012 at 4:26 am
keith #4: Thanks for the rec! I’ll give it a try.
Comment #9 July 13th, 2012 at 4:28 am
Joe #6: Yes, the Whisky Society is where the photo was taken of me eating haggis!
Comment #10 July 13th, 2012 at 4:37 am
Mathematician proves a theorem.
Earth-shattering result to computer scientists.
Just another Tuesday to mathematicians.
Anonymous #3: If you were aiming for the snarkiest comment ever left on this blog, nice try but you’ll need to go snarkier. 🙂
Seriously, granting that what you say is indeed pretty common, shouldn’t our mathematician friends be grateful that someone else actually cares what they do, and is able to vivify their theorems with a meaning and purpose that they themselves can’t?
(OK, that was my snark for today…)
Comment #11 July 13th, 2012 at 6:09 am
Matt #1: I agree, from one perspective Tobias is “merely” presenting Bell’s theorem in what I always thought was the right way: as a statement that has nothing inherently to do with the free will of the experimenters, but only with the independence of various sources of randomness. What made it more interesting to me was that Tobias managed to leverage that philosophical perspective into a whole bunch of neat technical results and (even more so) open problems. Anyway, while my ardor has since cooled a bit, I got pretty excited reading the paper on the plane to Edinburgh; Dana can testify that I wouldn’t shut up about it.
Comment #12 July 13th, 2012 at 9:13 am
Scott,
Pretty awesome to have a country named after you 🙂
Comment #13 July 13th, 2012 at 11:32 am
A few weeks ago our quantum seminar featured Michael Ben-Or who explained to us the recent exciting result by Ito and Vidick. This was a very unusual talk. It was based on a videotaped lecture by Vidick, which was often interuppted by questions from the audience that Michael and Dorit tried to explain. It was almost like Michael and Dorit were two provers trying to interactly convinced us about that work. Of course, Michael was part of the first tean that introduced multi-prover interactive proof systems in the late 80s.
Comment #14 July 13th, 2012 at 4:03 pm
keith #4: Thanks again!! The acai smoothie was acailicious.
Comment #15 July 14th, 2012 at 3:57 pm
Gil: I guess that makes me the (non-interactive) oracle…I’d be curious to see a video of the whole proof system 🙂
Comment #16 July 17th, 2012 at 7:50 pm
No remarks on the Higgs boson? How dare you! 😉
Comment #17 July 21st, 2012 at 9:49 pm
Tobias #5: I took some astronomy classes way back when we already had good satellite telemetry but no conclusive evidence for water. That why I wasn’t all that surprised when it was finally confirmed. Still thought it was mega cool – just not terribly surprising. There are many formations on Mars that that are spit images of dried out riverbeds, so the consensus has long been that Mars had a watery past and that chances are good that some of this water was still there.
As to your paper – I quite like it. There is still an awful lot of confusion around the Bell theorem and this is quite a nice take on it that I think could open up some additional perspectives.
Comment #18 July 21st, 2012 at 9:53 pm
@Scott, thanks for the links to the papers.
I musty admit I am a bit surprised to learn that a country has been named after you 🙂 So the next logical question: Will you now support Scottish Independence?
Comment #19 July 29th, 2012 at 5:22 pm
Do they pronounce Edinburgh “Edinborough”?
Comment #20 August 3rd, 2012 at 8:06 pm
Hans: no, it’s pronounced “Edinbruh”: three syllables, not four. The sound at the end is a neutral vowel (a schwa).