ScottAaronson

Thanks!

Given your particular situation, it sounds to me like you should not only buy QCSD, but buy 200 copies of it to give all your friends and family. :-)

More seriously, the overlap between QCSD and WPSCACC is actually relatively small---e.g., WPSCACC just has one short section about quantum mechanics, whereas that's at least half of QCSD. QCSD is also written in a much chattier style (but at the same time, it has more space to exposit basic material). I can't guarantee that you'll like QCSD, but I hope that gives you a sense for the diff.

Relax, my friend. If you accept the Many-Worlds Interpretation at all, then you're constantly splitting into parallel copies, millions of times per second, with every little decoherence event that takes place in your brain. Whether or not you use a quantum random number generator is totally beside the point. :-)

(But if it makes you feel less terrified, you could also choose one of the interpretations according to which "only our branch is real." As far as anyone can tell today, there are no consequences for any experiment we'll ever be able to do.)

Yes, I'm (not surprisingly :-) ) a fan of increasing federal funding for academic research. Equally important, enough of the funding needs to be in unrestricted, competitively awarded grants for basic science, rather than tied up in huge projects that are someone's hobbyhorse. And dramatically cutting NSF graduate fellowships---something that the NSF will likely do if Trump gets his way with slashing the NSF budget---would obviously be a huge step in the wrong direction.

In quantum computing in the US, we have no right to complain right now about the level of federal funding, since almost everyone else has it worse! For us, the limiting factor has instead tended to be tenure-track faculty positions in CS and physics departments. All the funding and brilliant students in the world wouldn't matter if, outside of a few elite universities, the CS departments all said "this is really physics," the physics departments all said "this is really CS," and both treated it as a passing fad that might disappear in a couple years. Fortunately, though, the situation has steadily improved and I expect that to continue.

On the whole, I think the fact that Google, Microsoft, and other companies hire so many CS PhDs is good, not bad. That's a big part of what lets us admit lots of talented PhD students, and honestly tell them that their career prospects afterward are good. On the other hand, I think it's also true, as you say, that society could better capture the value of a lot of these people by trying to keep them in the open academic world.

Yup

Thanks!!!

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?

1. Quantum computing is the most powerful model of computation we have based on currently known physics---in the sense that anything more powerful would need to be based on new physics. From the standpoint of theoretical computer science, a biological computer is "just" a different way to implement classical computation, typically with very slow speed but very enormous parallelism. It might someday have practical advantages, but unless we're totally mistaken about biology, it's not going to solve any problems efficiently that are outside BPP (i.e., classical probabilistic polynomial time). For that you need a quantum computer.

2. Yes, if quantum computing is successful, I imagine that might be good for the careers of many of the people involved in quantum computing.

3. Regarding D-Wave, there's this weird tendency to get fixated on words and definitions (but is it "really" QC or "really" analog?) even after you've explained the reality of the situation. See https://news.ycombinator.com/item?id=17426023 for my current summary.

Again, I'm skeptical that analog computers will ever be able to solve any problems outside BPP---for that I think you need a QC. (I.e., if not for quantum mechanics, I would have believed in the Extended Church-Turing Thesis. :-) ) Whether analog computers will ever again compete with digital ones on the constant factors, leaving aside the asymptotics, for problems that people actually care about, is a harder and more complicated question to which I don't know the answer.

Aha, thanks for that extremely useful clarification! I was also confused from the abstract and intro about exactly what the inputs and outputs were. Yes, the clear impression was created that they learned the rules---in the sense that they could then generate moves that would (usually? almost always?) obey the rules---when it sounds like really they just learned an evaluation function that encodes lots of implicit knowledge about the rules, of course, but that still requires a piece of code that knows the rules explicitly as a "guardrail" when generating moves.

Since you obviously know this subject, what are the best current results in the direction of inducing the rules of chess from played games?

I'm not an expert on this, but I think the surface code is so popular because it's 2-dimensionally local and has great parameters and speed of error correction. But people certainly work on other codes too, and if someone invents something that's unequivocally better than the surface code---or better for what the experimentalists are building now---I guarantee you they'll take notice! They don't always care about finer points of complexity theory, but this they do care about.

Yup.

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.

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!

I'm constantly learning new things that to people from other fields would be freshman-level trivialities! The most recent such example would need to be something I learned today. For example, maybe a little tidbit that I picked up from Sanjeev Arora's STOC'2018 tutorial on deep learning (where I was this morning): it turns out, backpropagation is just a dynamic programming algorithm for calculating a gradient in time linear in the size of the network, improving over the quadratic time that one would've needed naively.

I feel bad that I rarely have the time (or willpower!) to do exercises anymore, though I'd probably benefit if I did.

+1

There's no clear relationship between P vs. NP and the Riemann hypothesis, except that the generalized Riemann hypothesis (GRH) would let you derandomize certain randomized algorithms, and also Mulmuley's Geometric Complexity Theory (a speculative approach to P vs. NP using algebraic geometry and representation theory) involves some of the same mathematical objects that were used to prove the analogues of RH over finite fields.

No, almost certainly not in the coming decade. See my answer here: https://news.ycombinator.com/item?id=17429547

See this recent survey article: https://arxiv.org/abs/1710.10377

Briefly, a fully fault-tolerant quantum computer could give a square-root speedup for Bitcoin's proof-of-work, and could completely break its elliptic-curve-based signature scheme. Both issues could in principle be fixed by migrating Bitcoin to quantumly harder problems, though in practice doing so could open up security holes of its own. This hasn't been done, but I think maybe there are other cryptocurrencies trying to use quantum-secure crypto from the outset? Googling just now, I found something called "Quantum Resistant Ledger" (https://theqrl.org/) -- does anyone here know more about what's out there?

Let me stress that none of this is a concern with the QCs of the near future, which will have at most a few hundred decent qubits and no error correction, and which will not be able to threaten Bitcoin or any other cryptography.

Qubits lose their quantum superposition states as they interact with their environment---effectively getting "measured" by their surroundings. This is called decoherence, and is the central engineering obstacle to building useful QCs.

The longer a qubit lasts while maintaining its quantum coherence, and (especially) the more operations you can do on it while keeping it coherent, the better that qubit's quality.

In practice, we will never be able to build qubits of perfect quality (i.e., ones that maintain their coherence forever except when we deliberately measure them). In the 1990s, some people thought this would be a fatal obstacle to scaling up QCs. But then two closely-related discoveries, called quantum error-correction and quantum fault-tolerance, dramatically changed the picture. These discoveries showed that, even if your physical qubits fall short of perfection, as long as they have a high enough quality, you can glom a bunch of them together into a single "logical qubit"---that is, a qubit that lives in the collective state of multiple physical qubits, and that can still be recovered even if any small number of those physical qubits lose their coherence. Furthermore, one can do an arbitrarily long quantum computation on these encoded (logical) qubits, continuously monitoring to see which of the physical qubits have suffered errors and correcting those errors (but not monitoring in a way that would collapse the logical qubits!). In this way, one can in principle build a reliable quantum computer out of unreliable parts---a generalization of John von Neumann's famous discovery from the 1950s, which showed that the same was true of classical computation.

"cue-bit." I.e., the name of the letter Q, followed by "bit."

Yes, you can define a universal quantum Turing machine, which is a single quantum Turing machine U able to simulate any other quantum Turing machine M (at least, to arbitrary precision) given a coded description of M on its tape. This is one of the main observations David Deutsch made in his famous paper from 1985.

Thanks; that made my day!!!

Yes, a fundamental property of quantum information undergoing unitary evolution (meaning, no measurements, no discarding stuff into the environment, etc.) is that it can be neither created nor destroyed. This fact enters into my work, or the work of anyone else in quantum information, sort of like how the number '2' enters into our work---i.e., so thoroughly that it would be hard to pick it out as a separate ingredient!

That's a tough one! So far, I've only seen ONE game meant to teach quantum mechanics that I thought actually worked, in terms of being (1) actually about QM rather than some vague analogy, and (2) fun to play. It's this one:

http://quantumgame.io/

Notably, this game doesn't even try to teach about entanglement (which, no surprise, is hard to keep track of in your head!). Tt deals only with a single photon passing through a network of beamsplitters and phaseshifters: a situation that has one foot in quantum physics and one foot in classical physics (the macroscopic state of a laser beam obeys exactly the same math). But the puzzles are really clever!

If you're just trying to create an educational game, why bother using the Quantum Experience? Won't it just introduce enormous errors and delays (~30 seconds per run when I tried it), complicating and obfuscating whatever you're trying to teach? Why not just make some puzzles that force people to reason about small, idealized quantum systems, along the lines of the successful example above?

It has multiple PR problems, including the one you mentioned. :-)

Everyone who follows QC knows that simulating quantum chemistry could be commercially important, while breaking RSA is not. And as far as I can tell, no one cares anymore about doing tiny demonstrations of Shor's algorithm, to factor 21 into 3x7 or whatever. Over the past 5 years, the experimental interest has shifted to (1) demonstrating sampling-based quantum supremacy (which has nothing to do with Shor's algorithm), (2) demonstrating the building blocks of quantum error correction, and (3) the prospect of doing useful simulations.

