## Quantum Computing Since Democritus: New Foreword!

Time for a non-depressing post. Quantum Computing Since Democritus, which is already available in English and Russian, is about to be published in both Chinese and Japanese. (So if you read this blog, but have avoided tackling QCSD because your Chinese or Japanese is better than your English, today’s your day!) To go along with the new editions, Cambridge University Press asked me to write a new foreword, reflecting on what happened in the seven years since the book was published. The editor, Paul Dobson, kindly gave me permission to share the new foreword on my blog. So without further ado…

Quantum Computing Since Democritus began its life as a course that I taught at the University of Waterloo in 2006.  Seven years later, it became the book that you now hold.  Its preface ended with the following words:

Here’s hoping that, in 2020, this book will be as badly in need of revision as the 2006 lecture notes were in 2013.

As I write this, in June 2020, a lot has happened that I would never have predicted in 2013.  Donald Trump is the President of the United States, and is up for reelection shortly.  This is not a political book, so let me resist the urge to comment further.  Meanwhile, the coronavirus pandemic is ravaging the world, killing hundreds of thousands of people, crashing economies, and shutting down schools and universities (including mine).  And in the past few weeks, protests against racism and police brutality started in America and then spread to the world, despite the danger of protesting during a pandemic.

Leaving aside the state of the world, my own life is also very different than it was seven years ago.  Along with my family, I’ve moved from MIT to the University of Texas in Austin.  My daughter, who was born at almost exactly the same time as Quantum Computing Since Democritus, is now a first-grader, and is joined by a 3-year-old son.  When my daughter’s school shut down due to the coronavirus, I began home-schooling her in math, computer science, and physics—in some of the exact same topics covered in this book.  I’m now engaged in an experiment to see what portion of this material can be made accessible to a 7-year-old.

But what about the material itself?  How has it held up over seven years?  Both the bad news and the (for you) good news, I suppose, is that it’s not particularly out of date.  The intellectual underpinnings of quantum computing and its surrounding disciplines remain largely as they were.  Still, let me discuss what has changed.

Between 2013 and 2020, the field of quantum computing made a striking transition, from a mostly academic pursuit to a major technological arms race.  The Chinese government, the US government, and the European Union have all pledged billions of dollars for quantum computing research.  Google, Microsoft, IBM, Amazon, Alibaba, Intel, and Honeywell also now all have well-funded groups tasked with building quantum computers, or providing quantum-computing-related software and services, or even just doing classical computing that’s “quantum-inspired.”  These giants are joined by dozens of startups focused entirely on quantum computing.

The new efforts vary greatly in caliber; some efforts seem rooted in visions of what quantum computers will be able to help with, and how soon, that I find to be wildly overoptimistic or even irresponsible.  But perhaps it’s always this way when a new technology moves from an intellectual aspiration to a commercial prospect.  Having joined the field around 1999, before there were any commercial efforts in quantum computing, I’ve found the change disorienting.

But while some of the new excitement is based on pure hype—on marketers now mixing some “quantum” into their word-salad of “blockchain,” “deep learning,” etc., with no particular understanding of any of the ingredients—there really have been some scientific advances in quantum computing since 2013, a fire underneath the smoke.

Surely the crowning achievement of quantum computing during this period was the achievement of “quantum supremacy,” which a team at Google announced in the fall of 2019.  For the first time, a programmable quantum computer was used to outperform any classical computer on earth, running any currently known algorithm.  Google’s device, called “Sycamore,” with 53 superconducting qubits cooled to a hundredth of a degree above absolute zero, solved a well-defined albeit probably useless sampling problem in about 3 minutes.  To compare, current state-of-the-art simulations on classical computers need a few days, even with hundreds of thousands of parallel processors.  Ah, but will a better classical simulation be possible?  That’s an open question in quantum complexity!  The discussion of that question draws on theoretical work that various colleagues and I did over the past decade.  That work in turn draws on my so-called PostBQP=PP theorem from 2004, explained in this book.

