## “THE TALK”: My quantum computing cartoon with Zach Weinersmith

OK, *here’s* the big entrée that I promised you yesterday:

**“THE TALK”: My joint cartoon about quantum comgputing with Zach Weinersmith of SMBC Comics.**

Just to whet your appetite:

In case you’re wondering how this came about: after our mutual friend Sean Carroll introduced me and Zach for a different reason, the idea of a joint quantum computing comic just seemed too good to pass up. The basic premise—“The Talk”—was all Zach. I dutifully drafted some dialogue for him, which he then improved and illustrated. I.e., he did almost all the work (despite having a newborn competing for his attention!). Still, it was an honor for me to collaborate with one of the great visual artists of our time, and I hope you like the result. Beyond that, I’ll let the work speak for itself.

Comment #1 December 14th, 2016 at 9:10 am

Wait… does this mean you’re NOT joining the President-elect’s Cabinet!? (…you were my last hope)

Comment #2 December 14th, 2016 at 9:15 am

Great. Amazing. Thank you.

Two of my favorite creators coming together, and it didn’t disappoint.

For people who, willfully or not, misunderstand my work and are open to reforming their ways I have a list of references of increasing mathematical precision that I send to help set them straight. This has now become first on that list.

Comment #3 December 14th, 2016 at 9:30 am

> It’s not the size that matters. It’s the rotation through complex vector space

Other ideas in this comic are familiar to me, but not this one. Any reference explaining this ?

Comment #4 December 14th, 2016 at 9:43 am

Hwold #3: In principle, according to QM, you can see quantum interference with a physical system of any size, as long as it’s sufficiently isolated from its environment (so that it rotates unitarily through complex vector space rather than collapsing). As for the saying we were riffing off—“it’s not the size that matters, it’s the motion through the ocean”—maybe I should let someone explain that who has less of an academic reputation to uphold? 😉

Comment #5 December 14th, 2016 at 9:55 am

Zach has a link to your blog at the bottom of the comic, but it links to the blog itself (www.scottaaronson.com/blog) rather than to this particular blog post (www.scottaaronson.com/blog/?p=3058). You should tell him to change that — otherwise a month from now it will be hard to tell what the comic and your blog have to do with each other.

Comment #6 December 14th, 2016 at 9:57 am

I got all the way to the bottom of the SMBC thinking I should possibly point it out to you before I saw your name on it. It just seemed so much like what you’ve been saying!

It’s wonderful!

Comment #7 December 14th, 2016 at 10:01 am

As a journalist infecting young minds with filthy quantum articles in magazines, this got a laugh out of me. But the fact that the comic is so long means it can’t quite sustain the joke, which handily illustrates the point of coming up with these incorrect approximations – sometimes you just don’t have room to be right!

Comment #8 December 14th, 2016 at 10:32 am

Hilarious and enlightening at the same time. Is the last box a jab at Penrose?

Comment #9 December 14th, 2016 at 11:15 am

I just saw this independently of your blog. I came here to see what your take on it was. My thoughts when I saw this blog entry:

“Okay, that makes sense I guess.”

Comment #10 December 14th, 2016 at 11:17 am

Aaron,

Would you mind posting that list of references?

Comment #11 December 14th, 2016 at 12:35 pm

Jack #10: In the history of this blog, that might be the first time anyone who addressed a comment to “Aaron” actually meant “Aaron,” and wasn’t just transposing my last name with my first. 🙂

Comment #12 December 14th, 2016 at 1:16 pm

Very funny and elightening cartoon. I hope it makes its rounds in the popular presses.

But I wonder what would have happened if the kid started asking other questions like, “But I heard complex numbers could just be represented by two ordinary numbers?” or “What do you mean by ‘isolated’?” …Or something else that might have given the mom a little more pause(I’m not sure if those questions would actually do that, as this mom seems pretty smart and quick to respond with enlightening answers).

Scott, what are the hard questions that this kid could have asked his Mom where she would not have been able to give him an answer that he’d be satisfied with?

Comment #13 December 14th, 2016 at 1:42 pm

Jon #12: Those are fine questions, to which I think the mom could’ve given perfectly satisfying answers, but sheesh! People are complaining on Twitter (and above) that the cartoon is already too long as it is.

PS. The answer to the first question is, “yes, a complex number is an ordered pair of reals, what of it?” 🙂

To the second: to define “isolated system,” you should first define a tensor product Hilbert space; then a system is isolated if it lives in one tensor factor and its Hamiltonian acts only on that factor.

Comment #14 December 14th, 2016 at 2:49 pm

I was about to send this to you.

Comment #15 December 14th, 2016 at 4:09 pm

[…] Weinersmith — 62 panels³ of deep-dive on quantum computing (with a writing assist from Scott Aaronson), which is a pretty damn good primer on an entire field of theoretical work, in the form of a […]

Comment #16 December 14th, 2016 at 4:18 pm

Another aspect of Quantum Computation that’s difficult to relate to, particularly for software engineers, is how quantum algorithms are developed.

In the classical world, if you need to fill a cup with water, you break it down into a set of operations and address each one separately. You know, first you get the water, then you get the cup… In the worst case you have to get the cup and the water concurrently.

In the quantum world it’s difficult to break things down into steps. It’s like you’re given an explosive… and you have to figure out how to blow up the kitchen such that you get a cup full of water among the debris.

I know there are quantum circuit simulators and these are useful for visualizing the operation of a QC but i can’t imagine building a useful quantum algorithm that way. I guess that’s why it’s so important to have an intuitive understanding of how QCs work? And QM is anything but intuitive.

Sure you can take preexisting quantum sub-routines and compose them in a purely classical way, but that’s not a

realquantum algorithm.When i’ve thought about it, it’s usually something like this. I have a problem X, could i solve X using a QC? Well, i could make the wrong answers interfere… Let me work backwards from there and hope that at some point i’ll make a creative leap that gets us the desired interference.

And it doesn’t work because, first and foremost, you can’t actually solve X using interference.

Comment #17 December 14th, 2016 at 4:27 pm

Somewhat off-topic request: can you answer my question at English Language SE?

Comment #18 December 14th, 2016 at 4:52 pm

Ahh, what a nerdgasm.

Comment #19 December 14th, 2016 at 4:57 pm

You might want to update the link to point to http://www.smbc-comics.com/comic/the-talk-4

Currently you point to the home page, so your link will break when a new comic is published, if I’m not mistaken.

Comment #20 December 14th, 2016 at 4:58 pm

Job #16: It’s true that inventing entirely new quantum algorithms is hard, but inventing entirely new classical algorithms is also hard! And you can develop an intuition for QC the same way you’d develop an intuition for anything else. There are certain building blocks—Hadamarding, the Fourier transform, amplitude amplification, the swap test…—that you know to try, and if they don’t work then you look for something else, or give up. It’s hard only in the same ways that any math is hard.

Comment #21 December 14th, 2016 at 6:25 pm

John B #5 and Roy Badami #19: I think linking to the top of Shtetl-Optimized is correct. The blog almost always talks about quantum computing, and the misconceptions about how quantum computing come up so often that it’s even in the tagline and the previous tagline.

Comment #22 December 14th, 2016 at 7:12 pm

Roy #19: Thanks—fixed! Yes, I’d noticed that issue, but as it happened, I was giving a colloquium in Lyon a mere 10 minutes after the cartoon went up (fittingly, my colloquium about quantum computing and why it’s not just exponential parallelism…). So, I needed to prepare my post before I knew exactly what Zach’s URL would be, and then be ready to upload the post from my mobile phone at the touch of a button.

Now that I write that, I realize I could’ve just

askedZach for the URL, but that didn’t occur to me at the time. 🙂Comment #23 December 14th, 2016 at 9:48 pm

Scott, what are the hard questions that this kid could have asked his Mom where she would not have been able to give him an answer that he’d be satisfied with?Well, there’s this really great book called Quantum Computing Since Democritus…

Comment #24 December 14th, 2016 at 10:02 pm

Awesome comic!!!

Can we expect next version of Quantum Computing Since Democritus to have more comics?

Matt #23: I think the best question would be from Scott’s TED talk.

Comment #25 December 14th, 2016 at 11:16 pm

Scott: Is tunneling, Heisenberg uncertainty, and action at a distance really consequences of complex amplitudes? I would think to predict tunneling you’d need to know Schrodinger’s equation, to understand the uncertainty principle you need to know [x,p], and to get action at a distance you need entanglement. Can’t all those things exist independently of complex amplitudes?

Comment #26 December 14th, 2016 at 11:33 pm

I liked the last frame in the cartoon where it takes a swipe at the connection between quantum mechanics and consciousness.

Lubos Motl seems – as best as I can figure out – to be saying that a conscious observer is needed for quantum wave collapse. I tried to point out that there can be no difference between a mindless robot observing a quantum particle and a conscious scientist observing it. There can be no experiment that differentiates between the two.

To be fair I’m not really sure what his position is since he banned me for disagreeing without discussing it.

I like the idea of a connection between quantum mechanics and consciousness. But if that connection exists it is not easy or obvious and nobody has suggested an experiment that shows its usefulness.

Comment #27 December 15th, 2016 at 12:37 am

Scott, this is fantastic.

Might I point to what I suspect is an error, and is at least an ambiguity, in the comic? This ambiguity concerns logic, and not quantum physics.

Refer Mom’s statement: Superposition doesn’t mean “AND”, but it also doesn’t mean “OR”.

The ambiguity lies in the meaning of OR.

As you’re aware, in plain English, OR can mean one of 2 different things:

– Either this, or that, or both. Equivalent to the OR logic gate. Example: “I wish I were richer or more good looking”

– Either this, or that, but not both. Equivalent to the XOR logic gate. Example: “Give me liberty, or give me death”

