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.

October 6, 2006

Classical vs Quantum Computation (Week 1)

Posted by John Baez

Here are yesterday’s notes on classical versus quantum computation:

  • Week 1 (Oct. 5) - Types and operations. Categories as theories. Monoidal categories versus categories with finite products - also known as “cartesian categories”.
    • Homework: show that every category with finite products can be made into a monoidal category - see above notes for details.

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

Faithful readers of this blog will see that among other things, I’m preparing the students for Lawvere’s mindblowing theory of doctrines. I’m also teaching them the tao of mathematics, by showing a bunch of ways you could get the definition of monoidal category wrong.

As I explained in the seminar, a good graduate course in mathematics should require not just that students prove theorems, but also guess the right definitions. Good definitions slice the concepts neatly, instead of hacking away at them. To make good definitions, you have to learn the tao of mathematics. For example:

  • The Indians contributed nothing to mathematics - and it’s been incredibly useful ever since. Definitions involving sets should apply to the empty set without special exceptions. Similarly, definitions should apply to all natural numbers, not just nn > 0.

    For example, when you have binary associative product, which lets you define nn-ary products for all nn > 0, you should also have a unit, which lets you define 0-ary products. This comes up in the definition of “monoid”, and also - as we saw in this lecture - the definition of “monoidal category”. A monoidal category has a tensor product - so it wants to have a unit, too!

  • Don’t say two objects in a category are equal, and don’t just say they’re isomorphic: specify an isomorphism between them. And, if this isomorphism depends on a parameter, it should be a natural isomorphism.

    This too comes up in the definition of monoidal category, when we’re trying to impose the laws governing the tensor product and unit.

These are just two of many rules of thumb a good mathematician should know. Like all rules of thumb, they admit exceptions - but they’re still important to know.

Right now math grad students have to pick up these rules of thumb in a hit-or-miss way. Maybe someday we’ll write a book about them!

Posted at October 6, 2006 8:09 PM UTC

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

8 Comments & 0 Trackbacks

Re: Classical vs Quantum Computation (Week 1)

Through the notes (top of page 10), you write:

To allow many inputs & many outputs we need monoidal categories — i.e. categories with a “tensor product” so we have morphisms like

f: A1 ⊗ ⋅⋅⋅ ⊗ An → B1 ⊗ ⋅⋅⋅ ⊗ Bm

The kind of operation that we get directly from the lambda calculus, such as λxyz.t, has many inputs but only one output. For this, we don’t need a tensor category but rather (merely) a multicategory. Here, there is no notion of tensor product, but instead the fundamental notion is multimorphism, a generalisation of a function of many variables (as in the category of sets) or multilinear transformation (as in a category of linear spaces).

Of course, I know that you’re working towards CCCs, so you’ll eventually give your categories far more structure than this —enough structure to handle the pairing operations in lambda calculus. So there’s no harm in skipping multicategories (which, after all, are more complicated to define than monoidal categories —see my attempt to write it out). But it’s worth pointing out to interested people that they’re there.

(PS: Also, the TeXnician in me must point out that there should be a comma after “i.e.”. Please forgive me.)

Posted by: Toby Bartels on October 6, 2006 11:48 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 1)

Toby wrote:

For this, we don’t need a tensor category but rather (merely) a multicategory.

Right! In case you missed it, we had a nice little chat about multicategories and operads here - you may enjoy Tom Leinster’s terminological crustiness.

There are indeed many levels of structure that are interesting to put on a category, but right now I’m heading for symmetric monoidal closed categories as quickly as possible, so I can compare cartesian closed categories (which are “classical” in flavor, or at least “intuitionistic”) and compact closed symmetric monoidal categories (which are more “quantum”). So, I can’t afford to take the scenic route. Maybe later in the year…

But the cool part is that this blog can fill some of the holes left in my lectures. So, thanks for bringing up multicategories!

Posted by: John Baez on October 7, 2006 8:31 AM | Permalink | Reply to this

Contexts.

From the bottom of page 8:

Then we think of the functor F: T → C as a model of the theory T in the context C.

This reminds me of contexts in proof theory, except that there we like to look at morphisms out of a context instead of morphisms into a context. Is this an example of the duality of syntax and semantics?

Posted by: Toby Bartels on October 15, 2006 1:09 AM | Permalink | Reply to this

Re: Contexts.

Toby wrote:

This reminds me of contexts in proof theory, except that there we like to look at morphisms out of a context instead of morphisms into a context.

I don’t know about that proof theory stuff. Can you give me a two-sentence introduction?

I don’t think “context” is a standard name for the category in which a model lives; I just didn’t know a standard name, and this name seemed to make sense.

I hear λ\lambda-calculators talking a lot about “terms-in-context”, but that’s something else. It’s more related to proof theory, in fact! Maybe it’s related to what you just mentioned?

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

Re: Contexts.

I don’t know about [contexts in] proof theory […]. Can you give me a two-sentence introduction?

When I first wrote that comment, I tried to. By the time it was done, it was 4 paragraphs, didn’t really explain anything, and might not have been correct. So for now, I refer you to Chapter 8 in Paul Taylor’s Practical Foundations of Mathematics. This is probably not the best introduction, but it’s where I first learned of them (and which does cover the category of contexts).

Actually, I wish that I could give a two-sentence introduction, because I think that the concept is very important and needs to be more widely understood. Context in a formal proof-theoretic setting tend to be very staid creatures: a list of variables and hypotheses. But really, the context of a proof consists of all of the assumptions that you make in order for the reasoning to be valid. Every proof ought to be presented with its context, even if this is nothing more complicated than “classical mathematics”.

I keep trying to say more, then deleting it because it’s not coherent. I have strong opinions about this, but I’m not sure what they are! In any case, they’re rather removed from the subject here ….

Posted by: Toby Bartels on October 22, 2006 4:18 AM | Permalink | Reply to this

Re: Contexts.

I wrote in part:

Context[s] in a formal proof-theoretic setting tend to be very staid creatures: a list of variables and hypotheses.

I should point out that there’s already an example on this blog. (Even relevant to the topic!)

Posted by: Toby Bartels on October 27, 2006 8:58 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 1)

So… week 2?

Posted by: John Armstrong on October 15, 2006 6:35 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 1)

Sorry, the week 2 notes were a bit delayed - that’ll happen a lot. But, they’re available now!

Posted by: John Baez on October 18, 2006 3:12 AM | Permalink | Reply to this

Post a New Comment