(A central reason for this is that, until you have a full fault-tolerant QC with millions of physical qubits, you almost certainly can't run Shor's algorithm in a way that will outperform a classical computer, even if you wanted to. By contrast, people are excited right now that they might be able to learn something new for physics or chemistry with just a few hundred good physical qubits.)

So anyway, we all know all of this, but popular expositions still like to concentrate on breaking public-key crypto because of its wow-factor (and, of course, the undisputed theoretical importance of Shor's algorithm, and its possible eventual security importance). In addition, there's often a time-lag problem, where the people working in the field have one set of concerns, and then the broader discussion is still stuck in the world of 1997.

Yes, when you look at the history of AI, a "quantum winter" is an obvious worry---i.e., a situation where the hype about QC becomes so unmoored from the reality as finally to cause the popular narrative to switch its polarity. Picture a pointy-haired boss who's now pouring money into QC, for no better reason than that it's new and faster and it's the future and people are talking about it and it could speed up his company's data mining by trying all possible answers in parallel. If something spooked that boss, one could imagine him joining a stampede for the exits with no greater understanding, canceling good research along with bad. If it happened to AI, then why not to us?

The fear of a quantum winter is one reason---if any reasons were needed besides the truth!---why I've spent so much effort on my blog over the past decade trying to counter irresponsible QC hype. Like, if anyone ever comes to me and says "you lied to me! it turns out that scalable QCs are really hard to build, and a lot more basic science needs to be done, and even if you did manage to build them, as far as anyone knows they'd only give you exponential speedups for a few special problems, not for most of the stuff my company cares about," I'll have a pretty enormous record that I can point to when I reply, "I WAS SCREAMING THAT AT THE TOP OF MY LUNGS AND YOU DIDN'T WANT TO HEAR IT!" For all the good it will do. :-)

Then again, maybe the worry is overblown. Some people claim that we've now passed the point where there will never again be an AI winter, any more than there will be an "electricity winter." The train just has too much momentum. Likewise, so long as the pressure continues to get more and more computing power and stave off the end of Moore's Law, it could be that QC will continue to entice people, regardless of the naysayers and regardless of how hard the engineering problems turn out to be.

I honestly don't know. I feel like I have a hard enough time understanding and communicating the truth about where this field stands in the present---and sometimes, trying to advance it by a small increment---without also prognosticating its future. :-) The latter involves all sorts of questions of economics, politics, and psychology that I have no special expertise about.

Here's a modern viewpoint: there are many different things we can mean in saying that one model of computation (e.g., quantum) has abilities that exceed another model's (e.g., the polynomial hierarchy). So, we could be talking about the number of computational steps, the first thing that complexity theory tried to understand and also (by a twist of fate) nearly the hardest. But we could also be talking about several other things, like communication complexity for a distributed problem, or query complexity: the number of accesses that need to be made to a very long input, which is more fancifully called an "oracle." For each of these settings, we could be talking about decision problems, promise problems, relation problems, or exact or approximate sampling problems.

Think of all these separation problems as terrifying monsters that we have to defeat. Some monsters, like P vs. NP with no oracle, are clearly the bosses of the entire game. But in the meantime, we just try to slay whatever monsters we can, because that's how we build up our stamina points and learn ins and outs of the game. And also, almost all these monsters live in dungeons that you can only reach by slaying easier monsters first.

For now, unrelativized separations, like P!=PSPACE, are monsters that we almost never have the tools to defeat. They're like 30 levels ahead of us in the game---or maybe 300 levels; one thing about this game is that it never tells you how many levels you still need to clear.

Oracle separations---and communication complexity separations for that matter---are easier monsters. But the point I want to make is that they're clearly, unequivocally part of the same game as the harder monsters that we're trying to get to.

This is particularly clear in the case of oracle separations from PH. When theoretical computer scientists proved in the 1980s that there's an oracle relative to which PH!=PSPACE, they did so only by proving the inability of small constant-depth circuits of AND, OR, and NOT gates, so-called AC0 circuits, to compute the n-bit PARITY function. This is universally considered one of the most important lower bounds on circuit size ever shown. (Circuit size lower bounds, of course, are the dungeon that P vs. NP is the boss of.)

The connection is this: a PH algorithm that queries an exponentially-long oracle string can be seen as just a massively scaled-up AC0 circuit reading its n-bit input (with no oracle). Conversely, an AC0 circuit is just a massively scaled-down version of relativized PH. There's a giant monster that you have to fight with giant swords, and a tiny monster that you have to fight with tiny swords, but the two battles are isomorphic. Win one and you win the other.

In the same way, proving an oracle separation between BQP and PH, is exactly the same challenge as giving an ordinary computational problem (with no oracle) that quantum computers can solve in polylogarithmic time, by querying the n-bit input in superposition, but that's not in AC0.

Of course, eventually we'd like to prove that interesting problems like 3SAT have no polynomial-size circuits of any kind, thereby establishing P!=NP. For now, though, a little beyond AC0 is the frontier: the most complicated place where we still know how to prove lower bounds on circuit size. And for problems that have the sort of structure that comes with being solvable in quantum logarithmic time (basically, being approximable by low-degree real polynomials), we didn't know until a month ago even how to put them outside AC0, let alone the classes slightly beyond AC0. So an important monster has been slaughtered in the frontier region, and we can now advance to a previously unexplored corridor, in the huge sprawling dungeon where somewhere P!=NP is lurking.

See this previous answer: https://news.ycombinator.com/item?id=17429093

Sure, inborn talent matters. Hard work matters. And what about the less-appreciated converses of those two qualities: namely, acquired talent and inborn propensity for hard work? :-)

