21 ms·

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

• mcnamaratw 8y ago
  Hi Scott, Can you recommend a nice technical intro on what this is all about? (Level: I'm an EE, fine with undergrad quantum mechanics but never understood field theory at all.) Thanks! Tom McNamara
• xTouny 8y ago
  Hello Scott, I have gathered from YouTube that you enrolled in CS Major in order to make your own video game, How does that fit a prodigious math geek who started learning calculus aged 11 and lately one of the pioneering quantum theorists?
• selimthegrim 8y ago
  Hi Scott - What was the best part/most favorite thing about your sabbatical? Can you explain why Forrelation is a guiding light for quantum deep learning these days? As a bonus - it would be nice to see a walkthrough - commentary of the recent oracle separation proof of Tal and Raz and how they used Fourier transforms specifically.
  • ScottAaronson 8y ago
    My favorite part of my sabbatical in Tel Aviv was having some actual time to do research. My second-favorite part was the hummus. Forrelation is not a “guiding light for quantum deep learning.” I’m not even sure if there’s such a thing as “quantum deep learning” that’s sufficiently well-developed to deserve the name. You can use Forrelation as a separating example for some other quantum learning problems, e.g. k-means clustering, but so far that mostly just shows that you can artifically shoehorn an exponential quantum speedup into those tasks, rather than that the tasks will give us useful quantum speedups in “real life.” In the Forrelation problem, I conjecture that the only thing that really matters about the Fourier transform is that it’s a unitary matrix all of whose entries have small absolute values. As such, it lets you relate two Boolean functions in a way that a quantum computer can notice, but that’s extremely “global” in nature and doesn’t show up locally. Raz and Tal may have used some additional technical properties of Forrelation in their proof (now that I write that, I’m actually not sure—I’ll need to check!). But if they did, then I conjecture that another proof could avoid the use of those properties.
    • ScottAaronson 8y ago
      Just as a quick followup: Avishay Tal has confirmed for me that, indeed, their proof still goes through if you replace the Fourier transform by any other unitary matrix with bounded entries.
      • selimthegrim 8y ago
        Thanks, Scott! I thought you’d missed this. Maybe we’ll get to have you give a colloquium here at Tulane someday soon!
    • quantum_dog 8y ago
      Hi Scott, Have you seen https://arxiv.org/abs/1806.09729 https://arxiv.org/abs/1806.09729? I would call that quantum deep learning, or more accurately, foundations of quantum deep learning.
      • ScottAaronson 8y ago
        No, I hadn't seen that paper; thanks! I don't want to comment on it without having studied it, except to mention that it doesn't make any reference to Forrelation.
• NoKnowledge 8y ago
  Hi Scott, Do you think we will see a Quantum Winter (or even several), similar to how we've had several AI Winters? We see tremendous amounts of funding in academia (and also industry) to build ambitious projects that still have significant issues to overcome (both theoretical and engineering) before being any close to being implemented. At the same time there (still) seems to be much misunderstanding, such as Vivek Wadhwa's recent post[0] or various reports about an unhackable internet based on quantum information. I am afraid that this may lead to people having unrealistic expectations on what can be built and how fast it can be built, with the consequence that we will see less and less funding and investments in the nearby future. [0]: https://www.scottaaronson.com/blog/?p=3645 https://www.scottaaronson.com/blog/?p=3645
  • deleted 8y ago
    [deleted]
  • ScottAaronson 8y ago
    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.
• matrixmatty 8y ago
  Hi Scott, Is there any chance advances in quantum computing will affect crypto currencies. I.e. it might be possible to shortcut mining or mess with the quorum of the distributed ledger? I'm curious as crypto currency is so hyped, it would dismay me that advances in quantum computing might disrupt the current landscape, or even better improve it in some way. Entanglement is already deployed and in use for data transit, in curious how annealing or other physics might be a game changer
  • ScottAaronson 8y ago
    See this recent survey article: https://arxiv.org/abs/1710.10377 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/ 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.
• bruth 8y ago
  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 8y ago
    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 https://www.scottaaronson.com/blog/?p=3848 about exactly this!
• DC-3 8y ago
  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 8y ago
    Exactly the question I would love answered. Edit: this seems roughly answered to a question by user r4um
    • mrfusion 8y ago
      I don’t see where it’s answered?
  • ScottAaronson 8y ago
    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 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-quantum-computing-promises-new-insights.html 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. :-)
    • 8y ago
• SRasch 8y ago
  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 8y ago
    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.)
• r4um 8y ago
  How far are we from "emergence" in terms of AI ecosystem ? Will quantum computing pave the way for it ?
  • ScottAaronson 8y ago
    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 8y ago
      "not to mention our own brains" Is this a known known that our brain doesn't use QC?
      • ScottAaronson 8y ago
        No, it's an unknown known. :-)
• glifchits 8y ago
  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 8y ago
    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 8y ago
  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?
  • ScottAaronson 8y ago
    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 https://www.scottaaronson.com/blog/?p=1951 or in the Ghost in the Quantum Turing Machine essay that’s linked below.
  • bascule 8y ago
    There have been some poorly received hypotheses to this effect, most notably Roger Penrose's Orch-OR: https://en.wikipedia.org/wiki/Orchestrated_objective_reduction 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://arxiv.org/abs/quant-ph/9907009 https://onlinelibrary.wiley.com/doi/pdf/10.1207/s15516709cog0000_59 https://onlinelibrary.wiley.com/doi/pdf/10.1207/s15516709cog...
  • ahussain 8y ago
    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 https://www.scottaaronson.com/papers/giqtm3.pdf
    • ttctciyf 8y ago
      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 https://www.scottaaronson.com/blog/?p=1438#comment-80656
• TrinaryWorksToo 8y ago
  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 8y ago
    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 8y ago
      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 8y ago
  What do you think would be the best route into Quantum Computing? Through physics, maths or computer science?
  • ScottAaronson 8y ago
    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 8y ago
  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.
  • adrianN 8y ago
    Check out some lecture notes, e.g. https://cs.uwaterloo.ca/~watrous/LectureNotes/CPSC519.Winter2006/all.pdf https://cs.uwaterloo.ca/~watrous/LectureNotes/CPSC519.Winter...
    • mrybczyn 8y ago
      Also another course: http://www.math.uwaterloo.ca/~jyard/qic710/ http://www.math.uwaterloo.ca/~jyard/qic710/
  • ScottAaronson 8y ago
    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 8y ago
  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.htm 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 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 https://news.ycombinator.com/item?id=14674333
  • rspeer 8y ago
    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 8y ago
  What advice would you give for productivity/getting things done?
  • ScottAaronson 8y ago
    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 8y ago
      I hear that. But followup question! What do you think of commitment devices (like Beeminder!) for imposing discipline on oneself?
    • davesque 8y ago
      It's actually really encouraging to hear that Scott has many of the same vices as me.
    • VladimirGolovin 8y ago
      > 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 8y ago
  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 8y ago
    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 8y ago
  [deleted]
• n0mi1k 8y ago
  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 8y ago
    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 8y ago
  Do you have any thoughts on the IEEE Quantum Computing Nomenclature Working Group? http://standards.ieee.org/develop/wg/QCN-WG.html http://standards.ieee.org/develop/wg/QCN-WG.html
  • ScottAaronson 8y ago
    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 8y ago
      Is it pronounced kew-bit or kuh-bit or kwu-bit?
      • Koshkin 8y ago
        Depends on how you pronounce 'Q', I guess...
      • ScottAaronson 8y ago
        "cue-bit." I.e., the name of the letter Q, followed by "bit."
• MartianSquirrel 8y ago
  Which do you prefer: Crêpes or waffles?