In the past seven years, there were also several breakthroughs in quantum computing theory—some of which resolved open problems mentioned in this book.

In 2018, Ran Raz and Avishay Tal gave an oracle relative to which BQP (Bounded-Error Quantum Polynomial-Time) is not contained in PH (the Polynomial Hierarchy).  This solved one of the main open questions, since 1993, about where BQP fits in with classical complexity classes, at least in the black-box setting.  (What does that mean?  Read the book!)  Raz and Tal’s proof used a candidate problem that I had defined in 2009 and called “Forrelation.”

Also in 2018, Urmila Mahadev gave a protocol, based on cryptography, by which a polynomial-time quantum computer (i.e., a BQP machine) could always prove the results of its computation to a classical polynomial-time skeptic, purely by exchanging classical messages with the skeptic.  Following Urmila’s achievement, I was delighted to give her a \$25 prize for solving the problem that I’d announced on my blog back in 2007.

Perhaps most spectacularly of all, in 2020, Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen proved that MIP*=RE.  Here MIP* means the class of problems solvable using multi-prover interactive proof systems with quantumly entangled provers (and classical polynomial-time verifiers), while RE means Recursively Enumerable: a class that includes not only all the computable problems, but even the infamous halting problem (!).  To say it more simply, entangled provers can convince a polynomial-time verifier that an arbitrary Turing machine halts.  Besides its intrinsic interest, a byproduct of this breakthrough was to answer a decades-old question in pure math, the so-called Connes Embedding Conjecture (by refuting the conjecture).  To my knowledge, the new result represents the first time that quantum computing has reached “all the way up the ladder of hardness” to touch uncomputable problems.  It’s also the first time that non-relativizing techniques, like the ones central to the study of interactive proofs, were ever used in computability theory.

In a different direction, the last seven years have witnessed an astonishing convergence between quantum information and quantum gravity—something that was just starting when Quantum Computing Since Democritus appeared in 2013, and that I mentioned as an exciting new direction.  Since then, the so-called “It from Qubit” collaboration has brought together quantum computing theorists with string theorists and former string theorists—experts in things like the black hole information problem—to develop a shared language.  One striking proposal that’s emerged from this is a fundamental role for quantum circuit complexity—that is, the smallest number of 1- and 2-qubit gates needed to prepare a given n-qubit state from the all-0 state—in the so-called AdS/CFT (Anti de Sitter / Conformal Field Theory) correspondence.  AdS/CFT is a duality between physical theories involving different numbers of spatial dimensions; for more than twenty years, it’s been a central testbed for ideas about quantum gravity.  But the duality is extremely nonlocal: a “simple” quantity in the AdS theory, like the volume of a wormhole, can correspond to an incredibly “complicated” quantity in the dual CFT.  The new proposal is that the CFT quantity might be not just complicated, but literally circuit complexity itself.  Fanciful as that sounds, the truth is that no one has come up with any other proposal that passes the same sanity checks.  A related new insight is that the nonlocal mapping between the AdS and CFT theories is not merely analogous to, but literally an example of, a quantum error-correcting code: the same mathematical objects that will be needed to build scalable quantum computers.

When Quantum Computing Since Democritus was first published, some people thought it went too far in elevating computer science, and computational complexity in particular, to fundamental roles in understanding the physical world.  But even I wasn’t audacious enough to posit connections like the ones above, which are now more-or-less mainstream in quantum gravity research.

I’m proud that I wrote Quantum Computing Since Democritus, but as the years go by, I find that I have no particular desire to revise it, or even reread it.  It seems far better for the book to stand as a record of what I knew and believed and cared about at a certain moment in time.

The intellectual quest that’s defined my life—the quest to wrap together computation, physics, math, and philosophy into some sort of coherent picture of the world—might never end.  But it does need to start somewhere.  I’m honored that you chose Quantum Computing Since Democritus as a place to start or continue your own quest.  I hope you enjoy it.

