HN Explorer

I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

649 points by ScottAaronson ↗ HN
Hey HN,

We recently recorded a podcast (https://blog.ycombinator.com/scott-aaronson-on-computational-complexity-theory-and-quantum-computers/) where I discussed my research, AI, and advice for nerds in general or people who want careers in science.

We covered many but not all of the questions submitted over the internet so AMA!

372 comments

[ 0.25 ms ] story [ 275 ms ] thread
bruth
Hi Scott. I did not listen to the podcast (yet), so sorry if you answered this already, but what, in your opinion, could be the greatest impact quantum computing has in society? I know its a broad question, but curious of a few bullet points.
ScottAaronson
Short answer: I think the greatest impacts might be in simulating quantum physics and chemistry themselves, and thereby giving a new window into nature that could have applications to drug design, materials science, batteries, high-temperature superconductors, and more. But I could be as badly wrong as (e.g.) someone speculating about the impacts of classical computers in the 1940s, who could see applications to weather prediction and other physical simulation problems but would've totally missed the creation of Hacker News.

Long answer: See my recent blog post https://www.scottaaronson.com/blog/?p=3848 about exactly this!

DC-3
Hi Scott,

Shtetl-Optimized's tagline is famously "Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once". What phrase do you think should replace 'trying all the possible solutions at once' in the public conciousness as a succinct description of the mechanisms of a quantum computer? Or is this topic simply too complex to be distilled into a neat synopsis while retaining accuracy?

tomahunt
Exactly the question I would love answered.

Edit: this seems roughly answered to a question by user r4um

mrfusion
I don’t see where it’s answered?
ScottAaronson
A quantum computer is a device that exploits constructive and destructive interference among exponentially many amplitudes, which are numbers that are closely related to probabilities but can be positive, negative, or even complex.

If you feel that sentence wasn't clear enough, and it would take at least a few more paragraphs to flesh it out ... well, duh, what did you expect? :-D

For a SLIGHTLY longer account, see my attempt to explain quantum computing in 35 seconds or fewer, which Maclean's magazine challenged me and others to do in response to Justin Trudeau's quantum computing explanation: https://www.scottaaronson.com/blog/?p=2694

When I did a piece for the New York Times, I managed to get an explanation that I was reasonably happy with into ~6 paragraphs: https://www.nytimes.com/2011/12/06/science/scott-aaronson-qu...

Given that quantum mechanics is, famously, one of the most counterintuitive things that humanity ever discovered, I don't think it's that big of an ask for people to read 6 paragraphs about QC before they decide they basically know what it's about. :-)

ahelwer
My favorite quote of yours is that quantum computers "have a profile of abilities so strange that no sci-fi writer would have had the imagination to invent it" - it's a great quote to inspire people to dig deeper into the (literally beyond classical imagination) concepts of quantum mechanics!
[deleted]
(comment deleted)
stcredzero
Here's my attempt at a two sentence over-over-over simplification that at least gets people away from the "magic bit-sting that contains your answer." (It also harkens back to an old Einstein quote, so may be attractive to science writers.)

Quantum computing is a technique that lets you sample a problem's answer-space using "loaded dice," such that the problem's correct answers correspond with probability spikes in your dice throws. Right now, we only know how to usefully "load" those dice for certain problems, and it's pretty hard to do.

[deleted]
(comment deleted)
bariswheel
Do you mean all the possible solutions to a problem when you say 'answer space' ?
tadhgds
That's how I would interpret it, yes
ejanus
"Loaded dice ", I have not heard that before... Is it same as Biased dice
lambda
In your 35 second blurb, and the New York Times article, it seems like the point you're making is that interference is the main way that quantum computers work. But what makes quantum interference special over other kinds? You can get interference in sound waves, light waves, radio waves, etc. You also mention that magnitudes can be complex, but the same is true of other kinds of waves; complex numbers are used for discussing impedance in electronics.

These are even relatively simple to work with; back in high school, I set up my basement as a darkroom, set up a sandbox for isolation, borrowed a laser from my physics teacher, bought a kit online with a beam splitter, mirrors, lenses, and film, and made some holograms of various objects utilizing light interference.

You could set up an apparatus in which light goes through a beam splitter, reflects off mirrors to travel via different paths, and is recombined and interferes in the end to produce an interference pattern. You could probably encode a lot of information in the exact length of the different paths, perhaps in an array of mirrors which could be actuated to produce slightly different path lengths in different parts of the beam (after the beam is expanded), and use the interference to make calculations.

Other than the smaller scale, and greater difficulty of working with it, what is special about quantum interference that would make it more amenable to solving problems that are NP complete than some apparatus producing similar kinds of interference with light?

Also, has it been proven (or argued sufficiently convincingly) that quantum computation at scale is actually possible? I'm wondering if there could be an issue where it requires more computation to construct a quantum computer than the computation you get out, or require a non-constant number of quantum computers (with respect to the size of the problem) to actually get reliable enough results out, or something of the sort.

I think this is somewhat like the questions of whether certain automata are Turing-complete (https://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_T...), when a sufficiently complex process is needed to encode the problem into the automata that it could be argued that the computation was not actually carried out by the automata itself (I don't actually know if that question was answered; Wikipedia references a mailing list thread that has a lot of discussion, but I haven't seen any authoritative conclusion).

Given that empirically, only extremely simple quantum computers have been able to be constructed, what makes us think that there isn't some kind of tricky scaling issue like this were the additional complexity of building, running, or verifying the results of quantum computers will negate the benefits?

[deleted]
(comment deleted)
ScottAaronson
The difference between QC and all those other examples of interference is that, in the case of QC, the interference happens in configuration space rather than ordinary 3-dimensional space. And configuration space is enormous; it has a dimension that grows exponentially with the number of particles. The number of paths that could interfere with each other to produce a given amplitude is likewise exponential (in that case, in the number of computational steps).

No, of course no one has proven that it can work: presumably, the only proof that will convince everyone will be the actual construction of the machines! But in the 1990s, the theory of quantum error-correction convinced almost everyone that, as far as current physics can say, the difficulties (though staggering) seem to be ""merely"" difficulties of engineering. As I discussed in another answer, a deep reason why QC could never be scaled would be MUCH more interesting scientifically than a mere success in scaling it (which would "merely" confirm what physicists already believe). And of course, with the ongoing efforts of Google and others to demonstrate "quantum supremacy" with 50-70 qubits, we're likely to get experimental results that are relevant to your questions within the next few years.

zackmorris
Out of all your replies, I THINK that this is the one that helped me grok why QC is different than somehow simulating quantum math in a classical computer. The idea of being able to tap into more than 3 dimensions sounds like something very fundamental, kind of like relativity, and a key aspect of how our universe works that at least I was never aware of (and probably a lot of other people!)

Would you consider writing an in-depth article on configuration space and how it applies to QC (and possibly other research) and sharing it here on HN someday?

ScottAaronson
Pretty much any intro to QC (and in particular, any of the intros I've written, and linked to elsewhere on this thread) will make the point about Hilbert space (that's what it's called) having a dimension that grows exponentially with the number of particles in your system. This is because every possible classical configuration of the system is its own orthogonal "direction" in Hilbert space, and the full state can be an arbitrary superposition (i.e., complex linear combination) of those directions.
[dead] dschuetz
QM was invented, not as you say "discovered". It was the only means to explain things that were inexplicable with the means of classical physics, or even rational thought. And still, there are a so many physicists who claim and toot that they've got it all about QM and act like it's a no-brainer to study 5 years worth physics curriculum first to properly get it.

Most people mistake QM for a natural mechanism, rather than means to explain things. Same people invent Quantum Computing and Entanglement Communication. Well, good luck, I guess?

And you sir, please get over yourself.

dang
If you post like this again we will ban you.
akavel
Ok, I'll try another attempt at explaining the stuff :P Not sure if correct, because I'm not a parent :P neither a quantum scientist actually, just dabbled a tiny bit in QC at one point :) So you can choose whether to believe my words or not :)

Imagine you are a parent/teacher in a room full of happy kids, playing their kid games. Some kindergarten playground or something. They're generally all doing some kind of stuff, and doing it in parallel. Is this "doing work in parallel"? Every one of them is doing something totally else, one kid is building a castle, the other is throwing bricks at it and destroying it ("interference cancelling each other's work"). One is digging holes in a sandbox, another just kicked the sand inside, filling the holes back.

Now, you are just one, insignificant adult in this room. Imagine you would want them to do something for you. Can you just shout at them, "do me some parallel computation"? "Build me a castle of bricks"? Meh, sure you can, but they'll look at you funny, maybe a few of them will start, but their attention will be soon diverted by others, and anyway they'll soon get bored and start fudging around.

But here comes the fun part - if you're a smart and creative teacher/parent/..., you can actually do much better: you can "trick" them into doing your work; you have to either find some kind of a "system", or a "fun game", that they will like, that will fit their abilities and sensibilities, so that they'll choose to generally more or less contribute in the direction you want them to. You have to find a way of doing the task that will be "compatible" with them. Then, collectively, you can actually have them make your work done! But if you don't find the trick - sorry, no free lunch for you :) But you can still keep enjoing watching in awe and wonder how they're having fun, the little buggers... erm, sweethearts :P

In a somewhat similar way, in QC, you have to invent a system that can trick all the qubits, who have their particular, peculiar ways of living and behaving, to contribute to some particular result that will be meaningful and useful to you. Otherwise, they'll totally do some kind of "parallel work", but the result will be just irrelevant mess. To make the challenge even more tricky, you're actually outside the room when the work is happening. You don't see the "calculation" ([wavefunction] vector) each kid... umm, qubit is contributing, you only see the one final result. Nah; that would be too easy still; you can only see the shape of the result's shadow (just the length of the final vector).

(edit: ah, and I forgot the most important thing: if I'm not wrong, each extra kid is are actually contributing exponentially more work; if you have N qubits, you are trying to trick 2^N vectors to work for you)

Sorry for still being very vague and handwavy :)

Hmm, one more vague analogue could be to "computer proof systems/theorem provers", e.g. Idris, or trying to prove/enforce something with GADTs. You have this set of rules/mechanisms; now, you have to sit and squeeze and tear your brain in different ways to invent how to force those limited rules to encode the thing you want to prove. Not easy. But sure a challenging and potentially fun brainteaser :)