• danharaj 8y ago
  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 8y ago
    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 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 8y ago
  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 8y ago
    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 https://arxiv.org/abs/1706.06752 [2]: See section VI of https://arxiv.org/abs/1805.03662 https://arxiv.org/abs/1805.03662 [3]: https://docs.google.com/presentation/d/e/2PACX-1vReeRxH80RuuU1cAwrsJ1ybeVQyxG35CqvRSGRGX2PhkYybAup7ScLz6G-AYH5DF-J7EhEJzMoVceCL/pub#slide=id.g3bd373e21f_0_23 https://docs.google.com/presentation/d/e/2PACX-1vReeRxH80Ruu... [4]: https://crypto.stackexchange.com/a/47337/7860 https://crypto.stackexchange.com/a/47337/7860 [5]: https://ai.googleblog.com/2018/03/a-preview-of-bristlecone-googles-new.html https://ai.googleblog.com/2018/03/a-preview-of-bristlecone-g... [6]: https://www-03.ibm.com/press/us/en/pressrelease/53374.wss https://www-03.ibm.com/press/us/en/pressrelease/53374.wss [7]: https://newsroom.intel.com/press-kits/quantum-computing/#49-qubit-processor https://newsroom.intel.com/press-kits/quantum-computing/#49-...
  • ScottAaronson 8y ago
    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 8y ago
  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 8y ago
    Thanks!!!
    • lisper 8y ago
      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 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-puzzle-part-drei.html http://blog.rongarret.info/2018/05/a-quantum-mechanics-puzzl.... Also FWIW, that's my blog.)
• enriquto 8y ago
  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 8y ago
    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 8y ago
      my point exactly. The class P contains this silly stuff.
      • svat 8y ago
        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 8y ago
          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 8y ago
            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 8y ago
  Hi! So, what do you do when you're not flipping qubits around? Got any cool stories you wanna share?
  • ScottAaronson 8y ago
    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 8y ago
      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!)
      • ScottAaronson 8y ago
        Thanks!!!
• elizabeth8890 8y ago
  Are you collaborating with the National Labs at all, i.e., http://quantum.lanl.gov/q_computing.shtml http://quantum.lanl.gov/q_computing.shtml
  • ScottAaronson 8y ago
    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 8y ago
  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 8y ago
    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 8y ago
      How about Germany? It seems people doing optics here like to connect their research to quantum computing.
      • ScottAaronson 8y ago
        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 8y ago
  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-propaganda-machine-86dac61668b https://medium.com/join-scout/the-rise-of-the-weaponized-ai-...
• da-bacon 8y ago
  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 8y ago
    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 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.
• marcelluspye 8y ago
  Hi Scott, Do you think some understanding of the implications of quantum computers is important for laypeople, and what do you think is the best way to communicate this kind of information? You can see the eyes of `regular people' glaze over mid-sentence if you use the word quantum, and associate any quantum-anything to magic. In the era of clickbait and fake news, this makes misinformation all the more prevalent, especially when it comes to pop-sci/`mainstream' coverage. tl;dr a) How much of a problem is it that people will believe anything with the word `quantum' in it? and b) What do you think is the best way to remedy this?
• adrianN 8y ago
  When do you think will we have the first quantum computer that can solve useful problems faster than the classical competition, for example in quantum chemistry?
  • ScottAaronson 8y ago
    I hope in 5-10 years, but really I don’t know, and no one else does either.
• Ono-Sendai 8y ago
  Hi Scott, What's your current position on the likelihood of quantum computing working/being possible? P.s. I enjoyed your book 'Quantum Computing Since Democritus'.
  • dsr_ 8y ago
    That's a very wide question. How about something like: What's the likelihood of quantum computing being a practical method to solve some class of problem in the next ten years?
    • fiatjaf 8y ago
      You're assuming it's possible without explicitly saying it?
      • dsr_ 8y ago
        If it's not possible, then the answer is clearly 0. If it is possible but not practical for solving any problems, that's a thing one would want to know. If it's possible but unlikely to be practical within the next ten years, that's even more useful. Perhaps it's possible and already practical for some problem. I don't know what that is, so it would be good information. In all of these cases, it's Scott's presumably better-informed opinion that's being requested.
        • fiatjaf 8y ago
          I want to know if it is possible.
• godelmachine 8y ago
  Hi Scott, Its been my longtime dream to work in Electronics Engineering - more specifically, design integrated circuits for Artificial Intelligence/ Machine Learning applications. I read about FPGA's a lot and love the concept of Reconfigurable Computing. Its because of my love for FPGA's I want to carve out a career in VLSI. Right now, I work in Enterprise Software (BMC Software - as a Support Engineer and in administrator role). I tried to get a job in VLSI after attending a 6 month finishing school from CDAC, but no luck. However, I still dream of getting an opportunity in companies like Intel/ Xilinx and being able to develop some FPGA based solutions for AI/ ML. In the next 18 months, I see myself getting my Canada PR and searching for a job there. My current job requires me to be in touch with Java and Java related frameworks to a very small extent (primarily for reading logs, and our development platform is build up on Eclipse.) I am hoping to get a job in Canada based on these skillsets. What do you reckon is the future of the hardware industry? I heard there's a lot of scarcity of jobs there? Or should I stick to Enterprise Software? Honestly need your opinion here. Thanks in advance, and great job taking up this AMA !! :)
• drostie 8y ago
  Hi Scott, I first stumbled across your blog while I was across the pond doing my Master's in Delft; it looks like you've been relatively successful since then. I was wondering how you feel that success/celebrity has affected you. Does it actively drive you to something other than research -- say, are you viewing it as a building block to maybe publishing a book or so? Or does it feel like a distraction from research in that "oh why do I have these arguments online" way that we can often fall into?
  • ScottAaronson 8y ago
    There’s no question that celebrity can get to your head in this line of work. Every single time I get off my private plane somewhere, I’m mobbed by quantum complexity theory groupies, not to mention the Hacker News paparazzi, and the women shrieking and throwing their panties at me ... oh god, the women are so persistent! Don’t they realize I’m married? But I do try hard to “keep it real”—or better, “keep it complex”—by setting aside some quality time just for me and some pen and paper. As I like to say, it’s all about the amplitudes. (Seriously: I do have a book, Quantum Computing Since Democritus! And I have been approached by people asking me to sign it. But typically only in a few highly selected places, like Cambridge, MA or Berkeley, CA. :-) )
• fiatjaf 8y ago
  How does quantum computing fit in the quantum worldview of Wolfgang Smith?
  • ScottAaronson 8y ago
    Sorry, I don't know who that is.
    • Koshkin 8y ago
      I got curious and found out that it's this guy who "raises the questions of whether the scientific method is in fact dependent on the scientistic philosophy and, if it is not, whether linking it to other philosophical frameworks would provide better solutions to the way [quantum] physical phenomena are interpreted."
• chrispeel 8y ago
  Quantum information theorists such as Patrick Hayden and Leonard Susskind suggest that information can be neither created or destroyed. Do you ever think about such things? If so, how does it enter into your work?
  • ScottAaronson 8y ago
    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!
• mygo 8y ago
  you’ve written about P vs NP in the past. What are your current thoughts on P vs NP as of today? Do you have any speculation as to whether it’s one or the other, and why? Do you think there have been any major recent breakthroughs (say, in the past 5 years) to move us closer to a solution?
• Raed667 8y ago
  Hi Scott, Would you see, in the future, quantum computing used by end-users? If so in what possible applications?
• andrepd 8y ago
  How do you feel about the state of higher education? Specifically, do you think expensive degrees, underpaid PhD/Postdoc positions, and shortage of tenured jobs may discourage students from joining academia and push them into industry instead? It feels to me our best brains are at Facebook and Google doing cutting-edge research on how best to manipulate our mammal brains into buying ever more crap...
  • modzu 8y ago
    for sure more research is being done at the corporate level, and youre absolutely right about why that sucks (public institutions mean public knowledge). in some cases its the only way to it though, unless we step up and fix academia (ie provide more funding for science)
  • ScottAaronson 8y ago
    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.
• Y_Y 8y ago
  Hi Scott, Why do we live in a universe where the Halting Problem is unsolvable?
  • schoen 8y ago
    (Not Scott!) The Halting Problem's unsolvability is proven in a fully abstract mathematical way, and so the truth of this result is as logically necessary as the truth of other mathematical theorems. It doesn't refer to anything about physics. So it seems like this question might be better bifurcated into Why do we live in a world in which Turing machines are a good model for what computations we can physically perform? and Would the laws of mathematics be the same in any universe? Each of these questions might then be a good one to pose to Scott.
    • Y_Y 8y ago
      Who said anything about physics? I was thinking about axioms/logic systems and finitism.
      • lisper 8y ago
        > Who said anything about physics? You did. You asked about why the universe we live in has a particular property. That's a question about physics.
        • Y_Y 8y ago
          Well I obviously don't think so, and all you've done is state the opposite claim.
          • lisper 8y ago
            What do you think the word "physics" means?
            • Y_Y 8y ago