Scott Aaronson
Austin, Texas
June 2020

### 46 Responses to “Quantum Computing Since Democritus: New Foreword!”

1. Harrison P Gross Says:

Thanks so much for publishing this Scott. As a lay-ish person (only a BMath) who has followed your blog for a while, I intend to print this new foreword out and tuck it into my copy of QCsD. I met you once in person when you were back in Waterloo, and we and two other students who were prospecting for an advisor went out for bubble tea. I pushed the conversation towards politics too much. I’m trying to get back to learning, even outside of academia, and the frankness and simplicity and openness of this blog is refreshing as always. I still haven’t made it very far, with my knowledge of classical computing being low, but this still does seem to be one of the best places to get no-nonsense takes on the state of quantum in both settings.

I hope that you and your family continue along and thrive in these turbulent times, and that we all can work together for a better future for humanity.

2. mjgeddes Says:

I do have a kindle copy, I was sceptical of ‘It From Qubit’ for quite a while, but now I’ve flipped right over (bit flipped!) to the opposite extreme, and I want to go even further than the most fanatical ‘It From Qubit’ supporters 😀

What I’ve realized is that we need to go to ‘Tegmark Level 5’ ! Why should even math and physics be taken as fundamental? If, as I do, you want to grant reality to both (mathemaical and physical reality), there’s simply no way to do that without either having to accept dualism ( which I don’t want to do), or else bite the bullet and say that even math and physics come from something more fundamental that can unify both within a single framework, and that can only be ‘information’ and ‘complexity’ !

You said

‘The new proposal is that the CFT quantity might be not just complicated, but literally circuit complexity itself.’

‘But even I wasn’t audacious enough to posit connections like the ones above, which are now more-or-less mainstream in quantum gravity research.’

Exactly. So why not carry this to the logical extreme?
Why not postulate that all of reality is literally nothing but information and complexity , *even math and physics themselves*

The idea is that it’s all information, and everything in reality comes from a ‘data compression’ , that is to say, even all of math and physics are emergent from the right information encoding/decoding. So I suggest that even all of math and physics are simply sub-branches of coding theory.

There’s something that smacks of an infinite regress in the idea, but that’s a feature, not a bug. As Scott said to Sean Carroll ,’ the definition of complexity is itself complex’ – in fact infinitely complex I suggest.

3. Saurabh S Says:

Can you please share the books or your notes on teaching physics maths and computer science to your 7 year old kid.

4. Quantum and p is np Says:

What are the consequences to these proposals if P is NP holds?

5. gilcu3 Says:

I have a doubt regarding the RE class, as far I know it includes only the computable problems, not the undecidable like the halting problem mentioned here. Am I wrong? And if yes can someone point me to some reference regarding this?
BTW I plan to read the book soon 🙂

6. Filip Says:

I think there’s nothing more satisfying than working on a niche area that survives the test of time. Not to mention having your thoughts and interests timestamped and then some years later proven to be important.

The only reason I have faith in humanity is that while most focus on short term rewards and status games, there’s a minority working on difficult ethical and scientific problems that aren’t mainstream at all but turn out to save (or improve the quality of life of) humans.

Congrats Scott 🙂 P.S. I hope you will record a video lecture with your first grader.

7. Nick Says:

QCSD is a great book. Congratulations on this minor milestone. Two (sets of) questions:

1. Do you have any involvement with these translations? Do you have any sense of how the text is rendered in different languages? Do you care?

2. What’s up with “Speaking Truth to Parallelism”? That was the name, right? I would buy it.

3. Will this foreward be “officially” published in English?

8. Scott Says:

Saurabh #3:

Can you please share the books or your notes on teaching physics maths and computer science to your 7 year old kid.

I’m planning for that to constitute my next book!

9. Scott Says:

Quantum and p is np #4:

What are the consequences to these proposals if P is NP holds?

