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.

August 28, 2006

Quantum Computation and Symmetric Monoidal Categories

Posted by John Baez

This entry is an excuse to start talking about generalizations of cartesian closed categories (CCCs) suitable for quantum computation. In this discussion, let’s focus on symmetric monoidal categories with duals. Unlike CCCs, these don’t let us duplicate or delete information - as Wootters and Zurek put it, you can’t clone a quantum. But, they permit quantum entanglement, since a state of a two-part system needn’t be just a state of each of its two parts.

All this comes from the fact that the tensor product needn’t be cartesian. On the other hand, the presence of duals for objects lets us draw morphisms as diagrams with lots of input wires and output wires, where we can take any input and bend it around to become an output, or vice versa. These diagrams are a generalization of the Feynman diagrams that physicists know and love:

feynman.diagram

In quantum field theory, such diagrams describe how particles come in and go out… but in quantum computation, they describe how data flows in and flows out! They’re like “quantum flow charts”.

I’ll start by listing some references….

For the easiest introductions to this stuff, try these:

The first is written for philosophers who only know a little math. All four have lots of pictures - that’s part of the fun here!

To dig a bit deeper, try these:

You’ll see lots of diagrammatic reasoning in symmetric monoidal categories here!

There are also attempts to define a “quantum lambda calculus”. Various flavors of this should provide a syntax for various flavors of symmetric monoidal closed category, just as the lambda calculus provides a syntax for cartesian closed categories:

There is also a whole lot of work on linear logic, but I’ll only mention two kinds of linear logic, which both apply to the category of finite-dimensional Hilbert spaces:

It’s probably worth listing some definitions here. Suppose CC is a symmetric monoidal category. Then we say:

  • CC is closed if the functor of tensoring with any object xCx \in C: axa a \to x \otimes a has a right adjoint, the internal hom bhom(x,b). b \to hom(x,b) . In other words, we have a natural isomorphism HOM(xa,b)HOM(a,hom(x,b)). HOM(x \otimes a, b) \cong HOM(a, hom(x,b)). Here HOM denotes the usual set of morphisms from one object to another, while hom is the “internal hom”, which is an object in our category.

  • CC has duals for objects if it is closed and for any object xCx \in C there is an object x *Cx^* \in C, the dual of xx, such that hom(x,b)x *b hom(x,b) \cong x^* \otimes b for all bCb \in C. If CC has duals for objects, it’s common for category theorists to say CC is compact or compact closed; algebraic geometers say it’s rigid.

  • CC has duals for morphisms if for any morphism f:abf : a \to b there is a morphism f :baf^\dagger: b \to a such that f =f f^{\dagger \dagger} = f (fg) =(gf) (f g)^\dagger = (g f)^\dagger 1 =1 1^\dagger = 1 and all the structural isomorphisms (the associator, the left and right unit laws, and the braiding and balancing) are unitary, where a morphism ff is unitary when f f^\dagger is the inverse of ff.

  • CC has duals if it has duals for objects and morphisms. If CC has duals, Abramsky and Coecke call it strongly compact closed, while Selinger calls it dagger compact closed.

The category of finite-dimensional Hilbert spaces is symmetric monoidal, and it has duals. The same is true for nCob, whose morphisms are n-dimensional cobordisms, like this (for n = 2):

cobordism

These examples are worked through in Track 1 of my Fall 2000 and Winter 2001 Quantum Gravity Seminar notes, featuring Oz and the Wizard.

I’m also fond of another symmetric monoidal category with duals, where the morphisms are spin foams:

spin.foam

All this stuff is part of a bigger theory, just beginning to be developed, of n-categories with duals and their relation to tangles, cobordisms, and n-Hilbert spaces - see page 22 here to get started on that.

So, what should we talk about? As part of his thesis, Mike Stay wants to work out the syntax for symmetric monoidal categories with duals. It should include all the features of MILL and CMLL. So, one thing we could talk about is those logical systems…

Posted at August 28, 2006 6:58 AM UTC

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

52 Comments & 14 Trackbacks

Read the post Categories and computation
Weblog: The n-Category Café
Excerpt: What's the relation between the lambda-calculus, computation and CCCs?
Tracked: August 28, 2006 8:31 AM
Read the post CCCs and the λ-calculus
Weblog: The n-Category Café
Excerpt: Let's discuss cartesian closed categories and the λ-calculus!
Tracked: August 28, 2006 8:38 AM

Re: Quantum computation and symmetric monoidal categories

Mike Stay wants to work out the syntax for symmetric monoidal categories with duals.

How will this differ from what Abramsky and Duncan have done?

Posted by: Mike on August 28, 2006 6:40 PM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

Reading it over again, it seems that they’re only considering free dagger closed categories on some underlying category. I’d like to describe all dagger closed categories (and their quotients, if that’s indeed what’s happening with CCCs)

Posted by: Mike on August 29, 2006 4:49 AM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

Mike wrote approximately:

Reading it over again, it seems that they’re only considering free strongly compact closed categories on some underlying category. I’d like to describe all strongly compact closed categories…

Right. Abramsky and Duncan actually consider the “free strongly compact closed symmetric monoidal category with biproducts” over a given category. Or in other words, the “free symmetric monoidal category with duals and biproducts” over a given category.

(People drowing under jargon may wish to refer back to the original entry in this thread, which I have today enhanced to include definitions of terms including “dagger compact closed”, “strongly compact closed”, and “with duals” - all of which mean the same thing. A beautiful elegant concept is buried under a plethora of terminology!)

So, on the one hand, Abramsky and Duncan are going further up the ladder of structure - demanding their categories have biproducts or “direct sums” ABA \oplus B, as well as the tensor products ABA \otimes B. This rules out nCob.

And on the other hand, they’re only considering free such structures. As they note in their last section:

If the category in question has an object for the type of qubits, then the resulting free structure will not contain, for example, the controlled not gate, nor any other multi-qubit operation. Without such maps the expressivity of the system is limited.

So, they’re not proving a “syntax/semantics duality theorem” establishing an equivalence between a certain 2-category of theories formulated in some language, and some nice 2-category of symmetric monoidal categories with extra bells and whistles. Instead, they’re proving a “soundness” theorem.

It sounds like Duncan will go further in his thesis. But, there’s tons of stuff for you to do in this general vicinity, so we should just plunge and start writing stuff.

…(and their quotients, if that’s indeed what’s happening with CCCs).

Of course the relevant “quotient” of a given kind of category is another category of the same kind, so this would already be covered.

Posted by: John Baez on August 30, 2006 10:07 AM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

The difficulty with developing the syntax of something like compact closed categories is that the tensor connective is self-dual (which mucks around with cut elimination procedures). Shirahata’s paper that you point to does resolve the situation here though. As I understand it, the syntax for symmetric monoidal categories with duals is provided by linearly distributive categories with duals (weakly distributive in the old language), which are equivalent to star-autonomous categories.

As far as logic goes, taking 2Cob as a model of MLL is not totally ideal, because of its frobenius structure, which is not present in the logic. An interesting question to warm up on could be to derive a sequent calculus for frobenius algebras.

If you care about classical computation, then this can be modelled as a monad on a CCC - this insight is usually credited to Moggi. There’s also a nice geometric interpretation of this situation.

Posted by: Jon on August 29, 2006 12:36 AM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

Concerning Frobenius algebras, one can actually drop the additional biproduct structure used in A categorical semantics of quantum protocols and encode classical data manipulations using dagger-compact Frobenius algebras, while, crucially, seemingly retaining all required expressive power. In Quantum measurements without sums Dusko Pavlovic and I showed that such a level of expressiveness is achieved in a much more high-level fashion than in the case of biproduct structure, by also abstracting over classical data, and with axiomatic freedom substantially increased. The power of this particular axiomatization of the classical-quantum interaction is exhibited in the purely graphical proof of Naimark’s theorem which can be found in POVMs and Naimark’s theorem without sums. Currently Eric Paquette and myself are exploring how close the expressiveness of this structure comes to what people in mainstream quantum informatics really care about, and we seem to be able to go the whole way. Another important issue about this is that the biproduct structure constitutes an obstruction to a projective formalism cf. De-linearizing Linearity: Projective Quantum Axiomatics from Strong Compact Closure, a feature which led to so-called Birkhoff-von Neumann quantum-logic. The failure of that approach is exactly the lack of an abstract counterpart to the tensor product, which is of course overcome in the symmetric monoidal approach by starting with an axiomatization of the tensor product.

Posted by: bob on August 30, 2006 12:23 PM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

It’s great to see you here, Bob! This whole thread is inspired by your work with Abramsky… and you just gave me reading material for another month.

Posted by: John Baez on September 1, 2006 1:34 PM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

Hello John, and Bob, et. al.—

Hope this is the right place for this, if not let me know to start another thread. It may be most closely related to Pierre Selinger’s work mentioned at the top of the thread, also from the domain-theoretic formal semantics side there are some references in Elham Kashefi’s paper Quantum Domain Theory to some papers formulating computing on Banach spaces, but I don’t have access to the most promising-sounding ones. I’m actually concerned with something a bit more general than a categories for quantum computation, but closely related—categories for describing information-processing in fairly general “operational” theories, let’s say convex ones, in which you have a cone of unnormalized states with a base that’s the normalized ones, and the dual cone is where the “measurement operators”—POVM elements in quantum mechanics—live. A tensor product of two state spaces, then, is a convex cone containing the convex hull of product states (the “minimal” tensor product), and contained in the cone of states that are positive on product measurement functionals (the “maximal” tensor product, i.e., the dual of the minimal tensor product of the duals). One would like to describe a theory of this sort as a category whose objects are convex cones, which has a tensor product (later we might make it braided monoidal or something), and whose morphisms are positive maps (maybe with additional requirements) which of course must behave nicely with respect to the tensor product (the requirement that in the quantum case will give us completely positive, not just positive, maps as the morphisms).

I’m not much of an expert in category theory, so I’m not sure, but here’s something I think should be known, but I can’t find and haven’t so far constructed. It seems to me that given two self-dual cones, one should always be able to find a (probably unique) self-dual tensor product of them.
The tensor product, in the ordinary linear-operators sense, of the maps from
V to V^*, W to W^* that exhibit the self-duality of the cones K (in V) and M (in W), ought to exhibit the self-duality of this tensor product as well, where ” L exhibits the self-duality of K” means that the cone should be identical with its dual according to the inner product
= L(x)[y]. (I’m happy to assume finite dimensions if needed to help this make sense.)