• smikhanov 8y ago
  What is your opinion on how advances in QC may advance our understanding of human consciousness? I remember that in your QCSD book you make few remarks about Penrose's microtubules theory, the one that tries addressing two questions about human mind: 1. Are mind processes Turing-computable? 2. If yes, at which level in the brain does the consciousness emerge? Penrose's answers to that (as far as I know) are not generally accepted by the scientific community. What is your intuition about these two questions?
  • ttctciyf 8y ago
    I don't want to prejudice an actual answer here, but it's worth noting Mr Aaronson has produced a fantastic paper, almost uniquely substantive in its field, commenting on several aspects of possible relations between quantum physics and the mind, see https://www.scottaaronson.com/blog/?p=1438 https://www.scottaaronson.com/blog/?p=1438 See also his blog posts on IIT, etc., such as: https://www.scottaaronson.com/blog/?p=1799 https://www.scottaaronson.com/blog/?p=1799
• internetman55 8y ago
  Hi Scott, hope you are doing well. A friend of friend worked with you and said that you are nice and they enjoyed it a lot. Hope you have a wonderful day
• Yajirobe 8y ago
  Hi Scott. I've read your 'Why Philosophers Should Care About Computational Complexity' - I found it to be a very nice read. Is your book 'Quantum Computing Since Democritus' worth getting my hands on? Is it not going to be too repetitive given that I've read your article?
  • ScottAaronson 8y ago
    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.
• rain1 8y ago
  If I use a quantum random number to pick my actions does that mean there's a universe where I took each option? This terrifies me
  • gooseus 8y ago
    Why would this only apply to using a quantum random number to make a decision? Also, what do you find terrifying about the existence of multiple universes where every possible outcome of a decision you make plays out?
  • rain1 8y ago
    nvm i didn't want you to answer my question anyway
  • ScottAaronson 8y ago
    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.)
• OscarCunningham 8y ago
  How do you feel about the Axiom of Choice?
  • ScottAaronson 8y ago
    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.
    • phs 8y ago
      As a follow-up, what is your position on intuitionist/constructivist logic?
      • ScottAaronson 8y ago
        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.
    • OscarCunningham 8y ago
      Thanks for the answer! For other people reading, here's the blue/red hats puzzle that Scott was referring to (edited from https://en.m.wikipedia.org/wiki/Hat_puzzle#Prisoners_and_hats_puzzle https://en.m.wikipedia.org/wiki/Hat_puzzle#Prisoners_and_hat...): > A countably infinite number of prisoners, each with an unknown and randomly assigned red or blue hat, line up in a single file line. Each prisoner faces away from the beginning of the line, and each prisoner can see all the hats in front of him, and none of the hats behind. Starting from the beginning of the line, each prisoner must correctly identify the color of his hat or he is killed on the spot. The prisoners have a chance to meet beforehand, but once in line no prisoner can hear what the other prisoners say. The question is, is there a way to ensure that only finitely many prisoners are killed? The solution is that it is possible, and you can look on the Wikipedia page to find out how. Even more paradoxical is that the prisoners can still save all but finitely many of themselves even if there are infinitely many possible hat colours. For example you could allow the hat colours to be specified by three real numbers giving an RGB value.
• rsln-s 8y ago
  Hi Scott, Do you think there is a significant chance that quantum will never take off (i.e. there are non-obvious limitations that will prevent quantum architectures like superconducting qubits / trapped ions / quantum dots /... from ever outperforming classical supercomputers)? Related, what in your opinion is the best indicator (or would be the best indicator if demonstrated) of the potential of quantum devices?
  • jovial_cavalier 8y ago
    I would also like to know the answer to this. Popular culture has seemingly latched onto the phrase "quantum computer" and decided it's the next logical step for computing in general, without ever really defining what it is or thinking about it too clearly.
    • opportune 8y ago
      Well, never is a long time. I guess the more interesting question (to me) is whether engineering challenges will be easily overcome so as to make quantum computer components cheap and ubiquitous, or if there's some innate difficulty to their production that will make them uncommon for everyday personal use.
      • 781 8y ago
        People struggled for 40 years to make a blue LED. Even if quantum computers required near zero temperatures, superconductors and such stuff, there is no reason why you couldn't have all that in a no-serviceable-parts-inside box if the economic incentives were strong enough.
        • rsln-s 8y ago
          Well the question really is economic incentives. If it is too hard to do (say, doesn't scale) or can be simulated efficiently-ish on a classical computer -- no one will do it.
        • martin1975 8y ago
• aswanson 8y ago
  Any recommended books on complexity theory?
  • ScottAaronson 8y ago
    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.
• bem94 8y ago
  Do you think that humanity is well placed to be responsible wielders of quantum computing as a tool, and what do you feel your role (as a scientist with a large public following) is in shaping those future perceptions of responsibility?
  • ScottAaronson 8y ago
    No, I don’t think humanity is well placed to be responsible wielders of quantum computing. But the thing is, we’re even less well-placed to be responsible wielders of nuclear weapons, or climate-destroying combustion engines, or probably even guns or fire! :-) So with all the more dangerous technologies out there, it would be weird to fret about quantum computers of all things: something that seems unlikely to do much harm (at least if we take care to upgrade our crypto), and that might even do significant good for the world, for example if quantum simulation lets us design more efficient batteries and solar cells.
• nicklaf 8y ago
  Hi Scott, If quantum computing ever becomes commonplace, and quantum computer programs widely written and understood, do you envision that the teaching of quantum mechanics itself will be significantly impacted? Or instead will we simply see quantum complexity theory begin to redefine the undergraduate computer science curriculum?
  • ScottAaronson 8y ago
    I think that the teaching of QM has already been impacted by quantum information—and I hope it gets impacted more, regardless of if and when we get useful QCs! To my mind, it’s just infinitely clearer to start with the basic rules and properties of QM—states, unitary transformations, measurements, tensor products, entanglement, density matrices, etc.—illustrated with the simplest systems to which those rules apply, namely collections of qubits (or more generally, finite-dimensional Hilbert spaces). This already lets the students fully understand no-cloning, quantum teleportation, quantum key distribution, basic quantum algorithms like Bernstein-Vazirani and Simon, and other cool things from quantum information, and it already lets them explore the conceptual questions (the measurement problem and so forth) that interest most of them. After this material has been mastered, and only after, one could see how it gets applied to real physical systems like the harmonic oscillator, the hydrogen atom, or a particle in a 1D potential well. So, all the mathematical complications of infinite-dimensional Hilbert spaces—which are not essential to understanding QM itself—could be deterred to this part of the course. This is the reverse of the historical order in which the ideas were discovered in the 1920s, but I think it’s the much more logical order in which to learn them—even if quantum information weren’t a big thing that people now care about. If you want to see a recent text by a bona fide physicist that presents QM in exactly this way—what I think of as simply the “modern” way—then check out Lenny Susskind and Art Friedman’s remarkable “The Theoretical Minimum” series. Or you could look at pretty much any introductory book or course lecture notes about quantum information, including mine. We do it this way as well, except that we never do get to the harmonic oscillator or the hydrogen atom. :-) I can say from experience that the material is then totally accessible to any bright undergrad who’s done math up through linear algebra.
    • 8y ago
• vymague 8y ago
  Most people were not able to succeed in academia. What do you think you did differently than most people?
  • ScottAaronson 8y ago
    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.
    • vymague 8y ago
      Thank you very much for your answer. I suppose the situation is a bit different in CS.
• mkagenius 8y ago
  If related, Have you heard about qubits being able to explain dark energy mystery? What is you view about that?
• beefman 8y ago
  What good is oracle separation? The recent separation between BQP and PH, for example, doesn't seem to mean much. Of course such results may spur the discovery of new proof techniques, or new ways of thinking about a problem, but is the result itself useful? I must be missing something, like a way of stringing together oracle separations to produce a real separation... or is it just the case that oracle separations are considered some kind of suggestive evidence that a real separation exists? Edit: This post[1] says two classes are equal with no oracle if they are equal with respect to every oracle, but apparently only because "every oracle" includes the null oracle... [1] https://www.scottaaronson.com/blog/?p=451 https://www.scottaaronson.com/blog/?p=451
  • jkabrg 8y ago
    I think oracle separations are currently only useful as barrier results, showing that certain proof techniques can't solve the full problem.
  • ScottAaronson 8y ago
    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.
