ScottAaronson

Dude, if you'd just asked me a more specific question, you could surely have baited me into commenting on this or that culture war issue. Since you asked a general question, though, I'll simply answer with the generality that I wish we could all make more of an effort to show empathy for each other's problems, and (as I said on the podcast) carefully articulate where we agree and disagree with each other rather than just flinging 140-character excrement.

OK, I'll also give you a few links. Here's my Quora answer about what it felt like to be widely attacked on social media, for trying to host a conversation about gender and teenage nerdery that got past platitudes to the roots of people's feelings:

https://www.quora.com/What-was-it-like-for-you-to-be-widely-...

Second, here's my friend Sarah Constantin's blog post about the changing nature of social media, the one I mentioned in the podcast:

https://srconstantin.wordpress.com/2016/11/27/hiding-in-plai...

Third, here's a recent post called "On Culture War Bubbles," from the blog "Thing of Things":

https://thingofthings.wordpress.com/2018/06/27/on-culture-wa...

This is much easier said than done, but as Ozy writes in that post, may we all be granted the mental strength to ignore culture war bullshit, until and unless we decide with the rational parts of our brains that it's important or worth responding to.

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.

There are really two questions here.

The first one is, can the human brain be simulated by a Turing machine in its input-output behavior (to a suitable precision, given appropriate initial data, yada yada)? Note that, even though you specified "infinite tape/memory and time," from the outset I'm going to outlaw "simulations" that simply cache what the human would do in response to every possible stimulus in a gargantuan lookup table. For that kind of simulation trivially exists, and its existence tells us nothing interesting. I'll insist instead that the simulation be "reasonable"---so, at a minimum, that it simulate the brain without an exponential blowup in size.

I don't know for certain, but as a believer in the physical Church-Turing Thesis, my guess is going to be yes, this is possible. I.e., I guess that the laws of physics are fully computable---that there's nothing in them like what Roger Penrose wants---and I see no evidence that the brain can violate the laws of physics that govern everything else in the universe.

(Even here, though, there remains the extremely interesting question of whether, even in principle, one could scan a specific person's brain well enough to "bring additional copies of the person into being," without simply killing the person if one tried. My friends in the futurist and singularity movements expect that the answer is yes, but if one needed to scan all the way down to the molecular level, then the No-Cloning Theorem of quantum mechanics would certainly present an obstacle. For my thoughts and speculations about this question, see my "Ghost in the Quantum Turing Machine" essay, which was referenced elsewhere on this thread: https://www.scottaaronson.com/papers/giqtm3.pdf )

Anyway, the second question is whether, even if we agree that a human brain can be simulated by an appropriate Turing machine, there's some special sauce of consciousness that makes there be something that it's like to be us, but nothing that it's like to be a conventional Turing machine. I.e. there's Chalmers' "hard problem of consciousness."

Here I'm going to plead ignorance, with my extenuating circumstance being that we're up against arguably the ultimate mystery of existence. :-)

Yes, I feel like there's something that it's like to be me. (Though if I were a philosophical zombie, just a glorified Turing machine made of meat, I could've told you exactly the same thing, so you should take whatever I have to say about this with a grain of salt. :-) )

And yes, I take it as axiomatic that there's similarly something that it's like to be you---or for that matter, to be a chimpanzee or a dog (but an ant? a bacterium? unclear). No, I don't understand it. No, I don't know what properties of a computational process are either necessary or sufficient to cause there to be something that it's like to inhabit that process; I don't know how we should build an AI either to ensure that it's conscious or to ensure that it isn't. In practice, we'd probably have to extend a presumption of consciousness to anything that behaved sufficiently similarly to us---that, famously, was Turing's point in 1950. But even here there are many uncertainties: for example, would you still take a machine to have "passed the Turing Test" if you could perfectly predict everything it would say given a copy of its source code---not just in principle but in practice?

Sure, you could shake off the idea (if you haven't already...) that quantum entanglement means communication faster than light. This is, interestingly, exactly the same kind of error as the one that says that a quantum computer is just like a classical computer but with exponential parallelism. Namely, you look at the resources that would be needed to simulate a quantum system using a classical system (faster-than-light communication in the one case, exponential parallelism in the other). You then confuse those with the resources that the quantum system itself provides you.

In reality, quantum mechanics is carving out a third profile of abilities, which is neither as weak as the classical profile, nor as strong as the thing that people mistakenly overcorrect to once you tell them that the classical profile is inadequate. E.g., you can violate the Bell inequality but NOT send instantaneous signals; you can solve factoring in polynomial time but probably NOT NP-complete problems. As I like to say (someone already quoted it elsewhere), it's a sufficiently strange state of affairs that no science-fiction writer would have had the imagination to invent it.

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.

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. :-) )

Yes, that's PRECISELY what I meant.

