Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

November 15, 2006

Classical vs Quantum Computation (Week 6)

Posted by John Baez

Here are last week’s notes on Classical versus Quantum Computation:

  • Week 6 (Nov. 9) - Classical versus quantum lambda-calculus. From lambda-terms to string diagrams. Internalizing composition. The "untyped" lambda-calculus: building a computer inside the free cartesian closed category on an object XX such that Xhom(X,X)X \cong \mathrm{hom}(X,X). Church numerals and booleans.

The previous week’s notes are here; next week’s notes are here.

I’ll be flying to Baton Rouge this Thursday (Nov. 16), so there won’t be any classical vs quantum computation this week: instead, Derek Wise will lead the class on a tour of homogeneous spacetimes.

Posted at November 15, 2006 9:23 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1039

10 Comments & 2 Trackbacks

Re: Classical vs Quantum Computation (Week 6)

So your internal composition (p.3) is an example of the bimodule composition, you told us about.

Posted by: David Corfield on November 16, 2006 9:16 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 6)

I don’t see how internal composition is a special case of composition of bimodules. Nor do I see how composition of bimodules is a special case of internal composition. But, I know thing that are special cases of both, and things they’re both special cases of.

Posted by: John Baez on November 16, 2006 5:47 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 6)

I know things that are special cases of both

If we were working in the monoidal category of vector spaces over kk, and the bimodules were kkk-k-bimodules?

and things they’re both special cases of

If the monoidal category is seen as a one object bicategory, then internal composition is a certain 2-morphism across a triangle of 1-morphisms. The tensor product of bimodules can also be seen as such a 2-morphism in a bicategory.

Posted by: David Corfield on November 17, 2006 9:41 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 6)

These are great notes!

I have a quibble, though. The theorem at the bottom of p.4 states that if C\mathbf{C} is a category and α:AB\alpha: A \rightarrow B is an isomorphism in C\mathbf{C} then there exist a category C\mathbf{C'} and an equivalence F:CCF: \mathbf{C} \rightarrow \mathbf{C'} such that F(A)=F(B)F(A) = F(B) and F(α)=1 F(A)F(\alpha) = 1_{F(A)}.

Let C\mathbf{C} be the two-element group {1,α}\{ 1, \alpha \}, regarded as a category with single object AA. If there exist FF and C\mathbf{C'} as in the Theorem then F(α)=1 F(A)=F(1 A)F(\alpha) = 1_{F(A)} = F(1_A). But α1 A\alpha \neq 1_A, so FF is not faithful: contradiction.

The same problem occurs whenever A=BA = B and α\alpha is a non-trivial automorphism of AA.

I agree, though, that you can force A=BA = B by passing to an equivalent category.

Posted by: Tom Leinster on November 16, 2006 8:36 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 6)

Thanks for the correction, which I’ve noted in the errata.

Ironically, the theorem stated in the notes becomes true if we add the hypothesis ABA \ne B.

Ironically, because the point of the theorem is to show that up to equivalence, you can pretend isomorphic objects AA and BB are equal, and that your chosen isomorphism is the identity. And, you can only do this if AA and BB are not equal.

(Of course you’re right that we can always pretend isomorphic objects are equal, but that may not be good enough for my application.)

This correction made me realize I need to think harder about some other issues, and probably make some other corrections. But, not tonight.

Posted by: John Baez on November 21, 2006 8:54 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 6)

Right, agreed: you can do it if ABA \neq B. Strange!

Posted by: Tom Leinster on November 21, 2006 7:21 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 6)

John, can you explain why you’re interested in lambda calculus? If it’s just that it’s one of your atomic interests, then that’s of course fine, but I suspect your interest in it is based on something else, or at least it originally was. I feel like I’m missing the point of all this lambda stuff, and I’d like to know what it is!

Posted by: James on November 17, 2006 4:48 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 6)

James wrote:

John, can you explain why you’re interested in lambda calculus? If it’s just that it’s one of your atomic interests, then that’s of course fine, but I suspect your interest in it is based on something else, or at least it originally was.

Great question! Indeed, it’s always upsetting when someone whose work I’m following seems to suddenly switch interests in a discontinuous way - it makes me wonder if I missed some connecting link, or they just got bored with what they’d been doing and jumped to something new. Is there a deeper integrity to their life work, or is it just a bunch of disconnected pieces?

I think about this issue a lot these days - especially in music, where (for example) Miles Davis repeatedly stumped his old fans by switching styles, and Bob Dylan annoyed his by “going electric”. I think the music they made is more enjoyable when you can see the deeper continuities running through their work.

Anyway: for a long time my goal has been to unify our understanding of spacetime with our theory of quantum processes: that’s the big challenge of quantum gravity. So, I got really excited when Rovelli and Smolin introduced spin networks in loop quantum gravity. Spin networks blend in a very nice way some primitive aspects of geometry (graphs) with some primitive aspects of quantum theory (group representations), to give a description of quantum states of the geometry of space.

But, we need to get spacetime into the picture. So, Reisenberger, Rovelli and I introduced spin foams, which are 2-dimensional cell complexes labelled by group representation data. The point is that a slice of a spin foam gives a spin network, just like a slice of spacetime gives a “space”. We can also think of spin foams as a 2-dimensional generalization of Feynman diagrams, which describe the time evolution not of 0-dimensional point particles but of 1-dimensional spin networks.

But, since spin networks already include Feynman diagrams as a special case (taking the group to be the Poincaré group), something funny is going on here: spin foams are like meta-Feynman diagrams going between Feynman diagrams.

