So today I got to attend a wonderful talk on quantum supremacy by Umesh Vazirani, at the CMU theory group’s weekly seminar. It was particularly nice because the talk was a lighter on the technical side. I was actually quite star-struck; the attendees included Manuel Blum (recipient of the Turing Award)1, as well as a host of professors whose classes I’ve either taken or want to take. (I also saw a few of my TAs.)
The talk itself was great, although being quite tired, I may have dozed off slightly when Prof. Vazirani got into the weeds of a protocol for testing quantum supremacy. One particular thing that was very cool was a connection to the collapse of the polynomial hierarchy, which is something that came up in my complexity theory class.
In high school, I had a little bit of exposure to quantum computing; I did a short mentorship at the MITRE quantum information science group at Princeton, where I was taught the basics by a physicist. Since then, I’ve had a somewhat casual interest in the topic, but it was not until studying some theoretical computer science in college that I could appreciate it more.2
The talk somewhat reminded me of another talk about quantum computing that I attended last fall. This was at Penn, where I was attending a hackathon; the talk was given by a Bloomberg employee. The Bloomberg talk was aimed at more of a popular audience, so a lot of the claims were naturally less rigorously stated, and more than a few of them contained errors.3
Probably the most egregiously wrong claim was that quantum computers can solve NP-complete problems (with good efficiency and high probability4). I think the example given in the presentation was the traveling salesman problem. The justification for this (when people present one) is usually Grover’s search algorithm. But this is not sufficient to solve an NP-complete problem via a naive brute-force search for a witness5, since it gives only a quadratic speedup, whereas there may be exponentially many candidates for the witness. Indeed, the relationship between NP and BQP is not known.
Another example was the claim that a quantum computer could radically increase the amount of available memory, because qubits can be in superpositions. Yes, superposition can give you an state space for qubits, but according to people smarter than I am, Holevo’s bound implies that you cannot get more than classical bits of information out of this by measurement. Quantum computers are cool, but they aren’t magic.
I guess the point is that “hot” technologies are often hyped up a lot. Hearing the misinformation in the Bloomberg talk made me realize that others are probably “over-hyping” other hot topics that I am not very familiar with, like blockchains or machine learning.6
Funny thing: I was confused at first over the description of Google’s famous quantum supremacy experiment from last year. Then Manuel Blum asked a question about just that!↩︎
Examples: knowing classical circuit complexity helps a bit with quantum circuits, and knowing some basic complexity classes is useful.↩︎
I wasn’t as bothered by the errors in the talk as I was by the speaker’s attitude. During a Q&A session after the talk, she more or less said that requiring strong math prerequisites before getting into quantum computing was tantamount to gatekeeping. I think it’s better to acknowledge when you’re out of your depth—as I am with a lot of more advanced topics—and trust the experts.↩︎
It also usually isn’t explained what it means for a quantum computer to “solve” a problem, which is best understood analogously to classical probabilistic algorithms. Also, how big of a practical breakthrough this would represent depends strongly on the problem; we may already have fast classical probabilistic or approximation algorithms for some problems, although this is veering into hardness of approximation, a different topic.↩︎
Sorry, I just had to throw in the word “witness.” The word has become a running joke in my homework group because of how much we overuse it.↩︎
Maybe some of the ML stuff is justified. At the time of writing, it looks like DeepMind just published an incredible breakthrough in protein folding.↩︎
Comments