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 2, 2006

Classical vs Quantum Computation (Week 5)

Posted by John Baez

Here are the notes for the latest installment of my course on Classical versus Quantum Computation:

  • Week 5 (Nov. 2) - Theorem: evaluating the "name" of a morphism gives that morphism! The naturality of currying. A new "bubble" notation for currying and uncurrying. Popping bubbles to reveal the quantum world.

Last week’s notes are here; next week’s notes are here.

Last week I said that a monoidal category CC is closed if for each object AA there is a functor hom(A,):CC\mathrm{hom}(A, -) : C \to C which is right adjoint to tensoring with AA: A:CC - \otimes A : C \to C This means that there’s a natural isomorphism Hom(A,)Hom(,hom(A,)) Hom(- \otimes A, --) \cong Hom(- , \mathrm{hom}(A, --)) called currying.

Today, we actually used the naturality of this isomorphism to prove something interesting! We’ve already seen that every morphism f:AYf: A \to Y has a name: "f":Ihom(A,Y). "f" : I \to \mathrm{hom}(A,Y). We also have an evaluation morphism: ev:hom(A,Y)AY ev: \mathrm{hom}(A,Y) \otimes A \to Y Here we show that evaluating the name of ff, as follows: AIA"f"1 Ahom(A,Y)AevY A \cong I \otimes A \stackrel{"f" \otimes 1_A}{\to} \mathrm{hom}(A,Y) \otimes A \stackrel{ev}{\to} Y gives back ff, as it should.

In preparing to give this proof, I realized that a slightly different string diagram notation for currying and uncurrying would be very nice. So, after giving the proof I explain this new notation. It’s copied after the usual notation for compact categories, where hom(A,Y)YA *.\mathrm{hom}(A,Y) \cong Y \otimes A^*. But, it uses “bubbles” to remind us that certain parts of the picture shouldn’t be taken too literally. In the compact case we can “pop” these bubbles and our equations remain true.

The cute thing about this is that the compact case is applicable to quantum logic, while other sorts of monoidal closed categories (like cartesian ones) are applicable to classical or intuitionistic logic. So, our bubble diagrams make sense in all these forms of logic - but when we pop the bubbles, they only make sense in quantum logic.

So, we can “pop the bubbles to reveal the quantum world”! I’m not sure yet how important this is, or what it really means. But, it’s cool.

Posted at November 2, 2006 9:45 PM UTC

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

7 Comments & 1 Trackback

Notation for currying.

You can really see the “zipper” on the top of page 7, not so well on the bottom of page 6.

It occurs to me that you don’t really need to draw either the bubbles or the zipper/ribbon. That is, the diagrams are unambiguous without these marks. On the other hand, drawing them in helps ensure that your diagrams are legitimate!; I suppose that this is why you keep them.

Posted by: Toby Bartels on November 3, 2006 12:27 AM | Permalink | Reply to this

Re: Notation for currying.

Toby wrote:

You can really see the “zipper” on the top of page 7, not so well on the bottom of page 6.

These zippers are your idea, Toby. Derek drew the beautiful pictures in these notes based on my less beautiful pictures on the blackboard, and for some reason he really got into emphasizing the zippery look of currying and uncurrying on pages 7 and 8.

I don’t think Derek has had time to follow the n-Category Café lately - he’s been busy going to conferences, writing his thesis and applying for jobs! He’s also busily trying to finish writing up beautiful notes for two sessions of the quantization and cohomology course which took place while he was travelling.

But, I mentioned your zipper idea in class, and I guess he liked it.

It occurs to me that you don’t really need to draw either the bubbles or the zipper/ribbon. That is, the diagrams are unambiguous without these marks.

I mentioned this possibility at the very end of class, when I was discussing the bubbles. But, I haven’t carefully checked to see if it’s true - I just came up with this bubble notation last night.

It would be great if these bubbles and zippers are unnecessary. The notation would become much lighter and more suggestive of the compact case. Of course, it might still be good to include the bubbles and zippers in some theorem saying they can be deleted without ambiguity.

If such a theorem is true, maybe it’s a consequence of some 2-functor between the the 2-category of compact categories and the 2-category of monoidal closed categories.

Posted by: John Baez on November 3, 2006 4:58 AM | Permalink | Reply to this

Re: Notation for currying.

John wrote in part:

Toby wrote:

You can really see the “zipper” on the top of page 7, not so well on the bottom of page 6.

These zippers are your idea, Toby.