omarchowdhury
As someone still trying to understand the essence of quantum computing, your analogy to me can be summed up as coherence only comes from coherence. Which to me is too general, and describes computing as a whole. How coherence is determined in the particular case of quantum computing as opposed to classical computing is the meat and potatoes that I'm looking for.
akavel
Sorry, don't think I can do more at this point; I once managed to understand the Shor's algorithm from some book; but I didn't reinforce it, and now I'm left only with a vague recollection of the main a-ha moment... Though I actually don't really get what do you mean by coherence here (esp. in the area of classical computing).
omarchowdhury
My coherence I mean something intelligible that can be acted on (ie. computer code and its results).
randomsearch
“Quantum Computing is the exploitation of quantum state evolution to perform computation.”
4n0nym00s3s
A quantum computer is a high-tech ouija board.
SRasch
You were said to be a skeptic of quantum computing company d wave. Then you started believing and then went back to skepticism. What is your current status, do you think it works? What would you like to see from them?

Also, what is your take on Max Tegmark's quantum suicide experiment. Would it work? If yes would that imply that each of us should expect to live a really long time subjectively?

ScottAaronson
My position on the technical fundamentals never changed much: namely, D-Wave is building devices that could be interesting from various engineering perspectives, but that as far as most of us can tell, are not getting speedups over existing computers that are clearly attributable to quantum computation (as opposed to building special-purpose hardware that's, essentially, very fast at simulating itself). If you want quantum computing speedups, I think you're going to need qubits of much higher quality, and ultimately error correction or at least error mitigation. In principle, D-Wave could do that, and I applaud any steps they take in that direction. However, I'm personally much more excited right now about the experimental efforts in superconducting quantum computing that are happening at Google, IBM, Intel, and Rigetti -- all of which use qubits with orders-of-magnitude better coherence times than D-Wave's qubits. In some sense, D-Wave optimized for being able to say that they had 2000 qubits as quickly as possible, rather than for the qubits actually doing what we want.

On a more sociological level, D-Wave earned a lot of bad blood with the academic QC community by making false, inflated, and overhyped claims (with a primary offender being its founder, Geordie Rose, who's since left the company). And I certainly took them to task for those sorts of things on my blog. Then the D-Wave folks met with me, John Preskill, and other academics, and pledged to improve in how they communicated, so I was nicer to them for a while. Then they went back to egregious hype about speedups that weren't real, so I criticized them again. Nothing more to it than that. :-)

Regarding quantum suicide: no, I do NOT recommend killing yourself any time anything happens in your life that makes you unhappy, on the theory that other versions of you will survive, in other branches of the quantum-mechanical wavefunction where the bad event didn't happen. This is partly because, even assuming you accept the Many-Worlds Interpretation, "your" moral concern and responsibility presumably extend only to those branches that are in "your" future -- you have no contact with the other branches! And partly it's because I take it as almost an axiom of rationality that, if a metaphysical belief leads you to do "obviously insane" things with your life, then it's probably time to look for a better metaphysical belief. :-) (I wouldn't say the same about scientific or mathematical beliefs.)