Is a construction, or existence/uniqueness proof known? (I’m guessing if it’s true it’s pretty simple, but I haven’t gotten it yet.)

Posted by: Howard Barnum on February 8, 2007 4:45 AM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

So, are these dagger-compact closed categories the elusive ‘quantum topoi’? There certainly seems a lot to support the analogy

Hilb is to dagger-compact closed categories
as
Set is to topoi.

Is this the right way to think about things? And if it is, I suppose it must just be another way of saying

linear logic is to intuitionistic linear logic
as
nonlinear logic is to intuitionistic nonlinear logic.


What’s more interesting to me is the hypothesised connection between quantum mechanics and spacetime. There seems to be plenty of circumstantial evidence, but has anybody actually suggested a construction for this? Is it really possible to take something like Hilb, and end up with something like nCob? That’s a pretty big question, especially given that the solution to the measurement problem should be hiding somewhere in the answer!

Posted by: Jamie Vicary on August 31, 2006 12:08 AM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

Is it really possible to take something like Hilb, and end up with something like nCob?

Well, Just as a 2d TQFT assigns to the circle a Hilbert space and to each cobordism a linear transformation, one can go back the other way with a functor that assigns to \mathbb {C} a disjoint union of circles and to each linear transformation a cobordism. But I don’t think that’s what you meant.

Posted by: Mike on August 31, 2006 6:47 AM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

Jamie Vicary writes:

So, are these dagger-compact closed categories the elusive ‘quantum topoi’?

They’re a step in that direction, but I wouldn’t put it that way. They aren’t “maximally nice” the way topoi are - for example, they don’t even have finite coproducts, the way Hilb does. I’d say they’re about as nice as you can get while still including both nCob and Hilb as examples - this is why I’ve been pushing them as a framework for unifying general relativity and quantum theory.

What’s more interesting to me is the hypothesised connection between quantum mechanics and spacetime. There seems to be plenty of circumstantial evidence, but has anybody actually suggested a construction for this? Is it really possible to take something like Hilb, and end up with something like nCob?

I’ve been working on this for almost 10 years now, together with lots of other people. The basic idea is to set up categories of spin foams, which are sort of intermediate between Hilb and nCob.

Spin foams look like 2-dimensional - or perhaps ultimately even higher-dimensional! - generalizations of Feynman diagrams. So, in fact, to glue these entities together in all the obvious ways, one needs to treat them not just as morphisms in a category, but as n-morphisms in an n-category. This is one reason I’m so interested in n-categories with duals. Symmetric monoidal categories with duals - aka “dagger-compact closed categories” - just happen to be a really tractable example.

I don’t really want to discuss quantum gravity on this thread, though. We’ll have plenty of other chances for that. The goal of this particular thread is to ponder quantum computation with the help of symmetric monoidal categories with various extra bells and whistles (like duals).

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

Re: Quantum computation and symmetric monoidal categories

I’d be grateful if anyone (like John and Mike) who has thought about this deeply, could make a couple of further comments on what the apparent close relation between quantum computation and quantum field theory would mean.

I gather that in both cases we may be dealing with functors from SMCCs to Hilb\mathrm{Hilb}. Does this mean that it may happen that I am handed a quantum field theory and say “hey, that’s the xyzxyz-flavor of quantum λ\lambda-calculus in disguise!” ? Or the other way around?

If so, is this just a funny coincidence or is there some deeper meaning to it?

(Sorry to be asking about such vague things as “meaning”.)

Is it just that in both cases we have something incoming, being processed and spit out on the other end? Or is there more to it?

I recall having had a discussion about the faintness of the distinction between computation and physical process before. Maybe what we are dealing with here is precisely the formal counterpart of that non-existing distinction?

Posted by: urs on August 31, 2006 10:15 AM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

Urs writes:

I’d be grateful if anyone (like John and Mike) who has thought about this deeply, could make a couple of further comments on what the apparent close relation between quantum computation and quantum field theory would mean.

I gather that in both cases we may be dealing with functors from SMCCs to Hilb. Does this mean that it may happen that I am handed a quantum field theory and say “hey, that’s the xyz-flavor of quantum λ-calculus in disguise!” ? Or the other way around?

Yes. If you’re into quantum computers, you’ll say the former. If you’re into quantum field theory, it’ll be the other way around. :-)

This duality is especially vivid for topological quantum computers based on Chern-Simons theory.

If so, is this just a funny coincidence or is there some deeper meaning to it?

(Sorry to be asking about such vague things as “meaning”.)

Don’t be sorry! Philosophy is in the mandate of this newsgroup, and since our professional philosopher is vacationing in southern France we’ll just have to do the best we can without any training.

My current theory is this. What Mike and I are calling the quantum lambda-calculus is the syntax of quantum mechanics; symmetric monoidal categories with duals give the semantics. (We probably need to add extra bells and whistles to both sides to be able to say everything we want, but let’s not worry about that now, since we’re being philosophers - let’s consider it done.)

So, any sort of specification of a collection of allowed quantum processes is something we can say in the language of the quantum lambda calculus. So, we can use this language to describe a quantum computer or a quantum field theory, equally well. And, in some cases, as with topological quantum computers based on Chern-Simons theory, it’ll really be just a matter of viewpoint what we have: a computer, or a quantum field theory!

I’m glossing over all sorts of important issues here - I can see more and more of them, the longer I think about this! - but this is my general attitude.

Posted by: John Baez on August 31, 2006 2:24 PM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

Yes.

That’s intriguing. I need to understand that better.

Is this something special to the quantum world or is there a similar correspondence between classical mechanics and classical λ\lambda-calculus??

In the QFT picture, there are actually two ways to interpret a functor nCobHilbn\mathrm{Cob} \to \mathrm{Hilb} as a QFT. First of all, it is of course always a QFT on nn-cobordisms. But in some situations (for n=1n=1 and n=2n=2 in particular) we want to interpret the functors as giving the amplitude of a Feynman-nn-diagram. This makes us want to form a sum

(1) all cobord.CQFTfunctor(C) \sum_{\text{all cobord.} C} \text{QFTfunctor}(C)

and say it produces the S-matrix of another QFT, which we then call the QFT on target space (whereas our nn-cobordisms would then be called the parameter space). (You know this, I am just saying it to make my statement somewhat self-contained.)

So: what does forming this loop-expansion sum mean in terms of quantum computers (if anything)??

quantum lambda-calculus is the syntax of quantum mechanics […] SMCCs with duals give the semantix

I guess you said that before. But it still hasn’t penetrated my skull. Could you maybe say it again?

What precisely does “syntax” and “semantics” mean here?

In which sense is quantum λ\lambda-calculus the “syntax of quantum mechanics”?

Sorry, I didn’t pay as much attention in this λ\lambda-discussion as I should have.

Posted by: urs on August 31, 2006 3:32 PM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

In general, syntax is the set of rules for the language, while semantics is what the language means.

Lambda calculus has rules about what constitutes a term and rules like beta reduction that tell how to manipulate terms; lambda calculus is the syntax in which we write lambda theories. In the lambda theory of groups, there’s a morphism m:G×GGm:G \times G\to G that satisfies certain axioms, but it doesn’t have a precise definition until we map it to a morphism in the target category—that is, until we define the semantics of the theory.

So in a 2d TQFT, we’re ignoring nearly all the data about the surfaces; we’re taking homotopy equivalence classes of surfaces so that we can treat them algebraically as a commutative Frobenius algebra. The syntax consists of saying how we can put things together, and how to treat the composite: tensoring and composition and their axioms.

The semantics of a TQFT is what an object or a morphism in 2Cob “means”: it’s a Hilbert space or a linear transformation.

Posted by: Mike on August 31, 2006 8:09 PM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

Some pedantic corrections.

Mike wrote:

So in a 2d TQFT, we’re ignoring nearly all the data about the surfaces; we’re taking homotopy equivalence classes of surfaces so that we can treat them algebraically as a commutative Frobenius algebra.

You mean we’re taking diffeomorphism equivalence classes, where the diffeomorphism is the identity on the boundary of the surface. (A fully precise statement is even more lengthy.) This matters a lot in higher dimensions, where even two closed manifolds can be homotopy equivalent but not diffeomorphic.

Also, of course you meant that we’re treating the circle as a commutative Frobenius monoid A, so that cobordisms from nn circles to mm can be regarded as morphisms

A nA m.A^{\otimes n} \to A^{\otimes m}.

Posted by: John Baez on September 1, 2006 5:53 AM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

But in some situations (for n=1n=1 and n=2n=2 in particular) we want to interpret the functors as giving the amplitude of a Feynman-nn-diagram.

I don’t know how this works. Can you elaborate?

Posted by: Mike on August 31, 2006 8:18 PM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

the worldline formulation of perturbative QFT

Can you elaborate?

Sure.

Consider n=1n=1 first.

Ordinary quantum mechanics is a functor from 1-dimensional cobordisms to Hilbert spaces. So it’s (1+0)-dimensional QFT.

Consider the relativistic particle, bosonic or fermionic, maybe coupled to background fields.

From the worldline perspective, i.e. from the point of view that 1-dimensional cobordisms are “spacetime”, the action for this theory looks like 1-dimensional gravity coupled to scalar and possibly spinor fields living in 1+0 dimensions.

(1-dimensional gravity itself is of course very dull, but coupled to other fields it provides the crucial reparameterization constraint which makes the other fields sit on their “mass-shell”, thus providing the correct equations of motion.)

So there are two ways to regard, for instance, the Klein-Gordon particle. From one perspective it is a particle in (4-dimensional, say) target space. From the other, equivalent point of view, it is a collection of four bosonic quantum fields living in 1+0-dimensions and coupled to (1+0)-dimensional gravity, described by a functor 1DQFT:1CobHilb1D\mathrm{QFT} : 1\mathrm{Cob} \to \mathrm{Hilb}.

Now comes the main point. What we are interested in in the end is the field theory on 4-dimensional target space, of a field whose “quanta” are Klein-Gordon particles.

If we study this target space field theory perturbatively, Feynman tells us that amplitudes are computed by propagating single Klein-Gordon particles along all possible paths between fixed in- and out- configurations.