No, they're called qubits. It's literally a quantum-mechanical bit, in the sense that it's a superposition of the |0> and |1> states---i.e., a quantum state that returns a bit when you make a complete measurement on it.

There are also qutrits, which are quantum trits (superpositions of |0>, |1>, and |2>), "qubytes" (collections of 8 qubits), and so on.

This terminology is now 30 years old, and in probably thousands of books and tens of thousands of papers. It's not going to change.

The earlier name for "qubit"---the name that Feynman, for example, would have recognized---was "spin-1/2 particle." But while there was some resistance, I think that even within particle physics, condensed-matter physics, etc., they'd now typically say qubit rather than spin-1/2.

In any case, would you pronounce "qit" like "kit" or "kwit"? :-)

Every few months there's another paper on the arXiv trying to do exactly that. Pretty much without exception, I've found the papers to be terrible -- leaping immediately to QM without first considering more prosaic stories for whatever human behavior they're trying to explain. It's like quantum mechanics is a hammer, and explaining human decision-making is a steak, and all these people want to use the hammer to slice the steak for some weird reason, their strongest argument being that the problem of slicing the steak doesn't map well to their bare fingers. It's amazing what some people think they can get others to swallow just by using the word "quantum"! :-)

I don't begrudge others their sincerely held faiths! But I confess that I haven't yet seen the need for nonstandard logics for anything I've personally been interested in.

Which topics?

You should probably wait for an AMA with someone who's actually an expert in AI, and ask them this question.

Since you asked me, though, I did a quick Google search and found the following paper:

https://arxiv.org/pdf/1711.09667.pdf

where indeed they use machine learning to induce the rules of chess from a large number of played games (and then learn to play better than any human). It doesn't surprise me at all that this would be feasible with current tools, although I haven't studied the paper yet, and would be curious to know how many games you need before you've learned all the rules around, e.g., castling, en passant, promotion of pawns, and perpetual check.

My guess is that for a machine to learn the rules of the games of love and politics will take somewhat longer. :-)

It's not obvious why you'd want to talk about complex amplitudes, whose squared absolute values are probabilities, outside the context of quantum mechanics. Maybe a better way to say it is: once you're talking about such amplitudes, essentially by definition you ARE talking about quantum mechanics. :-)

Having said that, in classical probability theory, it's sometimes useful to look at the (positive) square roots of probabilities, for example to get a distance measure between probability distributions. See here:

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

Also, we've often been able to use quantum tools to prove new results even about classical theoretical computer science. See here for a beautiful survey, though one that's already a decade out of date:

https://arxiv.org/abs/0910.3376

In this way, the mathematical tools that we've developed in quantum information can "pay rent" in classical CS, even if we counterfactually imagined that our world wasn't quantum-mechanical at all. It would take some time to go through an example of this, but (e.g.) it was shown that if a certain classical error-correcting code existed (called a 2-query locally decodable code of subexponential size), then an even better quantum error-correcting code would also exist, but the latter was something that people already knew how to rule out.

In these situations, some people would argue that we're not "really" using quantum physics or amplitudes; we're just taking MATH that was developed for that purpose, and repurposing it for something else. But it would be weird to say in a talk, "I'm now going to introduce a unit vector of complex numbers that's just an ordinary vector, nothing physical at all about it, then apply the following tensor product of 2x2 and 4x4 unitary matrices to it...," when everyone knows full well that all your intuition about this came from quantum states. Indeed, I confess that even when I'm doing linear algebra that has nothing to do with QM---i.e., my vectors really are just vectors of real or complex numbers, not amplitudes---I sometimes slip up and use the physicists' notation for quantum states (called the Dirac ket notation).

Yes, I do think there's a significant chance of that. If it happens, my main interest would be to understand WHY. What are the non-obvious limitations that you mention? What is true about the world that makes it seem to have this exponential explosion of amplitudes, yet makes it impossible or infeasible to harness them for computation?

The depressing possibility, of course, is that we never succeed in building useful QCs, but we also never learn anything deep about why we failed: it was just too complicated, too messy, and then at some point the funding ran out.

But I like to proceed on the assumption that the world is ultimately comprehensible (what other choice does one have in science? :-) ). On that assumption, if QC can never work, then there must be a deep reason that's not articulated in any of the existing physics books: either a breakdown of quantum mechanics itself, or else some new principle on top of QM that "screens off" or "censors" QC. Needless to say, the discovery of that principle would itself be a revolution in science -- indeed, I'd personally be more excited about it than a "mere success" in building scalable QC! (But my own bet is on the "boring, conservative" possibility, that QC can ultimately work.)