• _rpd 8y ago
  What's our best understanding of the process of quantum decoherence? Are there open questions? Problematic engineering issues?
• mherrmann 8y ago
  What would you recommend to an amateur wanting to tackle P vs NP in his spare time?
  • tzahola 8y ago
    Algorithms 101
    • mherrmann 8y ago
      And beyond that?
      • 137things 8y ago
        The most accessible route would probably to try to think up a polynomial time algorithm for an NP-Complete problem. There are a lot of problems to choose from (e.g. Sudoku, Battleship are some fun ones) which you can find a list of on wiki or somewhere. Indeed you need some study on algorithm design (I guess Algorithms 101), but really it all takes is some creativity. Hope you solve the problem and win that million $s
  • lisper 8y ago
    https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf
• algon33 8y ago
  Hi Scott, Do you think that chaotic systems would be better analysed by quantum computing over classical computing? More generally, is BQP powerful enough to deal with chaotic systems in the same way P is for linear systems? Oh, and I think your review of "Enlightenment Now" was a bit too rosy. When he analysed the data he's superb, but he seems to lambast people he heavily disagrees with. Its a tad disheartening.
  • ScottAaronson 8y ago
    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_singlefile.html 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.
• nonamenoslogan 8y ago
  How long until quantum computing can put an end to those bullshit cryptocurrencies?
• kuwze 8y ago
  Why is P=NP/P!=NP so difficult to prove? I just wanted to say that I think your writing helped me appreciate Michael Cohen and learn what an amazing person he was. The more I read about him, the more I want to be like him. What qualities do you think helped him contribute and be such a great person? What do you think a lackluster programmer could do to be more like him?
  • jderick 8y ago
    If you have not seen it, you may be interested in his 116-page survey of the problem. https://www.scottaaronson.com/blog/?p=3095 https://www.scottaaronson.com/blog/?p=3095
    • kuwze 8y ago
      Thank you for posting that! That is a great overview and exactly what I was looking for.
• zitterbewegung 8y ago
  How long do you think that we will have a quantum computer that will out compete traditional computation? What do you think about Topological Quantum Computation? How do you think we can solve the problem that many people getting their PhD are vastly underpaid and also adjunct professors?
• Jommi 8y ago
  I have so many questions for you, but lets just go with one. Can you explain to me the concept of "logical qubit", and the whole debacle about qubit quality? I'm still getting confused again and again over this.
  • ScottAaronson 8y ago
    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.
• tombert 8y ago
  I don't have much to say, except I really enjoyed Quantum Computing Since Democritus. The lighthearted nature of the book made it a lot more approachable for someone who is mostly self-learning this stuff.
• Leibniz0 8y ago
  Scott, I loved your book (QCSD). What are the chances that overcoming noise in quantum gate systems as they get larger is a practical impossibility beyond some threshold - for instance in the same way that inverting a gaussian convolution requires super-exponentially less noise above a given sampling density / stdev ?
  • ScottAaronson 8y ago
    If anything like that turned out to be true, and fundamental (rather than just an engineering limitation), I’d regard it as a shocking discovery that would overturn our current understanding of QM. After all, physics is local—each particle couples mostly to its near neighbors—so there doesn’t seem to be any inherent reason why noise per qubit needs to keep increasing as you integrate more and more qubits. For more, see my other answers on this thread about QC skepticism.
• evanb 8y ago
  Hi Scott, What do you think of radical Mathematical Platonism (eg. a la Tegmark)? As a computational physicist I tend to tell people that in my hands a computer is like a telescope, but it lets me see into mathematics---but that seems to tacitly assume the reality of mathematical objects.
• deleted 8y ago
  [deleted]
• MrXOR 8y ago
  Hi Scott, What is the current status of PvsNP problem? P=NP or P!=NP? Is any relationship between PvsNP problem and Riemann Hypothesis? Who to follow to know the progress of solving PvNP problem?
  • FartyMcFarter 8y ago
    https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf
    • ScottAaronson 8y ago
      +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.
• marchdown 8y ago
  What are some research areas complementary to the quantum computing/computational complexity where additional effort would remove roadblocks in QC research?
• deleted 8y ago
  [deleted]
• ClintEhrlich 8y ago
  Howdy Scott, Is anyone in your field working on the implications of computational complexity for normative ethics? Hume's guillotine relies on the impossibility of any evidence for or against moral facts, but one could stipulate to that while using e.g. Kolmogorov complexity to select moral facts with the highest prior probability to a naive computational oracle. Not saying it's how I'd necessarily choose my ethics, but if AGI employs algorithmic inference (e.g., approximating Solomonoff induction) for conventional epistemology, the potential may exist for it to extend those algorithms to normative judgments, for better or worse.
• geraltofrivia 8y ago
  Hi Scott, I got interested in Quantum Computing, and fundamental mathematics a week ago. Ever since, I'm reading your book `Quantum Computing since Democritus`. I discovered your blog (oh and it's such a joy to read!). Today I run into your podcasts and AMA. This is going to get overwhelming very soon, I feel. Couple things: your book is an amazing repertoire of abstractions, theorems, phenomenon and whatnots. Does it get overwhelming sometimes walking down the street like normal people, with that deep an understanding of these domains? I personally think that your book is a nice place to start with, in the domain(s) of fundamental mathematics. The text gives a nice idea of the depth I'll encounter in these fields (I think). Keepin' it real helps me, an engineering grad, to not pass it up as ravings of men with too much time on their hands. Do you think your book should be read in this context? What else would you recommend, if any?
  • ScottAaronson 8y ago
    Knowing more math than most of the people who you pass on the street, but at the same time having vastly inferior social skills to them, is something that you sort of get used to in childhood. :-) You should keep in mind, also, that as a theoretical computer scientist, I spend a lot of my time hanging around people who are abnormal in more-or-less the same ways I am, and in many cases more so. Besides QCSD, I’d try Mermin’s Quantum Computer Science: An Introduction for QC, or any of my 50 favorite books from this list https://www.scottaaronson.com/blog/?p=3679 https://www.scottaaronson.com/blog/?p=3679 if you’re just looking for some interesting reading material.