I know; my point is that this idea works in (contexts like) the diagram on the top of page 7 but not so well in (contexts like) the diagram on the top of page 6. Well, Derek’s diagrams work pretty well in any case; it’s really just the term “zipper” that works better in one case than in the other.

It occurs to me that you don’t really need to draw either the bubbles or the zipper/ribbon. That is, the diagrams are unambiguous without these marks.

It would be great if these bubbles and zippers are unnecessary. […] But, I haven’t carefully checked to see if it’s true

Actually, I’ve just decided that it’s not true (except when the category is compact). This is because Hom(A, B ⊗ C) is not equivalent to B ⊗ Hom(A, C), except when the category is compact (try C := 1). These may be distinguished in a diagram by the width of the zipper/ribbon.

The bubbles may yet be unnecessary, given the zippers. My intuition suggests as much, but my track record is pretty bad at this sort of thing.

Posted by: Toby Bartels on November 3, 2006 10:40 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 5)

Hi, I have some questions/comments about these really cute diagrams. I think getting string-like diagrams for closed monoidal categories will be a great achievement, in the same way Burroni’s diagrams for cartesian categories were (original paper here).

For now, bubbles have the status of graphical decorations for intuition: this is already a really fine quality but they have no formal status in the categorical structure one studies. This is a question that I want to answer for some years now: how to describe the algebraic structure of such bubbles/boxes. This means finding which additional “algebraic” operations and relations does a monoidal category (or rather a 2-category) requires to be a closed monoidal category.

By algebraic operations, I mean something like additional generating 2-cells. This could be even more general, like 2-cells with “holes”, representing “polygraphical operations” (a not yet existing generalization of Burroni’s graphical algebras…). One of the first questions I try to answer is: how to represent hom(x,y*z), for objects x, y and z (or 1-cells in the corresponding 2-category)?

By algebraic relations, I mean additional 3-cells giving the behaviour of the additional 2-cells. For example, all the relations given in the last pages of the notes, such as the generalized “zigzag” identities.

I think getting such a formal presentation of closed categories will allow one to completely describe, in the language of n-categories, objects like the lambda-calculus and first-order proofs. This would be a major step towards making n-categories a language for the foundations of mathematics…

More practically, giving a full formal description of “zippers” and “bubbles” is the first step towards such a Skolem-like theorem:

It would be great if these bubbles and zippers are unnecessary. The notation would become much lighter and more suggestive of the compact case. Of course, it might still be good to include the bubbles and zippers in some theorem saying they can be deleted without ambiguity.

Posted by: Yves Guiraud on November 3, 2006 10:13 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 5)

I’ve been lurking here, reading and learning a small part of the presentation. I took Category Theory in Grad School back when dinosaurs walked the Earth, i.e. 1975-1977. We did read Goguen at the time. My question is motivational. It may be obvious to you, but I wonder why it is so earnestly desired: “I think getting such a formal presentation of closed categories will allow one to completely describe, in the language of n-categories, objects like the lambda-calculus and first-order proofs. This would be a major step towards making n-categories a language for the foundations of mathematics…”

Why is it intuited, or partly proven so far, that foundational Mathematics and Computer Science and Physics in n-Cat terms is superior to alternatives?

Just wondering. No basis to demand an answer, either wearing my Math, CS, or Physics hat.

Sincerely,

Jonathan Vos Post

Posted by: Jonathan Vos Post on November 3, 2006 10:55 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 5)

Jonathan Vos Post writes:

Why is it intuited, or partly proven so far, that foundational Mathematics and Computer Science and Physics in n-Cat terms is superior to alternatives?

This is a big question, and this whole blog can be seen as an attempt to answer it.

I don’t think “superior to alternatives” is the main point here. The main point is that n-categories are a good extra tool in our arsenal, since they let you categorify your existing insights, and squeeze more juice out of them.

This passage from my paper with James Dolan, Categorification, begins to explain what that means:

Though the concept it refers to has been lurking in the collective subconscious of mathematics for over a century, gradually becoming conscious, the term ‘categorification’ was invented only rather recently, by Crane. Categorification is the process of finding category-theoretic analogs of ideas phrased in the language of set theory, using the following analogy between set theory and category theory:

elements          objects

equations isomorphisms between elements between objects
sets categories
functions functors
equations natural between isomorphisms functions between functors

Just as sets have elements, categories have objects. Just as there are functions between sets, there are functors between categories. Interestingly, the proper analog of an equation between elements is not an equation between objects, but an isomorphism. More generally, the analog of an equation between functions is a natural isomorphism between functors.