To which proposals? The complexity=volume proposal in AdS/CFT? As far as I know, it wouldn’t be directly affected even by P=NP, although it certainly would be affected by P=PSPACE, which would rule the proposal out, as it would imply that the circuit complexity in question could never exceed a polynomial (even when the volume of the wormhole had become exponential).

10. Scott Says:

gilcu3 #5: No, RE is Recursively Enumerable, which means the class of all languages for which there’s a Turing machine to list all the yes-instances (not necessarily in order). That class of course includes the halting problem.

11. Scott Says:

Nick #7:

1. Do you have any involvement with these translations? Do you have any sense of how the text is rendered in different languages? Do you care?

For the Chinese edition, I met with the translator (who was then a student at MIT and—I was happy to see—an awesome guy with a sense of humor), wrote a special note for that edition (in English, to be translated), and helped him clarify various issues. I had no particular involvement with the Japanese edition besides giving it my approval. Alas, I read neither Chinese nor Japanese (I learned some Mandarin in school when I lived in Hong Kong at age 13, but have since forgotten nearly all of it!), so there’s no way I can vouch for the translations myself.

2. What’s up with “Speaking Truth to Parallelism”? That was the name, right? I would buy it.

The plan was shelved years ago, when it became clear that MIT Press would require a huge amount of additional work from me. Maybe it could be revived sometime in the future.

3. Will this foreward be “officially” published in English?

No plans for that at the moment.

12. historynoob Says:

There is something wrong with your blog.

I see a lot of spam posts like this one: https://scottaaronson-production.mystagingwebsite.com/?p=33953

13. Scott Says:

historynoob #12: Sorry about that! Yeah, I’ve been getting other complaints about spam, although I can’t reproduce them. Meanwhile, my WordPress dashboard tells me the problem is that my PHP installation is out of date and needs to be updated, but it gives zero instructions about how.

Bluehost remains horrible beyond belief and should be used by absolutely no one.

Does anyone here know how to update PHP in Bluehost?

14. Gerard Says:

Scott #9

> The complexity=volume proposal in AdS/CFT? As far as I know, it wouldn’t be directly affected even by P=NP, although it certainly would be affected by P=PSPACE, which would rule the proposal out

Do you have to go all the way to P = PSPACE to rule that out or would P = P^#P suffice ?

BTW: Is there some way to get superscripts in comments here ?

15. Scott Says:

Gerard #14: I don’t know how to get it from P=P#P, only from P=PSPACE. For more, see e.g. my Barbados lecture notes. I’m able to put superscripts in comments by using HTML tags; are other commenters unable to?

16. Gerard Says:

Scott #15

I haven’t tried submitting a comment with HTML tags but if I try to enter sup tags they get filtered out in the comment preview. From what I’ve been able to gather WordPress only allows a small subset of HTML tags in visitor comments and sup and sub aren’t among them. You might be able to get superscripted numerals with Unicode (if that’s accepted) but it wouldn’t work for symbols or most letters.

17. Sniffnoy Says:

Scott #15: Yeah in the past when I’ve tried to use <sub> and <sup> tags here in the comments they haven’t worked, hence why I stopped trying. IDK whether you have like special permission to use more tags as the blog owner or something, and if there’s a way you can adjust what tags are allowed for who.

Still, to make sure I’m not misremembering, let’s make a test right now:

If x2=y2=(xy)2=1, then xy=yx.

(AB)i,j = Σk Ai,k Bk,j

So, before I hit submit here, I should note that it certainly doesn’t work in the preview! Which means even if once I hit submit it ends up working, that means nobody will end up thinking it works, because they’re going to look at the preview to determine what works. (Although I have seen mismatches before — there are some HTML entities that I have observed to work in preview but fail when actually posting.)

18. mjgeddes Says:

I’ve wondering Scott, whether ‘complexity’ and ‘time’ are actually fundamentally the same thing ? I don’t mean it metaphorically or vaguely, I mean it *literally* and *precisely*