• denimalpaca 8y ago
  I took a grad-level quantum computing class which I didn't quite have the physics background for, and the lecture that lost me, about 3 weeks in, was on the different kinds of physical gates quantum computers use. My recollection is that there were 3 necessary gates for a quantum functionally complete set: One gate was classically functionally complete, the other two are where I got lost. Can you explain like I'm 5 (or explain like I'm an undergrad with minimal QM knowledge) what these other gates are doing? Thanks!
  • ScottAaronson 8y ago
    Actually, if you already have a classically functionally complete gate (say, the Fredkin or Toffoli gates), then you only need one other gate to get a functionally complete set for quantum computing. This one other gate could be the Hadamard, which I discussed in other answers. The Hadamard gate is needed to put your machine into a superposition of states, and then also to create interference between the different branches of the superposition. Of course, if you have no superposition and no interference, then it isn't much of a quantum computer! If your question was instead to explain the concepts of superposition and interference themselves, then unfortunately that would take more time. However, you could try some essays that I wrote a while ago https://www.scottaaronson.com/writings/highschool.html https://www.scottaaronson.com/writings/highschool.html https://www.scottaaronson.com/blog/?p=208 https://www.scottaaronson.com/blog/?p=208 in addition to the resources that have been linked to elsewhere on this thread.
• taserian 8y ago
  Hiya, Scott! I recently heard the first episode of Rationally Speaking podcast episode where you were the guest (yes, I'm catching up with the RS Archives during my long commute). I've also started reading QCSD (hey, if it's going to be our decade's GEB, we may as well give it an acronym. :: grin:: ) I've already corrected my very mistaken understanding of how QC works, as in the tagline of your blog. Are there any other concepts that we need to shake off that would make explaining these concepts easier for the layman? Do you have any words of wisdom for the masses?
  • ScottAaronson 8y ago
    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.
• JakeTyo 8y ago
  Why don't we call Qbits just "qits". Since Quantum-Binary-Digit doesn't really make sense. Do people in the field refer to them in other ways?
  • andbberger 8y ago
    Sure it makes sense - a qubit is canonically a quantum spin system, which has two eigenstates, up and down.
    • JakeTyo 8y ago
      What about superposition? Or is that not considered a 'state'?
      • Koshkin 8y ago
        One can justify the name using the fact that the state space is 2-dimensional.
      • OscarCunningham 8y ago
        They're states but not eigenstates. It's like the difference between RGB colour and greyscale. In both cases there are infinitely many possible colours, but in greyscale they're all mixtures of two "primary" colours (black and white) whereas in RGB they're mixture of four (black, red, green and blue). In a qubit the infinitely many superposition states are all mixtures of just two eigenstates.
        • JakeTyo 8y ago
          Thank you! This makes perfect sense.
      • virgil_disgr4ce 8y ago
        A superposition is indeed a state, comprised of linear combinations of the basis states. Further, (and anyone, please correct me where I'm wrong), the eigenfunctions (which could actually be called eigenstates) of an operator ARE the basis set, as they are orthonormal. (Right?)
• fpoling 8y ago
  Hi Scott, If somebody claims that there is no freedom of will, what what you accept as a reasonable proof? It seems that one can be sceptical even in presence of extremely precize predictions as it my be easier to alter memory about predictions than to produce them.
  • ScottAaronson 8y ago
    I’m not sure I fully understand your argument, but if someone showed that they could perfectly predict the actions of the people around them, say hours or days into future, placing the predictions into a sealed envelope or a cryptographic commitment and revealing them later, then to whatever extent fraud and the like had been ruled out as explanations (in the ordinary experimental ways, and possibly with the help of James Randi :-) ), I’d have to say that the person had successfully unmasked free will as an illusion.
    • fpoling 8y ago
      thanks for a reference about James Randi! Now I reliazed that indeed if the claims survives exteremely sofisiticated scrutiny, then it really does not matter if it was a fraud or not, and one would need to accept one lives in a world where one is predictable in one way or another.
• cc-d 8y ago
  Do you believe that nation state actors are currently utilizing quantum computing, and if not now, do you see this happening in the near future? If so, what use cases do you foresee?
• naiv 8y ago
  Hello Scott, can encrypted data on blockchains easily be decrypted with quantum computers in the coming decade?
  • ScottAaronson 8y ago
    No, almost certainly not in the coming decade. See my answer here: https://news.ycombinator.com/item?id=17429547 https://news.ycombinator.com/item?id=17429547
• rw 8y ago
  Hi Scott, thank you for writing your blog all these years. Your Busy Beaver essay ignited my passion for computer science, especially in algorithm analysis, logic, undecidability, and probability theory. I used to be someone who only thought in code; thanks to you, I now also think in math.
  • ScottAaronson 8y ago
    Thanks; that made my day!!!
• Tomte 8y ago
  Hi Scott, what would you say are the main reasons why you in your mid-thirties are a professor at a prestigious university? Sheer determination and perseverance? Less partying and more learning? Your upbringing? I’m asking, because sometimes there’s an interesting story behind it, like with Matt Might (http://matt.might.net/articles/tenure/ http://matt.might.net/articles/tenure/) who found himself in a objectively bad situation — a child believed to die soon — making him reevaluate priorities and getting successful as a side effect.
  • ScottAaronson 8y ago
    Well, the "less partying" part sounds accurate. :-) In grad school, for example, I had some good friends, but very little "party life" and certainly very little dating life---not out of choice, just because I didn't even know how to start. As a result, I was often severely depressed. On the positive side, though, I was more productive at research than I've ever been since! I had unlimited time to think, and also enormous drive to succeed so that at least something would be going right in my life. Just as important, though, I loved actually working on research problems (still do), as opposed to just the recognition you get from other people after you've solved one. I could form an infatuation with a particular problem that would last weeks or months. Now that I have tenure and a wife and two kids, and get to travel the world and study what interests me, I'd like to tell myself a story according to which "all the hard work and sacrifice ultimately paid off." On the other hand, I know people who had fantastic social lives all throughout college and are now also highly successful---an instance of the general phenomenon that there's no justice in the universe. :-D Anyway, if you're interested, I told some more of my story in my Scientific American interview with John Horgan - https://blogs.scientificamerican.com/cross-check/scott-aaronson-answers-every-ridiculously-big-question-i-throw-at-him/ https://blogs.scientificamerican.com/cross-check/scott-aaron...
• mathattack 8y ago
  No question. Just to comment that I enjoy your writing.
• mpodlasin 8y ago
  What would be your advice for older (25+) people who want to get into science? Is it even possible? Or should I just accept that the train has left and focus on something else? Can you develop your math/logic/critical thinking skills at that point? How about if you never excelled at these topics in school? Is hard work enough, or do you think some people are born with these talents?
  • sincerely 8y ago
    Practice makes perfect. Some people are born with the ability to learn some topics faster than others but over time hard work will always bear results. You can learn math/logic/etc the same way any college student learns.
  • WhompingWindows 8y ago
    The brain is able to change well into adulthood ("neuroplasticity"), and that includes mathematical/scientific/abstraction centers. There are plenty of folks who didn't get a great start in STEM, but through hard work and dedication, they pushed through the inherent frustration in learning STEM. While some people might be born with a proclivity for these activities, I wouldn't say any individual could not get into science. For the truly uninitiated, check out Planet Earth, Blue Planet, or Cosmos. For the novices, check out your local astronomy club, ask scientists you know to explain their work to you, and don't be afraid to ask follow-up questions. Get into reading science articles in the popular press, and use those to find links to the real research articles, which will be VERY hard to read for beginners. Feel free to skim those, look at graphs/charts/evidence, and read the abstract/conclusions rather than the intro/methods and the whole thing. Finally, check out some MOOCs or local community classes/continuing education.
    • code_coyote 8y ago
      Good uplifting answer. But it is for what can lead to a hobby, rather than a career. Even certificates from MOOCs won't lead to a job in science, researcher or not.
      • 8y ago
• code_coyote 8y ago
  Hello, As for "careers in science", what can someone later in life (I just turned 60, can't believe it) still do? I have a CS degree from ages ago, and have a scientific mindset (runs in my family, e.g., my sister was a research scientist [mathematician] before retirement). I don't want to retire anytime soon. But I'm unlikely to get into grad school. I can take MOOCs of course, and do. My interest in science tends toward neurology and embodiment.
  • ScottAaronson 8y ago
    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!
  • anonytrary 8y ago
    I our quantum mechanics class, there was an 80 year old woman with a degree in statistics taking the class with us. You can do anything.
• deleted 8y ago
  [deleted]
• slbenfica 8y ago
  Scott what do you think is going to be a successor to the scientific paper/academic journal? What do you think of platforms like distill.pub and Fermat's Library and the impact they might have?
  • ScottAaronson 8y ago
    I'd seen Fermat's Library but haven't used it. I hadn't heard of distill.pub before your comment. Honestly, I don't see scientific papers going away anytime soon. What's the alternative to an individual or group setting out clearly in writing what they discovered, the evidence that it's true, and the background and context to the discovery, putting the writeup where interested people can easily find it, and then taking full responsibility for it, so others can cite and build on the work? As far as I'm concerned, that's all a "scientific paper" means---regardless of whether it appears in a prestigious journal or just the arXiv or somewhere else on the web, and whether it otherwise follows normal academic writing conventions or flouts them. Even an answer on a website like MathOverflow, were it sufficiently well-written and sourced, could as far as I'm concerned be cited as a research paper and given academic credit. But while "papers," for some definition, are probably here to stay, I'm optimistic about deep reform to the system of journals. The first step, of course, should be for academics to shake off the yoke of the truly brazen predatory publishers like Elsevier. Many of us have already pledged never again to review for or submit to those publishers, at least until they fundamentally change their practices. For more about this, see my review of "The Access Principle": https://www.scottaaronson.com/writings/journal.html https://www.scottaaronson.com/writings/journal.html As the next step, we should break free even of society journals, insofar as they put research results behind a paywall. Everything---certainly if it was funded by the taxpayers---should be freely accessible on the web. (In math, CS, and physics, we already put essentially all our papers on the arXiv, where they're freely available, and have been doing that for ~25 years. But the fact that the paywalls even exist still rankles---and other fields, like biology, have yet to catch up.) Ultimately, we might converge on the model of journals as "arXiv overlays": that is, stamps of approval that particular arXiv preprints have been peer-reviewed (which is pretty much the only service that journals now provide anyway). Or maybe we'll even handle peer review in some other way entirely. E.g., people keep trying to experiment with peer reviews being public, but it keeps failing---possibly because, lo and behold, most academics don't want their frank commentary on the importance of each other's work to be made public with their names on it! :-) As it happens, my friend and colleague Michael Nielsen used to work in quantum computing, but now spends full time at Y Combinator thinking about the future of scientific communication. He wrote a book that had lots of interesting ideas for how we could improve things, and surely there are many other good ideas waiting to be proposed, possibly taking advantage of recent or near-future technologies. While the concept of a "paper" (or treatise, or monograph, or note, or other unit of written research) strikes me as mostly determined by the nature of science itself, as far as I'm concerned almost everything else is up for grabs.
• master_yoda_1 8y ago
  What is your suggestion for introductory quantum computing book?
• deleted 8y ago
  [deleted]
• virgil_disgr4ce 8y ago
  Thanks for doing this AMA, Scott. My question is: Could I ever get a job in quantum computing (or related) being 100% completely self-taught?
• soberhoff 8y ago
  How's that quantum supremacy coming along? I heard it was supposed to take a year. And it's been a year. Also, are you planning to write another book at some point?
• beefman 8y ago
  Will the power of 2^72 complex numbers working for me cause gravitational collapse? Has anyone calculated holographic bound limitations on quantum computers?
  • beefman 8y ago
    (can't edit) There's a related comment here[1]. The simpler version of the bound doesn't depend on mass or energy, just surface area (or radius for a Schwarzschild black hole). It seems to me that 2^72 of "storage" is already pushing it, but anyway I don't understand why the number of bits needed to "describe" the state isn't the relevant quantity. IIRC Bekenstein had at least one completely classical derivation of the bound. [1] https://www.scottaaronson.com/blog/?p=2428#comment-786973 https://www.scottaaronson.com/blog/?p=2428#comment-786973
    • beefman 8y ago
      Scott briefly discusses this issue in his book[1], where he cites a paper by Davies[2], which in turn cites one of Scott's talks[3]. I'm not sure about Davies' idea that the holographic bound should be formulated in terms of Kolmorgorov complexity instead of Shannon entropy, but the general question of holographic limitations on quantum systems deserves further study, it seems to me. [1] https://www.amazon.com/dp/0521199565/ https://www.amazon.com/dp/0521199565/ [2] https://arxiv.org/abs/quant-ph/0703041 https://arxiv.org/abs/quant-ph/0703041 [3] https://arxiv.org/abs/quant-ph/0507242 https://arxiv.org/abs/quant-ph/0507242
• mjfl 8y ago
  Do you think modern PhDs overspecialize?
• soberhoff 8y ago
  Do you ever still do exercises? What's the last thing you learned that other people might have learned as students?
  • ScottAaronson 8y ago
    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.
• sixdimensional 8y ago
  Is it possible to simulate the function of a quantum computer in a traditional computing system, even if it is slower, and would doing so be of any value? Do you know what the Google Bristlecone quantum processor is? Is it a "real" or simulated quantum computer? Do you think quantum computers (or perhaps alternate computing paradigms like trinary) are better at fuzzy problems than traditional binary systems?
• angel_j 8y ago
  Is anybody attempting to build Quantum Computers that use light as the medium?
• EtherTyper 8y ago
  Will non-linear quantum computers ever be possible? If so, how would they be made, and what would programming them be like? Do we still model non-linear states with vectors and transformations with unitary matrices?
  • ScottAaronson 8y ago
    If you mean, quantum computers that would exploit a nonlinear term in the Schrödinger equation to solve NP-complete and even harder problems in polynomial time (as studied by Abrams and Lloyd in 1998), then the central problem is that I don’t believe such a nonlinear term exists. Experimental searches have put more and more severe upper bounds on its size, if it did exist. But the bigger problem is that such a term would completely break the structure of quantum mechanics, in even more “basic” ways than by making NP-complete problems easy. For example, it would genetically lead to faster-than-light communication and to violations of the uncertainty principle. So while it’s interesting to think about, and even worth searching for just in case, it almost certainly belongs to the category of “what if?” physics.
  • jey 8y ago
    What does "linear" mean to you? Integration is linear[1]. The Hilbert space of all the functions you care about is linear[2]. Life is locally linear[3]. So maybe "non-linear" is just a red herring. 1. https://en.wikipedia.org/wiki/Linearity_of_integration https://en.wikipedia.org/wiki/Linearity_of_integration 2. Not really but close enough. 3. I don't know what I mean either, but https://en.wikipedia.org/wiki/Linear_time-invariant_theory https://en.wikipedia.org/wiki/Linear_time-invariant_theory is interesting anyway.
    • EtherTyper 8y ago
      I mean quantum computers that harness the NLSE in their computations somehow.
      • jey 8y ago
        Interesting. That's way more physics than I know. :)
• Nokinside 8y ago
  What kind of computer architectures are realistic or possible with quantum computers? You can't have quantum von Neumann computer or can you? Are realistic quantum computers always going to be quantum circuits?
• hirundo 8y ago
  Hi Scott, I'm astounded by the accomplishment of AlphaZero in quickly becoming a chess master without chess specific programming. Could a program of the same kind be adapted to infer or deduce the rules of chess from a large set of valid games? Or is that a different kind of problem? If so, could it be adapted to learn the rules when we're not clear on them either, like those for the games of love or politics?
  • ScottAaronson 8y ago
    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 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. :-)
    • YeGoblynQueenne 8y ago
      >> 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). They didn't induce the rules of chess! What they did was learn an evaluation function for chess moves, from scratch, i.e. without giving it the rules or any hand-crafted features. So they learned a classifier for good/bad board states, which was later used in an alpha-beta minimax search. However, the classifier didn't learn the rules of the game, only a mapping from board positions to labels, good/bad. This is not made explicit in the text, but minimax typically has a rule-base to generate moves as successor states for the search; so the rules of the game were hand-crafted, but did not contribute to the learning of the evaluation function. It's extremely hard to induce a set of rules with neural nets, or indeed any statistical machine learning algorithm. I mean, imagine representing the rules of chess as a function; let alone trying to learn that function from data. (Full disclosure: I study algorithms that learn rules from data; they're not neural nets).