We could also mention drive to seize opportunities, judgment in picking the right problems to work on, social skill to get potential collaborators excited about those problems, and of course luck. And probably 200 other things I forgot. They all matter.

Maybe the key is, instead of struggling against the profile of abilities that fate handed you, to find a subject or problem that's an optimal fit for that profile. Had Darwin been forced to spend his life as a mathematician, Godel as a biologist, or Einstein as an experimentalist, you would never have heard of any of them.

See this previous answer: https://news.ycombinator.com/item?id=17428675

I admire your determination to start a scientific career at age sixty! I once faced the "converse" problem---how to start doing research at age 14 or 15, before I'd found any mentor to help me---and it was one of the great revelations of my life that, at least in theoretical fields, the barriers standing in the way are more internal than external. So long as you have the time, and enough income to live off, you can start reading textbooks and arXiv papers. You can email the authors your questions. You can go to conferences, with or sometimes without registering (just don't tell anyone I said so ;-) ). You can sit in on classes at a nearby university (ask the professor; most are fine with it). You can talk to the professors. You can start working on a problem that interests you. If you get somewhere, you can write it up and submit it to a conference or journal. You can offer your services as a research assistant. The gates are open.

Of course there's a chicken-and-egg problem here, where the stronger your research record, the more busy researchers will want to talk to you, and the more they'll talk to you, the stronger you'll be able to make your record. Just like with dating or anything else, I guess, it does take persistence to break this cycle. :-)

