Quantum computation and categories

Quantum computation and categories

[John Baez]

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/ ]

Re: Quantum computation and categories

[Toby Bartels]

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/ ]

Re: Quantum computation and categories

[John Baez]

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/ ]

Re: Quantum computation and categories

[Mark Weber]

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/ ]

in defense of strictness

[Peter Selinger]

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/ ]