Twitl-Optimized
Today I experiment with “tweeting”: writing <=140-character announcements, but posting them to my blog. Like sending lolcat videos by mail
Last week at QCrypt in Waterloo: http://2013.qcrypt.net This week at CQIQC in Toronto: http://tinyurl.com/kfexzv6 Back with Lily in between
While we debate D-Wave, ID Quantique et al. quietly sold ~100 quantum crypto devices. Alas, market will remain small unless RSA compromised
One speaker explained how a photon detector works by showing this YouTube video: http://tinyurl.com/k8x4btx Couldn’t have done better
Luca Trevisan asks me to spread the word about a conference for LGBTs in technology: www.outforundergrad.org/technology
Steven Pinker stands up for the Enlightenment in The New Republic: “Science Is Not Your Enemy” http://tinyurl.com/l26ppaf
Think Pinker was exaggerating? Read Leon Wieseltier’s defiantly doofusy Brandeis commencement speech: http://tinyurl.com/jwhj8ub
Black-hole firewalls make the New York Times, a week before the firewall workshop at KITP (I’ll be there): http://tinyurl.com/kju9crj
You probably already saw the Schrodinger cat Google doodle: http://tinyurl.com/k8et44p For me, the ket was much cooler than the cat
While working on BosonSampling yesterday, (1/6)pi^2 and Euler-Mascheroni constant made unexpected unappearances. What I live for
Follow
Comment #1 August 13th, 2013 at 7:40 pm
Regarding your blog tweet…
… do you have any opinion, Scott, of the following presentation from this year’s Black Hat conference?
The Factoring Dead: Preparing for the Cryptopocalypse
If you hadn’t heard, this presentation summarizes some work published just 6 weeks ago by Barbulescu, Gaudry, Joux, and Thomé entitled “A Quasi-Polynomial Algorithm for Discrete Logarithm over Finite Fields of Small Characteristic”. It comes to the provocative conclusion that the next “cryptographic black swan” for professional paranoiacs cryptographers to worry about is”
Comment #2 August 13th, 2013 at 7:53 pm
D’oh! At the risk of being neurotic, lemme just say that in my above comment:
1) “paranoiacs” should have been struck through (I guess comments here don’t support strikethrough… bummer)
2) the quotation mark ” before the final blockquote should’ve been a colon :, not a quotation mark ” (I guess I mistyped… bummer)
That is all. 🙂
Comment #3 August 13th, 2013 at 9:59 pm
Please. I’m happy to gift you more characters in case you’re running short. But there are few places left on the internet with any sustained, interesting (to me) writing. Don’t turn into a hash-tag diva.
Comment #4 August 13th, 2013 at 10:16 pm
I’m with Nilima. This twitter experiment has failed. Don’t waste your readers’ time with smug, vapid one liners. Give us something meaty, or nothing at all.
Comment #5 August 13th, 2013 at 10:31 pm
Actually, I owe you (Scott) an apology. It was rude of me to be dismissive of your experiments on your blog!
Comment #6 August 14th, 2013 at 1:28 am
The link to the LGBT conference seems to be broken.
Comment #7 August 14th, 2013 at 5:42 am
Regarding the relationship between BosonSampling and the Euler-Mascheroni constant, does the connection involve the coupon’s collector’s problem? http://en.wikipedia.org/wiki/Coupon_collector%27s_problem
Comment #8 August 14th, 2013 at 8:13 am
Moritz #6: Sorry, fixed!
Comment #9 August 14th, 2013 at 8:21 am
Ernesto #7: No, AFAIK there’s no relation to coupon-collector. If you care, π2/6 and γ both arose from calculating the moments of ln(Xn), where Xn is a chi-squared random variable with n degrees of freedom (or actually, its complex generalization — i.e., a sum of absolute squares of n independent complex Gaussians with mean 0 and variance 1). Calculating those moments let me understand the distribution of the product of squared 2-norms of the rows of an iid Gaussian matrix. And that, in turn, let me prove that the BosonSampling distribution can be distinguished from the uniform distribution in classical polynomial time.
Comment #10 August 14th, 2013 at 8:29 am
Nilima and Curly Q: Look, I had an unusually large number of things that I felt like announcing, but not writing whole posts about. And Sean Carroll, John Preskill, Richard Dawkins, and Steven Pinker all tweet, so I figured it was obviously worth trying once. And other people have considered me quaint and crotchety for not joining the Twitter bandwagon (“back in my day, all we had was blogs, and we liked it! now get off my lawn!”). But fine, I’ll go back to blogging.
Comment #11 August 14th, 2013 at 8:51 am
Twitter is an invitation to aphorism. It takes practice, and is worth stretching your mind this way.
Comment #12 August 14th, 2013 at 9:03 am
Bill Kaminsky #1: That was an excellent presentation; thanks very much for linking to it!
Yes, as they say, the situation is that there was a breakthrough this year, in solving discrete log in groups of small characteristic in (classical) quasipolynomial time. This doesn’t directly threaten Diffie-Hellman or RSA (which rely on groups of large characteristic), but if you’re a paranoid sort of person, it certainly increases your fear that Diffie-Hellman or RSA might fall in the foreseeable future. Or maybe not “fall” entirely—but even a modest improvement in the algorithms for large characteristic might force you to use huge key sizes if you want security, and that would make Diffie-Hellman and RSA much less convenient in practice.
So, yes, this might indeed goad some people into switching to elliptic curve cryptography, for which all the known attacks are still exponential-time—and which, as a result, was being used with much smaller key-sizes even before this discovery. (Of course, it’s conceivable that subexponential attacks will eventually be discovered for ECC as well. And we know ECC is breakable by a quantum computer, just as DH and RSA are.)
One omission in that presentation was that it never mentioned lattice-based (or LWE-based) cryptography—a form of public-key crypto that academic cryptographers have gotten more and more excited about, that’s not known to be breakable even by a quantum computer, that’s now been benchmarked in real implementations, and that’s much more different from DH, RSA, and ECC than any of them are from each other. I assume the reason for the omission is that lattice-based crypto still requires key sizes (and ciphertext sizes) that are too large to be “practical.” Still, the practicality has been improving, and I could imagine lattice-based crypto becoming competitive within (say) the next decade.
In any case, if I were a quantum crypto salesman, I’d certainly be trying to make hay right now of the discrete log progress, in hopes of ginning up some more interest in my devices.
Comment #13 August 14th, 2013 at 9:11 am
With the risk of playing captain obvious, but you could use both. Twitter is good for sharing links and one-liners while the blog is good for writing.
Btw, I am also interested in what you (Scott) think about the recent advances in factoring mentioned in the first comment. And a related subject. It seems many people think Elliptic Curve is immune to future attacks, but in a lecture on youtube I percieved it like you said that a hypothetical future quantum computer could also break EC, (ie any crypto based on abelian groups). Was that correctly percieved?
Comment #14 August 14th, 2013 at 9:11 am
Sorry, you answered while I was typing the comment 🙂
Comment #15 August 14th, 2013 at 11:05 am
“…a week before the firewall workshop at KITP (I’ll be there)” <– hooray! And then you'll give us your thoughts?
I am a non-expert but *quite* intrigued by these developments. The more I think about ER=EPR the deeper it seems. The interior is topologically nontrivially connected to a distant location, and this is how the monogamy is resolved.
Final quick question: have you seen 1308.0289 (from your institution)? Written by an undergrad and a Pappalardo fellow.
Comment #16 August 14th, 2013 at 12:41 pm
Scott,
Concerning BosonSampling, it looks like you’re working on a rebuttal of some recent work by Cogolin et al:
http://arxiv.org/abs/1306.3995
I’m looking forward to reading it!
Comment #17 August 14th, 2013 at 2:31 pm
Anthony #16: Yeah, you figured it out. 🙂 There are some rebuttals of that paper that are trivial to give. E.g., there’s no reason on earth to ignore the actual beamsplitter settings (which they strangely call “side information”)—would they also average over all possible inputs N to Shor’s algorithm, in order to claim that the output p*q is “just a couple of random prime numbers, which would be easy to generate with a classical computer”? Nor, as far as I know, is there any reason to do BosonSampling with so many photons that you couldn’t even verify the output classically—the goal is just to show you can solve the problem faster quantumly, and for that 20 or 30 photons should suffice! Furthermore, I thought we were quite clear about all this in our original paper.
However, instead of just writing a rebuttal paper that reiterated these simple points, I decided that I wanted to go further, and use even their mistakes as a jumping-off point to do something new and positive. Hence the result that I guess I’ve “announced” in comment #9. 🙂
Comment #18 August 14th, 2013 at 3:32 pm
Clayton #15: Yes, of course I’ll give you my thoughts! Indeed, not being an expert on these topics, serving as a sort of “blogger/journalist” might be the only useful thing I can do at this workshop. (Well, that and explaining the computer-science underpinnings of the Harlow-Hayden paper, if anyone wants to understand them.)
Now, regarding the ER=EPR paper: I read it and confess that I didn’t understand it. Indeed, one of my hopes for this workshop is that I’ll leave understanding it better.
I actually have no difficulties with one direction of Maldacena and Susskind’s claimed correspondence between quantum entanglement and Einstein-Rosen bridges. Namely, I can easily believe that, to whatever extent ER bridges make sense at all, they’re best understood as simply EPR pairs, with one qubit at each throat of the wormhole.
It’s the other direction that gives me difficulties. Why should I discuss arbitrary entangled states—including in ion traps, superconductors, and other relatively “humdrum” systems—using the exotic language of wormholes and general relativity? What do I gain by doing that? I feel like I already have mathematical tools for understanding entangled qubits that work just fine, thank you—so what do these new ones bring to the table?
More pointedly, even if a singlet state (|00⟩+|11⟩/√2) can be analogized to an ER bridge, how on earth would the analogy extend to more complicated entangled states on millions of qubits—like, say, a high-temperature superconductor, or the states arising in Shor’s factoring algorithm? If those states are “bridges,” then where does the bridge start and where does it end? 🙂
Maldacena and Susskind notice the problem, of course. As far as I understand, their response is simply to say that for sufficiently complicated states, the “classical geometric picture” of spacetime will likely break down, so that one will need to switch to a “foamier” quantum picture. Well, that’s fine, but didn’t we already have the quantum picture for such states? 🙂 So, as often the case, the real question is less about truth or falsehood than about usefulness: what does the new language buy us? what does it tell us that we didn’t know before? That’s exactly what I’m hoping to understand better at the workshop.
Comment #19 August 14th, 2013 at 10:38 pm
If you want to imitate twitter, you can’t correct broken links!
Also, you have to post in reverse chronological order (“Think Pinker was exaggerating?” above “Steven Pinker stands up for the Enlightenment.”)
Comment #20 August 15th, 2013 at 11:22 am
Scott #18 – thanks for your reply! I think this is exactly the right direction to take the discussion.
I think for instance that http://arxiv.org/abs/1308.0289 asks (or sets the stage nicely for asking) those questions, too. The point, as I see it, is that now we *are capable of asking* in a well-formulated, precise way: “what is a quantum ER bridge?” or more deeply, “what is quantum geometry?”
So to answer your question: the other direction purchases some guarantees about how quantum geometry *has to work,* which is totally non-trivial and new (to my mind). Knowing things about the properties of the entanglement picture tells us how the quantum ER bridge must behave – as 1308.0289 makes clear, it must be able to have positive interaction information, which is not a property of the classical geometry at all.
Or maybe I’m wrong! Keep us posted!
Comment #21 August 15th, 2013 at 9:52 pm
You can see how out of touch Scott is, by the fact that he has no hashtags in his “tweets”.
Comment #22 August 16th, 2013 at 1:27 am
In #18 you noted, Scott, that “as often the case, the real question is less about truth or falsehood than about usefulness: what does the new language buy us? what does it tell us that we didn’t know before?” Aye, you’ll be an engineer yet, lad. But seriously, sir, I love your shtick.
Comment #23 August 16th, 2013 at 2:28 pm
Vitruvius #22: Well, I think of science as nothing more or less than the “engineering of good explanations.” 🙂
Comment #24 August 20th, 2013 at 1:23 am
Did this blog just turn into marginalrevolution.com?
Seriously though, I say constrained writing is fun, let the experiment continue!
Comment #25 August 22nd, 2013 at 7:04 pm
Scott, to understand your KITP talk, could you help me understand what “maximally entangled” actually means? I am confused about states like (|000⟩+|111⟩/√2). It seems to me that 1st and 2nd qubits are maximally entangled as measuring one of them tells me everything about the other. Same is true about 1st and 3rd qubits. But now it looks like 1st qubit is maximally entangled with both 2nd and 3rd qubits in contradiction to the entanglement monogamy. What am I missing?
Thanks for your time!
Comment #26 August 23rd, 2013 at 3:24 pm
Late to the party, I know, but I see no one else has remarked on the Wieseltier thing. I’m always ready to hate on the ignorami, but in this case, giving the Brandeis speech a quick read, I don’t really see what the problem is. It’s just an encomium to the humanities, and by extension to the students who pursue and love those subjects, along with an overly extended complaint that we all walk around with our noses in our iPhones, thanks to our obsession with unconnected facts to the exclusion of ideas. “[K]nowledge is to information as art is to kitsch…” And then before he goes off on “scientism” he stops to praise the actual practice of science.
Clearly we’d be better off as a society if the level of scientific understanding were higher. Fewer unproductive arguments about climate change, GMOs, cancer-causing cell phones, etc. But he’s not complaining that people study science too much. He’s just objecting to its casual invocation in contexts where what’s being done or said isn’t actual science.
I’ve seen reference to things he’s said or done elsewhere that might be more disagreeable, but this doesn’t seem like the right target.
Comment #27 August 23rd, 2013 at 9:03 pm
Stas #25: A whole post about the KITP workshop is (hopefully) coming soon!
In the meantime: the 3-qubit state you wrote is called a GHZ state. In my talk, I was only interested in bipartite entangled states (between the qubit B and the many-qubit register R), for which quantifying entanglement is vastly less complicated than it is in the multipartite case. In particular, by “maximally entangled,” I simply meant that it’s possible to distill one EPR pair between B and R, by acting unitarily on R alone.
Comment #28 August 26th, 2013 at 2:54 pm
The link to the photon detector led to video showing how we can topple the empire state building using Dominos. Cool!
Comment #29 September 15th, 2013 at 11:25 pm
Good work, keep it up!