For example, the category FinSet\mathrm{FinSet}, whose objects are finite sets and whose morphisms are functions, is a categorification of the set \mathbb{N} of natural numbers. The disjoint union and Cartesian product of finite sets correspond to the sum and product in \mathbb{N}, respectively. Note that while addition and multiplication in \mathbb{N} satisfy various equational laws such as commutativity, associativity and distributivity, disjoint union and Cartesian product satisfy such laws only up to natural isomorphism

If one studies categorification one soon discovers an amazing fact: many deep-sounding results in mathematics are just categorifications of facts we learned in high school! There is a good reason for this. All along, we have been unwittingly ‘decategorifying’ mathematics by pretending that categories are just sets. We ‘decategorify’ a category by forgetting about the morphisms and pretending that isomorphic objects are equal. We are left with a mere set: the set of isomorphism classes of objects.

To understand this, the following parable may be useful. Long ago, when shepherds wanted to see if two herds of sheep were isomorphic, they would look for an explicit isomorphism. In other words, they would line up both herds and try to match each sheep in one herd with a sheep in the other. But one day, along came a shepherd who invented decategorification. She realized one could take each herd and ‘count’ it, setting up an isomorphism between it and some set of ‘numbers’, which were nonsense words like ‘one, two, three,…’ specially designed for this purpose. By comparing the resulting numbers, she could show that two herds were isomorphic without explicitly establishing an isomorphism! In short, by decategorifying the category of finite sets, the set of natural numbers was invented.

According to this parable, decategorification started out as a stroke of mathematical genius. Only later did it become a matter of dumb habit, which we are now struggling to overcome by means of categorification. While the historical reality is far more complicated, categorification really has led to tremendous progress in mathematics during the 20th century. For example, Noether revolutionized algebraic topology by emphasizing the importance of homology groups. Previous work had focused on Betti numbers, which are just the dimensions of the rational homology groups. As with taking the cardinality of a set, taking the dimension of a vector space is a process of decategorification, since two vector spaces are isomorphic if and only if they have the same dimension. Noether noted that if we work with homology groups rather than Betti numbers, we can solve more problems, because we obtain invariants not only of spaces, but also of maps. In modern parlance, the nth rational homology is a functor defined on the category of topological spaces, while the nth Betti number is a mere function defined on the set of isomorphism classes of topological spaces. Of course, this way of stating Noether’s insight is anachronistic, since it came before category theory. Indeed, it was in Eilenberg and Mac Lane’s subsequent work on homology that category theory was born!

For more on what you can do with categorification, try reading the rest of this paper - or for something easier, the Tale of n-Categories.

Posted by: John Baez on November 6, 2006 6:38 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 5)

Jonathan Vos Post writes:

Why is it intuited, or partly proven so far, that foundational Mathematics and Computer Science and Physics in n-Cat terms is superior to alternatives?

I did not mean that n-categories were superior to another known language for the foundations of mathematics: I think it is just a matter of taste! More languages mean more tastes satisfied… Furthermore, as far as foundations are concerned, I do not think that we can really prove one point of view to be superior to another one, but I cannot prove that either ;)

So, in order to give a partial answer to the original question, I like the algebraic homogeneity provided by n-categories to the study of “mathematical structures with a notion of computation”. Let me give the two main examples I have studied in computer science and proof theory, from one possible n-categorical point of view.

For example, in term rewriting (i.e. directed “universal” algebras), one considers computations on terms, which are arrows in an algebraic theory. Furthermore, computations are compatible with the algebraic theory structure. Since algebraic theories are special 2-categories, and since computations on n-arrows are (n+1)-arrows, term rewriting systems are a subclass of 3-categories.

This phenomenon also occurs with normalization of proofs in propositional logic: proofs are 3-arrows and computations on them are 4-arrows.

Both examples here are limited: they do not give a n-categorical description of lambda-calculus nor first-order logic, since the theory does not yet know how to handle the abstraction of the first (currying) or of the quantifiers of the second. I think that understanding the algebraic status of the bubbles and zippers in the nice diagrams of these course notes is one possible way to go. And then one should be able to write mathematics in the language of n-categories… but only if one wants to!

Posted by: Yves Guiraud on November 6, 2006 9:47 AM | Permalink | Reply to this
Read the post Classical vs Quantum Computation (Week 6)
Weblog: The n-Category Café
Excerpt: From lambda-terms to string diagrams. Building a computer inside a cartesian closed category with an object X with X ≅ XX.
Tracked: November 15, 2006 9:40 PM

Post a New Comment