In principle (up to the familiar technical problems with divergencies), this tells us how to construct a functor

(1)targetQFT:4CobHilb \text{targetQFT} : 4\mathrm{Cob} \to \mathrm{Hilb}

by only using the information contained in our

(2)1CobHilb. 1\mathrm{Cob} \to \mathrm{Hilb} \,.

(I am glossing over plenty of details. For instance “cobordisms” here may mean Riemannian cobordisms.)

The way we construct the 4Cob4\mathrm{Cob}-functor from the 1Cob1\mathrm{Cob} one is implicit in the standard Feynman rules, but is much more explicit in an equivalent reformulation known as the worldline formalism.

See for instance the first two or three pages of

Christian Schubert, QED in the Worldline Formalism, hep-ph/0011331.

This formalism makes it very explicit how the amplitudes in the 4D-theory are computed by applying functors 1CobHilb1\mathrm{Cob}\to \mathrm{Hilb}.

The only thing you need to know is how the Feynman path integral (for 1-dimensional QFT, i.e. for quantum mechanics) for the relativistic particle does encode this functor. For a situaiton needed in quantum electrodynamics, that path integral is given in equation (1) of Schubert’s text.

Everything I said above has a more or less obvious generalization - in principle at least - to higher dimensions.

So for n=2n=2 we would start with a functor 2CobHilb2\mathrm{Cob} \to \mathrm{Hilb} describing a 2-dimensdional field theory. In certain situations, we may interpret this functor equivalently as describing the propagation of some object in some target space. For n=2n=2 we call this object a “string”.

Then we may extend the above “worldline formalism” for computing amplitudes in a target space field theory to a “worldsheet formalism” for computing such amplitudes.

The study of this n=2n=2-program is called perturbative string theory.

Posted by: urs on September 1, 2006 1:15 PM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

If so, is this just a funny coincidence or is there some deeper meaning to it?

(Sorry to be asking about such vague things as “meaning”.)

Don’t be sorry! Philosophy is in the mandate of this newsgroup, and since our professional philosopher is vacationing in southern France we’ll just have to do the best we can without any training.

Yes, definitely don’t apologise. Meaning is what we’re after. Of course, a satisfactory understanding of the meaning of a theory can only come after engagement with it formulated in a rigorous language. But out of this engagement comes the ability to explain its meaning in natural language terms.

Something that I’m curious about is John’s reference to philosophy here. Certainly, a philosopher can talk about meaning and the place of meaning in enquiry, as I just did. But there seems to be a further notion that to work on the fundamental concepts of a theory, such as computation, causation, etc., is to do philosophical work. Now, I’m happy to go along with this, but the suggestion one sometimes hears that professional philosophers are somehow better equipped to do this kind of work strikes me as odd. Working on Klein 2-geometry feels more like maths to me than philosophy. I touch on this here.

Posted by: David Corfield on September 5, 2006 12:19 PM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

Urs wrote:

(Sorry to be asking about such vague things as “meaning”.)

John wrote:

Don’t be sorry! Philosophy is in the mandate of this newsgroup, and since our professional philosopher is vacationing in southern France we’ll just have to do the best we can without any training.

David wrote:

Something that I’m curious about is John’s reference to philosophy here. Certainly, a philosopher can talk about meaning and the place of meaning in enquiry, as I just did. But there seems to be a further notion that to work on the fundamental concepts of a theory, such as computation, causation, etc., is to do philosophical work. Now, I’m happy to go along with this, but the suggestion one sometimes hears that professional philosophers are somehow better equipped to do this kind of work strikes me as odd.

Oh-oh - the philosopher is back in town - gotta stop kidding around! Actually, my comments above were meant as a kind of joke, in response to Urs’ odd hesitance at discussing “meaning”. I also wanted to remind our readers that we have a broad mandate to explore foundational issues. And, I wanted to remind them that this blog would get more interesting once you came back.

… there seems to be a further notion that to work on the fundamental concepts of a theory, such as computation, causation, etc., is to do philosophical work. Now, I’m happy to go along with this, but the suggestion one sometimes hears that professional philosophers are somehow better equipped to do this kind of work strikes me as odd.

I think a lot of scientists reach for the word “philosophy” whenever they feel the abyss of uncertainty and doubt opening up beneath them. For example, physicists often shelve the foundational questions of quantum mechanics by saying “leave that to the philosophers” - meaning perhaps “leave that to people who are used to arguing about things endlessly without coming to firm conclusions.” I don’t think they actually believe philosophers are likely to make progress.

Posted by: John Baez on September 5, 2006 1:19 PM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

I suppose at the very least philosophers can keep a foundational question alive to put pressure on scientists to address that question at the earliest opportunity.

Perhaps good things in the interpretation of Quantum mechanics are at last beginning to happen. It would be interesting to know what posterity had to say about the long period between its first appearance and its proper interpretation. There’s a philosopher of science, Michael Friedman, whose work I like very much, who sees advances in philosophy and mathematical science happening hand-in-hand. Whereas Newton led to Kant, and Einstein to the Vienna Circle, he feels that QM has never been philosophy worked over properly. For more on this see my paper.

Posted by: David Corfield on September 5, 2006 3:59 PM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

Perhaps good things in the interpretation of Quantum mechanics are at last beginning to happen.

Sometimes, the most vexing unanswered questions turn out to evaporate once people try to actually make them precise.

So maybe in this case, too, it would already help to know what we should really understand under an “interpretation of quantum mechanics”.

I claim I don’t know what that’s supposed to mean. Can anyone explain it to me?

Another point, maybe related:

When working with quantum mechanics a lot, one comes to the point where it feels perfectly natural and all desire to “interpret” it as anything else than what it is disappears. It then is classical physics which begins to look odd and in need of “explanation”.

Posted by: urs on September 5, 2006 4:26 PM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

I can agree on that. The conceptual analysis of quantum mechanics has mainly been attempted in terms of one-dimensional statements such as locality vs non-locality, determinism vs. indeterminism, superposition vs. mixture etc. The more structural approaches mostly focussed on one ingredient only: non-distributivity (lattices), non-commutativity (algebra), non-Kolmogorovian (probability), and something similar for convex structure (Ludwig) etc. As a consequence, the quantum-classical distinction was always again very one-dimensional. Even more surprisingly, compoundness was always some secondary notion. I strongly believe that the categorical approach provides the appropriate framework for a profound structural analysis for quantum theory, a currently lacking prerequisite for a decent philosophical analysis.

Posted by: bob on September 5, 2006 4:50 PM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

Maybe even more important to note, almost all philosophical and structural features of quantum theory are expressed in negative terms: NON-locality, IN-determinism, NON-distributive, NON-Kolmogorovian, NON-commutative etc. On the other hand, technologically speaking, quantum theory has provided an enormous range of new capabilities, so a structural account on quantum theory should provide insights concerning this new capabilities, not what we `lose’ as compared to classical physics. Quantum logic is an extreme case of this attitude: ever since Birkhoff-von Neumann [ here’s a reasonably recent survey on this Birkhoff-von Neumann stuff with tons of references ], quantum logic was conceived as losing the distributive law between conjunction and disjunction i.e., in multiplicative terms (via the adjoint functor theorem), the loss of a `good’ implication, and hence, the mechanism of deduction. On the other hand, in compact categories one does not only get one deductive adjunction, but two, and both are internally witnessed by a morphism (the unit and co-unit of compact closure). This is an example of such a `positive’ approach to the quantum mechanical structure. Similary, rather than saying that quantum mechanics is governed by NO-cloning and NO-deleting, one can say that the lack of a Cartesian structure makes available the possibility of having a (dagger-)compact structure, Cartesian structure and compact structure being incompatible in the sense that having them both forces your category to collapse to a trivial one.

Posted by: bob on September 6, 2006 10:57 AM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

Bob writes:

Maybe even more important to note, almost all philosophical and structural features of quantum theory are expressed in negative terms: NON-locality, IN-determinism, NON-distributive, NON-Kolmogorovian, NON-commutative etc. On the other hand, technologically speaking, quantum theory has provided an enormous range of new capabilities, so a structural account on quantum theory should provide insights concerning this new capabilities, not what we `lose’ as compared to classical physics.

That’s a great point! I’m sorry if I’ve occasionally been guilty of “quantum negativity” when describing the features of symmetric monoidal categories with duals.

It’s a bit like me being in Shanghai. If someone asked me about the food here, I could complain about how hard it is to get breakfast cereal, milk, hamburgers and so on - and all that would be true, but it would completely fail to describe how wonderful the food is here!

In short, the “quantum negativity” you describe resembles the first impressions of a reluctant tourist in a strange land.

Posted by: John Baez on September 6, 2006 11:52 AM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

Picking up where John ended, a crucial difference between *dagger-compact categories for quantum gravity* and *dagger-compact categories in the lab (including quantum informatics)* is the role that measurements play.

Quantum gravitists and cosmologists typically are quite allergic to an operational concept of measurement since stars and universes needn’t be measured to expose quantum behaviour.

On the other hand, experimentally demonstrated phenomena such as teleportation, Rauch’s experiments, GHZ (etc.) just seem to make no sense without a clearly identified operational notion of quantum measurement. Moving further to what is really happening these days in quantum informatics, so-called measurement-based quantum computing (eg see Browne and Briegel and Jozsa and references therein), is a very promissing new quantum computational model in which not unitary dynamics, but the actual dynamics of measurement does all the work. There is substantial experimental activity at aiming to build such devices, which are expected to be scalable - all other current designs do embarrassingly bad on this front. Also all quantum communication protocols crucially rely on measurement dynamics.

Ultimately one would like to have some quantum-framework which both supports the actual experiments in the lab by providing the technician with a set of rules he has to obey in order to expose a certain physical phenomenon, while at the same time providing us with a model of the universe. But for the time being, for the purpose of quantum informatics, one will need to consider quantum measurement as a prime ingredient in one’s semantic framework.

Posted by: bob on August 31, 2006 1:11 PM | Permalink | Reply to this

The duality between syntax and semantics

Urs writes:

What precisely does “syntax” and “semantics” mean here?

I will only tackle this question here, not your harder question about the double role of Feynman diagrams in topological quantum field theory, and what it might mean for quantum computers. That’s a really interesting puzzle, but I’ve already spent too much time blogging today, writing a long comment about the inner automorphism 3-group of a 2-group!

