ScottAaronson

Thanks! In theoretical computer science as a whole, authorship is only for those who made a direct intellectual contribution. It’s one of the things I like best about the culture of our field.

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.

Pretty much any intro to QC (and in particular, any of the intros I've written, and linked to elsewhere on this thread) will make the point about Hilbert space (that's what it's called) having a dimension that grows exponentially with the number of particles in your system. This is because every possible classical configuration of the system is its own orthogonal "direction" in Hilbert space, and the full state can be an arbitrary superposition (i.e., complex linear combination) of those directions.

Results from inductive inference show that you’re not going to converge in general. In the specific case of chess, however, my point was that we, because we know the complete list of rules, could plausibly look in from the outside and say after some finite point: “ah yes, now the system has gotten all of them.”

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.

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

if you’re just looking for some interesting reading material.

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.

Short answer: not in any obvious way!

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

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

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

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.

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

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.

Honestly, almost all of the technical innovation in this breakthrough had to do with classical circuit complexity—-once you know my Forrelation problem, there’s almost no further input you need about quantum computation. (Well, a slight amount, since Raz and Tal had to modify Forrelation a bit to get their proof to go through.)

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

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

or, of course, their paper.

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

Right, but even if chess were infinite, we could still imagine an algorithm that would output the smallest explicit rule set that was consistent with all the games it had seen so far, and that would quickly (though how quickly?) converge on the correct rules in the case of chess, even if it would be up against undecidability when trying to do the same thing for a completely arbitrary game.

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.

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.

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.

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.

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.

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?

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.

I hope in 5-10 years, but really I don’t know, and no one else does either.

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

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

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

No, it's an unknown known. :-)

No, I wouldn't recommend that either. :-)

On further thought, we should distinguish two problems:

(1) "Induce" the rules, in the sense that after training on millions of played games, you now have a neural net or whatever that plays mostly or entirely according to the rules even though it can't articulate them.

(2) Output an explicit description of the rules.

I could easily believe that (2) is beyond the current abilities of AI, even if it turns out that (1) is doable.

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/blog/?p=208

in addition to the resources that have been linked to elsewhere on this thread.

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

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.

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