martin1975
Am I hearing this right, you think the whole multiverse concept is... meta-physics at best?
JakeTyo
You simply can't something 'physics' if its not testable. :)
martin1975
That word 'testable', is very loaded. :) But I get what you mean. Are there things that we can't test that do exist?
[deleted]
(comment deleted)
joshuamorton
Scientifically speaking, no. A scientific hypothesis must be falsifiable, and to be falsifiable it must be testable. I guess in some sense you could claim that there are hypothesis that are testable, but which we do not have the capacity to test. But then, is the claim that "one day in the future, we will be able to test this other claim" itself falsifiable? I'd argue not (it's a recognizable, not decidable claim, in the computational sense, and I think that for a claim to be falsifiable, it must be decidable).
kybernetikos
> A scientific hypothesis must be falsifiable

This is certainly one understanding about what science should be (although not a scientific one interestingly enough). Personally I prefer Thomas Kuhn's demarcation, which by my understanding concentrates more on whether a scientific program is producing interesting predictions which turn out to be true.

joshuamorton
I'm not speaking about science as a whole or a scientific program, but a scientific claim. CERN is certainly not falsifiable, but it produces predictions which (often) turn out to be true. It does so by devising falsifiable claims and then testing those claims.

In other words, the method to create interesting predictions which turn out to be true is to create interesting predictions, then test those predictions, and update your understanding of the world based on them. Once your world-model is good enough, your predictions will often be true. And, perhaps, eventually your predictions will be so often true that they become uninteresting, so you must move on to other questions.

kybernetikos
Fair enough, I think Kuhn was referring to things like the world-models and you're referring to finding out if the predictions of the model matches reality.

The heliocentric model of the solar system made less accurate predictions than the geocentric model for years, because the geocentric model was mature and had had lots of tweaks applied to it. In that time, you could have asked the heliocentric model to make a prediction, and shown that it was wrong compared to the geocentric model. You would have been wrong to conclude that heliocentrism was wrong though, it just hadn't matured as a theory enough yet.