Mike has already given a fine answer to this question about syntax and semantics.

But, the duality between syntax and semantics is one of the grand themes of logic, so one can never say too much about it.

So, I’ll take this excuse to repeat some introductory stuff I said in week227. I can’t resist expanding it a bit in the process, though, because this stuff is so cool!

Logic can be divided into two parts: SYNTAX and SEMANTICS. Roughly speaking, syntax concerns the symbols you scribble on the page, while semantics concerns what these symbols mean.

A bit more precisely, imagine some kind of logical system where you write down some theory - like the axioms for a group, say - and use it to prove theorems.

In the realm of syntax, we focus on the form our theory is allowed to have, and how we can deduce new sentences from old ones. So, one of the key concepts is that of a proof. The details will vary depending on the kind of logical system we’re studying.

In the realm of semantics, we are interested in gadgets that actually satisfy the axioms in our theory - for example, actual groups, if we’re thinking about the theory of groups. Such a gadget is called a model of the theory. Again, the details vary immensely.

In the realm of syntax, we say a list of axioms X implies a sentence P if we can prove P from X using some deduction rules, and we write this as

X |- P

In the realm of semantics, we say a list of axioms X entails a sentence P if every model of X is also a model of P, and we write this as

X |= P

We also say P is provable from X when X |- P, and valid given X when X |= P.

We say a logical system is sound if provability implies validity. We say it’s complete if validity implies provability.

You can begin to see a kind of “duality” between syntax and semantics here. But in fact, they are “dual” in an even more precise way, at least if you fix a specific class of logical systems. This duality is akin to the usual relation between vector spaces and their duals, or more generally groups and their categories of representations. The idea is that given a theory T you can figure out its models, which form a category Mod(T) - and conversely, given the category of models Mod(T), perhaps with a little extra information, you can reconstruct T.

A little extra information? Well, in some cases a model of T will be a set with some extra structure - for example, if T is the theory of groups, a model of T will be a group, which is a set equipped with some operations. So, in these cases there’s a functor

U: Mod(T) → Set

assigning each model its underlying set. And, you can easily reconstruct T from Mod(T) together with this functor.

This idea was worked out by Lawvere for a class of logical systems called algebraic theories, which I discussed in “week200”.

But, the same idea goes by the name of “Tannaka-Krein duality” in a different context: a Hopf algebra H has a category of comodules Rep(H), which comes equipped with a functor

U: Rep(H) → Vect

assigning each comodule its underlying vector space. And, you can reconstruct H from Rep(H) together with this functor. The proof is even very similar to Lawvere’s proof for algebraic theories!

A beautiful thing about Tannaka-Krein duality is that it generalizes the Pontryagin duality between locally compact abelian groups and locally compact abelian groups. And this, in turn, generalizes the Fourier duality between the integers Z and the circle S1, or the real line R and itself, or any finite-dimensional vector space V and its dual V*.

Pontryagin noticed that any locally compact abelian group has a “dual”, and there’s a kind of Fourier transform taking L2 functions on the group to L2 functions on the dual. The dual of the dual is always the original group.

The dual of Z is S1, the dual of S1 is Z, the dual of R is R, and the dual of any finite-dimensional vector space V is its usual dual V*.

So, Pontryagin duality subsumes Fourier duality and the usual duality for vector spaces.

When we try to generalize Pontryagin duality to nonabelian groups it turns out to be hard until we generalize still further, and then we get Tannaka-Krein duality.

So, amazingly enough, Fourier duality and the duality between syntax and semantics for algebraic theories are part of the same family of ideas.

With more work one could find a common generalization and prove a theorem which had both of these results as a special case. I don’t know if anyone has done this yet. If not, they should!

Posted by: John Baez on September 1, 2006 5:39 AM | Permalink | Reply to this

Re: The duality between syntax and semantics

Thanks to Mike and John for these explanations.

I’ll ask some further questions.

Given any (nn-)category CC. Can anyone stop me from addressing it as a syntax?

Given any (nn-)functor CCC \to C'. Do I have the right to call it a semantics for CC?

In other words: what are the conditions on a category that make it qualify as a “syntax”.

What are the conditions on a functor with a “syntax category” as domain to qualify as a semantics for that syntax?

For example, if we take

(1)C=Th(Grp) C = \mathrm{Th}(\mathrm{Grp})

to be the category —

let’s see: which is cartesian generated from a single object GG with morphism generated by G×GmGG \times G \stackrel{m}{\to} G, GsG G \stackrel{s}{\to} G and 1iG1 \stackrel{i}{\to} G modulo the relations which say that these behave as product, inverse and identity of a group —,

then I am entitled to say that “CC is the syntax of the theory of groups”. Or somehting along these lines.

Moreover, given a functor

(2)CSet C \to \mathrm{Set}

I am entitled to address it as a particular semantics for the theory of groups. Namely a particular group.

But assume I feel like it and take any old group GG, regard it as a category Σ(G)\Sigma(G) with a single object – and then declare that I want to think of Σ(G)\Sigma(G) as a syntax.

Next, assume I want to pick any functor

(3)Σ(G)Vect \Sigma(G) \to \mathrm{Vect}_\mathbb{C}

and say that this is a semantics for my syntax Σ(G)\Sigma(G)?

Would you tell me that I am free to do so if I like, or would you point out that Σ(G)\Sigma(G) violates some property that a category must have if we are going to admit that it is a kind of syntax?

Posted by: urs on September 1, 2006 12:27 PM | Permalink | Reply to this

Re: The duality between syntax and semantics

Would you tell me that I am free to do so if I like, or would you point out that Σ(G)\Sigma(G) violates some property that a category must have if we are going to admit that it is a kind of syntax?

I’d say that you’re free to do so; but I think treating categories as syntax is a relatively recent idea.

Typically, syntax is given in some other form that can be seen (from the category theory point of view) as a kind of “presentation” of a category; for universal algebra, an algebraic signature Σ\Sigma consists of a triple (S,F,A)(S, F, A) where SS is a set of sorts (what we’ve been calling types), FF is a set of triples (f,i,o)(f, i, o), ff is a function symbol, ii is a list of sorts (for the input variables), and oo is a sort (for the output) [in universal algebra, the pair (i,o)(i,o) is called a type], and AA is a set of equations involving products and compositions of function symbols and variables of the appropriate sorts for matching up inputs on either side of the equation. I guess Lawvere showed that this specifies a category with finite products and that models of the theory correspond to functors from the category into Set.

But morally, you should be able to take any two categories C,DC, D with some kind of structure and call a structure-preserving functor F:CDF:C\to D “a model of the theory CC in DD,” or “a CC in DD” for short. Last year in his seminar, John left as a puzzle “Of what structure is the category Set the theory?”

Thinking about it now, the question wasn’t fully qualified: first, the name of the theory depends where we’re taking the model. Th(Grp) has groups as its models in Set, but when we try to do the same thing in Vect we get Hopf algebras. Let’s restrict ourselves to models in Set for the moment.

Second, it’s inherently 2-categorical: of which doctrine are we considering Set an object? The doctrine of “no structure,” the 2-category Cat with all functors? The doctrine of categories with finite products and finite-product-preserving functors? The doctrine of CCC’s with product- and exponential-preserving functors? If the latter, then is Set a lambda theory? It has a proper class of objects.

So syntax and semantics are, in my mind, synonyms for source and target of a structure-preserving functor, and both the target category and the structure that gets preserved determine the kind of theory the source represents.

Posted by: Mike on September 2, 2006 12:56 AM | Permalink | Reply to this

Re: The duality between syntax and semantics

Thanks, that sounds good.

So when John writes

λ\lambda-calculus provides a syntax for cartesian closed categories

has he in mind that there is some category CC which we call “λ\lambda-calculus” such that any CCC “is” some functor CSetC \to \mathrm{Set}? Which category is that?

How does that relate to what we have here?

And what does it mean precisely to say that

quantum lambda-calculus is the syntax of quantum mechanics #

?

Is “quantum mechanics” here more than “symmetric monoidal categories”?

Posted by: urs on September 2, 2006 1:31 PM | Permalink | Reply to this

Re: The duality between syntax and semantics

Mike writes:

But morally, you should be able to take any two categories C,DC, D with some kind of structure and call a structure-preserving functor F:CDF:C\to D “a model of the theory CC in DD,” or “a CC in DD” for short.

Right, exactly - this is the idea behind Lawvere’s 1969 paper on “doctrines”.

Last year in his seminar, John left as a puzzle “Of what structure is the category Set the theory?”

Thinking about it now, the question wasn’t fully qualified: first, the name of the theory depends where we’re taking the model.

That’s not such a big deal - there’s usually one name that stands out, often the one where we take models in Set.

Th(Grp) has groups as its models in Set, but when we try to do the same thing in Vect we get Hopf algebras.

No we don’t! We get “groups in Vect”, and these aren’t the same as Hopf algebras. They are something incredibly famous, though.

I seem to remember you figuring this out once before.

Second, it’s inherently 2-categorical: of which doctrine are we considering Set an object? The doctrine of “no structure,” the 2-category Cat with all functors? The doctrine of categories with finite products and finite-product-preserving functors? The doctrine of CCC’s with product- and exponential-preserving functors?

Right - this is an important point, far more so than the previous. We can’t talk about theories and models until we fix a doctrine.

So, I need to do this to make my puzzles precise!

Say we take the doctrine of categories with finite products and finite-product-preserving functors - also called the doctrine of algebraic theories. Th(Grp) lives in here. A model of Th(Grp) in Set is just a group. What’s a model of Th(Grp) in Vect?

I also found a very nice answer to one version of my puzzle about Set. Let’s fix the doctrine of symmetric monoidal categories and symmetric monoidal functors - also called the doctrine of PROPs. (FinSet,+) lives in here, where we use disjoint union of finite sets as the tensor product. What’s a model of (FinSet,+) in Vect called?

(It’s a fairly famous thing.)

Presumably (Set,+) is similar, but more “infinite”.

If the latter, then is Set a lambda theory?

Sure!

It has a proper class of objects.

True, but that didn’t scare you when considering models of other lambda theories in Set:

F:CSetF: C \to \mathrm{Set}

So, it’s a little late to start having qualms when we turn the tables and start studying things like

F:SetCF: \mathrm{Set} \to C

After all, the identity model