• gb22 8y ago
  Hi Scott 1. What do you think is the potential for emergence of a third computing model, apart from classical and quantum, which is sufficiently different in its fundamental computing paradigm from these? Do you believe biological substrates offer opportunity for computing which classical/QC cannot replicate? 2. If we achieve quantum supremacy, who do you think will be the biggest winners and losers, in terms of professional skill set and in terms of business models for private companies? Will physicists become much more influential if their ability to model and deliver new evidence (and thereby theory) and convert them into commercial products is advanced? 3. Would it be fair to say that d-wave machine is more an analog computer than a quantum computer; And do you think there is possibly a class of computing problems that might be better/more efficiently solved by analog computers than digital, and without requiring QC?
  • ScottAaronson 8y ago
    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 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.
• Zophike1 8y ago
  For those wanting to undergraduate research basically in REU in QIT what's your advice for them?,what do they need to take on such an endeavor?,what are researchers looking for in prospective students?, and finally would a researcher take on a student who hasn't had much in terms of coursework but has been teaching themselves ?
• deveac 8y ago
  Hi Scott. I'd love your thoughts on quantum encryption's viability vs. supremacy, and how those two concepts might unfold in relation to each other.
• logeek 8y ago
  What are the prime factors of this number? 1847699703211741474306835620200164403018549 3386634101714717857749106516967111612498593 3768430543574458561606154457179405222971773 2524660960646946071249623720442022269756756 6873784275623895087646784409332851574965788 4341508847552829818672645133986336493190808 4671990431874381283363502795470282653297802 9349161558118810498449083195450098483937752 2725705257859194499387007369575568843693381 2779613089230392569695253261620823676490316 036551371447913932347169566988069
  • Koshkin 8y ago
    This number is prime.
    • schoen 8y ago
      I doubt it. >>> gmpy.is_prime(1847699703211741474306835620200164403018549338663410171471785774910651696711161249859337684305435744585616061544571794052229717732524660960646946071249623720442022269756756687378427562389508764678440933285157496578843415088475528298186726451339863364931908084671990431874381283363502795470282653297802934916155811881049844908319545009848393775227257052578591944993870073695755688436933812779613089230392569695253261620823676490316036551371447913932347169566988069) 0
  • sliken 8y ago
    Doesn't everyone have a quantum computer yet? 2^2, 47, 8121293, 1210175511547330273998081353233737902915153751853051779316281348898985913176974726270161034273517189585147616550512413067820157568220278077881421197895369014359432790978536356806591021