All models are wrong, but some are useful.

kybernetikos
> Are there things that we can't test that do exist?

Lots of people think so (e.g. unmeasurable things predicted by theory like parallel universes, but also things like evil or God or the color purple), but by definition it's hard to be very sure, or to transfer your own confidence in such things to others.

Lots of these kinds of questions reduce to quibbling about definitons; and also by definition, if we can't test the thing then the universe isn't going to punish us either way for believing or not.

mygo
> if we can't test the thing then the universe isn't going to punish us either way for believing or not.

If we can’t test the thing then what we are discussing is faith, not science.

Nothing wrong with faith and beliefs but I think it’s important to differentiate between these things and science because often times science is used as a basis for untestable beliefs and then people really start to think that those untestable beliefs are actually backed by scientific research.

sethrin
Do you have any empirical evidence for any particular QM interpretation? If not, does that make them unscientific?
mygo
I think the various interpretations of QM, until one is proven (or we otherwise come to one definition)... they all lie within philosophy.
AgentME
>Are there things that we can't test that do exist?

There's many reasons to believe that objects that exit our light cone continue to exist after they do, even though they could never have any future interaction with us to confirm that. (Say a spaceship leaves Earth at near the speed of light in a straight line, and then enough time passes that the space between the ship and Earth is expanding so fast that the spaceship or any kind of signal from the spaceship would have to travel faster than light to return to Earth, which is impossible. Believing that the spaceship disappears when it exits our light cone requires believing in unnecessarily more complicated physics.)

[deleted]
(comment deleted)
ianai
I think there’s a grave misunderstanding about the multi-universe interpretation. The scales at which the uncertainty principle come into play are vastly small. I think they’re small enough that they don’t summate to larger scale variances. The larger level probably asymptotes to the one reality.
mygo
Despite the scientific method giving rise to the fact-based ever-improving test-able body of work we call Science.. that doesn’t stop people from creating their own religions and beliefs based on it.
AgentME
I think he was saying about whether you should morally care about the other branches counted as meta-physics.
defen
Another problem with the quantum suicide thought experiment is that there are plenty of branches where you end up alive but horribly disabled.
red75prime
Yet another problem with that is no matter how small the measure of those branches is, you'll end up in them anyway.

The death of natural causes qualifies too.

tjhance7
> This is partly because, even assuming you accept the Many-Worlds Interpretation, "your" moral concern and responsibility presumably extend only to those branches that are in "your" future -- you have no contact with the other branches!

Would you say that the only moral way to implement quantum suicide is with a Doomsday Device that would destroy the entire world, thus ensuring your actions won't affect anybody else even in the worlds where you die?

[deleted]
(comment deleted)
r4um
How far are we from "emergence" in terms of AI ecosystem ? Will quantum computing pave the way for it ?
ScottAaronson
Sorry, I don't know what "emergence" means in this context. If you mean AGI, I think (hope?) that we're still quite some ways away from it. Yes, quantum computing could help with AI -- for example through Grover's algorithm, which lets you solve many search, optimization, and planning problems in roughly the square root of the number of steps you would need classically. But it's a complicated story: many of the problems we care about will still be asymptotically hard even for quantum computers; conversely, as the spectacular recent achievements of deep learning and reinforcement learning (not to mention our own brains? :-) ) remind us, there's a great deal that can be done even with classical computers---often, outside the regime where we understand theoretically why the methods work. If you check back in 5 years or so, I'm optimistic that we'll know more about the applications of quantum computing to AI than we do right now.
BenoitEssiambre
"not to mention our own brains"

Is this a known known that our brain doesn't use QC?

glifchits
In my opinion, you're one of the most entertaining and approachable writers on mathematical topics like QC. How did you get good at writing?
ScottAaronson
It’s funny: when Philip Roth passed away recently, I was rereading some of his stuff, and thinking to myself, “why am I so terrible at writing?”

If I have any tips, I guess they’d be bend-over-backwards honesty, willingness to make an ass of yourself, practice, and more practice.

jderick
Do you think that quantum physics can tell us anything about 'the hard problem' in philosophy? Is it possible that the mind could somehow control how quantum states collapse in situations where randomness would be the typical explanation?
bascule
There have been some poorly received hypotheses to this effect, most notably Roger Penrose's Orch-OR: https://en.wikipedia.org/wiki/Orchestrated_objective_reducti...

That said, most attempts at quantifying whether or not distinctly quantum mechanical processes in the brain related to things like microtubules and NMDA receptors are significant to cognition (i.e. is the brain a quantum computer?) have generally concluded the answer is no:

See:

https://arxiv.org/abs/quant-ph/9907009

https://onlinelibrary.wiley.com/doi/pdf/10.1207/s15516709cog...

ahussain
It doesn't answer this question directly, but Aaronson's paper "The Ghost in the Quantum Turing Machine"[1] is a great read. It talks about the relationship between quantum mechanics and free will.

[1] https://www.scottaaronson.com/papers/giqtm3.pdf

ttctciyf
It is a great read! Also, in the comments on his blog post introducing that paper, he says:

> Well, yes, “the fact of experience” is a toughie! :) In fact, I regard the “hard problem of consciousness” as so far beyond us, that it’s not even clear that science or rational argument give us any sort of toehold.

- https://www.scottaaronson.com/blog/?p=1438#comment-80656

[deleted]
(comment deleted)
ScottAaronson
Short answer: not in any obvious way!

Longer answer: whatever I have to say about possible implications of QC for the hard problem of consciousness, you can probably find in the following lecture

https://www.scottaaronson.com/blog/?p=1951

or in the Ghost in the Quantum Turing Machine essay that’s linked below.

TrinaryWorksToo
I'm halfway through the first chapter of Neilsen and Chuang's book. I'm enjoying reading about the subject and am at the quantum parallelism part.

Can you explain why Grover's algorithm has a runtime of root N? It seems like the runtime should be log2(n) because of exponential qubits or 1 because there must be a way for all the qubits to interfere.

Also, What resources do you reccomend for self study? Are there quantum computing meetups in San Francisco that you can recommend?

ScottAaronson
The reason why the running time of Grover’s algorithm involves sqrt(n) has to do with the Pythagorean theorem—or if you like, the fact that quantum mechanics is based on the 2-norm, in contrast to classical probability theory which is based on the 1-norm. Classically, each time you pick one item out of N to query, you can add ~1/N probability to the marked item—so the probability of having found the marked item after T queries goes like T/N. Quantumly, you can add ~1/sqrt(N) amplitude to the marked item with each query, so the amplitude on the marked item after T queries goes like ~T/sqrt(N), and hence the probability of observing the marked item when you measure goes like ~T^2/N.

A fundamental result from the 1990s, called the BBBV Theorem, shows that not even a quantum computer can solve the unordered search problem any faster than Grover’s algorithm solves it. I won’t prove the theorem in this comment :-), but the intuition is simply that quantum mechanics is a norm-preserving and linear theory. So you actually need to do something to gradually put more and more amplitude onto the marked item; you can’t just instantly and magically give an amplitude of 1 to whichever branch of your superposition happened to hit the marked item.

I’m not sure if there are QC meetups in SF (does anyone else?). But certainly nearby Berkeley is one of the centers of the world for QC—home to Umesh Vazirani’s group, the Simons Institute for Theory of Computing, and now also the startup Rigetti.

TrinaryWorksToo
That makes some sense with the extra dimension providing more space to store information about all the information. I appreciate the detailed response with some jumping off points. Thank you!
thetoejam
What do you think would be the best route into Quantum Computing? Through physics, maths or computer science?
ScottAaronson
That depends on you and your interests! From the very beginning and up through the present, the majority of people in quantum computing have goten there via physics. But my own background is in theoretical computer science---I've only gradually picked up little bits of physics through osmosis (what's a boson, what's a Hamiltonian, etc. :-) ) and there are still embarrassing gaps in my knowledge. And computer scientists and mathematicians, such as Peter Shor, Gilles Brassard, Umesh Vazirani, and Dorit Aharonov, have clearly made crucial contributions to the field, and we plan to continue doing so!

By now, there are large interdisciplinary programs in quantum information science (at Waterloo, Caltech, MIT, Maryland, Berkeley, CWI Amsterdam, Singapore, Oxford, and elsewhere), as well as smaller programs like the one we've been building at UT Austin -- where in some sense, the work of blending math, CS, and physics into the smoothie of quantum information science has already been done. So one obvious option for a student interested in this field would be to seek out one of those programs -- they typically have courses and research opportunities even at the undergraduate level.

blr246
As a programmer and practitioner, I'm curious about what kinds of skills and training it takes to program quantum computers.

Can you shed some insight into what's really different about the tools and task of programming a quantum computer versus using classical programming languages and tools? Do you think quantum computer programming will rapidly become standard training for CS undergrads, or do you expect it to remain a niche skillset like FPGAs, etc, since it will only supplement and not replace classical computers.

Also, nice to meet you. Your essays have been inspiring over the years.

ScottAaronson
Thanks!!

I imagine that programming QCs will be a lot like programming classical computers, except with an additional body of technical knowledge that one needs to master. In that respect, it will be a lot like 3D graphics programming, or crypto programming, or AI programming, or compiler programming. And much like with those other types of specialized programming, even in a world filled with useful QCs, I imagine that only a minority of programmers would really need to understand how to interface with them.

Everyone: OK, I'm going to sleep now, since I need to catch a flight tomorrow morning. I'll try to answer a few more questions on the plane, but then I'll probably call it a day (or rather, two days :-) ). No additional questions please. Thanks for all the interesting questions!

liamcardenas
Thoughts on this comment?

"You don't actually want qubits, you want an analog computer with differentiable signals. Most likely photonic. Qubits are a dead evolution branch.

I've been recently exploring computational metamaterials for photonic computation.

http://users.ece.utexas.edu/~aalu/research%20-%20page%203.ht.... (there's quite a few papers on this but unfortunately they are all paywalled. Spoiler alert, they seem to be based entirely on Fourier transform).

