* Quantum computation and categories @ 2009-12-28 0:30 John Baez 2009-12-29 6:03 ` Toby Bartels ` (2 more replies) 0 siblings, 3 replies; 5+ messages in thread From: John Baez @ 2009-12-28 0:30 UTC (permalink / raw) To: categories Dear Dusko - You wrote: bob coecke proposed to add quantum computing to andre joyal's list of > important directions of categorical research, but andre rejected it. most results in quantum computing are theorems about hilbert spaces. quantum > computing is a *tensor calculus*. but it is a tensor calculus of a special > kind: it attempts to describe a wildly unintuitive world. even the greatest > contributors, like von neumann and feynman, deplored the gap between the > quantum world, imposed on us in the lab, and the intuitions imposed on us in > everyday life. now category theory often helps where the common intuitions > fail. many of its applications demonstrate this. so > quantum computation might be an opportunity for an effective application of > *geometry of tensor calculus*. > Exactly! Samson Abramsky, Bob Coecke, Peter Selinger and others have been doing great work along these lines. I think this line of research will eventually be the key to understanding quantum gravity, because string diagrams reveal the common features of the tensor category of Hilbert spaces (Hilb, fundamental to quantum theory) and the tensor category of cobordisms (nCob, fundamental to our traditional notion of spacetime). I argued this case here, in a nontechnical way: http://math.ucr.edu/home/baez/quantum/ And I think that regardless of whether quantum computers or quantum gravity ever work, this line of research is very interesting. > is it really wise to reject an attempt to develop this, as objectionable as > it might be in any details? Andre didn't precisely "reject an attempt to develop" these ideas. He said "I am not convinced that quantum computing can contribute significantly to category theory". And that's fine. The bold researchers listed above will now redouble their efforts to convince Andre by proving lots of wonderful theorems. Here's one point where work on quantum computing, quantum gravity, and TQFT could have a radical effect on category theory. Researchers in these subjects have been forced by the nature of the material to embrace "dagger-categories". I explain why in my article above, but I called them "*-categories" instead of dagger-categories. A dagger-category is a category C with a functor F: C -> C^{op} which is the identity on objects and has F^2 = 1. Category theorists will note that the above definition is "evil", in the technical sense of that term: http://ncatlab.org/nlab/show/evil Namely, it imposes equations between objects, so we cannot transport a dagger-category structure along an equivalence of categories. Often evil concepts (like the concept of "strict monoidal category") have non-evil counterparts (like the concept of "monoidal category"). But in this particular case I know no way to express the idea without equations between objects. Both Hilb and nCob are dagger-categories. This fact is important. Try saying it in a non-evil way! Once Andre told me some ideas about this, relating to the case of Hilb, but unfortunately I don't see that how they could apply to nCob. I was very interested at Mark Weber's reaction to this problem. He said, roughly, "So dagger-categories aren't really categories with extra structure. Okay: they're something else! And that's fine." (I'd be happy for him to correct my rough summary and make his point more precisely.) I like this bold attitude, especially coming from someone like Mark, who knows enough category theory to carry it off. This could lead to really new developments. Best, jb [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Quantum computation and categories 2009-12-28 0:30 Quantum computation and categories John Baez @ 2009-12-29 6:03 ` Toby Bartels [not found] ` <20091229060352.GA14681@ugcs.caltech.edu> 2009-12-29 14:33 ` Mark Weber 2 siblings, 0 replies; 5+ messages in thread From: Toby Bartels @ 2009-12-29 6:03 UTC (permalink / raw) To: categories John Baez wrote in part: >A dagger-category is a category C with a functor >F: C -> C^{op} >which is the identity on objects and has F^2 = 1. >Category theorists will note that the above definition is "evil", in the >technical sense of that term: >http://ncatlab.org/nlab/show/evil >Namely, it imposes equations between objects, so we cannot transport a >dagger-category structure along an equivalence of categories. >Often evil concepts (like the concept of "strict monoidal category") have >non-evil counterparts (like the concept of "monoidal category"). But in >this particular case I know no way to express the idea without equations >between objects. Both Hilb and nCob are dagger-categories. This fact is >important. Try saying it in a non-evil way! By default, there is a non-evil way to say it: Given a category C, a _non-evil dagger-category structure_ on C consists of a dagger-category C' and an equivalence F: C -> C' of categories. So one question is whether there is a less long-winded way to say that. Another question (which logically comes before the first question) is what is the right notion of equivalence of such structures. --Toby [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 5+ messages in thread
[parent not found: <20091229060352.GA14681@ugcs.caltech.edu>]
* Re: Quantum computation and categories [not found] ` <20091229060352.GA14681@ugcs.caltech.edu> @ 2009-12-29 7:30 ` John Baez 0 siblings, 0 replies; 5+ messages in thread From: John Baez @ 2009-12-29 7:30 UTC (permalink / raw) To: Toby Bartels Toby wrote: John Baez wrote in part: > > >A dagger-category is a category C with a functor > >F: C -> C^{op} > >which is the identity on objects and has F^2 = 1. > > >Category theorists will note that the above definition is "evil", in the > >technical sense of that term.... > > By default, there is a non-evil way to say it: > > Given a category C, a _non-evil dagger-category structure_ on C > consists of a dagger-category C' and an equivalence F: C -> C' of > categories. > Yes, you can do that. But Jacob Lurie has argued (in email to me) that the resulting notion is problematic. So, he took a different tack in his work on the cobordism hypothesis. I'd need to review that email to say more... Best, jb [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Quantum computation and categories 2009-12-28 0:30 Quantum computation and categories John Baez 2009-12-29 6:03 ` Toby Bartels [not found] ` <20091229060352.GA14681@ugcs.caltech.edu> @ 2009-12-29 14:33 ` Mark Weber 2009-12-31 1:54 ` in defense of strictness Peter Selinger 2 siblings, 1 reply; 5+ messages in thread From: Mark Weber @ 2009-12-29 14:33 UTC (permalink / raw) To: John Baez, categories Greetings all and thanks to John for the friendly provocation ... I was very interested at Mark Weber's reaction to this problem. He said, > roughly, "So dagger-categories aren't really categories with extra > structure. Okay: they're something else! And that's fine." (I'd be happy > for him to correct my rough summary and make his point more precisely.) > OK. First of all when thinking about cobordisms, or paths, or homotopies, the act of reversing orientation is fundamentally strictly involutive. So at first glance, it's not at all clear what would be gained by weakening in this case, despite the light that replacing equations by isomorphisms sheds on so many other mathematical situations. Algebraically also, it appears natural to think of the strict involutions as more fundamental. Just as categories are algebras of a very nice and easily described monad on the presheaf topos of graphs, "dagger categories" (I think the terminology "involutive category" would be better) are algebras of an analogous monad on the presheaf topos of involutive graphs. An involutive graph is a graph together with an involution on the set of edges which switches sources and targets. Formally the dagger category monad is obtained by a canonical lifting of the category monad through the forgetful functor from involutive graphs to graphs, so we have a canonical monad distributive law describing this situation. The observations of the previous paragraph generalise a lot and rather easily, and this encourages me to resist any urge to weaken the involutory aspects of the notion of dagger category. So the "something else" of John's post is that dagger categories are *involutive graphs* with structure, and their higher dimensional analogues are *involutive n-globular sets* with structure. So all the way up the dimensional ladder, regardless of how weak your higher compositions happen to be, if involutions (to model orientation reversals) are to be part of the picture, then I think they should be strict and strictly compatible with all the compositions and coherence data. For those still interested, I'll now give a few more details. First some background. In http://arxiv.org/abs/0909.4715 Michael Batanin, Denis-Charles Cisinski and I reformulated much of the "Batanin approach" to defining higher categories as the study of monads on categories of enriched graphs, particularly those that arise from multitensors. Briefly, given a category V, one can associate to any "distributive multitensor on V" (which is a lax monoidal structure on V such that the n-ary tensor product functor V^n-->V preserves coproducts in each variable), a monad on the category GV of graphs enriched in V. So for example this process takes the cartesian product for Set to the category monad on Graph. The operads used by Batanin to define weak higher categories, seen as certain monads on the presheaf topos G^n(Set) of n-globular sets, also arise in this way. One can also consider the category G_i(V) of involutive graphs enriched in V, and so begin to consider structures defined by monads on the presheaf topos (G_i)^n(Set) of what would be sensible to call "involutive n-globular sets". An involutive graph enriched in V is a V-graph X together with, for each pair of objects a,b from X, maps i_(a,b) : X(a,b) --> X(b,a) in V such that for all a,b, i_(b,a)i_(a,b) = identity. It is easy to verify that both processes V |-> GV and V |-> G_i(V) preserve presheaf toposes, so (G_i)^n(Set) really is a presheaf topos. To spell out the generalisation alluded to above, let E be a distributive multitensor on V, and write (as in the above paper) Gamma(E) for its associated monad on GV -- corollary(4.5) of our paper indicates an explicit formula. This formula is easily adapted to the involutive case to describe the monad Gamma_i(E) on G_i(V) and this is by definition a canonical lifting of Gamma(E) though the forgetful G_i(V)-->GV. In summary, for any higher categorical structure of interest, there is an involutive version (eg one can define involutive Gray categories), and from the above remarks we understand as much about the monads which describe them as we do their non-involutive counterparts, and moreover there's a canonical distributive law relating them. For me the interesting question now is how to adapt this to give an explicit description of monads which describe weak higher groupoids (with strictly involutive "inverse operations"). Steve Lack and I observed recently that ordinary groupoids are algebras for a monad on the category of involutive graphs, which arises via a *weak* distributive law in the sense of http://www.tac.mta.ca/tac/volumes/22/12/22-12abs.html between the category monad on Graph and the involutive graph monad on Graph, but I really don't see yet how this generalises. Best new years wishes to all, Mark Weber [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 5+ messages in thread
* in defense of strictness 2009-12-29 14:33 ` Mark Weber @ 2009-12-31 1:54 ` Peter Selinger 0 siblings, 0 replies; 5+ messages in thread From: Peter Selinger @ 2009-12-31 1:54 UTC (permalink / raw) To: Categories List Here is a bit of hyperbole. Hopefully entertaining. Suppose, hypothetically, that category theorist X had a close look at the definition of "inverse": morphisms f : A -> B and g : B -> A are inverses if fg = id_B and gf = id_A. Suppose that she makes the following argument: "The definition of inverse is really too strict. It requires an equation between objects, namely, the domain of f must equal the codomain of g, and vice versa. A natural thing to do would be to weaken the definition to replace this equality by an isomorphism." So what definition would she come up with? Definition. Let f : A -> B be a morphism. A *weak inverse* of f is given by the following data: (1) Objects A', B', and a morphism g : B' -> A' (2) an isomorphism a : A' -> A (3) an isomorphism b : B' -> B (4) such that the following diagram commutes: g A' <------- B' a | | b v f v A --------> B Everybody can see that this is nonsense. First, one must have a prior definition of isomorphism before one can define inverse in this way. But the definition of isomorphism depends on inverses, so this is circular. Second, each "weak inverse" in the above sense already gives rise to an ordinary inverse, namely a o g o (b^{-1}). Perhaps category theorist X would like to formulate this as a Coherence Lemma ("each weak inverse is canonically equivalent to a strict inverse"). But it is clearly nonsense nevertheless. Naive attempts to define a weak version of dagger structure fall into the same category. Recall the definition of a dagger structure on a category, namely a contravariant, involutive, identity-on-objects functor. Or in elementary terms: to each f : A -> B, associate some f+ : B -> A, such that f++ = f, (fg)+ = (g+)(f+), and id+ = id. Each category theorist (including myself) who sees this definition immediately dislikes the identity-on-objects part. The first instinct is to try to weaken it. But what would one come up with? After one or two failed attempts, it seems that the "correct" definition is the following: a contravariant functor (-)+, and for each object A a chosen unitary isomorphism a_A : A+ -> A, such that one has the following diagram (but note that it doesn't have to commute): f+ A+ <------- B+ a_A | | a_B [not assumed to commute] v f v A --------> B Plus, there should be some further requirement to replace the "involutive" condition (i.e., the obvious diagram involving f and f++ should commute), and perhaps a coherence condition or two. Note that a_A and a_B must be assumed to be unitary. The analogous definition where they are just isomorphisms does not work for a variety of reasons. For example, this is supposed to be a weakening of the strict situation, and identities are always unitary. The problem with any such definition is the same as for the "weak inverses" hyperbole above. First, to define dagger in this way, one must have a prior definition of "unitary", but the definition of "unitary" depends on "dagger", so this is circular. Second, given any weak dagger structure in this sense, it already induces a strict dagger structure, namely by using a_A o f+ o (a_B^{-1}) : B -> A as the strict dagger. One could again regard this as a coherence lemma, but it's clearly a pointless one. Actually, my leading example of "weak inverses", while ludicrous, is not entirely besides the point. One of the main reasons for considering dagger structure is so that we can define a morphism u : A -> B to be unitary if u+ is the inverse of u. Trying to say this with the "weak" dagger structure inevitably leads to weak inverses. In light of all this, I completely agree with Mark Weber that dagger structure should be strict and that is what we should live with. -- Peter [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2009-12-31 1:54 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2009-12-28 0:30 Quantum computation and categories John Baez 2009-12-29 6:03 ` Toby Bartels [not found] ` <20091229060352.GA14681@ugcs.caltech.edu> 2009-12-29 7:30 ` John Baez 2009-12-29 14:33 ` Mark Weber 2009-12-31 1:54 ` in defense of strictness Peter Selinger
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).