My 5-minute quantum computing talk at the White House | Hacker News Reader

My 5-minute quantum computing talk at the White House

scottaaronson.com

91 pointssndean14 comments

> I like to say that a fast classical factoring algorithm might collapse the world’s electronic commerce, but as far as we know, it wouldn’t collapse the polynomial hierarchy!

This is my favourite quote because it sums up pretty nicely the most common misconceptions people have about factorization, crypto and quantum computing. Of course the first part is hyperbole, but still put very nicely.

I liked the '10 second' explanation on what quantum computing is that Scott gave some time ago, a propos the Justin Trudeau incident [0]. And here's other experts' '35 seconds' versions besides Trudeau's [1].

[0] http://www.scottaaronson.com/blog/?p=2694

"I say something about how a QC is a proposed device that would solve certain specific problems much faster than we know how to solve them today, by taking advantage of quantum mechanics, which generalizes the laws of classical probability.

Then I talk about how you’d never talk about a -20% chance of rain tomorrow, but quantum mechanics is based on numbers called amplitudes, which can be positive or negative or even complex numbers.

And how, if an event can happen one way with a positive amplitude and another way with a negative amplitude, the two possibilities can “interfere destructively” and cancel each other out, so that the event never happens at all. And how the state of a QC with (say) 1000 bits would have one amplitude for each of 21000 possible settings of the bits—an astronomical amount of information, if one wanted to write it down classically, for example in order to simulate what the QC was doing classically.

But about how, when you measure the QC’s state, you just see a single random output (with its probability determined by its amplitude), not the gargantuan list of possibilities. And about how the goal, in QC, is always to choreograph things so that the possible paths leading to each wrong answer interfere destructively and cancel each other out, (say) some having positive amplitudes and others negative, whereas the paths leading to right answer reinforce.

And how this is a very weird and specialized capability—it’s not nearly as simple as “trying all the answers in parallel” (if you did that, you’d simply observe a random answer), nor is it just a smaller or faster version of ordinary computing (a QC might even be “bigger” or “slower” than an ordinary one; all the hoped-for advantage comes from the QC’s ability to create interference patterns).

Finally I talk about how a QC is known to give huge advantages over any known classical algorithm for a few tasks of practical importance (quantum simulation, breaking almost all the crypto used today…), and it might also give some advantages for broader goals like optimization and machine learning, but that’s an active research topic, and if the advantages exist they’ll probably be more modest and/or specialized."

[1] http://www.macleans.ca/society/science/trudeau-versus-the-ex...

Possibly the best place to see massive spin in action.

I see what you did there.

I have Idea. But... who cares :)

"I like to say that for me, the #1 application of quantum computing—more than codebreaking, machine learning, or even quantum simulation—is just disproving the people who say quantum computing is impossible! So, quantum supremacy targets that application."

\facepalm

Could you elaborate on why you dislike this quote? Maybe there is some context missing: for a lot of researchers quantum computing is interesting because of how its existence informs fundamental questions in physics and math like the Church-Turing thesis. For those people the code breaking application are indeed pretty boring, just like internal combustion engines can be boring for people working on statistical physics and thermodynamics.

Well, it's not really an application, is it? It seems like a fancy way of saying, "the stuff I'm working on isn't good for anything - it's just to satisfy my intellectual curiosity". Which is fine as far as it goes, but not exactly inspiring.

I would say for me it is the applications that are boring, not the fundamentals behind them.

For a lot of people fundamental laws of nature are deeply inspiring, tangentially because of a belief that those fundamental laws and their deeper understanding bear fruit beyond our wildest imagination. Compared to this it is easy to see how today's applications are just boring.

Sure, today's technology was yesterday's research project, but you can not fault people for being excited more about current research than about applications of yesterday's research.

PS: However I agree that the quoted statement was poorly phrased to convey this sentiment. From what I know about the speaker I am fairly confident that this is what he was trying to say.

Maybe we're reading it differently, but it seems to me that he's admitting there are practical applications, but their importance is unclear if we can't first demonstrate that the QC approach is superior.

If you continue reading, he's making an argument that comes together at the end:

"After this scientific milestone is achieved, I predict that the whole discussion of commercial applications of quantum computing will shift to a new plane, much like the Manhattan Project shifted to a new plane after Fermi built his pile under the Chicago stadium in 1942. In other words: at this point, the most “applied” thing to do might be to set applications aside temporarily, and just achieve this quantum supremacy milestone—i.e., build the quantum computing Fermi pile—and thereby show the world that quantum computing speedups are a reality."

He's saying we need to do some purely scientific experiments to demonstrate the fundamentals of quantum computing before we start trying to use it for codebreaking or AI.

Quantum PC master race? /s

"Quantum supremacy" experiments are those that can show that quantum computing can indeed do things that classical computers can not, without having to build an entire quantum computer. They are important in practice because they are "cheap" checks on whether our premises are wrong and important in theory because they show interesting new ways to think about the problems we want to solve.

> "Quantum supremacy" experiments are those that can show that quantum computing can indeed do things that classical computers can not [...]

Putting it the way you did is very misleading for folks not familiar with the difference between complexity and computability.

Quantum computing is not about computability, because it is well agreed that a quantum computer can solve exactly all problems a classical computer can and vice versa (Church–Turing thesis).

What is not agreed on is if there are problems that a quantum computer can solve more efficiently than a classical computer (where more efficiently means either in time or space and has a strict mathematical definition).

Now, put simply, if someone could come up with a computer that would solve a task faster than the theoretical limit of a classical computer that would put an end to the discussion once and for all. This is what Quantum Supremacy means in the article, or in the words of Scott Aaronson:

> But what quantum supremacy means to me, is demonstrating a quantum speedup for some task as confidently as possible.

Reply on news.ycombinator.com