These computational metamaterials don't need electricity to be powered (you need something that will shoot the photons on them and read back the values off tho).

Machine learning would be much, much faster on these as you have O(1) differential calculus.

They don't heat up. You can possibly build a house sized CPU out of these. I can see it, a city block sized CPU and a nuclear reactor next to it.

Did you know that on an analog machine, you can do sort in O(n)?

https://en.wikipedia.org/wiki/Spaghetti_sort

Hit me up if you wanna chat about this. I've seen the "light" (xdddd) now and can't go back to stupid bits.

I'm not like super married to the metamaterials but analog photonic trumps quantum for just about every task I can think of."

- adamnemecek

Source: https://news.ycombinator.com/item?id=14674333

rspeer
I'm not Scott, but spaghetti sort isn't any kind of computational breakthrough, it's just trading off measurement error for computation time.

Here's the digital version of spaghetti sort:

1. Enumerate the possible lengths of spaghetti that your spaghetti sorter can distinguish above a certain probability. This enumeration will be small and finite.

2. Round your values to one of these lengths.

3. Radix sort or bucket sort those values in O(n).

nqureshi
What advice would you give for productivity/getting things done?
ScottAaronson
I'm like the worst person on earth to be giving anyone else advice about that!! Do you have any idea how much time I waste obsessively reading the news, or worrying about people saying mean things about me on social media, rather than doing research or anything else useful for the world? I suppose my advice would be: don't do what I do. As my former PhD adviser, Umesh Vazirani, likes to tell people, "concentrate on the high-order bits."
dreeves
I hear that. But followup question! What do you think of commitment devices (like Beeminder!) for imposing discipline on oneself?
davesque
It's actually really encouraging to hear that Scott has many of the same vices as me.
VladimirGolovin
> how much time I waste obsessively reading the news

This is oddly comforting. As Tim Ferris said in Tools of Titans, every successful person is dysfunctional in some way. I guess the trick is to work around your own personal deficiensies, and that's something everyone must figure out on their own.

montrose
Do you think the state of the art in quantum computing is already more advanced than we realize, in the same way that the state of the art in cryptography was when R, S, and A thought they had discovered RSA?
ScottAaronson
If I knew the answer, I couldn't tell you. :-)

More seriously: people have mooted this possibility for as long as I've been in this field (~20 years). But keep in mind that, when Cocks and Williamson at GCHQ discovered what would later become known as RSA and Diffie-Hellman key exchange---so, 3-4 years ahead of the open world---cryptography essentially didn't yet exist as an academic subject. Almost all the action was still closely tied to the intelligence community. So, no surprise that a not-yet-existing discipline had fallen behind!

By contrast, quantum computing has been openly studied for decades and has thousands of people working on it all over the world. The central thing that causes me to be skeptical of the "million-qubit quantum computer sitting in the NSA's basement" hypothesis, is that we pretty much know who the best people are, and we haven't noticed any effort to vacuum them all up analogous to the Manhattan Project.

Like, it's no secret that the NSA and DoD, and other military and intelligence agencies around the world, are interested in this field and fund a good deal of work on it. In fact my main grant right now (the Vannevar Bush Faculty Fellowship) comes from the Office of Naval Research. But if the secret world is light-years ahead of the open world, then they'd also need to be executing a giant cover operation of pretending to care about what we in academia are doing! :) So at what point does it become an unfalsifiable conspiracy theory?

[deleted]
(comment deleted)
n0mi1k
If advanced quantum computing were available in smartphones and other small devices today, what applications would be possible that are not currently? (Or which would be greatly improved)

Would it affect the things many people do most on their phones like messaging, news and social media

ScottAaronson
As far as I know, it would have zero effect on any of that ... unless you need to simulate quantum physics or chemistry, factor large integers, calculate discrete logarithms, or possibly solve some large optimization problems while doing your messaging, news, and social media. :-)
godzillabrennus
Do you have any thoughts on the IEEE Quantum Computing Nomenclature Working Group?

http://standards.ieee.org/develop/wg/QCN-WG.html

ScottAaronson
No, I hadn't heard of it before your comment! Please no one tell the physicist David Mermin about this, or he'll picket the group with his long-running campaign to change the spelling of qubit to "Qbit." :-)
Y_Y
Is it pronounced kew-bit or kuh-bit or kwu-bit?
Koshkin
Depends on how you pronounce 'Q', I guess...
ScottAaronson
"cue-bit." I.e., the name of the letter Q, followed by "bit."
danharaj
A lot of machines that purport to solve an NP-hard problem in a short period of time have some trick that makes them impractical, like requiring the ability to reduce the noise floor in a signal exponentially or pump an exponential amount of energy into a system. Has it been shown that such physical resources are more-or-less interchangeable with running time for the purposes of complexity theory?
ScottAaronson
No, I think this is more a question for physics than for complexity theory -- complexity theory basically just takes the computational model and the resources you care about as inputs, then uses math to study how much of the resources are inherently required to solve a given problem.

Absent an ultimate theory of fundamental physics, we're unlikely to have a full answer to your question -- e.g., to be able definitively to rule out the possibility of "hypercomputers" solving NP-hard problems in polynomial time. What we can do is