• jcmoscon 8y ago
  Do you believe in the simulation hypothesis?
  • gooseus 8y ago
    So I've been thinking about this simulation thing a bunch lately and while I'm curious about Scott's answer here, I'll preemptively post my followup question in case anyone else has any ideas or he wants to weigh in here: Can you use the premises of the Simulation Argument to make similar statements regarding the availability/capability of sufficiently advanced technology that would potentially impact our coming into existence? For instance, directed panspermia. Would at least one of the following have to be true? 1. The human species is very likely to go extinct before we can develop the capability to successfully seed the galaxy with R/DNA-based life and spawn another biosphere. 2. Any sufficiently advanced civilization is unlikely to attempt to seed other worlds with the basic building blocks of their living system so as to initiate other biospheres. 3. Our biosphere was almost certainly initiated by way of directed panspermia from another sufficiently advanced R/DNA-based civilization that has existed. For this argument, imo, (1) seems less likely than in the simulation argument since I'd think we're closer to being able to send out small ships with hibernating microscopic life than we are to building Universe-sized simulations. (2) also seems less likely since the cost/benefit analysis of seeding other worlds seems much higher to me than building and maintaining a universe-sized simulation. So for (3) if we assume abiogenesis started a civilization which decided to start seeding other planets which then have a chance of leading to other seeding civilizations, then we'd need to compare the likelihood of seeded life vs abiogenesis to determine how likely it is that we are an abiogenesis civilization vs a seeded civilization.
• robertjoec 8y ago
  What are some of the most interesting research problems in your field? How promising would you say topological quantum computers are to allowing for fault-tolerant systems?
• tomlemon 8y ago
  In your mind what is the solution to the "Dice Room" paradox you describe in "PHYS771 Lecture 17: Fun With the Anthropic Principle" (https://www.scottaaronson.com/democritus/lec17.html https://www.scottaaronson.com/democritus/lec17.html)? I take it you don't believe in the SIA? Is this paradox irreducible? Is the world going to end soon?
  • ScottAaronson 8y ago
    There are at least two plausible solutions to the Dice Room, depending on whether you adopt SSA or SIA. I wish I knew something more insightful to say about it than that, but I still don’t know the right way to think about indexical probabilities. Do you?
• kingofking 8y ago
  ELI5 quantum computing since I’m a total noob at it.
• akeck 8y ago
  I think you've written that QM is in part probability math using complex numbers. I've also read that human decision making doesn't map well to classical probability. Do you know if QM/"complex probability" has been used to build better models of human decision making?
  • ScottAaronson 8y ago
    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"! :-)
• ahelwer 8y ago
  Hey, Scott! Love your book, Quantum Computing Since Democritus. There is one section which confused me, in the Quantum chapter (https://www.scottaaronson.com/democritus/lec9.html https://www.scottaaronson.com/democritus/lec9.html). I have two questions: 1) You say applying the unitary operation is the quantum analogue of "taking a coin and flipping it" - what do you mean by this? Could we think of, for example, a pair of slits as applying this transformation on a photon qbit being sent through them, so it's now in superposition with regard to which slit it went through? 2) What does it mean when you say there are two paths to |1>? I understand this section is getting at the physical underpinnings of this mathematical model, but I can't quite wrap my head around how there are two "paths". My mind is stuck thinking of the Bloch sphere as a state machine you can deterministically hop around by applying unitary transformations. P.S. I did a talk called Quantum Computing for Computer Science which covers everything up to the one-bit Deutsch Oracle problem in 1.5 hours; I found that presenting quantum algorithms as running on a "unit circle state machine" (basically 2d Bloch sphere by restricting states to real numbers) was a very effective way to explain the subject to software engineers! (https://www.youtube.com/watch?v=F_Riqjdh2oM https://www.youtube.com/watch?v=F_Riqjdh2oM)
  • ScottAaronson 8y ago
    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.
• deepnotderp 8y ago
  What do you think about the silicon photonic approach to quantum computing? In particular, thoughts on scalability? Photonic qubits are unique wrt decoherence, no?
• jkabrg 8y ago
  Do you think there's any hope of finding a practical algorithm for USTON that runs in logarithmic space? Reingold's algorithm needs O(n^64^32) time(!!!)
• wokawoka 8y ago
  Can you describe how different the operating system would be from the traditional operating system we use today for quantum computing? Broad question but any specifics you can answer....
  • Koshkin 8y ago
    More importantly, what would quantum web browsing look like.
• vslira 8y ago
  What would be the best way to understand the relation between amplitudes and probabilities in the “non-quantum” world? In your NYT piece you say that it would be weird to give a “sq(-1) probability of rain tomorrow”, but are there relatable uses or cases for amplitudes outside of quantum physics?
  • ScottAaronson 8y ago
    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 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 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).
• jd007 8y ago
  Hi Scott, This may be an ill-formed question, but it's something I've been thinking about for a long time: Do you think the human mind is equivalent to Turing machines, or somehow above it? Assuming we have an infinite tape/memory and time.
  • ScottAaronson 8y ago
    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 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?
• erostrate 8y ago
  Hi Scott There are non-quantum physical systems that exhibits positive and negative amplitudes and interference. Can I factor large numbers by throwing rocks in a lake and measuring the water height at the right place? Why not?
  • sethrin 8y ago
    Lakes don't have the required quantum properties, I think, but this might work: http://math.mit.edu/~bush/?page_id=484 http://math.mit.edu/~bush/?page_id=484
  • mindcrime 8y ago
    Not Scott, and this has nothing to do with interference, but it is possible to "calculate" certain things using physical phenomenon like water levels. It's basically a variation of "analog computing". https://en.wikipedia.org/wiki/Analog_computer https://en.wikipedia.org/wiki/Analog_computer An analog computer or analogue computer is a form of computer that uses the continuously changeable aspects of physical phenomena such as electrical, mechanical, or hydraulic quantities to model the problem being solved I don't think it has much to do with QC, but analog computing is interesting in its own right.
    • erostrate 8y ago
      Thanks! This is indeed related and part of my inspiration for this question. Some other interesting references: - The waterfall argument in paragraph 6 of the mind-boggling "Why Philosophers Should Care About Computational Complexity". https://www.scottaaronson.com/papers/philos.pdf https://www.scottaaronson.com/papers/philos.pdf - "NP-complete Problems and Physical Reality" https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf
    • brett40324 8y ago
      So, basically, yes. Particularly if you consider most concepts in mechanical engineering. What you're talking about is the real implementation of what we call physics, just working as expected, automagically.
• mudil 8y ago
  Hi Scott, David Deutsch, in his book "The Fabric of Reality", gives example of a problem that is presumably easily solvable by the quantum computer. On the other hand, he explains that the total number of particles in the universe is smaller than number of computations that will take place. The question that he poses is where the problem was actually solved? His answer is that there parallel universes, and the computation is performed in these universes. He also stipulates that the "weird" quantum behavior of particles, such as spooky action at a distance, all could be explained by the multiverse. What is your opinion about the multiverse and potential of quantum computers to solve quantum physics problems?
  • mudil 8y ago
    I found the relevant passage. "Logically, the possibility of complex quantum computations adds nothing to a case [for the Many Worlds Interpretation] that is already unanswerable. But it does add psychological impact. With Shor’s algorithm, the argument has been writ very large. To those who still cling to a single-universe world-view, I issue this challenge: explain how Shor’s algorithm works. I do not merely mean predict that it will work, which is merely a matter of solving a few uncontroversial equations. I mean provide an explanation. When Shor’s algorithm has factorized a number, using 10^500 or so times the computational resources that can be seen to be present, where was the number factorized? There are only about 10^80 atoms in the entire visible universe, an utterly minuscule number compared with 10^500. So if the visible universe were the extent of physical reality, physical reality would not even remotely contain the resources required to factorize such a large number. Who did factorize it, then? How, and where, was the computation performed?"
• ryao 8y ago
  What books do you recommend on those topics?
  • ScottAaronson 8y ago
    Which topics?
• noobermin 8y ago
  Hey Scott, thanks for doing this. What do you think of the Copenhagen Interpretation especially in light of the delayed choice quantum eraser experiment[0]? I know interpretation of QM is something actual working scientists try to avoid (I know I do such for my little corner of physics) but given how much interpretation informs intuition it's worth considering once in a while. [0] https://en.wikipedia.org/wiki/Delayed_choice_quantum_eraser https://en.wikipedia.org/wiki/Delayed_choice_quantum_eraser
  • ScottAaronson 8y ago
    I confess I get annoyed when people make arguments about the interpretation of quantum mechanics using complicated thought experiments involving lasers and mirrors. Why not just talk about it in the modern way, in terms of qubits and states? :-) For some of my recent thoughts about interpretation of QM, see this blog post, and especially the discussion in the comments section: https://www.scottaaronson.com/blog/?p=3628 https://www.scottaaronson.com/blog/?p=3628
    • noobermin 8y ago
      I'm a laser physicist, so I think exclusively in terms of lasers and mirrors, but I get your point.
