BosonSampling Lecture Notes from Rio
Update (January 3): There’s now a long interview with me about quantum computing in the Washington Post (or at least, on their website). The interview accompanies their lead article about quantum computing and the NSA, which also quotes me (among many others), and which reports—unsurprisingly—that the NSA is indeed interested in building scalable quantum computers but, based on the Snowden documents, appears to be quite far from that goal.
(Warning: The interview contains a large number of typos and other errors, which might have arisen from my infelicities in speaking or the poor quality of the phone connection. Some were corrected but others remain.)
The week before last, I was in Rio de Janeiro to give a mini-course on “Complexity Theory and Quantum Optics” at the Instituto de Física of the Universidade Federal Fluminense. Next week I’ll be giving a similar course at the Jerusalem Winter School on Quantum Information.
In the meantime, my host in Rio, Ernesto Galvão, and others were kind enough to make detailed, excellent notes for my five lectures in Rio. You can click the link in the last sentence to get them, or here are links for the five lectures individually:
If you have questions or comments about the lectures, leave them here (since I might not check the quantumrio blog).
One other thing: I can heartily recommend a trip to Rio to anyone interested in quantum information—or, for that matter, to anyone interested in sunshine, giant Jesus statues, or (especially) fruit juices you’ve never tasted before. My favorite from among the latter was acerola. Also worth a try are caja, mangaba, guarana, umbu, seriguela, amora, and fruta do conde juices—as well as caju and cacao, even though they taste almost nothing like the more commercially exportable products from the same plants (cashews and chocolate respectively). I didn’t like cupuaçu or graviola juices. Thanks so much to Ernesto and everyone else for inviting me (not just because of the juice).
Update (January 2): You can now watch videos of my mini-course at the Jerusalem Winter School here.
Videos of the other talks at the Jerusalem Winter School are available from the same site (just scroll through them on the right).
Follow
Comment #1 December 28th, 2013 at 4:56 pm
Lecture 2 says “These two classes are even related with the Riemann hypothesis: if it is true, this would imply a class of problems in BPP would be in P”- What is this referring to?
Comment #2 December 28th, 2013 at 5:06 pm
Does this mean no FQXI conference???
Comment #3 December 29th, 2013 at 1:25 am
Sean: No!! In a temporary bout of insanity, I agreed to leave the Jerusalem Winter School after I finish lecturing there, fly to Puerto Rico, attend the FQXi conference, fly back to Israel for the rest of my winter vacation there (and for another conference, this one a firewall one), and only then return to MIT. Honestly, if you weren’t going to be there I’m not sure I’d make the effort.
Comment #4 December 29th, 2013 at 1:34 am
Joshua #1: I just meant that we’ve known since the 70s that assuming the GRH, quadratic residuosity, finding primitive roots mod p, primality, and various other number-theoretic problems that I don’t remember are all in P (see here). Of course, for primality, we now know that it’s in P even without the GRH, which you could call a “successful prediction” of GRH if you were so inclined. 🙂
Comment #5 December 29th, 2013 at 8:28 am
Ah, I was confused because of the phrasing in the notes did not mention GRH but just RH. I wasn’t aware of any that were simply RH dependent.
Comment #6 December 29th, 2013 at 9:20 am
Josh #5: Sorry! I figured RH=GRH at both physicists’ and complexity theorists’ level of resolution. I hadn’t banked on mathematicians also reading the lecture notes. 🙂
Comment #7 December 29th, 2013 at 2:34 pm
You are obviously insane, but in this case it works to my benefit, so it’s okay.
Comment #8 December 29th, 2013 at 3:53 pm
Just a note, the correct name of “fruta do congi” is “fruta do conde” :).
Comment #9 December 29th, 2013 at 9:20 pm
Alex #8: D’oh!! Fixed.
Comment #10 December 30th, 2013 at 12:27 pm
With all that time in the air, I hope you’re taking DVT precautions.
Comment #11 December 30th, 2013 at 1:18 pm
Brad #10: No, I’m not. What precautions do you recommend?
Comment #12 December 30th, 2013 at 2:13 pm
I am not a doctor, but certainly stay hydrated, avoid alcohol and caffeinated drinks, flex and stretch your legs and feet. There is plenty of information on the web, some of which might even be valuable.
Comment #13 December 30th, 2013 at 2:40 pm
#3,#7 If you really think it is insane, the clear rational decision (regardless of DVT) would be to cancel; and feeling bad about it is a little price to pay for avoiding similar things in the future (but people will certainly understand). In fact, one way to make good of it would be to even skip both competing activities after Jan 4 and do something else you would like.
Comment #14 December 31st, 2013 at 7:58 am
Pedantic note, typo in lecture 3: the better determinant algorithm should have runtime O(n^2.373) rather than O(n*2.373)
Comment #15 December 31st, 2013 at 7:15 pm
Happy new year, Scott et al. In the Lecture 1 notes from Scott’s “Complexity Theory and Quantum Optics” mini-course in Rio de Janeiro there is an aside to the effect that “the video of the lecture should be posted soon”. I’ve not been able to find any such videos yet, so I’d like to ask anyone who knows where they are or sees them later to please let us know where they can be found.
Comment #16 January 2nd, 2014 at 11:10 pm
SECRET: The fact that NSA has determined that a specific classical public-key cryptography design is or is not secure against QC attack for algorithms for which the security or non-security is not widely known and publicly available.
TOP SECRET: The existence or nonexistence of any NSA plan or program to build a cryptanalytic-scale quantum computer.
Did I just break US law by quoting a TOP SECRET government document? How much of what the government does in quantum computing should be classified secret, including budgets? A friend of mine says, “who the hell do they think they are?” What should I answer him?
Comment #17 January 3rd, 2014 at 4:45 am
Vitruvius #15: I still don’t know what’s happening with the videos from Rio, but all the videos from Jerusalem are now up, and they cover essentially the same material! Enjoy! 😀
Comment #18 January 3rd, 2014 at 8:03 am
I wonder if this last “Snowden revelation” is actually a plant of NSA, an attempt to manage the news cycle. Because it is exactly the kind of exciting high-tech story that media gobble up, and everybody (and his brother) can have opinion on it .
Now that the TAO gear catalog was just published by SPIEGEL, NSA would welcome new headlines, including the expert speculations about how far NSA could have gotten towards building a quantum computer; it is far less problematic for them than explaining the “interdiction”, i.e. those Dell servers with pre-installed BIOS malware.
Comment #19 January 3rd, 2014 at 9:24 am
Loved Scott’s frank and straight debunking of the DWave hype in the interview! Good job!
I thought it was a great interview overall. Very balanced and hype-free.
Wish more QC coverage had this tenor.
Comment #20 January 3rd, 2014 at 12:15 pm
Scott!!! How much would the NSA have to pay you per year to leave your gig at MIT and to work on building (if possible) a QC for govt work? This isn’t just a hypothetical question. NSA people read this blog. If your figure is low enough you may have a new job this year….
Comment #21 January 3rd, 2014 at 1:16 pm
Hypothetical!!! Why on earth would the NSA want me? First of all, I’m not exactly known for my ability to keep my mouth shut. I’ve publicly opined on almost every imaginable topic (including criticizing the NSA). But more importantly, I know almost nothing that’s relevant to building QCs capable of breaking cryptography (and not even terribly much that’s relevant to building BosonSamplers). I’ve always been completely upfront that my interest is in the fundamental science: for example, in how quantum mechanics changes our understanding of the limits of computation. For actually building a scalable universal QC, you’d want experimentalists, as well as theorists who are experts in things like quantum error-correction (a topic I’ve never worked on, although many other theorists have).
Comment #22 January 3rd, 2014 at 2:07 pm
NSA does have “quantum” capabilities:
e.g. “Nevertheless, TAO has dramatically improved the tools at its disposal. It maintains a sophisticated toolbox known internally by the name “QUANTUMTHEORY.” “Certain QUANTUM missions have a success rate of as high as 80%, where spam is less than 1%,” one internal NSA presentation states.
A comprehensive internal presentation titled “QUANTUM CAPABILITIES,” which SPIEGEL has viewed, lists virtually every popular Internet service provider as a target, including Facebook, Yahoo, Twitter and YouTube. “NSA QUANTUM has the greatest success against Yahoo, Facebook and static IP addresses,” it states. The presentation also notes that the NSA has been unable to employ this method to target users of Google services. Apparently, that can only be done by Britain’s GCHQ intelligence service, which has acquired QUANTUM tools from the NSA.”
Comment #23 January 4th, 2014 at 12:08 am
Rahul, you better shut up or the NSA will terminate your career like it did to the Trailblaizer whistleblowers.
http://en.wikipedia.org/wiki/Trailblazer_Project
Comment #24 January 4th, 2014 at 1:15 pm
In principle can a quantum computer sift through astronomical amounts (or exponential amounts) of data to locate information without violating privacy?
Comment #25 January 5th, 2014 at 12:21 pm
The NSA product generator
http://ternus.github.io/nsaproductgenerator/
Comment #26 January 5th, 2014 at 1:49 pm
rrtucci,
Don’t forget the NSA has infiltrated the GMO industry.
If you eat any sweetcorn from Walmart, nano transmitters will make their way to your brain, and phone home anytime you have any weird thoughts!
Comment #27 January 5th, 2014 at 2:27 pm
come on, it is all good fun. I wish – with so many omnious-sounding names of the surveillance programs and gadgets that NSA uses – that someone would make an alphabet poem of them, something like the Gashlycrumb Tinies: “A is for Amy who fell down the stairs. B is for Basil assaulted by bears…”
Comment #28 January 5th, 2014 at 6:02 pm
Raoul, I believe that one is called JIFFYPOP in NSA’s TAO product catalog
Comment #29 January 6th, 2014 at 2:56 pm
Great lectures! Btw, the whole interaction with “Feynman’s ghost” a.k.a “the Oracle” was hilarious.
Comment #30 January 6th, 2014 at 6:42 pm
For those paranoid about the NSA, (and perhaps Facebook, Twitter, …), check out the following from today’s “Good Morning Silicon Valley:
http://www.siliconbeat.com/2014/01/06/cess-unsettling-message-everything-will-be-tracked/
This is about new products for sale to the public ** RIGHT NOW ** to track anything you can think of.
Comment #31 January 7th, 2014 at 9:30 am
Imagine what a field day J.Edgar Hoover or Richard Nixon would have had if these NSA tools had been available to them. Is it so unlikely that there exist similar people in positions of power in the US, either today or in the near future?
Comment #32 January 7th, 2014 at 10:34 am
Regarding your interview, all that business about Quantum Computers eventually triggering full nuclear explosions is making me really nervous.
Comment #33 January 7th, 2014 at 12:57 pm
rrtucci:
So what? Tracking technology has good and bad sides, but it is a reality.
Many people appear to be under the impression that [“bad guys”, big companies, foreign spys, etc.,]are not using tracking technology, and the US government should be prohibited from doing so.
Comment #34 January 7th, 2014 at 4:17 pm
Raoul,
You’re right, tracking can be a good thing, like when police are able to use a cell phone ping to track a kidnapping victim, etc. The problem is that we as a society are unwilling to draw *any* lines, and because of that, it’s safe to assume that the tracking will most certainly be misused at times.
As an example, take the FISA court, which recently re-authorized for 90 more days the mass collection of all Verizon (and perhaps other carriers’) phone call metadata. I believe anyone involved in creating the FISA court that had a good-faith expectation that it would serve as a safeguard against abuses might now be thinking that a court order covering everyone’s everything, everywhere may be outside the scope they were imagining when they voted for a law authorizing a secret court to decide extraordinary data collection requests on a case-by-case basis.
If we don’t create reasonable rules, we should all expect to be unpleasantly surprised sooner or later by something somebody decides to do.
Comment #35 January 7th, 2014 at 4:30 pm
Vadim, I mostly agree.
But the rules should be about what can be done with data.
All kinds of entities are harvesting data. Why shouldn’t the US know as much as Facebook or the Russians?
Comment #36 January 7th, 2014 at 5:38 pm
1) Users willingly sign up for Facebook. Don’t want Facebook collecting any more data on you? It’s as simple as closing your Facebook account.
2) I find it hard to believe that Russia has anywhere near as much access to data on Americans as the US does. This is probably not for lack of want, but the reality is that the US government gets to use its muscle against US-based companies more effectively than a foreign power can. I propose that since Russia does, undoubtedly, spy on American citizens-of-interest to the extent that it can, that we do the same to them. If Russia punched our citizens in the face, would a proper response by the US be to punch our own citizens even harder?
I disagree that limits should be strictly on use and not collection. There are no possible safeguards to ensure that data would not be misused at that point – whether institutionally, or just by bored analysts with access to tremendous amounts of personal information (I wonder how my ex-girlfriend is doing…). I hate to bring up a tired cliche, but if that came to pass, would we permit mandatory surveillance cameras in private homes, as long as the government promised to only use the information in the event of a crime? What could go wrong?
Comment #37 January 7th, 2014 at 6:07 pm
Vadim,
You are missing the point. Everybody is collecting as much data as they can. There is nothing you can do about it. That is the way the world has evolved to 2014. Get used to it.
Some of the data the US collects goes to good uses. You might have noticed the lack of planes flying into buildings lately. Many commenters say “That is not due to the NSA”. These same commenters agree airport security is a joke. And the war in Afganistan was a mistake. So what is the reason? Good karma?
Can you name any downside that has actually happened due to NSA?
Comment #38 January 7th, 2014 at 6:19 pm
Raoul Ohio @37,
One major issue in these sorts of contexts is the “chilling effect”. But if you want more specific, less abstract downsides, there have been many examples of “Love-int” where people with access to the data have used it to spy on significant others, exes, love-interests, and romantic rivals. See e.g. http://www.slate.com/blogs/future_tense/2013/09/27/loveint_how_nsa_spies_snooped_on_girlfriends_lovers_and_first_dates.html There has also been substantial diplomatic and economic fall back, where corporations are now less willing to store data in the US or be involved with US companies involved in IT.
Comment #39 January 7th, 2014 at 6:33 pm
Scott:
One of your main worries about quantum computing has always been “decoherence”. I came across this blog by Dr. M. Amin, lead theorist & chief scientist at D-Wave Systems Inc. Have you seen it, and if so, can you poke any hole in it?. Thanks.
http://dwave.wordpress.com/author/mhsamin/
Comment #40 January 7th, 2014 at 8:56 pm
Sol #39: It’s strange to call decoherence one of “my” main worries about QC, since it’s one of the main worries of absolutely everyone in the field—but especially of the many people who work on quantum error-correction, an important topic that I’ve never directly worked on myself.
I agree with Mohammad Amin’s blog post, at the abstract level he’s writing at: yes, decoherence can be basis-dependent (and generally will be, unless it’s something simple like the depolarizing channel), and yes, you can have decoherence in (say) the energy eigenbasis even while coherence is maintained in other bases. These are important points for the experts in decoherence, but they certainly don’t decrease the overall importance of decoherence as a concept!
Comment #41 January 7th, 2014 at 9:02 pm
Scott said:
But there are some things that make me think it’s not likely. One of them is that we know who the best experimentalists are, and yes the NSA is interested and talks to them and funds them, but we haven’t seen them hoovering them up like the Manhattan project.
That made me think of a counterexample, Bruce Kane. I have no inside information about the guy. All I know is what I’ve read on the Internet: that he started off brilliantly in quantum computing, by postulating the Kane quantum computer. After working in Australia for a while, he accepted a position at the U. of Maryland, where he still works. I always wondered how come, after such a brilliant start, we haven’t heard much about his work at the U. Of Maryland. And now I learn from the Snowden revelations that the NSA has a top secret project at the U. of Maryland that is building a QC that sounds very similar to the Kane computer
Comment #42 January 7th, 2014 at 9:16 pm
rrtucci@41:
I always thought you were, you know, sort of a jerk, but unless you know something specific to support your insinuations, I’m thinking that your comment is incredibly irresponsible — know what I mean? But who knows, I don’t follow rumors “on the internet” that close, and so maybe I’m alone on this . . .
Comment #43 January 8th, 2014 at 12:29 am
Thanks Curious.
It is well known that the classified QC work at the U. of Maryland is being conducted at the LPS (Laboratory for Physical Sciences) Here the LPS website says
Source
“LPS has housed an internal research program in quantum computing (QC) for several years, and it currently includes seven research groups. Four of the research groups experimentally investigate various solid-state systems at low temperatures, and are connected to either semiconductor-based or superconductor-based quantum computing. These groups are led by Bruce Kane, Kevin Osborn, Ben Palmer, and Michael Dreyer.
The remaining three research groups theoretically investigate a broad range of topics which include: solid-state quantum-computing systems, ground-state quantum computation, and quantum control. These groups are led by Frank Gaitan, Ari Mizel, and Charles Tahan. Further details on QC research at LPS can be found by visiting the links shown above.”
Comment #44 January 8th, 2014 at 4:23 am
Scott, I’m sure your readership would enjoy hearing your opinions on today’s arXiv posting by Max Tegmark: http://arxiv.org/pdf/1401.1219.pdf
It seems like it’s on a topic that is of some interest to you, so if you do read it, your commentary would probably be entertaining for us.
Comment #45 January 8th, 2014 at 6:21 am
jim #44: I’m at the FQXi conference on physics of information in Vieques, Puerto Rico right now, where I’m getting overdosed with cosmic speculation as it is (with Tegmark himself the maestro of the proceedings). This Onion article from 1999 gives a pretty good idea of what it’s like. So, sorry dude, but I don’t think I’ll also be able to take on Tegmark’s preprint right now. 🙂
Comment #46 January 8th, 2014 at 12:59 pm
rrtucci@43,
Didn’t see anything that would lead one to think he’s working in a secret project for the government, but again, I don’t follow these things as closely as you.
Assuming you’re right, however, it must be about time to post his address, phone number, pictures of his family and where they go to school, no? 🙁
Comment #47 January 12th, 2014 at 12:07 am
Curious #46, I think you are overreacting. It’s not like rrtucci is blowing the cover of some field agent. Even if his speculation was correct, working on some classified NSA efforts would not paint a bullseye on your forehead.
It’s ideal speculation as to what smart minds the NSA may a have attracted to do some classified QC research, and rrtucci labeled it just as that, a speculation.
Comment #48 January 12th, 2014 at 12:23 am
Curious #46, just to be clear on this, I don’t think there is anything wrong with a US citizen to work on classified projects for the American government. So I don’t really see why ‘outing’ Bruce Kane should pose any problem in this particular instance, as I cannot see how this puts him into any bad light or could be construed as a security risk.
Comment #49 January 12th, 2014 at 10:14 am
http://www.wired.com/threatlevel/2014/01/how-the-us-almost-killed-the-internet/all/
Comment #50 January 12th, 2014 at 10:58 am
quax,
You may be right. There probably isn’t some crazy person lurking out there who would seize on this information and try to do damage. Probably . . .
But I think you’re missing the point a bit, because putting him in a “bad light” seems to be exactly what was intended. For example, the comment by “rrtucci@49” is posted without explanation, and so it must be felt that it speaks for itself as justification for the previous related posts.
While you may not think there is anything wrong in working on classified projects for the US government, it’s clear that others view it somewhat differently.
Comment #51 January 12th, 2014 at 12:45 pm
Sorry to go off topic, but…
Someone in Kazakhstan is claiming to have found a strong solution for Navier-Stokes.
I know, I know! Yet I always get my hopes up. On the chance this actually pans out, you saw it here first!
http://bnews.kz/en/news/post/180213/
Here’s the paper:
http://www.math.kz/images/journal/2013-4/Otelbaev_N-S_21_12_2013.pdf
Comment #52 January 12th, 2014 at 4:15 pm
Curious #50, from rrtucci’s blog post on the subject I don’t get the impression that he wants to paint Kane in a bad light. He is snarky as always, but the overall sense is that he regrets that the work is qualified and hence cannot publicly appreciated at this time.
If he doesn’t like or appreciate somebody he is much more explicit.
Comment #53 January 12th, 2014 at 4:52 pm
As far as I’m concerned, no research into quantum computer devices or algorithms should be classified, period. From what I gather, DARPA funded the development of the internet as a non-classified project, and that worked admirably well.
I have nothing against Bruce Kane. General Keith Alexander, on the other hand…what a putz. Maybe Steven Levy should have titled his article: “How General Keith Alexander almost killed the internet”
Shit, I know that as soon as I press this button, I’m going to get into trouble… not again Bob
Comment #54 January 12th, 2014 at 6:41 pm
rrtucci #53, but, but … the General even build a classified Enterprise bridge replica at the US taxpayers expense in order to brief and bamboozle senators.
C’mon, such chutzpah deserves some respect!
Comment #55 January 14th, 2014 at 12:27 am
Scott,
Please tell us that BLACK HOLES AND QUANTUM INFORMATION
at Weizmann will be televised or that slides will be available.
If not, no big. The site indicates that that information isn’t out to the public. Thank you.
Comment #56 January 14th, 2014 at 2:20 am
dc #55: MY SLIDES ARE HERE. Enjoy! I don’t know if there are any plans to put videos online (I’ll ask).
Comment #57 January 14th, 2014 at 9:02 am
Scott,
Let me be the first to publicly ask for a comment:
http://arxiv.org/abs/1401.2910
😉
Comment #58 January 14th, 2014 at 2:18 pm
Mike #57: blog post is a-comin’!
Comment #59 January 15th, 2014 at 12:20 am
Mike, thanks for the pointer.
That (the result) would have been my guess.
Comment #60 January 16th, 2014 at 4:50 am
Dyakonov and D-Wave published a paper on the arxiv on the same day!
Dyaknov:
http://arxiv.org/abs/1401.3629
D-Wave:
http://arxiv.org/abs/1401.3500
Comment #61 January 16th, 2014 at 7:07 am
cf#60. M.Dyakonov wrote in sec.8
Measurement-based error correction transforms the state a|0> + b|1> to |0> or |1>, depending on what term is considered to represent an error, and this is not a linear operation.
What does it mean? Standard error correction schemes use only linear, unitary operations.
Comment #62 January 16th, 2014 at 8:10 am
Michal #60: Mmmgrrhhhh … and I also came down with a cold today. Assaulted from every direction?
Comment #63 December 21st, 2014 at 7:02 pm
[…] about permanents has come recently from boson sampling, for which we also recommend these online notes scribed by Ernesto Galvão of lectures given by Scott Aaronson in Rio de Janeiro a year ago. […]