1:SetSet1: \mathrm{Set} \to \mathrm{Set}

is one of the best-behaved of all!

One last nitpicky point: I think we decided that the doctrine of lambda-theories should have CCCs as objects and functors that preserve finite products but not necessarily exponentials as morphisms! It came as a shock to me, but we’ll really get in trouble otherwise.

Posted by: John Baez on September 3, 2006 6:04 AM | Permalink | Reply to this

Re: The duality between syntax and semantics

No we don’t! We get “groups in Vect”, and these aren’t the same as Hopf algebras. They are something incredibly famous, though.

You’re right. That’s why I said “the same sort of thing” rather than “take models in Vect”, because I was thinking of models in (Vect, \otimes) rather than (Vect, \oplus). In the former, there’s no duplication or deletion, so you have to put those in by hand, and then you get a Hopf algebra. In the latter, you just get a vector space, where the multiplication is addition of vectors.

What’s a [symmetric monoidal] model of (FinSet,+) in Vect called?

Well, 1 goes to VV; [n][n] should go to V nV^n. A function f:[n][m]f:[n]\to[m] should go to a linear transformation F:V nV mF:V^n\to V^m. I don’t know what this is called (or if I do, I don’t recognize it).

Posted by: Mike on September 4, 2006 2:38 AM | Permalink | Reply to this
Read the post Ringoids
Weblog: The n-Category Café
Excerpt: Just as a "group with many objects" is a groupoid, a "ring with many objects" is called a ringoid. Gregory Muller has emailed me a question about ringoids. I don't want to get into the habit of posting emailed questions...
Tracked: September 2, 2006 5:27 AM

Re: Quantum computation and symmetric monoidal categories

Urs writes:

So when John writes:

The λ-calculus provides a syntax for cartesian closed categories.

has he in mind that there is some category CC which we call “λ-calculus” such that any CCC “is” some functor CSetC \to \mathrm{Set}. Which category is that?

No, I didn’t mean that. I don’t even think Mike was trying to say that. Furthermore, it’s not true.

Let me try to say what I meant. Mike has already infected you with Lawvere’s “functorial” approach to syntax, which is great - but unfortunately you caught a mutant strain, and it seems to be making you sick. Instead of trying to straighten that out, I want to explain what I was actually saying, which was based on a much more traditional notion of syntax.

I don’t know how much logic you’ve studied, but you may know that logicians like to scribble down “theories”, which consist mainly of lists of “axioms” in some “language” or other, and deduce “theorems” from them, using various “deduction rules”.

There are lots of ways to play this game - each of the quoted terms covers lots of ground. But let’s say that any choice of a “language” and “deduction rules” is a “syntax”. I could list a lot of examples, but I’ll just list one: the typed lambda calculus.

(We’ve been talking a lot about the untyped lambda calculus in this thread, but mainly because this highly popular setup is far trickier in certain ways than the typed lambda calculus, and I wanted to understand it. For the question at hand, everything will work out infinitely more elegantly if we use the typed lambda calculus - that’s why they invented it!)

To specify a lambda theory we need to list:

  1. a set of generating “types”,

  2. a set of generating “function symbols”, each of which has a specified input type and output type,

  3. a set of “axioms”, which are equations built using the function symbols.

You may not know what this jargon means, and I’m probably not even using the standard jargon. But that’s okay, because in a minute you’ll see these three things are secretly objects, morphisms and equations between morphisms in a certain category.

Let me write down an example, though:

  1. Let’s choose two generating types, say AA and BB. This immediately gives us infinitely many more types, like A×BA \times B and hom(A×A,hom(B,A))\mathrm{hom}(A \times A, \mathrm{hom}(B, A)) and so on.

  2. We could choose two function symbols, say FF and GG. Since we’re doing the typed lambda calculus we have to say what type of input this function symbol eats, and what type of output it spits out. Let’s say the input type of FF is hom(A,B)\mathrm{hom}(A,B) and its output type is hom(B,A)\mathrm{hom}(B,A). So FF is the name of some operation that eats operations from AA to BB, and spits out operations from BB to AA. Similarly, let’s say the input type of GG is hom(B,A)\mathrm{hom}(B,A) and its output type is hom(B,A)\mathrm{hom}(B,A).

  3. Now we can write down some axioms. Here’s a really simple one:

    λf:hom(A,B).G(F(f))=λf:hom(A,B).f\lambda f:\mathrm{hom}(A,B) . G(F(f)) = \lambda f:\mathrm{hom}(A,B) . f

    This should look vaguely like stuff you’ve seen in the untyped lambda calculus, except that now all our variables are “typed”, so we have to say what type the variable ff is - and when we say f:hom(A,B)f:\mathrm{hom}(A,B), we’re declaring that it’s an operation that eats guys of type AA and spits out guys of type BB.

    This “type declaration” business might be new to you - but if you’ve done some computer programming, you’ve seen something like it.

    Anyway, our axiom says that if we hit any such ff with FF, and then hit it with GG, we get back ff.

This is not a thrilling example. A cooler one is the system “PCF” that Robin Houston was talking about - see Selinger’s notes. This has types called “natural numbers” and “truth values”, and enough function symbols and axioms so you can really do a lot of stuff. Another example is the “lambda theory of groups”, which is just the axioms for a group, written out in the lambda calculus.

If you think about it, I hope you can see that a lambda theory can have “models” in any cartesian closed category YY In a model, all the types are interpreted as objects of YY, and the function symbols are interpreted as morphisms, and the axioms have to hold as equations. For example, a model of the lambda theory of groups in the category Set is just a group.

This is the typed lambda calculus in its traditional form. But we can also take a more modern view: any lambda theory determines a cartesian closed category!

To get this, you just take your generating types as objects, and throw in all the other objects you know must exist by virtue of having a CCC. You take your function symbols as morphisms between objects, and throw in all the other morphisms you know must exist by virtue of having a CCC. And, you take your axioms as equations between morphisms, and throw in all the equations you can derive from these by virtue of having a CCC!

Conversely, any CCC gives a theory in the typed lambda calculus. We can do this systematically by taking all the objects as generating types, and putting in isomorphisms whenever needed to cut down the redundancy this creates.

So, once you get the hang of it, you see that a CCC and a theory in the typed lambda calculus are almost the same thing.

However, they still feel a bit different. The theory feels like “syntax” - you’re fiddling around with variables, and using deduction rules to prove theorems from axioms (i.e. derive new equations from old ones). The CCC feels like “semantics” - you’ve got actual objects and morphisms floating around.

In particular, there are lots of famous CCC’s, like Set, or Cat, which are tricky to describe as a typed lambda theory. You might need tons of types, and tons of function symbols, and tons of axioms, to describe one of these typed lambda theories - even if you feel you understand the corresponding CCC perfectly well!

Also, there are lots of famous lambda theories, like the axioms for a group, or PCF, which are tricky to describe as a CCC. It might be really hard to understand all the objects and morphisms of some CCC - even if you feel you understand the corresponding lambda theory perfectly well!

So, the duality between syntax and semantics is interesting, even if from certain viewpoints it seems trivial.

Now for Lawvere’s new-fangled concept of “model”, which is equivalent to the old one, but slicker. You’ll like it. For this, we take a lambda theory and right away replace it by its corresponding CCC, say XX. A model of our lambda theory is then a product-preserving functor

F:XYF: X \to Y

where YY is some other CCC. We also call this a model of XX in YY.

Note that this deliberately blurs the roles of syntax and semantics, because we’re using the CCC XX as a stand-in for its corresponding lambda theory.

But, the moral difference between syntax and semantics is still there! What we do in practice is take a CCC, say XX, that we can understand really well syntactically, and look at models of it

F:XYF: X \to Y

where YY is a CCC that we can understand really well semantically. For example, XX could be the CCC corresponding to the axioms for a group, and YY could be Set. Then FF would be a “model of the lambda-theory of groups in Set” - in other words, a group!

If we switched the roles here, and looked at things like

F:YXF: Y \to X

these would be quite hard to understand.

The moral: we map out of syntax, into semantics.

That’s all I have time for now, but I hope it helps. All the stuff I just wrote is what I mean when I say

The λ-calculus provides a syntax for cartesian closed categories.

Posted by: John Baez on September 2, 2006 3:10 PM | Permalink | Reply to this
Read the post Doctrines
Weblog: The n-Category Café
Excerpt: In 1969 Lawvere invented "doctrines". A doctrine is a roughly a kind of category, thought of as a kind of logical theory.
Tracked: September 3, 2006 4:59 AM

PROPs and Algebraic Theories

Most people probably won’t understand what Mike just said, since it involves knowing the history of our previous conversations. So, I’ll discuss our current crop of puzzles a bit more thoroughly.

1. Say we take the doctrine of categories with finite products and finite-product-preserving functors - also called the doctrine of algebraic theories. Th(Grp) lives in here. A model of Th(Grp) in Set is just a group. What’s a model of Th(Grp) in Vect?

It’s called a group object in Vect, but what it turns out to be is simply a vector space! The point is this. If we have a vector space to be equipped with an extra group operation which is linear, we can show this new group operation has to be the same as addition in the vector space!

So, any vector space can be made into a group object in Vect in a unique, boring way.

Similarly, a group object in Grp is an abelian group. A group object in Ab is also an abelian group.

2. Say we take the doctrine of symmetric monoidal categories and symmetric monoidal functors - also called the doctrine of PROPs. (FinSet,+) lives in here, where we use disjoint union of finite sets as the tensor product. What’s a model of (FinSet,+) in (Vect,\otimes) called?

Hmm - actually I don’t feel like answering this one. It’s fun to work it out. It’s a fairly well-known kind of thing! If anyone gets stuck, the answer is in my universal algebra lecture notes. And, the answer is nice not just for models in (Vect, \otimes), but for models in any symmetric monoidal category.

3. What’s a model of the PROP (FinSet,+) in (Vect,\oplus) called?

Mike took a stab at this but then claimed he didn’t recognize the answer. I’m pretty sure he’ll recognize it when he thinks harder - I’m pretty sure it’s an incredibly famous thing!

Maybe someone else can help him out.

4. Finally, about another puzzle Mike and I were discussing. There is no PROP for groups. But there is an algebraic theory for groups, and there’s an adjunction between PROPs and algebraic theories. So, we can take the algebraic theory of groups and turn it into a PROP. What do we get?