And of course, you'll need to be considerate of people's time, and you'll need to decline to take it personally if some people are too busy to answer you. Just plow ahead and ask others.

Lastly, let me strongly suggest finding some other people who started their research careers later in life, and asking their advice. They'll surely be able to think of things I didn't!

1) Yes, a unitary transformation like the Hadamard gate maps the state |0> to |0>+|1>, while mapping |1> to |0>-|1>. In either case, if you then just measured immediately in the {|0>,|1>} basis without doing anything else, you'd see |0> or |1> with equal probabilities, so it would have the effect of a coin flip. But of course, in other cases---e.g., if you measured in a different basis, or if you applied the Hadamard to a state that wasn't just a |0> or |1> basis state---you could see that Hadamard is not just a coin-flipping transformation, because it's able to produce interference.

2) When we talk about the different "paths" that contribute to a given amplitude, it's just a fancy way of saying that we can organize the matrix multiplications in such a way that the amplitude we want is a giant sum. So for example, suppose we apply Hadamard twice in sequence to the initial state |0>. The first Hadamard maps |0> to (|0>+|1>)/sqrt(2). The second Hadamard maps |0> to (|0>+|1>)/sqrt(2) and |1> to (|0>-|1>)/sqrt(2). So by linearity, it maps (|0>+|1>)/sqrt(2) to

((|0>+|1>)/sqrt(2) + (|0>-|1>)/sqrt(2))/sqrt(2) = (1/2+1/2)|0> + (1/2-1/2)|1>.

So in this case, we could say that there are "two paths leading to |0>," both of which contribute 1/2 to its final amplitude (so that the amplitude is 1). There are also "two paths leading to |1>," but one contributes 1/2 to its amplitude and the other contributes -1/2, so the two contributions interfere destructively and the final amplitude of |1> is 0.

This is sometimes called the "Feynman" or "sum-over-paths" picture of quantum mechanics. As you can see, though, it's just a different way of looking at exactly the same math, namely multiplication of matrices and vectors.

So then why use the sum-over-paths picture at all? Well, a few reasons: physicists like it because it often gives them more insight into what's going on, into what are the more and less important contributions to a given process, and it can also make calculations easier. Meanwhile, computer scientists like the picture because it lets us simulate a quantum computer by a classical computer, still using exponential time but now using only a linear amount of memory, rather than the exponential amount of memory we'd need if we tried to store all 2^n amplitudes at once.

1. The P vs. NP survey is only 2 years old, so all the edits I'd make to it now would be rather minor ones: for example, including some more recent circuit lower bounds of Ryan Williams and others, some more no-go results for Geometric Complexity Theory, and Raz and Tal's BQP vs. PH breakthrough (which required a new circuit lower bound, though not of a kind that can evade the natural proofs barrier).

2. See here for my answer to someone who asked me for my thoughts on blockchain just a couple weeks ago: https://www.scottaaronson.com/blog/?p=3861#comment-1768247