If we see the milestone of "quantum supremacy" achieved in the next few years -- i.e., a 50-70 qubit quantum computer used to solve some artificial sampling task many orders of magnitude faster than we know how to solve it classically -- that will obviously be one strong indicator that the potential of QC can be realized. An even better indicator would be the use of a quantum error-correcting code, like the Kitaev surface code, to keep encoded qubits alive for longer than the underlying physical qubits are staying alive for (or better still, to perform 1- and 2-qubit gates on them).

Yup. :-)

Or better yet, we could bifurcate into:

(1) Why is our universe apparently unable to solve the halting problem for Turing machines?

The answer, presumably, is a combination of the physical Church-Turing Thesis (specifically, the apparent impossibility of Turing-uncomputable processes in our world), with Church and Turing and Post's theorem on the unsolvability of the halting problem.

Of course one could then push back and ask why the Church-Turing Thesis should be true of our world: i.e., why shouldn't there be physical "hypercomputers"? That's an enormous question, but my old survey "NP-Complete Problems and Physical Reality" contains some thoughts about it: https://arxiv.org/abs/quant-ph/0502072

And then there's:

(2) Why should we live in a universe that's unable to solve "its own" halting problem?

I.e., even if super-Turing computers were physically possible, we could presumably formulate a halting problem for those computers, which would then require a still more powerful computer to solve (a super-duper-Turing computer?), and so on forever. This is because we could simply repeat Turing's diagonalization argument at a higher-level up -- given very minimal properties of computation, such as the ability to feed one program to another program as code, the ability of one program to emulate another one, and the ability to compute the NOT function. Once you have those properties, the inability of any given computational model (even a super-Turing model) to solve its own halting problem is just a matter of logic, as schoen said.

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)!

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. :-)

Uhh, most people don't even try to succeed in academia! So no surprise if they don't. It's not like I made it to the NBA or something. :-)

Let me speak only about academic CS, since that's what I know best. Of the students who enter the major CS PhD programs in the US, I think something on the order of half of them (maybe a bit less) end up in academic positions, with the rest going to startups and industry and government. So, of the PhD students who really want academic positions in CS, fortunately a large fraction are still able to get them---just not necessarily at a top-tier school. Of course, many students outright prefer industry -- Google and Microsoft can, after all, offer compensation packages that blow academic ones out of the water -- or else they prefer industry to the academic options that are available to them. And that's fine. I feel lucky to work in a field where PhD students have multiple career options, and when a student comes to me for advice, I try to help them figure out what's best for them, rather than imposing some global preconception on it.

From what I know, the situation is worse in other academic fields, like math and high-energy physics and certainly philosophy and other humanities fields -- where you can get dozens of well-qualified applicants for every academic opening, with all the cutthroat competition and other pathologies you'd imagine that would lead to.

No, I don't think that QCs will help much for simulating chaotic systems, except insofar as those systems are also quantum-mechanical. For (e.g.) predicting the weather, there may be small quantum speedups that you can get here and there, from Grover's algorithm and faster gradient computation and so forth, but at a fundamental level, as far as anyone knows, you still need to just iterate the partial differential equation from one time step to the next, same as a classical computer does.

Stepping back, note that "quantum" and "nonlinear" are two completely different concepts -- in fact, at the level of amplitudes (i.e., the Schrodinger equation), quantum mechanics is the one example we have in physics of a perfectly LINEAR theory! Alan Sokal had a lot of fun with that point in his "Social Text" parody article: http://www.physics.nyu.edu/sokal/transgress_v2/transgress_v2...

On the other hand, this is perfectly compatible with quantum systems having chaotic phenomena at the level of observables (like the positions and momenta of particles), and in fact there's a whole field called "quantum chaos" that studies such situations.

It feels really uncomfortable that, if you have infinitely many people wearing red or blue hats that they can't see, then they can all guess their own hat color with only finitely many of them being wrong. Not to mention Banach-Tarski and a hundred other strange phenomena. This all militates toward rejecting AC.

But then, if we reject AC, we can have infinite sets that are incomparable (i.e., they're not isomorphic and neither is larger than the other). So pick your poison!

Thinking about such things for too long makes me feel grateful that I spend most of my time in the finite world (or, let's say, the world of continuous parameters that we only ever measure to finite precision, so that the statements we care about can ultimately be phrased arithmetically). In this world, because of e.g. the Shoenfield absoluteness theorem, anything that can be proved with the help of AC can also be proved without it.

A classic from 1994 is "Computational Complexity" by Papadimitriou.

Two good sources for newer material (from the past quarter-century) are "Complexity Theory: A Modern Approach" by Arora and Barak, and "The Nature of Computation" by Mertens and Moore.

A personal, idiosyncratic favorite is "Gems of Theoretical Computer Science" by Uwe Schoning.

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.)

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.

Sorry, I don't know who that is.

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."

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." :-)

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!" :)

Thanks!!!

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.

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.