I know the multiverse conceptions so far are a bit of a mess, I’ve got to the point what I see a possible way to ‘repair’ these flawed notions – by introducing a new notion of time that differs from the conventional physics one – a sort of ‘super-time’ as it were, where time is *defined* as complexity!

If we go back to considering all of reality as literally information and complexity, then I think the complexity actually represents time dimensions !

I suggested reality was a ‘sphere of information’ in earlier post- but I think I gave the wrong number of dimensions, I said 3, let me change the number to 4.

Furthermore, I now think 2 dimensions of information, and 2 complexity dimensions, which are literally time dimensions! (4-sphere)

And now, perhaps, I’ve got it ! 😀

19. Gerard Says:

Scott #15

Looking at the Barbados lecture notes I take it that the connection between P = PSPACE and the “complexity = volume” proposal follows from Proposition 7.7.1. whose proof references Proposition 3.3.5 (which concerns quantum state complexity relative to some oracle A).

So it looks like what I need to understand is how 3.3.5 relates to P = PSPACE. But searching through the first 3 lectures for references to PSPACE, I haven’t been able to find an explicit connection that I can understand, or even any discussion of any properties specific to PSPACE other than the fact hat it it’s in a containment sequence between BQP and EXP, which is a property shared by PP and P^#P.

The only other mentions of PSPACE properties are the fact that that the above mentioned containment hierarchy remains valid relative to any oracle and that there exists an oracle A such that P^A = PSPACE^A. Since proposition 3.3.5 is also an oracle result maybe there is some connection here that I’m missing ?

I do see you bring up a P = PSPACE or P != PSPACE assumption a number of times, usually in the form of questions, but I’m not really seeing where those questions get explicit answers.

20. Douglas Knight Says:

Dear Sniffnoy,

If x²=y²=(xy)², then xy=yx
(AB)ᵢⱼ=ΣₓAᵢₓBₓⱼ

Is this a “shitpost”? ????

21. Gerard Says:

https://www.fool.com/investing/2020/06/21/honeywell-unveils-the-worlds-fastest-quantum-compu.aspx

about the Honeywell “highest performing quantum computer”, which apparently has all of 6 qubits. Wow !

Anyway it contains this sentence:

> Scientists expect quantum computers to handle problems that are essentially unsolvable with current technology in fields such as cryptography, weather forecasting, artificial intelligence, and drug development.

which, except for cryptography, is incorrect, as everyone here is well aware.

It seems like this has become the standard media spiel for quantum computers despite Scott’s best efforts.

22. Gerard Says:

Douglas Knight #20

If you can get it to correctly format P<sup>#P</sup> I’ll be impressed.

23. Scott Says:

Gerard #19: Sorry, you should’ve just asked me point-blank “why does PSPACE arise here?” 🙂

The reason why we get PSPACE is that we’re considering situations where a quantum state with n qubits evolves under some Hamiltonian for ~2n time, and we’re interested in the final result. Almost by definition, the simulation of such a machine is a BQPSPACE-complete problem, and it’s known that BQPSPACE=PSPACE.

24. Shmi Says:

If you are fed up with bluehost, consider setrahost.com. They migrate wordpress for you and have a good customer service. The speed is good to. (I’m not affiliated in any way.)

25. rrg Says:

Gerard #21: Quantum computers are useful for quantum chemistry simulations which are useful for drug development. Am I wrong?

26. Gerard Says:

rrg #21

Right, I missed that one.

27. Chaoyang Lu Says:

Great news! Chinese version!!

28. Chaoyang Lu Says:

I have an English version already – now I can read without a dictionary 🙂

29. asdf Says:

Yikes–Scott Alexander has taken down SSC after NY Times doxxed him. This sucks. Further info is on former SSC main page. Apparently this is a day or two old but I just found out about it a minute ago. Scott Double-A, you might want to post about it. The Hsu cancellation might also figure in somehow. The NYT is now a full-on yellow rag, though it sort of was already that.