In the comic, Mom means XOR, but it appears, at least to me, that she is likely “intending” to use AND and OR not as conjunctions from plain English, but as logic gates from Computer Science, simply because she is being precise, and because she is talking about computing, and also because AND and OR are written in bold in that panel.

Of course, the meaning of what she’s trying to say is still clear, but this was bothering me and I thought I’d point it out.

Comment #28 December 15th, 2016 at 2:58 am

Jahan #25:

Is tunneling, Heisenberg uncertainty, and action at a distance really consequences of complex amplitudes?

Well, not specifically of the amplitudes being

complex—almost every phenomenon in QM would still be there with positive and negativerealamplitudes—but of the basic structure of QM, involving linearly-evolving amplitudes whose 2-norm is conserved, I claim yes.Entanglement is just something that unavoidably pops out when you have superposition and also a tensor product structure on your Hilbert space. It doesn’t need to be added as a separate axiom. And yes, things like the Bell inequality can be explicitly understood as interference effects.

It’s true that the usual formulation of the uncertainty principle involves a peculiarity of the Schrödinger equation—namely, that position and momentum are conjugate observables—but I prefer the more abstract formulation, which applies to

anypair of conjugate observables, in Hilbert spaces ofanydimension (the finite case probably being the clearest). And in the latter case, yes, it’s just a logical consequence of the basic axioms of QM, the ones that talk about amplitudes.Finally, tunneling can be seen even in discrete quantum walks and the adiabatic algorithm. And yes, for the last 15 years, it’s been pretty clear that even if these phenomena hadn’t been known from nature, and we only knew the abstract axioms of QM and the basic ideas of computer science, we would’ve eventually rediscovered the phenomena anyway, just for internal quantum algorithms reasons.

Comment #29 December 15th, 2016 at 3:02 am

Niraj #27: Not sure if I understand the error. Had the OR/XOR distinction been relevant given the context, the mom could’ve added, “superposition doesn’t mean AND,

andit doesn’t mean OR,andit doesn’t mean XOR either.” 🙂Comment #30 December 15th, 2016 at 3:12 am

ppnl #26: The magazine headlines were all Zach’s, but I enjoyed and approved them.

For what it’s worth,

Ididn’t mean to take a swipe at the idea that there’s some sort of interesting connection between the conceptual problems of quantum mechanics and those of consciousness—an idea that, even if it’s wrong, is obviously notobviouslywrong. (See, e.g., my 85-page Ghost in the Quantum Turing Machine essay, which takes the idea very seriously even while rejecting many variants of it.)On the other hand, even if (like me) you think that consciousness

doessometimes unavoidably come up in discussions about the foundations of QM, and vice versa, it’s still undeniable that the vague, mangled idea of a connection has by now inspired generations of pure cringe-inducing woo, by hucksters who couldn’t correctly explain the first thing about QM but just find its mysteriousness convenient. And I’m happy to poke fun at that.Comment #31 December 15th, 2016 at 3:37 am

Asolutely brilliant Scott – cystal clear, simple and entertaining- ALL profound insights should look exactly like this when correctly stated – if they don’t, the theorist is doing it wrong.

Now, can you make comics for ‘consciousness’, ‘free-will’ and ‘time’ which brilliantly cut through to clear simple explanations of these things in the same way? 😉

After years of thinking about these issues, my mind seems to have undergone a ‘phase shift’ and I suddenly now feel I’m taking huge chunks out of the backsides of these age-old problems! 😀

Here’s the core of my current thinking, hopefully it can provide inspiration towards new comics:

*The universe is a self-modeling language, and there are 3 levels of recursion: Information>Fields>Cognition. Each level has it’s own ‘arrow of time’.

*Cognitive systems form symbolic representations of causal processes in the form of ‘narratives’. But the key point that’s been missed is that the *representations* (models) of causality *are themselves a form of causality*! (A higher-order causality!)

*Normally the representation of a thing does not have the characteristics of the thing. For instance, the word ‘Green’ is not itself colored green. But the one exception is time! THE *REPRESENTATION* OF TIME *IS* ITSELF A FORM OF TIME!

Comment #32 December 15th, 2016 at 4:07 am

mjgeddes #31: I have, of course, spent a fair amount of time trying to set out my own thoughts about consciousness, free will, and the other ancient unanswerables—and as it happens, Zach has often cartooned about those topics as well. But the difference from quantum computing is that those topics have much less of an “uncontroversial core of knowledge”—i.e., stuff that’s intricate and non-obvious, but still basically assented to by every serious worker in the field, because it corresponds to math or to observable reality. So for that reason, they call for a very different kind of comic.

Comment #33 December 15th, 2016 at 6:46 am

I follow Zach Weinersmith and Professor Aaronson and and enjoy all their posts.

I also follow Luboš Motl “Reference Frame” and like the physics and am baffled by the politics.

So the phrase “Damned with faint praise” (https://en.wikipedia.org/wiki/Damning_with_faint_praise) came to mind when I read Dr Motl’s post.

http://motls.blogspot.com/2016/12/i-approve-message-of-aaronsons-qm-comic.html

Comment #34 December 15th, 2016 at 7:49 am

jonas #21 — If the comic links to a particular blog post, then it is in fact linking to the blog. Anyone who finds the post finds the entire blog. The reverse isn’t true; six months from now someone reading the comic will know that Scott Aaronson was involved, but they won’t know that there was a particular blog post associated with the comic, and even if they guess that there might have been, they will have a difficult time finding it. And since Zach’s comics aren’t dated, finding this post will become harder and harder as time passes, since they’ll need to search more and more of the blog.

The same argument goes the other way: six months from now its going to be just as hard for someone reading this blog post to find the particular comic (unless they read comment #19 of course!). Either way, I think it’s better to provide full information — doing otherwise just offends my nerdish OCD.

Comment #35 December 15th, 2016 at 8:03 am

Scott #28,

Are you sure that for real amplitudes just the 1-norm won’t be enough? … Ummm… But wait… Energy of a wave is proportional to the *square* of its amplitude… So, yes, if measurements via eigen-states were still to be necessary, and were still to depend on energy, then it would still have be a 2-norm. … So, yes, you are right, in that sense.

It’s not really the fact of linear operators (i.e. linearly evolving amplitudes) which gives QM its peculiar character. The peculiarity of QM lies in the necessity of measurement, and the collapse postulate which an act of measurement involves. In other words, the peculiarity of QM lies in the “quantum jumps.” Schrodinger was unhappy only with this part of QM; and it is only this part that makes QM as we know it, incomplete.

Yes, entanglement is not a requirement of instantaneous action at a distance (IAD). IAD in QM (as in classical diffusion) comes about only because the Fourier theory itself has IAD built into it. And the Fourier theory comes in because measurements involve eigenstates.

No, QM (whether in the simplest Schrodinger picture or in the more abstract formalism) is not all that peculiar in having conjugate variables. In fact, conjugate variables, I think, aren’t brought in even by the Fourier theory. I men to say, there *are* conjugate variables also in *classical* mechanics. For instance, p and V are conjugate in thermodynamics. The Poisson bracket *was* invented by, well, Poisson—an 18th/19th century guy. …Hmmm… I am not as clear whether there is any *necessary* connection between the Poisson brackets and the Fourier theory. I think not. The Poisson brackets, I think, spring from the energetics program of classical physics, i.e. the Lagrangian mechanics. So, waves, harmonic analysis, shouldn’t really be necessary for the theory to lead to the conjugate variables. (But I have to think a bit more about it, anyway.)

Interesting question, and interesting answer…

–Ajit

[E&OE]

Comment #36 December 15th, 2016 at 8:18 am

ppnl #26, and esp., Scott #30:

If all that you want to do is to introduce consciousness in a theory of physics, then you wouldn’t need the specific development of QM for that.

A classical physics description of the act of catching a ball in his hands by a man (or that of throwing it) would be enough. In fact, a classical description of a dog catching a ball also would be enough. … An ant carrying a grain of sugar. An amoeba surrounding its food. …

So, no, I don’t at all like the idea of consciousness in a *theory* of physics. Though, of course, when it comes to applications, obviously, consciousness (or life) *is* capable of bringing about physical effects (say of exerting a physical force).

But even talking even of such application areas (i.e. those involving will, consciousness, or life) from the viewpoint of *physics*, it should handle consciousness simply via *auxiliary* *physical* data (i.e. appropriate initial/boundary/continuing conditions). … You don’t need a Superman, God, or any other willed or plain conscious-being, in a theory of physics. You don’t need them even just in order to set the values of physical constants, say the fundamental physical constants such as the specific values that G or \hbar carry. On the same basis, you don’t need any of them to set the values of any other numbers (such as those comprising the auxiliary data) that come up in an application of a physics theory—*any* physics theory.

Once again, an interesting question…

Best,

–Ajit

[E&OE]

Comment #37 December 15th, 2016 at 9:59 am

John B #34

Not only does Zach link to Scott’s blog and not this post in particular, but Scott does the same back at Zach! He links to the front page of SMBC instead of this particular comic. Link should be http://www.smbc-comics.com/comic/the-talk-4.

Comment #38 December 15th, 2016 at 11:10 am

The “consciousness” joke at the end is priceless! You just punctured my fondest dream, that the brain is a QC. Ah well.

Comment #39 December 15th, 2016 at 11:47 am

Zach #33: I’ve already decided that I’m not going to get upset when Lubos calls me “the most corrupt moral trash,” urges my students to spit in my face, etc. So by symmetry, I shouldn’t be gratified either if he happens to like something that I was involved with.

Incidentally, if Lubos Motl and the Trump supporters attack you as a weak, emasculated castrato, while at the very same time, the SJWs attack you as a privileged, entitled, sexist dudebro, is that, like, a warning sign that you might have uttered something reasonable and true? 🙂

Update:I know I promised not to respond directly to Lubos on this blog, but … oh man. I have it good authority that Lubosmighthave written, in his comment section, that while it’s true that I’m an anti-quantum crackpot zealot, etc. etc., many others (the hardcore MWIers, Bohmians, etc.) are far worse, andI’m merely as confused about quantum mechanics as Steven Weinberg is.I’d be proud to have the latter description etched on my tombstone.Comment #40 December 15th, 2016 at 11:54 am

Ajit #35: I think our views are consistent. I would say that what gives QM its character is the interplay between the 1-norm and the 2-norm—evolution of the wavefunction (when you don’t measure) preserves 2-norm, but evolution of the density matrix (when you do measure) preserves trace, which is a 1-norm.

Comment #41 December 15th, 2016 at 12:59 pm

Great post.

There are six kinds of people on the issue of QC and I want to know whats the most common:

1) People who don’t know a lot but think QC can do LOTS more than it can (or at least can now). The boy in your strip.

2) People who do know a lot but think QC can do LOTS more than it can (or at least can now). I think this set was larger at one time then it is now.