As Mike notes, this amounts to taking stuff we have in any algebraic theory - the diagonal

Δ:GG×G\Delta: G \to G \times G

and the map to the terminal object

e:G1e: G \to 1

and turning them into explicit extra operations in our PROP. They come “for free” when we have an algebraic theory, but not when we have a PROP.

So, we get a PROP for algebraic gadgets that have the usual group operations but also a comultiplication Δ\Delta and a counit ee.

The obvious guess is that this is the PROP for Hopf algebras. That’s what I wrote at first in my lecture notes where I explained this puzzle in detail.

But, I later realized that we get more axioms than just the bare-bones Hopf algebra axioms! We also get the cocommutative law: if you apply Δ\Delta, and then switch the two outputs, it’s the same as just applying Δ\Delta. This is a feature of the diagonal in any category with finite products. So, it’s inherited by our PROP.

So, right now I think the answer is the PROP for cocommutative Hopf algebras.

Unfortunately, I haven’t checked this - there could be other axioms I’m forgetting. Indeed, the first axiom I noticed was not the cocommutative law, but the involutory law - if you take the inverse of a group element twice, you get back the same thing. This law does not hold for an arbitrary Hopf algebra. But, it holds for all cocommutative Hopf algebras. So, right now I’m hoping the cocommutative law is all we need. And, I have some theoretical reasons for guessing that.

Posted by: John Baez on September 4, 2006 4:29 AM | Permalink | Reply to this

Re: PROPs and Algebraic Theories

What’s a model of the PROP (FinSet,+)(\mathrm{FinSet},+) in (Vect k,)(\mathrm{Vect}_k,\oplus) called?

Second attempt: maybe we can identify such a model with the free commutative algebra over k nk^n, where k nk^n itself is (isomorphic to) the image of any one 1-element set.

Posted by: urs on September 4, 2006 6:50 PM | Permalink | Reply to this

Re: PROPs and Algebraic Theories

Urs writes:

What’s a model of the PROP (FinSet,+)(\mathrm{FinSet},+) in (Vect k,)(\mathrm{Vect}_k,\oplus) called?

Second attempt: maybe we can identify such a model with the free commutative algebra over k nk^n, where k nk^n itself is (isomorphic to) the image of any one 1-element set.

I don’t see where you’re getting an “algebra” from: an algebra has a multiplication

AAAA \otimes A \to A

but nothing in this puzzle mentions the tensor product of vector spaces - just the direct sum!

Maybe you were secretly trying to solve some other puzzle, like this:

What’s a model of the PROP (FinSet,+)(\mathrm{FinSet},+) in (Vect k,)(\mathrm{Vect}_k,\otimes) called?

Nonetheless, you are on the right track!

One approach is to tackle the general question of this form:

What’s a model of the PROP (FinSet,+)(\mathrm{FinSet},+) in a symmetric monoidal category CC called?

However, the general answer takes a shockingly simple form when the tensor product in CC is just the coproduct. That’s why I gave Mike an example like that:

What’s a model of the PROP (FinSet,+)(\mathrm{FinSet},+) in (Vect k,)(\mathrm{Vect}_k,\oplus) called?

Posted by: John Baez on September 5, 2006 7:28 AM | Permalink | Reply to this

Re: PROPs and Algebraic Theories

model of (FinSet,+)(FinSet, +) in (Vect,)(Vect, \oplus)

The lecture notes state that (FinSet,+)(FinSet, +) is the PROP for commutative monoids, but I don’t see how that can be so. First, FinSet has a proper class of objects, while the PROP for commutative monoids only has countably many.

What if we take a single representative of each equivalence class and throw away all the extraneous isomorphisms? Then I still think we have too many morphisms for it to be the PROP of commutative monoids, since the only morphisms in the PROP of commutative monoids are the ones that must be there for a PROP along with the morphisms generated by the function symbols for multiplication and unit. FinSet includes all functions between finite sets.

Posted by: Mike on September 7, 2006 11:22 PM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

What’s a model of the PROP (FinSet,+)(\mathrm{FinSet},+) in (Vect,)(\mathrm{Vect},\oplus) called?

I am also not sure about the answer. But if I slightly modify the question…

So if I take (FinSet,+)(\mathrm{FinSet},+) to have only isomorphisms, then a PROP model in (Vect,)(\mathrm{Vect},\oplus) would be lots of representations of symmetric groups S(n)S(n) for all nn.

Posted by: urs on September 4, 2006 6:33 PM | Permalink | Reply to this

Re: Quantum computation and symmetric monoidal categories

Urs wrote:

If I take (FinSet,+) to have only isomorphisms, then a PROP model in (Vect,)(Vect,\oplus) would be lots of representations of symmetric groups S(n)S(n) for all n.

Right, but there’s more to it than that - or actually, less to it!

Since I write C 0C_0 for the underlying groupoid of a category CC, I sometimes use (FinSet 0,+)(\mathrm{FinSet}_0,+) to stand for what you’re talking about here: the groupoid of finite sets and bijections, made into a symmetric monoidal category with disjoint union as the tensor product.

The groupoid of finite setsand bijections is also called the symmetric groupoid and denoted S. This is a nice name, because it’s the coproduct of all the symmetric groups S(n)S(n):

S= nS(n) S = \sum_n S(n)

In fact, SS is the free symmetric monoidal category on one object. From a certain overly educated viewpoint, this is why finite sets and bijections are important!

If you want to think of a symmetric monoidal category as a kind of “theory”, you call it a PROP, and you call symmetric monoidal functors out of it models. So, a model of S in (Vect,)(Vect, \oplus) is just a symmetric monoidal functor

V:SVect V: S \to \mathrm{Vect}

What does this amount to?

For starters, what’s a plain old functor

V:SVect? V : S \to \mathrm{Vect} ?

It’s the same as a vector space V(n)V(n) for each object nSn \in S, together with a representation of S(n)S(n) on V(n)V(n)!

However, saying that VV is a symmetric monoidal functor is a powerful extra constraint. For starters, just because it’s a monoidal functor, we get

V(n+m)V(n)V(m)V(n+m) \cong V(n) \oplus V(m)

But in fact we get much more…

… so when you finally work it all out, I think you’ll be surprised at how pathetically simple it is.

(Of course Mike and everyone else should also take a crack at this puzzle!)

Posted by: John Baez on September 5, 2006 6:21 AM | Permalink | Reply to this
Read the post Connes on Spectral Geometry of the Standard Model, I
Weblog: The n-Category Café
Excerpt: Connes is getting closer to the spectral triple encoding the standard model coupled to gravity. Part I: some background material.
Tracked: September 6, 2006 12:26 PM

the syntax of quantum mechanics

For some reason parts of the discussion that really belongs here appeared in the comment section of the Doctrines entry.

I began by summarizing aspects of my current understanding of what John and Mike mean when they talk about the syntax of quantum mechanics here, essentially by spelling out some obvious things about how models of topological strings are examples for models of quantum λ\lambda-calculus.

Of course I also had yet another question. Namely, I was wondering if all the domain categories we encounter in quantum theory are really closed.

nCobn\mathrm{Cob}, which governs “topological” quantum theories, clearly is closed.

This can be traced back to the fact that the zig-zag identity defining duality on objects is manifestly a consequence of the fact that in nCobn\mathrm{Cob} only the diffeomorphism class of a cobordism counts.

This made me worry. In other quantum theories, like the non-topological (called “physical”) string, also known as 2D CFT, the domain category is that of 2-dimensional Riemann surfaces.

Hence we seem to lose duality on objects, and hence our internal hom\mathrm{hom}s.

Instead of mentioning this 2D example, I mentioned what I thought would be a simpler example that still makes this point, namely non-relativistc QM of point particles. One way to conceive the domain category in this case is as that of 1-dimensional Riemannian cobordisms - namely pieces of “worldline” equipped with a length (their temporal extension) associated to them.

There was a little back and forth with the question being stated incorrectly, being un-asked, being corrected and finally being re-asked.

John then wrote:

I tend to think of nonrelativistic quantum mechanics this way: we have a Hilbert space HH, and a self-adjoint Hamiltonian on this Hilbert space. This generates a 1-parameter family of unitary operators

(1)U(t):HH U(t):H \to H

describing time evolution, where tt\in \mathbb{R}. They form a 1-parameter group, meaning

(2)U(t+s)=U(t)U(s). U(t+s)= U(t)U(s) \,.

In other words, we have a unitary representation of \mathbb{R} on HH.

Now, how do we think of this as a model of some theory in the doctrine of symmetric monoidal categories with duals?

It’s a model of a certain symmetric monoidal category with duals which you would probably call Σ()\Sigma(\mathbb{R}). As a category, this has one object. The morphisms from this object to itself are real numbers, and composition is addition.

In other words: morphisms in a category always describe processes, and morphisms in this category describe processes of “time evolution”!

This category becomes a symmetric monoidal category with duals in a thoroughly trivial way, except that the dual of the morphism t t \in \mathbb{R} is t−t.

Then, a model of this symmetric monoidal category with duals in Hilb\mathrm{Hilb} - that is, a symmetric monoidal functor preserving duals

(3)U:Σ()Hilb U : \Sigma(\mathbb{R}) \to \mathrm{Hilb}

is nothing other than a unitary representation of \mathbb{R} on some Hilbert space!

[…]

We do, however, need the duals for morphisms, if we want to insist that time evolution is unitary.

It’s easy to generalize all this from \mathbb{R} to whatever group you like, for example the Poincaré group.

Posted by: urs on September 6, 2006 2:14 PM | Permalink | Reply to this

Re: the syntax of quantum mechanics

Here my reply:

Okay, good. By throwing in inverses to the morphisms which I considered, you managed to save the existence of dualities.

Namely, after the dust of making it precise has settled (one needs to deal with “collars” and with the identity morphism), that category of 1-dimensional Riemannian manifolds which I considered is nothing but the category version of the semigroup 0\mathbb{R}_{\geq 0}.

Throwing in inverse morphisms turns this into Σ()\Sigma(\mathbb{R}), which you consider.

Maybe this move of throwing in inverse morphisms also works for categories of higher dimensional Riemannian cobordisms. But I cannot remember having seen this. Does it?

Well, I guess it is at most a matter of getting some technicalities right.

Okay, good, thanks for that answer. I am now pretty close to having digested the statement that