I haven’t check Reddit yet but might look there.

More crap from 2020. Bah humbug.

30. Vampyricon Says:

Scott #11,

“(I learned some Mandarin in school when I lived in Hong Kong at age 13, but have since forgotten nearly all of it!)”

Greetings from Hong Kong!

I knew I should’ve waited a year before picking up QCSD when I read its foreword. Now I have to print this out and stick it onto the old edition.

31. I Says:

Scott, terrible news! Slatestarcodex has been deleted by other Scott.

32. John Smith Says:

Congratulations on the anniversary. Apologies for being unrelated to your above post, but did you hear that Slate Star Codex is now (perhaps permanently) down? What are your thoughts?

33. Gerard Says:

Scott #23

So let me see if I’ve got this right. To simulate an n-qubit quantum circuit with m gates requires performing m multiplications of 2ⁿ x 2ⁿ matrices (in case you’re wondering these are Unicode superscripts, which only exist for digits and a few lower-case letters).

Somehow this can be done with a polynomial number of calls (in n and m) to a #P oracle.

However if m = 2ⁿ then this problem is PSPACE-complete (in n).

But where does the 2ⁿ number of gates/timesteps come from ? Is that implicit in the construction of Proposition 3.3.5 ?

34. wolfgang Says:

The NYT knocked out slatestarcodex.

35. Mike Says:

Have you seen this?

https://slatestarcodex.com/

36. Douglas Knight Says:

Gerard,
In my text editor, the two subscripts are aligned and the pseudo-octothorpe is, while not octo, still thorpe.

Contrary to your claim, Unicode superscripts include all lower case Latin letters (but not all uppercase; and subscripts fail).

37. mjgeddes Says:

OK, so the ‘holographic principle’ suggests that perhaps you can decompose 3 physical spatial dimensions into 2 pseudo-dimensions right?

I’m thinking that there has to be something similar happening for time. It seems that there is only 1 *physical* time dimension, but perhaps time is a bit more complicated than physicists think it is, and it needs be decomposed into 2 pseudo-dimensions that are defined in terms of information/complexity.

It’s clear to me that something is very wrong with our current notions of time, and that’s why the ‘multiverse’ ideas don’t make sense – there’s the puzzle of what conscious observers should see for instance.

What I think has happened is that the notion of ‘time’ hasn’t been properly decomposed – it should be completely definable in terms of computational complexity, I’m thinking something like a 2-D ‘complexity space’ (1 physical time dimension = 2 informational dimensions?)

This may even be able to finally crack the nature of consciousness, which I’m now rather confident is closely related to our notions of time.

My current best guess is that phenomenal consciousness will turn out to be completely equivalent to a ‘complexity delta’ (change in complexity of a system), defined in terms of a 2-D ‘complexity space’.

So 2 abstract dimensions encode ordinary space, and I’m guessing that we need 2 more abstract dimensions to encode time, for a total of 4 abstract dimensions , all of which should be completely defined as information/complexity

38. Gerard Says:

Douglas Knight #36

In my browser at normal scale it looks plausibly like it should but my eyesight isn’t great so I have to zoom in pretty far to really tell and when I do that it doesn’t look much like #P. If I copy it to a terminal and boost the font size it looks vaguely like some Chinese character with a single vertical bar crossed by three horizontal bars instead of this: #. That’s also how it looks zoomed in on my Android phone.

Could you point me to information on the other Unicode super/sub-scripts ? The only ones I’ve been able to find are those between U+2070 and U+209C, plus three in the U+00Bx range.

39. Douglas Knight Says:

Gerard,
Everything I know is from the first two hits from google: wikipedia and stack overflow.

40. Sniffnoy Says:

OK but instead of all this futzing around with Unicode, Scott should really fix the <sub> and <sup> tags for everyone…

41. Gerard Says:

Sniffnoy #40

> OK but instead of all this futzing around with Unicode, Scott should really fix the and tags for everyone…

I would second that (though Latex support would be even better).