3) People who don’t know a lot but think QC is not worth studying. (Prob small set of people)

4) People who do know a lot but think QC is not worth studying (Oded Goldreich might be in this category)

5) People who don’t know a lot but realize that QC is interesting but don’t oversell it. If they know enough they may thing that its likely SAT is not in BQP, though they may not know the terms.

6) People who do knot a lot and realize that QC is

interesting but don’t overhype it. They largely believe that SAT is not in BQP.

I applaud Scott for his intelligent discussions with both the people who overhype and the people who think its not worth studying.

Comment #42 December 15th, 2016 at 1:12 pm

gasarch #41: I can say from experience that Oded Goldreich does indeed know a lot, but the lot that he knows is not about QC (and he readily admits as much).

Comment #43 December 15th, 2016 at 1:52 pm

Scott #40:

Ummm… Though you tried to be helpful by inserting parenthetical comments, it just so happens that I haven’t so far studied the density matrix formalism at all, and so can’t really comment. … I mean, I know that QM is about going from one real-valued measurement to a complex-valued time-evolution (which must preserve the 2-norm) and onto another real-valued measurement. But I can’t relate this character of QM to what you say in reference to the density matrix formalism or its 1-norm.

… Some time in future, when I do come to study the density matrix formalism, it would be interesting to pursue what its evolution would be like, in an *hypothetical* QM where the amplitudes are only real-valued, not complex-valued, and still, the idea of measurements and eigenstates applies.

… Anyway, it’s already past mid-night here, and I don’t want to be up till late every night. … So, thanks, and bye for now!

–Ajit