• vikR0001 8y ago
  Given that observing the state of a qubit changes it, and (I guess) that changes all entangled qubits, what methodology is used to read out the result of a quantum computer's calculation?
  • ScottAaronson 8y ago
    When the quantum computation is finished, you suck it up and you measure. The entire point of the quantum algorithm was to set things up in such a way that, even as the measurement destroys the superposition state, the right answer is observed with a high probability (since you used constructive and destructive interference to boost its amplitude, while suppressing the amplitudes of the wrong answers).
• henryaj 8y ago
  Do you have any thoughts to offer on the "culture wars", especially the way you were treated by the online mob when you wrote about your personal struggle with your sexual identity[0,1]? 0. http://slatestarcodex.com/2015/01/01/untitled/ http://slatestarcodex.com/2015/01/01/untitled/ 1. https://www.scottaaronson.com/blog/?p=2091#comment-326664 https://www.scottaaronson.com/blog/?p=2091#comment-326664
  • ScottAaronson 8y ago
    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-attacked-online 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-plain-sight/ 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-war-bubbles/ 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.
    • henryaj 8y ago
      That Quora post is wonderful - thanks for sharing. Glad you were able to rise above the attacks made on your character :)
• jaddood 8y ago
  Hello! Could you give an overview of the proceedings of your job as a researcher in quantum computing? For instance, how do you start your day job, what do you do during the day (how exactly do you do research,) how do you end your day, etc...
  • ScottAaronson 8y ago
    While I was on sabbatical: 7am - Wake up, eat breakfast, check email, help get daughter ready and walk her to school 9am - Back to sleep 2pm - Wake up again, shower, eat lunch, check email. Possibly coffee with friend or colleague. 4pm - Time to pick daughter up again! 4-6pm - Play with kids, eat more, check email 6-8pm - Read news and social media, get depressed 8-9:30pm - Help get kids ready for bed 9:30pm-4am: NOW it’s time to do some research!!! Tools: pen, paper, sofa, LaTeX editor, and sometimes web browser to look up papers (but this last tool is extremely dangerous and can lead to procrastination) 4am - Collapse Being back in Austin and teaching will severely affect the above hours. But in any case, it’s not like I consciously decided on them, as part of some plan to maximize productivity (!!) - this is just what I fall into when I don’t have other obligations.
• erdevs 8y ago
  I'd just first like to say that I love reading your work. I'm always delighted when I see an update on Shtetl-Optimized and I admire how you are both simultaneously rigorous and funny in your papers and posts. Your PnP survey stands out in my mind as a truly fun and insightful read in particular. Two questions: 1. Any meaningful updates you'd make to the PnP survey today? 2. As a total aside, I'm curious for your thoughts on blockchains. Not specifically proof of work as a BFT system per se, but more broadly curious to what degree you think "trustless" transactions and data processing might or might not be transformative. Apologies in advance if you've recently provided thoughts on either of these topics and I've sadly missed them!
  • ScottAaronson 8y ago
    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 https://www.scottaaronson.com/blog/?p=3861#comment-1768247
    • erdevs 8y ago
      Thanks for the reply! And apologies I didn't realize the autocorrect on my phone turned "PvNP" to "PnP". I'll read up on the recent works you mentioned here. Appreciate the link to your comment on Blockchain technology as well. If you still have time to answer questions.. is there any recent work in the cryptographic or blockchain space you see as standout? I haven't referred recently to any citations or updates, but found Ben-Sasson, Bentov, Horesh and Riabzev's recent work (https://eprint.iacr.org/2018/046 https://eprint.iacr.org/2018/046) on ZK-STARKs intriguing.
• amelius 8y ago
  Hi Scott, Of the two main possible applications of QC, i.e. computational chemistry and cryptography, it's often just cryptography that is mentioned in the media. The Wikipedia entry on QC, in its "Potential" section, discusses mostly cryptography, while only two sentences are dedicated to chemistry. Cryptography is also used as the toy-problem for QC prototypes, i.e. factoring integers. However, as I understand it, QC-for-cryptography will break existing techniques, and will not (from an application standpoint) bring anything new to the table. Therefore, my question: does QC have a PR-problem?
  • ScottAaronson 8y ago
    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.
• ttctciyf 8y ago
  Is there a model of a computation that stands to quantum computation in the same way a universal Turing machine stands to classical computers, or is the UTM already enough?
  • ScottAaronson 8y ago
    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.
    • ttctciyf 8y ago
      Thanks, and thanks for spending a big chunk of your time here!
• bloone 8y ago
  Hey there Scott! I just wanted to say I wrote a student-paper on quantum computational complexity last year and I felt like your papers made up almost 90% of my references. Thank you for making my learning about the subject possible! On to my question: I'm working on a capstone project right now that's using quantum computing to create a small video-game. I'm using the 5-qubit quantum experience from IBM and I was wondering if you had any cool ideas/suggestions for small game experiences that could use actual quantum computing resources to teach people about the properties of quantum mechanics? Thanks again for all your work in understanding the quantum world, Scott.
  • ScottAaronson 8y ago
    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/ 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?
    • bloone 8y ago
      That game is really quite cool, and certainly in the same vein as what I was thinking of doing - thanks so much for the suggestion (I've already spent too much time solving puzzles)! I am looking at using something like the Quantum Experience for two reasons: 1) Because giving people real quantum computing results is really cool, and 2) Because it's my capstone project and the work has to have a certain threshold of technical exploration. That being said, I'm not well-versed in alternatives that could maybe just simulate quantum properties without having to go through an actual quantum computer. I have been looking into creating a small quantum neural net (with either real or simulated qubits) to show how that differs from a neural network running on classical computing. I've been trying to work that into a game idea but I'd be lying if I said I've come up with anything compelling yet. If you got any cool game mechanics/ideas you think quantum computing resources would lend themselves to then I'm all ears!
• deleted 8y ago
  [deleted]
• distorted_torus 8y ago
  Hi Scott, I am interested in attending graduate school for a PhD in Computer Science and am beginning to think about the areas of research I'd like to get involved in. Below are a few sporadic questions. 1) I really like mathematics, so what are the foundational areas of mathematics in quantum computing? What areas of mathematics should researchers know very well? 2) Are there any exciting connections between machine learning and quantum computing that you know about? 3) What is a problem that really excites you about the field at this very moment? 4) Can you direct me to good books, papers, or resources for the absolute beginner in quantum computing?
• SurfaceCode 8y ago
  Scott, Do you think it's a good idea that all the teams working on quantum computing have put their money on the surface code? What are your thoughts? Do you believe that we are putting all our eggs in one basket?
  • ScottAaronson 8y ago
    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.