This sounds vaguely 2-categorical, and that’s no coincidence. I’d been working on n-categories in parallel with quantum gravity, hoping the two strands of research would converge someday. So for me, right from the start, spin foams were a way to push physics in the direction of nn-categories.

But, I wanted to see if spin foams could really work as a theory of quantum gravity. So, I spent a bunch of time working with Christensen and Egan on computer calculations with specific spin foam models, trying to see if any reduce to general relativity in the classical limit. The results were sort of depressing: nothing worked the way I expected, and it became ever more clear that we didn’t even know the right questions to ask. So, after a couple of years of this, I decided to give up - or at least take a break. Now Rovelli has some new ideas on this and may be making progress. But I think my skills lie elsewhere.

So, I decided to tackle some other projects. One is higher gauge theory. Another is more philosophical in nature. How can the same gadget - a spin network, or if you prefer, a Feynman diagram - look like a topological entity on the one hand (a graph), and on the other hand represent a quantum process? The answer is that a certain class of categories - symmetric monoidal categories with duals - are simultaneously “spatial” and “quantum-mechanical” in nature. If you think about things this way, it soon becomes clear that many quantum quandaries dissolve if you take this viewpoint: Hilbert spaces and operators are more like “spaces” and “spacetimes” like sets and functions.

Sets and functions form a symmetric monoidal category, but not with duals: they form a cartesian closed category. I had heard many times that cartesian closed categories and the lambda calculus are important for understanding computation, but I never quite understood what that meant. So, I’ve been trying to figure out what people were saying. Since n-categories are a very general formalism for understanding processes, metaprocesses, etc., it would be interesting if we could use them to understand how processes of computation do or don’t resemble the physical processes described by Feynman diagrams.

This is not as crazy as it might first seem, since category-theoretic computer scientists like to use diagrams for describing processes of computation: flow charts, proof nets, and more. And, some of them are even using higher-dimensional diagrams to describe “metaprocesses”, very much like spin foams.

Things get even more interesting when you throw quantum computation into the mix - this lets us see quantum processes as computations of their own special sort, which forbid duplication and deletion of quantum data, but allow entanglement and teleportation. All these differences arises from the difference between symmetric monoidal categories with duals, and cartesian closed categories.

So, in these lectures, I’ve so far been explaining the lambda calculus using diagrams which apply equally well to cartesian closed categories and symmetric monoidal categories with duals: the world of classical computation, and the world of quantum mechanics. These diagrams include Feynman diagrams (or spin networks) as a special case. Next - after I finish sketching how you can build a universal computer using the lambda calculus - I’ll show how you can (and should!) categorify all this stuff to make the process of computation visible. The resulting higher-dimensional diagrams will include spin foams as a special case.

I’m not sure where all this is going, but you can think of it as an extended meditation on the notions of “process”, “metaprocess” and so on - which are really what nn-categories are all about. Spacetimes, quantum processes, computations, proofs… they all seem to fit into a unified framework, and it’s fascinating to figure how they’re related.

Posted by: John Baez on November 17, 2006 9:10 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 6)

Thanks! I’ll have to ruminate a bit on all that.

Posted by: James on November 18, 2006 6:32 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 6)

Reisenberger, Rovelli and I introduced spin foams

[…]

I decided to tackle some other projects. One is higher gauge theory.

A spin network (in gauge theory known as a Wilson loop network) is a functional on a space of connections.

A spin foam should be a functional on a space of 2-connections.

More precisely (I am saying this for potential laymen reading this), a Wilson network is not just any functional, but one coming from evaluating the parallel transport of a connection on a given graph drawn in the connection’s base space and colored in Rep(G)\mathrm{Rep}(G).

Similarly, a spin foam (or “Wilson foam”) should be a functional coming from evaluating the parallel surface transport of a G 2G_2 2-connection on a “2-graph” drawn in the connection’s base space and colored in Rep(G 2)\mathrm{Rep}(G_2).

The “spin” in “spin foam” refers to the application of this general idea to gravity, when the latter is regarded as a gauge theory of Spin(n,1)\mathrm{Spin}(n,1)-connections.

I gather that the general idea that has emerged here is that that BF-theory # with structure 2-group the Poincaré-2-group should have a deformation # that yields Einstein-Hilbert gravity. (I also gather that classically this is easy to demonstrate. The problem is to use this in quantizing Einstein-Hilbert.)

It seems that BF-theory should be the theory of a 2-connection (or maybe rather of a 4-connection obtained from that - analogous to how Chern-Simons theory is a theory of a 3-connection coming from a 1-connection). If so, this would naturally want us to consider “Wilson foam” observables of the theory. (Even at the classical level, already.)

Whether or not “Wilson foams” have an application to quantum gravity or not, I would like to understand them in general.

It is clear what is needed: first of all a good understanding of 2-reps of 2-groups. Then a good notion of 2-trace # in 2-reps in 2-groups. This suffices to do the higher analog of Wilson loops.

For the higher analog of Wilson networks we’d also need a good understanding of intertwiners of 2-reps, i.e. of the monoidal structure and the morphisms in Rep(G 2)\mathrm{Rep}(G_2).

Posted by: urs on November 18, 2006 1:12 PM | Permalink | Reply to this
Read the post Classical vs Quantum Computation (Week 7)
Weblog: The n-Category Café
Excerpt: Building a computer using the lambda calculus: the Fixed Point Theorem.
Tracked: November 21, 2006 9:53 PM
Read the post Classical vs Quantum Computation (Week 8)
Weblog: The n-Category Café
Excerpt: How Curry's Fixed Point Theorem is related to Cantor's diagonal argument.
Tracked: December 1, 2006 1:42 AM

Post a New Comment