[E&OE

Comment #44 December 15th, 2016 at 1:53 pm

I see Lubos has commented on the subject including his usual over the top insults. For the record I concede that he is both more intelligent and better educated than I. Still, I maintain that his statements are either wrong or have no empirical consequence at all.

Lubos said…

Actually I agree. I did not intent to imply that your statement was this stupid. My apologies.

And…

I agree with this. But quantum mechanics does not define what an observer is. Does a cat count as an observer? How about a rock? It turns out that it makes no difference. What counts is not the recording of the information in a conscious brain but the recording of the information in the environment at large. In any measurable way the rock is just as much of an observer as a person.

And…

Again, I agree. But quantum mechanics contains no definition of conscious subjectivity. I am free to adopt the view point of a person, cat, robot or even a rock and ask what they would “see” as if they were conscious observers. The result is the same for all. I could insist that they are all conscious and there could be no quantum experiment that would prove me wrong. I could even insist that you are not conscious and there is no quantum experiment that you could do to prove me wrong.

Consciousness simply isn’t relevant.

Comment #45 December 15th, 2016 at 2:03 pm

#13 Scott, thanks for that definition of “isolated”. I will have to ponder that some more.

As for the question regarding complex numbers as ordered pairs of reals, I guess I was just thinking that it was possible that QM could be described without introducing the idea of a complex number. Of course if the kid wanted to understand more, you would still need to describe the properties of how these ordered pairs interacted under different operations and fit into larger structures, etc., so we might as well introduce some notion of an “imaginary” numbers, but I just thought it could be described in more fundamental way, like your “2-norm” way. I guess it relates to what Job wrote in #16, and Johan wrote in #25, and Ajit in #35… but while we’re on this topic of what is sufficient for describing QM, what about getting rid of reals too? Could you just describe QM in terms of rationals, floating point, or some finite theory?

#23 I actually did struggle through QCSD. I guess you’re saying some of the most difficult questions of QM are related to exploring complexity classes and that sort, but I I was trying to poke around and ask whether the underlying theory of QM had any chinks in its armor/foundations.

On an unrelated note, has there been any mention on this blog of Generative Adversarial Networks (GANs) yet? There seems to be some relationships to QM, although maybe it is only at some superficial, popular-press-kind-of level. A couple links to Yann LeCun talking about GANs are below:

https://youtu.be/IbjF5VjniVE?t=42m11s

https://youtu.be/Gwad1cWMcC0?t=19m15s

Comment #46 December 15th, 2016 at 2:18 pm

Jon K. #25: If you read Feynman’s superb QED book, he never once mentions complex numbers—he just talks instead about little arrows that you stack together head to tail. He then gets interference, the norm of a complex number, the Born rule, the path of least action, etc., all in terms of pictures with stacked arrows. I remember thinking while I read it: “I was so proud of myself for figuring out how to fully, correctly explain quantum mechanics to 12-year-olds. But now along comes goddamn Feynman, explaining it to 8-year-olds.”

Comment #47 December 15th, 2016 at 2:32 pm

Beautifully done! 😀

Comment #48 December 15th, 2016 at 2:36 pm

#45 Jon k.

You could get rid of numbers entirely and just use piles of stones and rules for moving those stones to represent quantum mechanics. And that’s how a computer works. There are no numbers in a computer. There are only patterns of charged and discharged capacitors and rules for charging and discharging them. You can label the states with the numbers zero and one, combine many of these to represent positive integers, use two’s compliment to represent negative integers, use a sign, exponent and mantissa to represent floating point numbers and use pairs of these to represent complex numbers. But all that is really there are capacitors and rules… or rocks. The numbers are just how we describe it and talk about it.

So all that is really necessary for quantum mechanics is the number zero and one. In large numbers.

Comment #49 December 15th, 2016 at 2:53 pm

Just (independently) saw the cartoon, immediately thought ‘wow, he must have been reading Shtetl Optimized. Feels like he’s channeling Scott here’. Guess you were just channeling yourself 😉 Anyway, awesome stuff, well done!

Comment #50 December 15th, 2016 at 4:49 pm

terrific.cartoon. almost as good as Calvin & Hobbes and more educational.

Comment #51 December 15th, 2016 at 5:20 pm

#46

Thanks, Scott. I will check out that Feynman QED book. I’m actually just finishing a “Feynman Lectures on Computation” book, which had one chapter devoted to quantum mechanics, but I didn’t find it as enlightening as I had hoped. (I think it was more of a transcript lifted from one of his lectures on QM, so it might have been slightly out of context, or been a talk intended for high schoolers instead of 8 year-olds) I guess it is best to read several different descriptions of QM to see what sticks.

#48

Yes, PPNL! But did you mean “All that is necessary to *describe* QM are the numbers 0 and 1”? So would you agree that the description of QM can be represented in a computer, but in order to simulate the observed results of a QM experiment, the classical computer would need a random or pseudo-random seed, to represent the “collapsing” of the wave function? (And the classical simulation would take longer?)

I wonder what the Kolmogorov complexity size of that QM description would be, not including the seed?

Scott, do you condone this discussion or line of thinking? Where is my understanding going wrong?

Comment #52 December 15th, 2016 at 7:00 pm

That was excellent, and quite a surprise from you!

Just expand on your meaning of this part:

“It’s not the size that matters it’s the rotation through complex space”

Comment #53 December 15th, 2016 at 7:10 pm

Aaargh! I didn’t read through the comments before posting, and you already answered that one, sorry.

Comment #54 December 15th, 2016 at 8:13 pm

IMO it’s just very different from how classical algorithms are designed, and the circuit model is so familiar that it’s totally misleading.

Comment #55 December 15th, 2016 at 8:30 pm

Hi Scott,

I’ve read your thoughts on the many worlds interpretation and dynamical collapse theories but I was wondering what you think of quantum Darwinism?

Thanks.

Comment #56 December 15th, 2016 at 10:52 pm

ppnl #48:

A model is a mathematical construct that describes some aspect of the material world. It’s purpose is to make visualization easy and give us an intuition for it.

One thing that surprised me when I first took a Physics course is the importance Physicists give to intuition.

The reason we use base 10 is the same reason we use Complex Numbers for QM.

base 12 is obviously the better choice, it makes daily calculations much easier but we have 10 fingers and so we have an intuition for base 10 and we need to develop an intuition for base 12.

We already know Complex Numbers and they fit properly to this model so why put in the extra effort, in fact like Scott says the concept of amplitudes is so simple mathematicians could’ve come up with it independently.

And this is an unpopular opinion but I think everyone who wants to learn more should learn more math, it is easier for the kid to learn more math than for the mom to come up with an analogy, to quote Feynman: ” To those who do not know mathematics it is difficult to get across a real feeling as to the beauty, the deepest beauty, of nature.”

Comment #57 December 15th, 2016 at 11:10 pm

ppnl #44:

Verywell put!—

All:

Let me share my “speculations”:

Actually, even though in discussing the QM theory, people don’t directly talk of it, to each state of a QM

system, there exists a different state of theenvironmentthat it is immersed in. … For the entire universe taken as an isolated system, the “environment” simply is an aspect of the same system, but it is an aspect which we don’t directly capture in the QM formalism.What does that lead to? Simple: The selection of one of the eigenstates making up the bra corresponds to and is brought about by the unspoken “environmental” aspects. The “environmental” aspects constitutes a hidden mechanism (which is not quite exactly a hidden

variable), and it is responsible for the selection.For the mechanism to select only one eigenstate (the one which is actually projected or measured) at the exclusion of the others, it must be catastrophic in nature. Something like how a switch at the middle critical point snaps into one of the alternative final positions. Whereas for the simple 2-way switch, both the positions (on or off) may be taken as equally likely, in QM, this mechanism must be such that the probability of a particular selection it makes is sensitive to the projection of the ket on to the bra, i.e., to the energy (a 2-norm). For both the ordinary mechanical switch and the quantum mechanical switching mechanism, the throw has a probabilistic character. The probabilistic character arises because the critical point is an abstraction, whereas the actual system-path always moves in the close vicinity to it but around it, and we have no independent means to determine the position of he path near this critical point in a given experiment/trial.

(And I do have further speculations for the kind of micro-structure such a mechanism may have. However, in theory, you have to put it in terms of the micro-structure of the wavefunction.)

—

Coming back to the role of the observer. No consciousness is necessary to describe the catastrophic switch-over in a (classical) mechanical switch. Ditto, for QM.

–Ajit

[E&OE]

Comment #58 December 15th, 2016 at 11:19 pm

Oops, an awkward construction.

In my immediately preceding comment (just submitted, still in moderation), in place of:

“…to each state of a QM

system, there exists a different state of theenvironmentthat it is immersed in”,please read:

“…to each state of a QM

system, there exists a corresponding state of theenvironmentthat it is immersed in”.I didn’t to imply a 1:N correspondence between a system state and the state of its environment. I meant only a 1:1 correspondence here.

Bye for now.

–Ajit

[E&OE]

Comment #59 December 16th, 2016 at 12:34 am

Jon K. #51:

Feynman Lectures on Computationis, frankly, not one of his best works.QEDis a masterpiece.Yes, given an initial state, Hamiltonian, and measurement basis, the probabilistic predictions of quantum mechanics can be calculated to arbitrary accuracy by a short computer program running in a large amount of time—so in that sense, QM has very low Kolmogorov complexity (though probably not

resource-boundedKolmogorov complexity, if we define the latter using classical computation).It’s true that technically, the program would need a random number generator to make the final selection of a measurement outcome, and have it “really” be random (rather than pseudorandom). But I’ve never seen that as such a big deal—as a challenge to the Church-Turing Thesis or whatever—because even a deterministic program can easily output a list of probabilities, so that the only thing left for you to do would be to “spin the wheel.”

In any case, essentially

everyknown theory in physics can be “compiled down” to where its predictions can be calculated to arbitrary accuracy by a computer toggling 0’s and 1’s—the only exceptions (not coincidentally) being the theories that aren’t yet fully defined or understood. So should we say, on that basis, that you don’t need any nontrivial math to do physics: no complex numbers, no linear algebra, no calculus, not even arithmetic? Alas, not if you actually want tounderstandwhat the theories say, which David Deutsch reminds us is more important than calculating with them… 🙂Comment #60 December 16th, 2016 at 1:22 am

Chris #55:

I was wondering what you think of quantum Darwinism?

I think that that research program—which is really what it is—is asking excellent, fundamental questions about, in effect, “how you would program a computer to pick out the branches in the Everett picture.” I.e., quantum Darwinism aims to solve the preferred-basis problem, which was always the central technical objection to MWI, and which Everett and DeWitt only handwavingly sketched a solution to. To whatever extent it succeeds, I’d say that the “only” remaining objections to MWI are philosophical ones.

The outline of the solution has long been clear: namely, to find a basis where branching and decoherence happen, search for observables that get redundantly encoded in many different locations in space. But what exactly does that mean? Does redundant encoding in one basis preclude redundant encoding in a different basis? How many copies of an observable are needed? (The example of the singlet state shows that 2 copies can’t possibly be enough.) Can we prove that this redundant encoding

willhappen in realistic quantum systems? Is there a reasonably efficient algorithm to identify the redundant encoding while it’s happening, given a description of a quantum system? Even if redundant encoding suffices for us to say that branching has happened, are there other conditions that would also suffice?As it happens, Jess Riedel, a former student of Zurek and friend of mine, visited our group at UT Austin a few weeks ago. While there he gave a talk about his recent paper Classical branch structure from spatial redundancy in a many-body wavefunction, which addresses some of the questions above. I found the result there to be beautiful: it explains why you want at least

threecopies of a record to say that it’s redundantly encoded, and also why those copies should be reasonably far apart from each other in space. I hope Jess carries the work further, as he intends to, by writing actual code that would use “quantum Darwinism” to identify the branch structure in simulations of realistic quantum systems.Comment #61 December 16th, 2016 at 2:21 am

Sanketh #56:

The reason we use base 10 is the same reason we use Complex Numbers for QM.

I’m not sure how analogous the cases are. If we ever make contact with extraterrestrial intelligences, I expect them to do arithmetic in base 17 because that’s how many tentacles they have, but I also expect them to have the same notion of complex numbers that we do.

Comment #62 December 16th, 2016 at 6:10 am

Finally finished the book Information ist Energie: Definition eines physikalisch begründeten Informationsbegriffs by Lienhard Pagel.

This book uses QM in normal handwaving mode. By information, the author means his definition of dynamic information, which is something like information(flow) per time. Higher energy is normally associated with shorter times. What is good about this book is that it really discusses the time dynamics, which is otherwise often neglected.

By “information is energy”, he means that this type of dynamic information is conserved in basically the same way energy is conserved. He investigates a great number of situations, both situations which should confirm his conjecture and make it more understandable, but also situations which seem to contradict his conjecture at first sight. Most of his solutions for those contradictory situations felt good (and sometimes enlightening) to me, but sometimes his solutions didn’t convince me.

I don’t expect that his book will ever be translated into English, but I hope that at least his concept of dynamic information and his conjecture that this dynamic information is conserved just like energy will find its way into discussions about quantum information theory. Maybe those discussions will show that his concept and conjecture is trivial or wrong, but I think that those discussions would be beneficial for highlighting to role of time dynamics in quantum mechanics. Not sure whether those are important for quantum information theory or not. (I hope I didn’t ran into that “damned by faint praise” issue again. In the part of Germany where I come from, praise is used “sparingly”.)

Comment #63 December 16th, 2016 at 8:18 am

Scott in #59:

> So should we say, on that basis, that you don’t need any nontrivial math to do physics: no complex numbers, no linear algebra, no calculus, not even arithmetic? Alas, not if you actually want to understand what the theories say, which David Deutsch reminds us is more important than calculating with them…

Please don’t tell that to the thousands of unmotivated CS students in the university. They’ll think they can get a job without learning mathematics as long as they’re fine with not understanding what they’re doing.

Comment #64 December 16th, 2016 at 11:05 am

This comic is excellent! Thanks for doing it.

Comment #65 December 16th, 2016 at 12:43 pm

#59

Ok, I’m giving Feynman another shot. (He deserves it.) QED is going on my very short holiday wish list! (i.e. Peace on Earth, QED by Feynman…in that order)

I agree that looking at the bits might not give us lots of predictive power, but it may provide understanding from a different perspective. Understanding at a higher-level, which might be dependent on concepts such as complex numbers, calculus, probabilities, etc. obviously has a lot of value too. For instance, it is easier to understand how gradient descent leverages calculus to find an optimal parameterization of a neural network model, then it is to look at the compiled code and figure out how some intricate program magically generates the same parameterization; It might be hard/impossible to see the forest for the trees at that low of a level. But I also think it is interesting to consider the algorithmic implementation of some of the concepts (i.e. probabilities, calculus, infinity, etc.), which I consider to be “Platonic”. In some sense, the machine learning model is just executing some deterministic code, and not “learning” at all.

And here is my final question(s): If we agree that a QM Description has a low Kolmogorov complexity, how do we know the universe needs “real” randomness, instead of a pseudorandom seed? Isn’t it possible that one pseudorandom number with low Kolmogorov complexity could provide QM with all the “randomness” it needed in order to recreate every historical measurement(in theory)? Could our universe actually have low Kolmogorov complexity(in theory)? Although Resource-Bounded Kolmogorov complexity and traditional complexity measures would be very relevant when it comes to engineering technology, if time and space were “emergent” in our universe–which it would seem like it would have to be if we are looking at this “compiled down” version–then the fact that our universe could not be simulated by any human in a low Resource-Bounded Kolmogorov sense, wouldn’t seem to be good evidence against these Schmidhuberian/Wolframian theories. Or in other words: Is it possible that our universe could be the output of short computer program, one which even encodes in it scientists “spinning the wheel”?

(I know this is the kind of question you hate answering over and over, so I apologize; I don’t mean to be another classical-hypothesizing troll on a QM blog. 🙂 But I’m wondering if the way in which this conversation has evolved makes you think any differently about this question. Don’t super-determinism theories which include the human experimenters as part of the system evade the consequences of Bell’s Theorem?)

Comment #66 December 16th, 2016 at 12:49 pm

Scott #60:

I can’t really wrap my head around quantum Darwinism. I don’t understand pointer states or why they are needed. I am clueless about redundant encoding. Well I’m not a physicist so not surprising. But it is frustrating.

I think about the problem by taking a toy model of the universe like a cellular automata. It has a set of rules of physics that is classically deterministic. Now create a quantum version where initially all cells are in a superposition of their states. The universe is in a superposition of all possible states. That is the many worlds multiverse.

Now let the automata evolve for a billion generations according to its rules without collapsing the superposition. Now you have a superposition of all possible universes that are a billion generations old. But what you also have is a vast network of entanglements. The states of the cells are still in superposition but those states are no longer independent of each other.

Now lets introduce an observer cell which is a cell that we look at after each generation. When we look at it we collapse its wave and reduce it to a particular state. But what we also do is reduce the set of initial states of the universe to only those that produce the observed state at the billionth generation. As the automata progresses past the billionth generation our observer cell interacts with its neighbors and further reduces the possible initial states. As far as that observer cell can see it has a consistent past, predictable future and is following deterministic rules of physics. The vast network of entanglements seem to guarantee that.

So why isn’t this how our classical universe emerges from the quantum world?

Comment #67 December 16th, 2016 at 12:59 pm

Scott #61:

I meant in a different form than we use, like base 10 or base 12 doesn’t change the number.

QM needs Complex Numbers but they might have a more complex or a simpler way for working with them. We are accustomed to working with a+bi form or some other equivalent form but they might be using pulses of electricity or be more comfortable with some matrix notation…..

QM needs L2 norm but I was referring to ways of representation. You can do QM even without our notion of complex numbers but you’d need something equivalent and I conjuncture that that other form would be harder for humans to parse.

Comment #68 December 16th, 2016 at 1:49 pm

Scott,

This comic made me rediscover your blog, which I used to read in high school. I recently graduated college with degrees in philosophy (focus in analytic metaphysics and epistemology) and mathematics (focus in ToC) and have found your articles on complexity theory and philosophy fascinating. As I work as a mathematician in industry, I have been flirting with philosophy projects but nothing has struck a chord quite like reading your articles on the topic. I was wondering if you had any advice, suggested reading, or direction to provide, or a problem or three that you would be interested in hearing about people working on that you do not have the time to pursue on your own. Even a list of people who are actively pursuing such questions would be helpful, as google searches are a suboptimal way to find answers to niche questions.

If there is a better way to reach out with questions like this, I am happy to do so. It felt less obnoxious to comment here than to email you unsolicited.

Comment #69 December 16th, 2016 at 2:15 pm

Sanketh #67

Actually electrical engineers do use complex numbers to talk about electrical pulses. So yes you could use electrical impulses to talk about complex numbers.

But it just doesn’t matter. However they talk about it and whatever they use to represent it their complex numbers must in a deep sense be the same as ours.

I believe that on the other side of the galaxy there is an alien nerd calculating the billionth digit of Pi. And making allowances for trivial things like number base or method of representation it will be the same digit as we calculate here.

Comment #70 December 17th, 2016 at 12:38 am

ppnl #66: The trouble with that intuition arises when you consider an example like the singlet state, |00>+|11>. Staring at that state, it seems obvious that there are two “branches”: one with two copies of 0 and the other with two copies of 1. Right? The problem is, the exact same state can be rewritten as

|+>|+>+|->|->,

where |+>=|0>+|1> and |->=|0>-|1>. So what’s to pick out one basis as being better than the other? This is just one example of what’s called the “preferred basis problem.” In your classical CA example, there’s only one basis. But in quantum mechanics, you always have a choice of any orthonormal basis. So if you want to say that “branching” is happening, then you need something—such as the dynamics itself—to pick out the basis in which you take the branching to be happening. That’s exactly the problem addressed in (e.g.) the paper by Jess Riedel that I mentioned, one of whose key observations is that, in a GHZ state like |000>+|111>, with 3 or more copies of 0 and 1, the situation with picking a preferred basis is already a lot better than when there are only 2 copies.

Comment #71 December 17th, 2016 at 12:44 am

Stella #68: Thanks for your comment! I’d be happy to help you, but maybe you could help me first. What kinds of problems are you looking for? In “Why Philosophers Should Care About Computational Complexity”, I did mention a bunch of underexplored issues that I found interesting. Is that the kind of problem you wanted? Or did you want something more concrete? Just point me in a direction.

Comment #72 December 17th, 2016 at 12:59 am

Jon K. #65: Yes, as you say, these are issues that we’ve been over many, many times before here. See, for example, Part II of my American Scientist article, about Bell’s Theorem. The bottom line is that, if you wanted a hidden deterministic pattern to quantum measurement outcomes, then you would also need faster-than-light communication to coordinate the measurement outcomes between different parts of the universe. Of course, if determinism was infinitely important to you, then you could postulate as much nonlocality as you needed to get it, as ‘t Hooft does with his superdeterministic conspiracy theory. But you then face what, to my mind, is a fatal problem: namely, you’re now utterly unable to explain why our universe

onlyallows precisely the nonlocal behavior predicted by quantum mechanics (such as winning the CHSH game 85% of the time), and not even more nonlocal behavior than that. Occam’s blade is trembling in its sheath.Comment #73 December 17th, 2016 at 1:15 am

Ah, but likely they’re computing the billionth digit of 2π instead. 🙂

Comment #74 December 17th, 2016 at 1:18 am

…also I only just realized that talk of “digits” implicitly means we’re talking about bases. Which are pretty much fully arbitrary. Unless it’s base 2, in which case the distinction between π and 2π hardly matters.

Unless instead it’s base 3 due to radix economy. Who knows, maybe that’s something an alien civilization might actually care about. 😛

Comment #75 December 17th, 2016 at 1:53 pm

Engineers sheath Occam’s blade by first acknowledging that yes, the causality-respecting realization of arbitrary Hamiltonian functions (even effectively) with

spukhafte Fernwirkungencan only be effected on large-dimension Hilbert spaces.Yet crucially, our universe does not allow physically allow arbitrary Hamiltonian functions … she insists instead on gauge theories that include at least two massless bosonic fields (photons and gravitons). The empirical consequences are that (1) demonstrating scalable quantum computation is proving to be far harder than previous generations of quantum physicists foresaw, and concomitantly (2) classical algorithms for accurately simulating large-scale quantum gauge-systems are proving to be far more efficient and capable than previous generations of quantum physicists foresaw.

Doesn’t Occam’s razor direct that the dual observations (1) and (2) be reconciled, as reflections (for example) of the natural Occam-compatible postulate that the universe permits only those Hamiltonians that accomodate the causal

spukhafte Fernwirkungen(that are beloved of quantum physicists and complexity theorists) on low-dimension tensor networks (that are cherished by algebraic geometers and simulationists)?This Occam-compatible postulate explains, naturally and even (arguably) very beautifully, why present-day experiments and simulations alike readily exhibit low-dimension

spukhafte Fernwirkungen(like photon interference), but exhibit high-dimensionspukhafte Fernwirkungen(like scalable quantum computation) only with very great difficulty such demonstrations perhaps being impossible even principle (as Kalai’s preprints argue).Regardless of whether this tensor-network quantum state-space postulate is Platonically true, for a great many quantum engineering purposes it is

effectivelytrue, and this is is one strong motivation (among several) for the present-day flourishing of the literature on tensor-network state-spaces.From this perspective, the Martinis/Google group’s recent preprint “Characterizing quantum supremacy in near-term devices” (2016) might alternatively been titled “Characterizing the

spukhafte Fernwirkungenassociated to large-dimension metric isomorphisms in quantum dynamics”. Further discussion of this thought-provoking preprint would be welcome by manyShtetl Optimizedreaders (including me).Comment #76 December 17th, 2016 at 5:27 pm

@ppnl #66

Now create a quantum version where initially all cells are in a superposition of their stateshaha – but how do you propose that happens? Do you say, like Dirac at the 1927 conference, that Nature does all the random jumps?

I think Nature must do all the random jumps, at a statistical time period close to Plank time unit, and then the rest of the universe updates via a huge unitary evolution so it knows what just happened. If it wasn’t unitary we could get infinities or zero states – maybe those are ruled out by anthropic arguments ?

Comment #77 December 17th, 2016 at 5:28 pm

Planck – my spell checker is shit

Comment #78 December 17th, 2016 at 8:53 pm

ppnl and Sniffnoy: I always assumed the alien nerd would be calculate the billionth integer in the continued fraction expansion of pi. (http://oeis.org/A001203)

Comment #79 December 17th, 2016 at 11:01 pm

I’d love to post this comic on Facebook, but it’s too long for reading on mobile and that’s how most people (including me) read things. Do you have a version that’s chopped up? Would you like a version that’s chopped up? For instance, instead of:

A

B

C

D

E

F

I could put a version together like:

ABC

DEF

so that it’s a little more readable.

Comment #80 December 17th, 2016 at 11:48 pm

Scott #70 and ppnl #66:

(I am writing in reference to the description in ppnl #6, and not to quantum Darwinism as such. I didn’t know about qD, and just now rapidly browsed the Wiki article on it, that’s all.)

I think that it is not the preferred basis which is primarily problematic with ppnl #66’s model. (Problematic, in the sense, what makes it unlike the actual QM.)

I think there is a more basic problem here, and it is the fact that the automaton has “a set of rules of physics that is classically deterministic.” By those words, I take it that ppnl does not mean a deterministic but chaotic process underlying those rules, and imparting an apparent disorder to their outcomes. I think he means that the updating rules are the simplest deterministic here; it’s just that the number of cells and updates are great.

In ppnl’s model, presumably, not just the updating rules but also the measurement rules which the observer cell uses in making its measurements, follow a classical, deterministic criterion. If the criterion is deterministic, it will impart a preferred basis.

The preferred basis thus is an outcome, an not an essential feature of the model. The basic reason the preferred basis comes about is: the classical determinism.

If ppnl makes either of those two—the updating rules or the measurement rules—probabilistic, then the problem would actually go away.

For QM to turn probabilistic the way it is described in its axiomatic description, it is sufficient if only the measurement rule is made probabilistic. The system evolution, represented here via the updates, could very well be deterministic. In QM, the Schrodinger evolution

isdeterministic anyway.Even if both the categories of rules (updating and measurements) are kept deterministic, the machine would still show certain similarities to the quantum mechanical (i.e. the actually existing) world—viz., a reduction in the number of input states required to get to a given observed state.

Yet, IMO (for whatever it is worth), speaking overall, the way this model is built is

nothow people should go about thinking about QM. The QM is about going (i) from one measured (definite) state (in whatever basis) (ii) through the deterministic Schrodinger evolution (iii) to another, probabilistically measured (but definite) state (in whatever basis). Starting a description in the middle—at (ii)—-is conceptually more difficult if not dangerous. The best way to approach QM is to start at (i), and also end at (iii). That’s what I think.Best,

–Ajit

[E&OE]

Comment #81 December 18th, 2016 at 2:18 am

Jair #78: Oh, good point! But shouldn’t that be 2π? 🙂

Comment #82 December 18th, 2016 at 2:22 am

Excellent!

(Yes, that’s all I have to say, and yes, it needs to be said ^_^ )

Comment #83 December 18th, 2016 at 6:52 am

In regard to Stella’s comment (#68), not the least of many virtues of Scott’s essay “Why Philosophers Should Care About Computational Complexity” is that the essay explicitly

disclaimscoverage of several broad classes of philosophical question.The

Gazetteof the Fondation Sciences Mathematiques de Paris takes up some of the slack in a recent interview with ISA mathematician Vladimir Voevodsky, that was published (in French) as “La bifurcation de Vladimir Voevodsky: De la théorie de l’homotopie à la théorie des types” (2014). TheGazettearticle derives in turn from an interview (in English) that has recently become available on youtube as “La bifurcation de Vladimir Voevodsky“.In a nutshell, Voevodsky’s philosophical agenda radically embraces, as a primary objective of mathematical practice, “to read and trust and enjoy, rather than doubt and work and eventually not read at all”; moreover Voevodsky sees “no other way for mathematics to prosper.” Yes, these philosophical ideas definitely are radical. 🙂

Needless to say, it is neither philosophically necessary nor socially desirable that every young STEAM-worker embrace Voevodskyian ideals and methods. Yet neither is it desirable for young researchers — young quantum researchers in particular — to be oblivious to the detailed roadmap that is set forth in works like the IAS Univalent Foundations Program’s survey “Homotopy type theory and Voevodsky’s univalent foundations” (Bull. AMS, 2014)

For practicing photonic engineers and quantum optics researchers, the fruits of this approach are manifest in practical computational tools like “MEEP: A flexible free-software package for electromagnetic simulations by the FDTD method” (Computer Physics Communications, 2010). Students of the history of science will appreciate, too, that the (DARPA-funded) Univalent Foundations Program is a direct descendant — philosophically mathematically, computationally, and programmatically — of the (DARPA-funded) MEEP program. This inheritance is very largely the legacy of Dennis Healy.

Looking toward the quantum future, the preceding considerations provide reason to foresee that practical large-scale demonstrations (or not) of quantum supremacy — whether achieved by photonic BOSONSAMPLING, DWAVE-style SQUID arrays, ion traps, or any other foreseen scalable quantum technology — will rely crucially upon MEEP-like computational tools and philosophical/social insights like Voevodsky’s.

In summary, the present decade is proving to be a golden era for all varieties of quantum researcher — including philosophers. 🙂

Comment #84 December 18th, 2016 at 6:36 pm

Ajit #80:

I often have trouble understanding what you are saying. When I do think I understand it seems wrong in strange ways. For example:

No, by deterministic I mean deterministic. As in the current state follows precisely from the previous state. Like Conway’s game of life for example. Now chaos may result from following the rules. But first that chaos does not change the fact that it is fully deterministic. And secondly that chaos is irrelevant to any point about quantum mechanics.

And I don’t understand what you mean by measurement rules being deterministic. Quantum measurements are always irreducibly ontogicaly random. That randomness simply is. There is no underlying mechanism. That is the point of the Born rule.

I’m still trying to wrap my head around Scott’s point about preferred basis. I can’t work out what it means physically. I guess that means I will have to work on an actual understanding rather than just an intuitive one.

Comment #85 December 18th, 2016 at 6:40 pm

Ajit #43: When you say “I haven’t so far studied the density matrix formalism at all”, do you mean that you have never seen density matrices before, or just that their ultrashort treatment found in introductory QM textbooks gave you no indication why they are useful? By ultrashort, I mean a short talk about mixed states followed by some basic facts like:

definition: p = Σ p_k |ψ_k> <ψ_k|

trace: tr(p)=1

pure state: p^2=p <-> pure state

expectation value: <A> = tr(Ap)

time evolution (von Neumann equation): ih dp/dt = [H,p]

Let me try to give some reasons (there are many more) why they are useful: (1) absence of global phase, (2) description of subsystems, (3) definition of entropy.

(1) A pure state is not measurable, because the global phase cannot be measured, The global phase is absent for the description by the density matrix, and it turns out that the density matrix is indeed measurable (in a suitable sense).

(2) Even if the global state of a system is given by a pure state, the state of a subsystem can in general not be described by a pure state. But the state of a subsystem can always be described by a density matrix, even if the global state of the system is itself given by a density matrix (or a pure state).

(3) The von Neumann entropy must be computed from the density matrix (or rather from the eigenvalues e_i of the density matrix p as S(p) = Σ e_i ln(e_i)). Taking the probabilities from the Born rule instead (or the p_k from the definition of the density matrix) simply gives the wrong result.

The definition of the entropy was the reason why John von Neumann introduced the density matrix. The description of subsystems was the reason why Lev Landau independently invented the density matrix. And the absence of global phase is a good reason for physics students to not worry too much about the global phase.

Comment #86 December 18th, 2016 at 11:30 pm

ppnl #84:

0. I won’t keep quoting your passages, though the context should make the particular reference clear. My reply does follow the order of your points in #84.

1. OK. There are two different flavors of deterministic theories. One is linear, another nonlinear. The nonlinear theory (viz. that at least for some regimes of the input data, the output does not scale linearly with the input) is a good candidate for producing randomness. (Oh, BTW, “randomness” is “random-ness”: it

isa matter of degrees.) All pseudo-random number generators rely precisely on such a (deterministic) nonlinearity. Theydohavesomerelevance tosomepoints “related to QM.” All software simulations of QM phenomena rely on the pseudo random number generators—i.e. on the nonlinear determinism. If they thus are practically useful, so is the linear vs. nonlinear distinction, esp. in the context of asoftwaremodel like CA. You failed to make it.Itherefore had trouble understanding what you had in mind.If you would still only emphasize: “but it

isdeterministic,” then, sorry, I would have nothing to add further w.r.t. this point.2. There was a typo in my #80. Instead of “For QM to turn probabilistic,” it should be: “For CA to turn probabilistic.”

But there was no typo when I wrote

thishere:“Even if both the categories of rules (updating and measurements) are kept deterministic, the machine would still show certain similarities to the quantum mechanical (i.e. the actually existing) world—viz., a reduction in the number of input states required to get to a given observed state.”

In particular, notice the words: “if,” “would,” “certain,” “similarities” etc. (Is skipping such words the reason you have difficulty understanding what I write? Were you very rapidly browsing what I wrote?)

3. Yes, quantum measurements are random—in the sense, quantum measurements do show randomness.

That what

quantummeasurements show is a perfect randomness, is ahypothesisnot a physically established fact. … Actually, it’s not even a hypothesis. It is just a conjecture because none has found a sensitive and accurate enough way to experimentally verify it. If you must refer to Popper’s falsifiability criterion (and I don’t care to), the matter has not yet experimentally come within the realm of falsifiability.As to me, I don’t accept the position that randomness exists in a metaphysical sense. This point of our difference is philosophical in nature; in fact even you yourself said “ontologicaly.” But QM is not a philosophical theory—it is not a branch of or theory in ontology (or metaphysics) any more than it is not a branch of theology. QM is a theory of physics. Don’t club the two together.

That there is no mechanism (for what? I take it for randomness) is what Born

mighthave said—and I am not sure if he really actually saidthat. Bohr could easily have said it, also Heisenberg. But Born? I am not sure.In case Born did say that: Born was not God—merely a Nobel laureate. This position (i.e., pre-emptying any possibility of there being any deeper mechanism) is not worthy of any serious attention—not in physics. May be (and just may be) Born shares a philosophic point with you, that’s all—at the most.

4. The preferred basis concept is not very clear to many people, I now gather. It (and qD) certainly is not very clear to me. The concept is new; what I gathered about it could be easily wrong—because the simpler sources (Wiki, Quora, others) could also be (at least partly) wrong about it. In any case, that part of my above comment could very easily be wrong. (It was just a blog comment, and I did indicate my lack of knowledge of qD etc.)

As to Scott, I am sure, he would be admiringly capable of stating what

hedid have in mind.5. If you think that I am wrong, feel free to say so too. It won’t be an

ad hominemif you are careful to distinguish the idea from the ideator.Also, in future, if you don’t understand something I write, simple: feel free to ask me (by private email, if you wish.)

But in no case would I allow you to simply observe—though publicly—that you find me difficult to understand, and let the matter explicitly stop just at that. There can be implicit bad effects out of this practice, and I am concerned about them.

On my own part, I most certainly

don’twish to be sneering, by just putting an emphasis: “oh,you(possibly: youall) don’t understand me,” either. Hence, the suggestion—to just ask me! It helps keep the air clear.Hope I addressed all your concerns.

Best,

–Ajit

[E&OE]

Comment #87 December 18th, 2016 at 11:51 pm

gentzen #86:

I have not worked (or thought) through density matrices. I had gathered something about them when I read those topics in text-books, but being concerned more with the foundational issues, my reading was geared towards really understanding Schrodinger’s and Heisenberg’s “pictures” first, before anything else. (It precisely is the reason why I have kept studying relativistic QM in the waiting list for quite some time—even though it’s been years since I bought Dirac’s Principles book.)

But thanks for taking so much care to note down the important points about DM! I really appreciate that!!

A few rapid comments:

(1) seems lovely. No doubt about it.

(2) I don’t quite understand right away, but never mind. (I don’t want to put you through the trouble of explaining something to me at a time that I am not even ready to understand it!)

(3) won’t interest me, I am sure. The application would be of interest to information theory/TCS folks, but it is not, to me. My interests are mainly in the QM foundations and then, may be, some software simulations of some basic QM phenomena and/or applications to some topic here and there, may be, from condensed matter physics (i.e., if at all).

Overall, (1) is absolutely great to have. This property by itself does motivate me to “pre-pone” my studies of density matrices to an earlier date (even if it won’t be right away—not right this week or next week!).

Thanks, once again!

Best,

–Ajit

[E&OE]

Comment #88 December 19th, 2016 at 8:07 am

Gentzen’s remarks on density matrices (#24) are well-conceived and clearly stated (as they seem to me). Thanks!

A three-step student-friendly

Shtetl-relevant reading program that builds on Gentzen’s remarks is:(1) Wikipedia’s article “Classical electromagnetism and special relativity”, in particular Section 2.1 “Deriving magnetism from electrostatics”. This section begins with a Feynman quote:

(2) Richard Ernst’s density-matrix-centric text (with Geoffrey Bodenhausen and Alexander Wokaun) “Principles of nuclear magnetic resonance in one and two dimensions”. Ernst’ text surveys the comprehensive capacity of density matrices in simulating quantum dynamics in the (superficially) non-relativistic world of the Schrödinger equation and the Heisenberg picture (note: Ernst’ lively Nobel Biography supplies some needed real-world zest to his dry text). In turn, Ernst’s text prepares us to appreciate a third text:

(3) “Quantum mechanical NMR simulation algorithm for protein-size spin systems” by Ilya Kuprov and collaborators (JMR 2014). The abstract of this article leads off with the challenging pro-skeptic assertion

Two particularly commendable aspect of the Kuprov et al. article are, first, the thousand-spin quantum mechanical predictions are compared in-depth with thousand-spin experimental observations, and second, the computational methods used are well-suited to scalably simulate the dozens-of-qubit experiments that the recent Martinis/Google preprint “Characterizing quantum supremacy in near-term devices” (2016, see #75) envisions.

In a nutshell, quantum supremacists envision that Martinis-style qubit protocols may (eventually) scalably demonstrate sufficiently large-dimension/high-order quantum coherences (in density matrix lingo) as to dimensionally overwhelm Kuprov-style dissipation-dependent simulation methods, whereas skeptics repose their trust in the decoherent aspects of the quantum gauge-dynamics that Nature supplies.

In aggregate, these four works — Ernst, Martinis, Kalai, and Kuprov — go far to establish the practical equivalence of Kalai-style fundamental skepticism of quantum supremacy with Kuprov-style optimism regarding the polynomially scaling celerity of quantum simulation methods for all of physical chemistry (and condensed matter physics too). The equivalence is grounded — physically, mathematically, and computationally — in the dissipative dynamics that is generically associated to the long-range gauge-invariant interactions that (as Feynman’s quote affirms) relativistic invariance requires even of the simplest Schrödinger-equation models of condensed matter systems.

A particularly wonderful aspect (as it seems to me) regarding works of Ernst, Martinis, Kalai, and Kuprov is that there’s no fundamental contradiction in regarding all of these works as excellent, and foreseeing too that the hopes of all these workers — including even some of the hopes of quantum supremacists — can be substantially realized in coming decades … albeit with a few adjustments! 🙂

Comment #89 December 19th, 2016 at 8:39 am

But isn’t this like saying that nature must be “using” quaternions rather than rotation matrices whenever we look around?

Comment #90 December 19th, 2016 at 9:10 am

Scott #72

“you would also need faster-than-light communication to coordinate the measurement outcomes between different parts of the universe.”

But since *any* quantum system can be simulated on a classical digital computer, can’t we always reduce the physics of the known universe to be the output of such a simulation?

“Efficiency” is pretty much irrelevant because we (are observers inside the system) only experience each successive state, but not how those states are generated (outside of the internal time tick).

Anytime the simulation needs to simulate a random event, it would just use the next digit in PI (or any other pseudo-random sequence).

Comment #91 December 19th, 2016 at 9:57 am

fred #90: Yes, of course. But Bell’s Theorem tells us that such a simulation of our universe on a classical digital computer would necessarily be a nonlocal one (that is, the

simulationwould involve rapid signalling between memory cells corresponding to faraway events, violating the causal structure of the spacetime, even if we, living inside the universe, never actually experienced such signalling).Of course, the aliens simulating our universe might be fine with that nonlocality, and you might be fine with it too! But what it does is to push the alleged pseudorandomness of quantum measurement outcomes to a level that’s disconnected from what we actually know about physics. Note, in particular, that it’s extremely important that none of us ever discover the pattern to the pseudorandomness, since if we did, we could break the whole structure of QM, communicate faster than light, etc. Personally, I’d say that it’s of limited interest to postulate a theoretical superstructure that has to be so intentionally sequestered from everything we know about the workings of the world, but YMMV.

Comment #92 December 19th, 2016 at 6:39 pm

@Scott To me, if you try to imagine the world simulated on a classical computer, then the part where QM in our world can compute functions that probably require exponential time to compute in the simulation is way more distracting than anything about nonlocality or randomness. If the simulation requires exponential slowdown anyway, then that’s enough time for the nonlocal data to move from one part of the simulation to another. And for generating pseudorandom numbers that we can’t distinguish from true randomness, it is likely that you don’t even need any slowdown.

Comment #93 December 20th, 2016 at 3:30 am

This comic is exactly where we should be going with our children, we should help children explore quantum computing at their own pace. Far too often these days the media pressurizes children into performing their first superposition at too young an age, most are not ready for it.

I realise parents can be embarrased, in previouas generations superposition was done in private and entanglement was practically a taboo, the end result is people too embarrassed to talk about real problems, 58.567% of all left handed american men can’t sustain an entanglement long enough to satisfy their spouses.

#breakthequantumsilence

Comment #94 December 20th, 2016 at 3:36 am

jonas #92: Indeed—and that’s exactly why I’ve often described quantum computing (and quantum supremacy demonstrations in particular) as “Bell inequality violation on steroids”! The one big disadvantage, compared to Bell violation, is that it hasn’t yet been clearly experimentally demonstrated—but hopefully that will change in the next decade.

Comment #95 December 20th, 2016 at 10:13 am

Scott #94,

On the topic of experimental demonstration of quantum supremacy, in your initial paper on Boson Sampling with Alex, you proved that BS being efficiently solvable by a classical computer implies that the polynomial hierarchy collapses to the third level. Is there any hope for reducing the collapse level further? It seems like the primary barrier is that the universal hashing scheme gives rise to BPP^NP, but one might hope that there would be some way to derandomize that down to P^NP.

Comment #96 December 20th, 2016 at 12:05 pm

Scott #91

“Of course, the aliens simulating our universe might be fine with that nonlocality”

But if we assume that

1) our universe is computable

2) our universe can perform computations

Isn’t it unavoidable that recursion is happening?

Comment #97 December 20th, 2016 at 12:10 pm

Joshua #95: Good question! I believe the answer is yes: from a more careful analysis, you can get a collapse of PH all the way down to AM—so in particular, to the second level of PH. Furthermore, if your simulation is

reallyexact (i.e., the error is 0, rather than merely exponentially small), then you get a collapse of the counting class NQP=coC_{=}P with NP. See Appendix 8.2 in this paper by Fujii et al.(On the other hand, as far as I can tell, if you want to collapse not just PH but P

^{#P}, as in my and Arkhipov’s paper or Bremner-Jozsa-Shepherd’s, then you still need the third level.)Comment #98 December 20th, 2016 at 7:42 pm

John #88: Thanks. I initially wanted to link to section 2.4 from Nielsen and Chuang “Quantum Computation and Quantum Information” on the density operator, but the excerpt available online only starts at section 2.5 on the Schmidt decomposition and purification. So I decided to mention only the historical motivation (and also global phase as a pet peeve related to my own background in statistical optics).

Looks like part of your background is in nuclear magnetic resonance spectroscopy. Even if I had access to the NMR texts you recommend, I probably wouldn’t be able to sustain the motivation to work through them, because I would need to the content neither for my daily work, nor for my private projects.

Comment #99 December 20th, 2016 at 10:24 pm

Fred and Scott,

I think the universe is a *self-simulation* that’s recursing. The universe is a self-modeling *language*. That is to say, I’m claiming that there is nothing apart from symbolic representation.

I first heard the idea from the American high-IQ savant Chris Langan, but others had also suggested it before- the trouble was, no one had ever managed to get the idea to work, because ‘the map is not the terrority’, so how could reality possibly be a ‘language’?

But I finally found the one exception to ‘the map is not the terrority’ mantra. And this one exception is what makes the whole idea of reality as a ‘language’ work.

It is the symbolic representation of *time* (or ‘causality’) that breaks the map/terrority distinction. I claim that a *representation* or *model* of time IS time.

Think of the ground-state of reality as a sea of pure ‘information’ (or pure mathematics) . Within this sea, some parts of math can form a *model* (or simulation) of other parts. And it’s the math structures that can form complete self-consistent models of themselves that become physically ‘real’: they draw themselves into existence by generating a physical arrow of time.

This explains why physical reality is computational. Only the computable parts of math have the potential to generate complete self-models and thus become physically ‘real’. So ‘physics’ is simply the complete ‘self-model’ of computable mathematics!

And there’s a 3rd level of recursion: within physics, some arrangements of matter can start to form ‘self-representations’ of themselves…and it’s precisely these structures that are conscious! A new arrow of time is generated…the representation of causality IS causality , and this is consciousness!

If my theory is correct, the task before us is suddenly clear: the creation of a super-intelligence that can complete the 3rd level of recursion. If my theory is correct, the goal should be ‘model all minds in general’. This would complete the 3rd level of recursion and initiate the intelligence explosion.

Here is the top-level of my domain model of this putative super-recursive structure. There are 27 ‘knowledge domains’ – for each domain, I’ve linked to books I made on wikipedia listing the core concepts (A-Z) for each knowledge domain. Check it out, and see if you can see the ‘big picture’ behind my idea:

http://www.zarzuelazen.com/CoreKnowledgeDomains2.html

Comment #100 December 21st, 2016 at 9:53 am

Comic link is broken again. It’s really at http://www.smbc-comics.com/comic/the-talk

Not sure what’s up with the URL schema, but the numeric suffix is superfluous.

Comment #101 December 21st, 2016 at 9:55 am

Er, make that http://www.smbc-comics.com/comic/the-talk-3

Good grief!

Comment #102 December 21st, 2016 at 10:17 am

Gentzen #98, thanks in return! Quantum density matrices are paradigmatic examples of high-dimension/high-complexity mathematical structures that admit low-dimension/low-rank descriptions (often approximate).

It’s difficult to name a STEAM discipline in which such structures — high-dimension structures admitting low-dimension descriptions and simulations — are

nota primary focus of contemporary research, in which surprising (even incredible) advances arenotbeing made.Even when our modern algorithms and simulations work well, we commonly don’t know why. E.g., Google’s

AlphaGoinstantiates (somehow) a low-dimension encoding of winning moves in go, but we don’t understand AlphaGo’s algorithmic encoding of go-skill all that much better than we understand a human master’s neuropsychiatric encoding of go-skill.As with go-playing — and SAT-solving, automated language translation, phylogenetic analysis, and securities trading — so too with quantum simulation. Our computers are presenting us with low-rank approximate descriptions of high-dimension quantum structures (including density matrices), with such surprising accuracy and efficiency, as to increasingly outpace our understanding of

howthese amazing capacities are achieved.Old geezers aren’t shrinking from tackling these post-reductionist/post-rationalist mysteries. At age 78, Donald Knuth’s most

Art of Computer Programmingfascicles fearlessly tackle the generically intractable problems of SAT-solving, and at age 87, Eric Kandel’s latest neuropsychiatric meditation isReductionism in Art and Brain Science: Bridging the Two Cultures(2016). Should should younger researchers hang back, from the post-reductionist/post-rationalist STEAM territories into which old geezers are so fearlessly venturing? 🙂It may at first seem odd that modern-day quantum simulation techniques can be accurately described as “post-reductionist” and “post-rationalist.” Yet we are led to reflect, that the program of quantum simulation described (for example), in the Google/Martinis group’s preprint “Characterizing quantum supremacy in near-term devices” (2016, see comment #75), requires the application of (classical) simulation algorithms whose efficiency and accuracy substantially surpass our present rational understanding, and whose predictions are consequently not self-evidently reductionist, but rather are effectively oracular (rather like the workings of our own minds).

In summary, the quest to demonstrate “Quantum Supremacy” is intimately entangled with quests to demonstrate “Rationalist Supremacy” and “Reductionist Supremacy”, and it is characteristic of our modern STEAM-era that our collective understanding of these entangled quests is evolving rapidly, surprisingly, confusingly, distressingly (sometimes), and yet hopefully (at all times).

This is why it’s a great era to be a young STEAM-researcher. 🙂

Comment #103 December 21st, 2016 at 11:00 am

Tod #101: Thanks! Fixed.

Comment #104 December 21st, 2016 at 2:55 pm

mjgeddes #99

but the hard problem of the objective vs the subjective, mind/body, consciousness vs the physical doesn’t go away by saying that reality and simulations are equivalent.

I.e. the relation between computation and consciousness is just as mysterious as the relation between particles and consciousness.

We’ll never be able to explain why considering one (or two or three) atoms in isolation doesn’t give rise to consciousness but considering fifty trillion trillion of them would be a source of consciousness. All physical properties (like fields, energy, mass) are really additive in their effects, global systems can always be explained by the sum of the contributions of their individual parts (but maybe QM brings a special ingredient to this where a system is “greater” than the sum of its part?!).

Saying that consciousness is pure information processing (computation) doesn’t really help – fundamentally a computation is a way to “link” numbers (states) together, why would some numbers give rise to consciousness while other wouldn’t? E.g. all numbers exist regardless of the way we decide to link them. Is the linking the source of consciousness? How?

Maybe consciousness is a special thing that is neither physical nor information processing, with no causal power whatsoever, entirely “contemplative”. The brain is a thought/emotion/action factory that the mind does not control, and “being” is all about passive observation of the present moment. The impression of free will/agency would be an illusion of the mind, a way for it to rationalize the choices/actions decided by the physical brain, after the fact.

Comment #105 December 21st, 2016 at 3:05 pm

mjgeddes #99

“within physics, some arrangements of matter can start to form ‘self-representations’ of themselves…and it’s precisely these structures that are conscious! A new arrow of time is generated…the representation of causality IS causality , and this is consciousness!”

Right, I forgot to add that “memory” is rarely mentioned in discussions on consciousness.

The impression of action/agency isn’t required to feel conscious, but it would be hard to imagine how contemplation would be possible without some form of memory. And, at a general level, memory means that the present state contains previous traces of itself (so, some self-recursion).

Comment #106 December 22nd, 2016 at 7:08 am

This may be true of philosophical discussion of quantum dynamics, yet it is increasingly far from true for philosophy’s sister-disciplines of psychiatry and neurology. George Dawson’s weblog

Real Psychiatry: the Reality of Psychiatry rather than the Perception, in an essay “Advice to Residents” (Jan 31, 2015), has this to say:Dr. Dawson’s advice has a sardonic aspect: Eric Kandel is a Nobel-winning neurophysiologist trained

anda (Freudian) psychiatrist. His publication list is long: PubMed lists Kandel as (co)author of 163 scientific articles, and Amazon shows him as author of at least ten books, including classics likeBehavioural Biology of Aplysia: Contribution to the Comparative Study of Opisthobranch Molluscs(1977, out of print, one copy for sale, asking price $500, yikes). 🙂In particular, Kandel is lead coauthor (with Jessell, Siegelbaum, and Hudspeth) of the standard med-school text

Principles of Neural Science. At 1760 pages this behemoth of neuropsychiatric pedagogy exceeds in length every physics text (that is known to me at least). Thus it’s no small commitment to follow Dawson’s advice, and read all of Kandel’s immense body of work. 🙂The chief focus of Kandel’s work is memory in all its aspects: physical, mental, biological, medical, cultural, and philosophical. Are

quantumaspects of memory included in this span? The answer is “yes”, as illuminated by the quantum biomolecular physics that is surveyed in a recent preprint — a preprint of of outstanding quality (as it seems to me) — “Elucidating reaction mechanisms on quantum computers”, by Markus Reiher, Nathan Wiebe, Krysta M. Svore, Dave Wecker, and Matthias Troyer (2016, arXiv:1605.03590).Far more comprehensively than any other single work (known to me), the Reiher / Wiebe / Svore / Wecker / Troyer preprint analyzes the quantum computational resources required to address the biochemical “reaction mechanisms” that are associated to real-world biomolecular phenomena (such as the synaptic dynamics that are the biomolecular basis of memory).

In a nutshell, the Reiher / Wiebe / Svore / Wecker / Troyer analysis predicts that the quantum computational resources required are substantial, typically in the range of 10^6-10^9 physical qubits, performing 10^14-10^16 gate operations. If this quantum computational capacity is a goal toward which the quest for Quantum Supremacy seeks to guide us, then we had best prepare for a long and technologically challenging journey … yet a journey well-worth taking.

In summary, from a Quantum Supremacy perspective, the crucial accomplishment of research like Eric Kandel’s, is to establish medical research objectives of sufficiently universal importance, as to justify the stupendous investments (both professional and economic) that the Reiher / Wiebe / Svore / Wecker / Troyer preprint foresees will be required of any program to demonstrate Quantum Supremacy in practical biomolecular simulations.

Comment #107 December 23rd, 2016 at 11:05 pm

It turns out that when someone *doesn’t* consult with you for their quantum-computing-related comic, they end up violating the no-cloning theorem:

http://questionablecontent.net/view.php?comic=3376 (published just a few days ago)

Comment #108 December 26th, 2016 at 3:22 am

Scott, are all math proofs contained in NP. Is it possible for a quantum computer to resolve P vs NP, however verifying the solution takes exponential time. BQP is not contained in NP.

Comment #109 December 26th, 2016 at 6:15 pm

Harold #108,

It isn’t meaningful to talk about whether “proofs” are contained in NP without more qualification about what you mean. If you mean something like “Given a mathematical statement in some formalism (say Peano-Arithmetic or ZFC) and given that the statement is provably true, does there exist a proof of the statement whose length is bounded by a polynomial of the length of the statement” (with the polynomial being independent of the statement) then the answer is no, and this follows from Godel’s theorems.

If you mean, given a statement and a length n, is there is a proof of S with length at most n, then given suitable formulations this is in NP.

There’s no specific reason to think at this time that quantum computers are especially good at searching for proofs, so there’s no explicit reason(that I know of) to think that having a quantum computer would help resolve any of these questions. I’m also not sure what you mean by “verifying the solution takes exponential time”- it isn’t meaningful to talk about an individual problem taking exponential time in some context, just a class of problems.

Comment #110 December 27th, 2016 at 12:26 pm

cute quantum computing cartoon

https://www.ias.edu/ideas/2014/ambainis-quantum-computing