Every model of quantum mechanics (in the sense of physicists) is a model (in the sense of nn-category logicians or whatever such people are called) of some theory in the doctrine of symmetric monoidal categories with duals.

I still feel a little shaky on what should be the next sentence, something like this, maybe:

And since every such model in the doctrine of symmetric monoidal categories with duals is also a model of quantum λ\lambda-calculus, we say that quantum λ\lambda-calculus is the syntax of quantum mechanics.

Posted by: urs on September 6, 2006 2:32 PM | Permalink | Reply to this

Re: the syntax of quantum mechanics

Urs wrote:

…after the dust of making it precise has settled (one needs to deal with “collars” and with the identity morphism), that category of 1-dimensional Riemannian manifolds which I considered is nothing but the category version of the semigroup \mathbb{R}_\ge.

Okay, now I see exactly what you meant by this category. I don’t know why I found it confusing before - I know what a Riemannian cobordism is! I guess I was confused by your remark that standard nonrelativistic quantum mechanics of a single point particle is described using functors

U: HilbU : \mathbb{R}_\ge \to \mathrm{Hilb}

i.e., 1-parameter semigroups of operators.

I didn’t see how the unitarity of time evolution would arise in this approach. Of course one can stick it in “by hand”, replacing Hilb\mathrm{Hilb} by the groupoid of Hilbert spaces and unitary operators. However, this seems to neglect the insight that unitarity of time evolution is a kind of enhanced version of its “reversibility”. Having a functor

U:HilbU : \mathbb{R} \to \mathrm{Hilb}

makes time evolution reversible:

U(t)=U(t) 1U(-t) = U(t)^{-1}

and then saying that UU preserves duals for morphisms:

U(t )=U(t) U(t^\dagger) = U(t)^\dagger

implies that UU is unitary, if we give both R\R and Hilb\mathrm{Hilb} the obvious duals for morphisms:

t =tt^\dagger = -t

for tt a morphism in \mathbb{R}, and

ψ,T ϕ=Tψ,ϕ\langle \psi, T^\dagger \phi\rangle = \langle T \psi, \phi \rangle

for TT a morphism in Hilb\mathrm{Hilb}. After all, we then obtain

U(t)=U(t )=U(t) U(-t) = U(t^\dagger) = U(t)^\dagger

which in combination with

U(t)=U(t) 1U(-t) = U(t)^{-1}

makes U(t)U(t) unitary:

U(t) 1=U(t) .U(t)^{-1} = U(t)^\dagger .

(You know all this by now; I’m just spelling out the details because I suddenly realize that these ideas are not common knowledge.)

Anyway, I think we see eye-to-eye on this now. But you raise a good puzzle that I have never tried to tackle:

Maybe this move of throwing in inverse morphisms also works for categories of higher dimensional Riemannian cobordisms. But I cannot remember having seen this. Does it?

I don’t know! The closest thing to this that I know about is the “bubble-time” formalism in field theory on Minkowski spacetime. Here we have a groupoid Cauchy\mathrm{Cauchy} where:

  • objects are Cauchy surfaces in Minkowski spacetime,
  • between any two objects there is one morphism.

In some cases the morphism between two objects can be visualized as a “sandwich of spacetime” between two “spacelike slices” - or more precisely, a Lorentzian cobordism. But, in addition to being able to evolve forwards in time, we can also evolve backwards! For example, we can have a “negative sandwich” going from the slice t=1t = 1 back to the slice t=0t = 0. We can also have more complicated things, where neither slice is completely in the future of the other.

As usual, this groupoid gets duals for morphisms by setting

f =f 1.f^\dagger = f^{-1}.

In quantum field theory one naively hopes to get a functor preserving duals for morphisms

U:CauchyHilb.U: \mathrm{Cauchy} \to \mathrm{Hilb}.

This doesn’t quite work, for reasons of analysis, not even for free field theories in dimensions greater than 2: we need to replace Hilbert spaces by C*-algebras of observables.

But anyway, here we are doing something like throwing in “inverses” to Lorentzian cobordisms - but it’s much more subtle than in the case of 1d spacetime. We could try the same thing for 2d Riemannian or conformal cobordisms; this would be even subtler, but I bet it would work if we were smart enough. There should be a “bubble-time formalism” for conformal field theory. And thanks to the magic of low dimensions, we should even be able to work with Hilbert spaces, and avoid the need for C*-algebras.

And, while dreaming of projects I’m too busy to do, let me mention another: we should really describe dynamics in conformal field theory, not using a mere category of conformal cobordisms, but something more like a 2-category or double category! After all, we can chop a Riemann surface into polygonal bits, so we want a syntax general enough to describe how to stick such polygonal bits together. When I last checked, Stolz and Teichner were still struggling to set up this syntax for their work on elliptic cohomology - but I should read starting on page 50 here, to see how far they’ve gotten.

Posted by: John Baez on September 7, 2006 2:49 AM | Permalink | Reply to this

Re: the syntax of quantum mechanics

Of course one can stick it in “by hand”

Yes, that’s what I would have done.

But one noteworthy point here is, that often when one actually uses this functorial way of thinking about QM to do something with it, one tends to “Wick rotate” anyway.

Instead of

(1)(t)Hexp(itΔ)H (\bullet \stackrel{t}{\to} \bullet) \mapsto H \stackrel{\exp(it\Delta)}{\to} H

we take

(2)(t)Hexp(tΔ)H. (\bullet \stackrel{t}{\to} \bullet) \mapsto H \stackrel{\exp(-t\Delta)}{\to} H \,.

This is even more pronounced once we go from 1-dimensional cobordisms to 2-dimensional (conformal) ones.

we should really describe dynamics in conformal field theory, not using a mere category of conformal cobordisms, but something more like a 2-category or double category!

Yes, that’s sort of my long-term project anyway.

Just for the record, let me list some things in this direction which I have thought about.

1) I have a pretty good idea how the “first half” of the FRS formalism of (R)CFT can be understood as “local trivialization” of a 2-functor with values in bimodules. I have notes on that here.

By “first half” I roughly mean everything that is 2-dimensional about this formalism. FRS in fact crucially use the realization of 2D CFT as a boundary theory of a 3D TFT, and hence ultimately one certainly needs a 3-functorial description to capture it.

2) I simply notice that Hilbert uniformization should be a beautiful tool to describe 2-transport along Riemann surfaces in terms of transport over lots of little bigons.

3) I believe I do have a pretty good idea about how the 2-functor with values in bimodules that Stolz & Teichner use to describe string connections is a 2-vector 2-transport associated to principal 2-transport in a String-2-bundle induced by a certain “canonical” representation of the string group on a 2-vector space.

A blog remark on that is here.

But I have more details typed on that. I am planning to post an entry on that. If you want to have a preview, you could look at these notes.

In these notes I describe this general class of 2-reps of strict 2-groups and spell out the description of line bundle gerbes with connection as associated 2-transport induced by the rep of (U(1)1)(U(1)\to 1). I discuss how here, too, we really have 2-transport with values in bimodules, which only becomes a line bundle gerbe after you pass to its “transition data”.

So, while these notes do not mention the string group but instead deal with (U(1)1)(U(1)\to 1) it is set up in such a way that when you switch the structure 2-group to String, everything looks pretty much like what Stolz-Teichner have.

4) One thing which I have not understood yet, but which I want to understand in this context, is the precise categorical concept of a “2-Dirac” operator.

In order to get that, I first need a good functorial way to understand what an ordinary Dirac operator is.

I think I see which way to go, but I haven’t fully figured it out yet.

Namely, I think it is crucial to start with Quillen’s point of view of a Dirac operator as a “quantized connection”.

For us, a connection is a parallel transport, hence a functor. That part is clear. We want to apply that functor on small pieces of path, compute the “covariant derivative” this way, and then sort of act with the path by Clifford multiplication.

It’s that last part which I still don’t have a good categorical/functorial understanding of.

The first part, however, that about the covariant derivative, can nicely be understood using some D-brane imagery #, I think.

Posted by: urs on September 7, 2006 1:03 PM | Permalink | Reply to this

Re: the syntax of quantum mechanics

You illustrate the concepts using strings instead of point particles. In M-theory, the fundamental objects are M2-branes and M5-branes, so how about you doing the same thing you did with strings, but instead use, say, M2-branes.

Posted by: anonymous on September 7, 2006 6:57 PM | Permalink | Reply to this

Re: the syntax of quantum mechanics

[…] instead use, say, M2-branes.

You can do that. And people are studying this. In particular topological membranes, since these are way easier to handle quantum mechanically than “physical” membranes.

The study of topological membranes in string theory is related to what they call “topological M-theory”.

There are also people working on the category-theoretic formulation of the theory of topological membranes, for instance Aaron Lauda.

Posted by: urs on September 7, 2006 7:02 PM | Permalink | Reply to this
Read the post Connes on Spectral Geometry of the Standard Model, II
Weblog: The n-Category Café
Excerpt: On the nature and implication of Connes' identification of the spectral triple of the standard model coupled to gravity.
Tracked: September 6, 2006 6:54 PM
Read the post On n-Transport: 2-Vector Transport and Line Bundle Gerbes
Weblog: The n-Category Café
Excerpt: Associated 2-transport, 2-representations and bundle gerbes with connection.
Tracked: September 7, 2006 2:06 PM

Re: PROPs and Algebraic Theories

Mike writes:

The lecture notes state that (FinSet,+) is the PROP for commutative monoids, but I don’t see how that can be so. First, FinSet has a proper class of objects, while the PROP for commutative monoids only has countably many.

What? You care about how many objects a category has? I’m afraid you’re being a bit… evil.

It’s evil, in a certain precise technical sense, to mention equations between objects in a category. To be good, one should instead work with specified isomorphisms. Thus, it’s evil to care about the difference between:

1. one object

and

2. any collection of objects, each isomorphic to each other in a unique way.

Anything useful that you can do with one, you can do with the other!

We formalize this a bit by creating a definition of equivalence of categories, which is weaker than isomorphism. Unlike the definition of isomorphism between categories, the definition of equivalence doesn’t involve any equations between objects! I like to say a property of categories is good if it’s invariant under equivalence, and evil otherwise.

The number of objects in a category is the same for two isomorphic categories, but not necessarily for two equivalent categories! So, this property is evil. Nothing useful can come of it.