42. Scott Says:

Does anyone care enough about this superscript and subscript issue to volunteer to help me? For example, by figuring out which WordPress plugin I could install to fix the problem? Thanks in advance!

43. Gerard Says:

Scott #42

I’m willing to make some effort to help but I’m afraid I can’t promise too much because for the past 10 years I’ve been at the mercy of some, not fully explained, health condition that causes me to require at least 12 hours of sleep per day and prevents my brain from functioning properly for more than about 4 hours at a time.

I’ve noticed that you’ve expressed some dissatisfaction with your hosting provider. I’m wondering if you would consider migrating to wordpress.com (note: I’m just asking, not making a recommendation here, I haven’t researched it enough yet for that). However it does support Latex and both Terrence Tao and RJ Lipton’s blogs are hosted there.

Feel free to email me if you want to discuss any of this further privately.

44. Serge Says:

Does the convergence you mentioned between quantum information and quantum gravity mean that, for a nonzero mass, reaching the speed of light would amount to solving quickly a hard problem?

45. Scott Says:

Serge #44: No. There’s an old idea of using time dilation to get huge speedups for computation, but it doesn’t yield any advantage because of the energy needed to get to relativistic speed. In any case, that has nothing to do with gravity, and “the convergence of quantum information and quantum gravity” refers to ideas that are much more interesting and non-obvious.

46. mjgeddes Says:

Scott,

I think I finally understand what logic (type theory, set theory, category theory etc.) is really all about! I remember, you’ve expressed puzzlement as to what all that stuff is good for, and now I think I have the answer.

In short, I think mathematical logic is the natural mathematical setting for statistical mechanics! Physicists have failed to properly understand classical physics, and category theory is in fact the correct framework for a full understanding of it!

Just as algebra is the right framework for quantum mechanics and differential geometry is the right framework for relativity, my claim is that category theory IS the correct mathematics of statistical mechanics.

It’s very surprising, so a brief a explanation is in order. The claim comes from trying to understand reality in terms of information and complexity. Order theory (closely related to set theory) is about how to order information. And the computer science version of this would be domain theory.

Now domain theory is a computer science version of the idea of convergence and approximation, in terms of how information is ordered. And immediately this is suggestive something like the perceived advance of time (the entropic arrow of time), which can also be expressed in information theoretic terms, i.e., as statistical mechanics.

So category theory is actually the natural framework for thinking about complexity, the arrow of time, and time irreversibility. I would look at the central role that the *partition function* is playing in information theory, and I would consider how you could express that in terms of category theory.

It’s unbelievable that physicists seem to have totally missed this. Only John Baez may have had an inkling, but even he never explicitly stated it.

You can use rich HTML in comments! You can also use basic TeX, by enclosing it within  for displayed equations or  for inline equations.

Comment Policies:

1. All comments are placed in moderation and reviewed prior to appearing.
2. You'll also be sent a verification email to the email address you provided.
YOU MUST CLICK THE LINK IN YOUR VERIFICATION EMAIL BEFORE YOUR COMMENT CAN APPEAR. WHY IS THIS BOLD, UNDERLINED, ALL-CAPS, AND IN RED? BECAUSE PEOPLE ARE STILL FORGETTING TO DO IT.
3. This comment section is not a free speech zone. It's my, Scott Aaronson's, virtual living room. Commenters are expected not to say anything they wouldn't say in my actual living room. This means: No trolling. No ad-hominems against me or others. No presumptuous requests (e.g. to respond to a long paper or article). No conspiracy theories. No patronizing me. Comments violating these policies may be left in moderation with no explanation or apology.
4. Whenever I'm in doubt, I'll forward comments to Shtetl-Optimized Committee of Guardians, and respect SOCG's judgments on whether those comments should appear.
5. I sometimes accidentally miss perfectly reasonable comments in the moderation queue, or they get caught in the spam filter. If you feel this may have been the case with your comment, shoot me an email.