(1) to explain the failure (often, the forehead-bangingly obvious, don't-point-to-the-exponential-elephant-in-the-room failure) of all EXISTING proposals along these lines, and

(2) to point to deep discoveries in fundamental physics -- most notably, the Bekenstein bound https://en.wikipedia.org/wiki/Bekenstein_bound -- which seem to constrain any future quantum theory of gravity to have a form that would rule out these sorts of hypercomputers (for example, by limiting the amount of energy that can be pumped into a finite region, without causing the region to collapse to a black hole, and by likewise ruling out computer components that are smaller than 1 Planck length across or that do more than 1 step per Planck time).

I've often speculated that ultimately, the hardness of NP-complete problems in the physical world might come to be seen as analogous to the impossibility of faster-than-light signalling or perpetual motion machines---i.e., something that we simply take as primitive and then use to explain other phenomena in physics. But while the hardness of NP-complete problems sometimes gets used in that way already, I also think we have a lot more work to do before the situations are truly parallel. (For starters, we could prove P!=NP. :-) )

api
Do you believe there is now a quantum Moore's Law in place? I've seen graphs showing quantum chips from Google, IBM, and Intel plotted on a log scale that are suggestive. (These exclude adiabatic quantum computers which are different beasts.)

If there is do you think we're perhaps less than 10 years from QC capable of breaking common number theory based asymmetric cryptographic algorithms like RSA or elliptic curve for at least lower key strengths? That's what these graphs suggest.

(I know breaking crypto is not by any stretch the only or the most valuable thing you can do with QC but it's the one that gets the most press and it's relevant to my current work.)

Strilanc
Even if the number of qubits doubled every year from here on out, it would be 15+ years until we had enough working space to run Shor's algorithm on modern cryptographic key sizes.

Back of the envelope:

- It takes 9n error-corrected qubits to break an n-bit ECDH key [1]

- Each error-corrected qubit requires ~2500 physical qubits [2][3]

- Typical ECDH key size is 256 bits [4]

- This year would be the year of ~64 physical qubit machines. [5][6][7]

- log_2(256 * 9 * 2500 / 64) ~= 16.4 years

Note that every one of the quantities in the estimate is subject to future research. E.g. the error corrected qubit size is smaller when using lattice surgery, but not enough to really move the needle on the time estimate.

[1]: https://arxiv.org/abs/1706.06752

[2]: See section VI of https://arxiv.org/abs/1805.03662

[3]: https://docs.google.com/presentation/d/e/2PACX-1vReeRxH80Ruu...

[4]: https://crypto.stackexchange.com/a/47337/7860

[5]: https://ai.googleblog.com/2018/03/a-preview-of-bristlecone-g...

[6]: https://www-03.ibm.com/press/us/en/pressrelease/53374.wss

[7]: https://newsroom.intel.com/press-kits/quantum-computing/#49-...

ScottAaronson
I think it's too early in the field, and there's too much basic research still to be done, to talk usefully about a "Moore's Law." For godsakes, we're not even sure yet whether superconducting qubits or trapped ions or something else (or a hybrid) will be the way forward!

Yes, you can make plots of the number of qubits, coherence times, etc. as a function of year -- and if you listen to talks by John Martinis, Chris Monroe, or the other leading experimentalists, you'll often see such plots. But at the very least, you need to look at both dimensions (qubits and coherence time) -- not just at "number of qubits," which will be severely misleading! And even if you do, there are very few data points to use for extrapolation, since it's really only within the last ~6-7 years that people have even gotten qubits to work well in isolation, let alone scaling them up. So it's really hard to extrapolate.

Like, I'm hopeful that within the next decade, we'll have systems with a few hundred qubits that will be good enough to do some useful tasks that are classically intractable (such as quantum simulation), though they certainly won't be threatening public-key crypto yet. But I'm not sure even about that. And I'd prefer to see what happens with this before speculating about the timescale for the next step, of building a full universal QC (the kind that would break our existing public-key cryptosystems)!

pc
This is slightly off-topic (I'm going to be that "this is sorta more a comment than a question..." guy for a second), but I just want to say that Scott's blog is one of my favorite blogs on the whole internet. If only there were more like it!
ScottAaronson
Thanks!!!
lisper
I know that me-too type posts are frowned upon here on HN, but in this case I think an exception is warranted. Too many scientists ensconce themselves in the ivory tower and treat the rest of the world with attitudes ranging from indifference to outright disdain. I also want to thank you for not following that model.

On a totally unrelated note, I've been trying to wrap my brain around coherent states and the photon-number/phase uncertainty relationship (e.g. http://hitoshi.berkeley.edu/221a/coherentstate.pdf). Do you know of any simple intuitive stories one can tell about that like one can with position-momentum uncertainty? I know this isn't really in your wheelhouse, but people who both understand this stuff and are willing to field questions like this are exceedingly rare (see above paragraph).

(FWIW, and for the benefit of lurkers, this question was prompted by the discussion on this blog post: http://blog.rongarret.info/2018/05/a-quantum-mechanics-puzzl.... Also FWIW, that's my blog.)

enriquto
You wrote this:

> For example, breaking almost any cryptographic code can be phrased as an NP problem. So if P=NP—and if, moreover, the algorithm that proved it was “practical” (meaning, not n^1000 time or anything silly like that)—then all cryptographic codes that depend on the adversary having limited computing power would be broken.

Can you explain this reasoning more precisely? The class P contains difficult problems that require O(n^googolplex) algorithms, so are not solvable in practice. The fact that P=NP would not make these problems any easier.

Recursing
He explicitly says «not n^1000 time or anything silly like that» in the sentence you quote, n^googolplex would be way more silly
enriquto
my point exactly. The class P contains this silly stuff.
svat
He's already covered that; not sure what's left to explain: he's said that if P=NP and if we get there with a practical running time algorithm (e.g. one that solves 3SAT in O(n^4) or something, and with reasonable constants too), then such-and-such consequences. So what are you asking?
enriquto
The second part of the claim seems much, much stronger than the first part, but he makes it sound like it's a minor detail. I am confused as to why.
teraflop
The claim was that "all cryptographic codes that depend on the adversary having limited computing power would be broken."

Here's a (very slightly) more rigorous justification:

If P=NP, then any NP problem is in P with at most a polynomial slowdown. That is, if there's an algorithm taking T steps on a non-deterministic Turing machine, we can solve it on a deterministic Turing machine in f(T) steps, where f is a polynomial. Presumably, a "practical" algorithm would be one for which f has a low degree.

The kinds of algorithms we're concerned about in cryptography (and plenty of other fields) already have low time complexity. For example, generating or verifying an HMAC is O(n) in the length of the input. So if we had a way to solve NP problems with a low-degree polynomial slowdown, we could break HMACs in low-degree polynomial time.

It doesn't matter that there are O(n^1000) problems out there that would still be realistically unsolvable, because those problems don't have practical applications in the first place.

thecupisblue
Hi!

So, what do you do when you're not flipping qubits around?

Got any cool stories you wanna share?

ScottAaronson
When I'm not flipping qubits around, I eat, sleep, blog, answer emails, play with my two kids, get depressed reading the news about US politics, and then get even more depressed reading people saying mean things about me and my nerdy friends on Twitter and Reddit.
thecupisblue
Awwww man! That sucks, but screw those naysayers. They ain't the ones running point on quantum computing.

(I don't really have much to ask you since anything I could comprehend is easily googlable and I don't wanna waste ur time. Just wanna say keep up the good work and thanks!)

elizabeth8890
Are you collaborating with the National Labs at all, i.e., http://quantum.lanl.gov/q_computing.shtml
ScottAaronson
I had close colleagues at LANL, but many of them (Leonid Gurvits, Howard Barnum, Manny Knill) have since left. I'll probably visit Argonne and Sandia sometime in the next few years to give talks, and to learn about what they're doing in quantum computing. I don't think I've written papers yet with anyone from those labs, but, uhh ... "there are no strangers, just coauthors you haven't coauthored with yet!" :)
navidfarhadi
Hi Scott. Thank you for doing this AMA.

In your opinion what are some good universities across the world to look into if one wants to do graduate or post-graduate level research in quantum computing?

ScottAaronson
I already answered that in another comment, but briefly: Waterloo/Perimeter, Caltech, MIT, Berkeley, U. Maryland, Singapore, Oxford, Cambridge, Bristol, CWI Amsterdam, Hebrew University, Tsinghua, UTS Sydney, McGill/Montreal, LRI Paris, and don't count out UT Austin -- we're planning to expand a lot! And many, many other places have at least one or two people in the field.
vymague
How about Germany? It seems people doing optics here like to connect their research to quantum computing.
ScottAaronson
Yes, there's some great stuff going on at the Max Planck Institute for Quantum Optics outside Munich.

Also the groups in Innsbruck and Vienna in Austria.

ttctciyf
Hi Scott,

If it turned out to be true that advances in advertising technology like profiling and microtargeting (see, e.g. [1]) could effectively deliver the likelihood of electoral victory to their highest paying and most ruthless practicioners, would this be something to worry about? And if so, what action should we take in order to preserve democratic ideals?

1: https://medium.com/join-scout/the-rise-of-the-weaponized-ai-...

da-bacon
Does the recent result on BQP not being in PH relative to an oracle do anything to your priors about the power of quantum computers relative to classical computers? If you had to distill why that oracle separation works, what would you say is the main trick from the perspective of "where does the power of quantum computers come from"?
ScottAaronson
Honestly, almost all of the technical innovation in this breakthrough had to do with classical circuit complexity—-once you know my Forrelation problem, there’s almost no further input you need about quantum computation. (Well, a slight amount, since Raz and Tal had to modify Forrelation a bit to get their proof to go through.)

For an attempt at a popular summary of what the circuit lower bound innovations consisted of, see my blog post:

https://www.scottaaronson.com/blog/?p=3827

or, of course, their paper.

No, this doesn’t much change my priors about the power of quantum computation—for one thing, because we all (or at least I :-) ) were already pretty damn confident that Forrelation was not in PH. On the other hand, I was not expecting that the separation could be proved right now—certainly, not without first proving some weaker separations like BQP vs. AM.