Indeed, every category is equivalent to a skeleton, which we obtain by throwing out objects until we’re left with just one object in each isomorphism class. A skeleton is obviously skeletal, meaning that isomorphic objects are equal.

It sounds like that’s what you’re hinting at here:

What if we take a single representative of each equivalence class and throw away all the extraneous isomorphisms?

In short: however you prefer to define FinSet, it’s equivalent to a category with just one 0-element set, just one 1-element set, just one 2-element set and so on!

So please, none of this evil talk about FinSet having a proper class of objects. If you want to work with a big fat flabby version of FinSet with that many objects, that’s fine. If you want to work with a skeletal version of FinSet, that’s also fine. But don’t tell me: I’ll never need to know, as long as we only discuss good concepts!

This is one of the big moral principles of category theory, which allows for incredibly robust results. When you get used to it, you’l feel perfectly relaxed about working with whatever equivalent “version” of a category seems to be handy.

This is one reason category theorists feel happy talking about “the” 5-element set.

One last comment: the very notion of “skeleton” is evil, since it involves counting objects in an isomorphism class. So, why did I even mention this evil concept? Just to scare you into not talking about the number of objects in a category!

But you’ve known this since you were a kid: skeletons are evil! That’s why they run around in the dark on Halloween!

Unfortunately, after switching to a skeletal version of FinSet, you’re still not happy:

Then I still think we have too many morphisms for it to be the PROP of commutative monoids, since the only morphisms in the PROP of commutative monoids are the ones that must be there for a PROP along with the morphisms generated by the function symbols for multiplication and unit. FinSet includes all functions between finite sets.

Yeah??? So???

Posted by: John Baez on September 8, 2006 4:01 AM | Permalink | Reply to this

Re: PROPs and Algebraic Theories

OK, now I see it. Multiplication decrements the exponent; the composition of the isomorphism TT1T \stackrel{\sim}{\to} T\otimes 1 and the morphism idιid \otimes \iota increments it. Consider a function f:[n][m]f:[n]\to [m]. Now interpret [n][n] as the disjoint sum of the preimages of each point in [m][m]. We multiply together all the points in a given preimage, and use the “increment” morphism to get points with an empty preimage.

For example, the function

(1){1,2,3}{1,2,3} \{1,2,3\} \to \{1,2,3\}
(2)11 1 \mapsto 1
(3)21 2 \mapsto 1
(4)32 3 \mapsto 2

corresponds to the morphism

(5)T 3midT 2T 21ididιT 3 T^3 \stackrel{\m\otimes id}{\to} T^2 \stackrel{\sim}{\to} T^2 \otimes 1 \stackrel{id \otimes id \otimes \iota}{\to} T^3

So the morphisms in the PROP for a commutative monoid are all the morphisms.

Posted by: Mike on September 8, 2006 11:41 PM | Permalink | Reply to this
Read the post Category Theory and Philosophy
Weblog: The n-Category Café
Excerpt: The place of category theory in philosophy
Tracked: September 8, 2006 9:14 AM

Re: Quantum Computation and Symmetric Monoidal Categories

Mike wrote:

The lecture notes state that (FinSet,+) is the PROP for commutative monoids, but I don’t see how that can be so.

and then

OK, now I see it. […] Consider a function f:[n][m]f:[n]\to [m]. Now interpret [n][n] as the disjoint sum of the preimages of each point in [m][m]. We multiply together all the points in a given preimage, and use the “increment” morphism to get points with an empty preimage.

You got it! And, you did a darn good job of explaining it in words. But alas, in words it always comes across as a bit tricky and “technical”. I like pictures.

There’s an easy way to draw a picture of any function from an nn-element set to an mm-element set. It’s called a string diagram. Here’s an example:

1  2  3  4   5
 \ | /    \ /
  \|/      \
   |      / \    |
   |     /   \   |
   1    2     3  4

This is the function from {1,2,3,4,5}\{1,2,3,4,5\} to {1,2,3,4}\{1,2,3,4\} with:

111 \mapsto 1 212 \mapsto 1 313 \mapsto 1 434 \mapsto 3 525 \mapsto 2

As we read from top to bottom, strands can be born, merge, and switch places. They can’t die or split.

If MM is a commutative monoid, it’s easy to see how to interpret any such diagram as a function

M nM m M^n \to M^m

You explained how. But in simple terms: we line up a bunch of elements of MM on top of the diagram. Then, when strands merge, we multiply them. When a strand is born, we stick in the element 1M1 \in M. And when strands trade places, we switch the monoid elements.

In our example, we get this function from M 5M^5 to M 4M^4:

a  b  c  d   e   
 \ | /    \ /
  \|/      \
   |      / \    |
   |     /   \   |
  abc   e     d  1

(a,b,c,d,e)(abc,e,d,1)(a,b,c,d,e) \mapsto (a b c,e,d,1)

It’s more work to turn this string diagram stuff into a rigorous proof, because we need a rigorous theory of pictures! But ultimately it’s worthwhile, because string diagrams are useful for lots of monoidal categories, not just (FinSet,+). The example we just did is one of a big bunch of similar examples.

Posted by: John Baez on September 11, 2006 3:20 AM | Permalink | Reply to this
Read the post Freed on Higher Structures in QFT, I
Weblog: The n-Category Café
Excerpt: Freed's old observation that n-dimensiopnal QFT assigns (n-d)-Hilbert spaces to d-dimensional volumes.
Tracked: September 12, 2006 3:40 PM

Re: Quantum Computation and Symmetric Monoidal Categories

Symmetric monoidal closed categories seem to be the meet of SMDs and CCCs, in that they have all the structure common to both. Is there a join? It seems like it would need a separate product and tensor product.

Posted by: Mike Stay on December 4, 2006 10:10 PM | Permalink | Reply to this

Re: Quantum Computation and Symmetric Monoidal Categories

SMDs

symmetric monoidal [categories with] duals?

Posted by: Toby Bartels on December 4, 2006 11:11 PM | Permalink | Reply to this

Re: Quantum Computation and Symmetric Monoidal Categories

Yes, exactly. Duals for objects and morphisms, AKA stongly compact closed AKA dagger compact closed.

Posted by: Mike Stay on December 4, 2006 11:18 PM | Permalink | Reply to this

Re: Quantum Computation and Symmetric Monoidal Categories

Mike Stay wrote:

Symmetric monoidal closed categories seem to be the meet of SMDs and CCCs, in that they have all the structure common to both. Is there a join? It seems like it would need a separate product and tensor product.

Acronyms are evil: they limit the number of people who can follow a conversation. If one is really too tired to type the whole word, the acronym should at least be defined when first mentioned.

  • CCC = cartesian closed category
  • SMD = symmetric monoidal category with duals

Anyway: you seem to be imagining a poset of ‘flavors of category with extra structure’. We’ve discussed ‘flavors of category with extra structure’ with (eventually) quite a bit of technical precision elsewhere on this blog: they’re called ‘doctrines’.

If you think about it a bit, you’ll see that doctrines naturally form a category. But, you’ll be hard pressed to get a poset of doctrines.

So, here’s one interesting puzzle your question raises:

  • If you’re trying to talk about the meet (greatest lower bound) and join (least upper bound) of two elements of a poset, but in fact what you’ve got is not a poset but a category, you should instead talk about the ??? and the ???? of two objects in this category.

After answering these puzzles one could make your question into a precise math question like this:

  • What are the ??? and the ???? of the doctrine of cartesian closed categories and the doctrine of symmetric monoidal categories with duals?

But, remember we had some difficulty understanding cartesian closed categories as a doctrine. So, we might prefer to use, not the official concept of ‘doctrine’, but the more relaxed concept of ‘2-category equipped with a 2-functor to Cat’. Then we’d be looking for ???’s and ????’s in the 2-category of 2-categories over Cat. This will require categorifying the concepts of ??? and ???? - but luckily, this has been done.

Of course, you may not have wanted to make your question so precise. Still, it’s nice to know that one can make it precise, so that answering it becomes a mere calculation, not requiring ‘free will’.

Anyway: I agree that in some loose sense, [symmetric monoidal closed categories] feels like the ‘meet’ of [cartesian closed categories] and [symmetric monoidal categories with duals]. That’s why I like it!

As for the ‘join’, you seem to be hinting at something about linear logic. I think linear logicians like to ponder categories that have both a noncartesian product caleld \otimes and a cartesian one called &. So, maybe a linear logician could take a stab at answering this question of yours. But, they’re more likely to know the answer with [symmetric monoidal compact closed categories] replacing [symmetric monoidal categories with duals].

Posted by: John Baez on December 5, 2006 12:16 AM | Permalink | Reply to this

Re: Quantum Computation and Symmetric Monoidal Categories

John wrote:

  • If you’re trying to talk about the meet (greatest lower bound) and join (least upper bound) of two elements of a poset, but in fact what you’ve got is not a poset but a category, you should instead talk about the ??? and the ???? of two objects in this category.

These should be the pullback and pushout, respectively. And yes, it’s clear these have n-categorical generalizations. Pushouts don’t always exist, though, right?

Posted by: Mike Stay on December 6, 2006 1:06 AM | Permalink | Reply to this
Read the post Ubiquitous Duality
Weblog: The n-Category Café
Excerpt: I'm in one of those phases where everywhere I look I see the same thing. It's Fourier duality and its cousins, a family which crops up here with amazing regularity. Back in August, John wrote: So, amazingly enough, Fourier duality...
Tracked: January 11, 2007 2:16 PM
Read the post Snowglobe Models
Weblog: The n-Category Café
Excerpt: Constructing strange 'nonstandard models' of typed λ-calculi.
Tracked: March 10, 2007 5:15 AM
Read the post Deep Beauty: Understanding the Quantum World
Weblog: The n-Category Café
Excerpt: A symposium honoring the 75th anniversary of von Neumann's book on quantum mechanics.
Tracked: September 20, 2007 5:04 AM
Read the post Spans in Quantum Theory
Weblog: The n-Category Café
Excerpt: You can use spans to understand why quantum processes act so much like pieces of spacetime.
Tracked: October 2, 2007 12:21 AM
Read the post Doctrinal and Tannakian Reconstruction
Weblog: The n-Category Café
Excerpt: Seeking what is common between Gabriel-Ulmer style dualities and Tannaka duality
Tracked: July 11, 2011 11:38 AM

Post a New Comment