Re: Quantum computation and categories

Re: Quantum computation and categories

[Peter Selinger]

Several people attempted to give a "non-evil" definition of a dagger
category. Not much of this makes sense.

Consider the following two categories:

(a) the category of finite dimensional complex vector spaces and
linear maps, and (b) the category of finite dimensional Hilbert spaces
and linear maps.

Clearly, they are equivalent categories. They have the same morphisms!
Yet everyone knows that Hilbert spaces and complex vector spaces are
not the same. For example, one can define unitary morphisms
w.r.t. Hilbert spaces, but not w.r.t. complex vector spaces. The
concept of "unitary" is itself "evil", because it is not preserved
under isomorphism of objects in the category (b)!

So whatever extra structure the category (b) has, which allows a
definition of "unitary", must be evil. Transporting this along
equivalences does not make any sense whatsoever.

Specifically, take Toby's proposal, and consider two different objects
A,B of (b) such that both A and B are two-dimensional Hilbert spaces.
Let u:A->B be some non-unitary isomorphism. Then you can easily find
an equivalence of categories which identifies both A and B with the
two-dimensional vector space C^2, and which identifies u with the
identity morphism on C^2.  At this point, you have not equipped the
category (a) with anything useful, because it does not induce a notion
of unitary map on C^2.

It is tempting to say that what is wrong with the category (b) is that
the morphisms don't accurately reflect the structure of the spaces.
Perhaps one would prefer to equip the category of finite dimensional
Hilbert spaces with unitary maps. Or with self-adjoint maps. Or with
isometries. Or with positive maps. The fact that there are so many
possible choices, and neither is strong enough to express all the
others internally, shows that this is not a good solution. One nice
feature of the dagger structure is that it does allow all of the above
to be expressed internally. So one gets lots of "evils" for the price
of one!

A sensible thing to do is to consider the category (b) of finite
dimensional Hilbert spaces with linear maps, to be also *equipped*, as
extra structure, with a distinguished lluf subcategory of isomorphisms
(the "unitary") ones. There is a natural notion of equivalence between
such categories-with-distinguished-subcategory (in particular, where
each component of the natural isomorphisms FG -> id and GF -> id is
required to lie in the subcategory). One can define a version of the
dagger structure for such categories-with-distinguished-subcategory
(in addition to the usual dagger axioms, one also must require that
the notion of "unitary" induced by the dagger structure coincides with
the distinguished subcategory that is a priori given).

Observe that the dagger structure can be transported along such
equivalence of categories-with-distinguished-subcategory. So the
dagger definition is non-evil on categories-with-distinguished-subcategory.

Unfortunately, the concept of a "distinguished subcategory" is itself
evil, if one does not require the subcategory to contain all
isomorphisms of the original category.

So it seems that, to define the extra structure of Hilbert spaces (on
top of vector spaces), one needs at least one "evil" concept, be it
that of unitary maps or the dagger structure.

-- Peter

Toby Bartels 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:
> >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]

Happy New Year!

Peter wrote:

Consider the following two categories:
>
> (a) the category of finite dimensional complex vector spaces and linear
> maps, and (b) the category of finite dimensional Hilbert spaces and linear
> maps.
>


> Specifically, take Toby's proposal, and consider two different objects A,B
> of (b) such that both A and B are two-dimensional Hilbert spaces. Let u:A->B
> be some non-unitary isomorphism.


Using "u" to stand for a non-unitary morphism!  Reminds me of the joke:

Teacher: Suppose p is a prime number...

Student: But what if it's not?

Teacher: Well then it wouldn't be called "p", now, would it!


> Then you can easily find an equivalence of categories which identifies both
> A and B with the two-dimensional vector space C^2, and which identifies u
> with the identity morphism on C^2. At this point, you have not equipped the
> category (a) with anything useful, because it does not induce a notion
> of unitary map on C^2.
>

Okay, that's a nice argument.  I'm pretty sure Lurie gave me some similar
argument: take a dagger-category, try to transport the structure along an
equivalence of categories, and get something unacceptable.

So it seems that, to define the extra structure of Hilbert spaces (on top of
> vector spaces), one needs at least one "evil" concept, be it that of unitary
> maps or the dagger structure.
>

 If this is really true (and I think it is), we're pushed towards Mark
Weber's idea: dagger-categories are not best thought of as categories but
rather something new, based on graphs-with-involution instead of graphs.

Best,
jb


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Quantum computation and categories

[Vaughan Pratt]

John Baez wrote:
> (The infinite-dimensional case would introduce extra wrinkles, like
> unbounded self-adjoint operators.  It's possible that only after we treat
> this case correctly can we declare that we know what's going on.  Perhaps
> trying to treat both unitary and self-adjoint operators as morphisms in the
> same category is simply a bad idea.  There are a lot of options worth
> exploring.)

How about starting with rigged Hilbert space?  If anything can restore
your dagger that should.  There's even a Wikipedia article on it;
something on dagger categories would be a useful addition to that article.

Vaughan

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Quantum computation and categories

[Toby Bartels]

John Baez wrote in part:

>If you treat Hilbert spaces as "sets with structure", the obvious
>morphisms are isometries - inner-product-preserving linear operators.  But
>in quantum theory, Hilbert spaces are being used for something quite
>different.  And so there's a struggle going on to understand this.

Even in quantum theory, the obvious isomorphisms --that is,
the notions of how one Hilbert space may be equivalent to another--
are invertible linear isometries, equivalently the unitary maps.

To know what Hilbert spaces really "are", we only need to understand
the groupoid of Hilbert spaces, which has ~unitary~ maps as morphisms.
But we don't stop there; we look for a more interesting or useful category
whose underlying groupoid (in an appropriate sense) is this groupoid.
We could take the category whose morphisms are short linear maps;
then the invertible morphisms are precisely the unitary maps.
Or we could take the dagger category whose morphisms are
bounded linear maps and with the usual adjoint as the dagger;
the appropriate underlying groupoid in this context consists
not of all invertible morphisms but only of those morphisms
whose daggers are their inverses, which again are the unitary maps.
(I leave open the problem of defining an appropriate structure
on the category whose morphisms are all densely defined linear maps;
in fact, I'm not even sure whether this is even a category.
But this reduces to the previous case if we restrict to finite dimensions.)

We might instead take the category whose morphisms are bounded linear maps,
with no additional structure; but this gives us the ~wrong~ isomorphisms.
So going only half way is no good here.


--Toby


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Quantum computation and categories

[John Baez]

Fred E.J. Linton wrote:


> Peter Selinger offered the thought that, considering
>
> > ... the category of finite dimensional complex
> > vector spaces vs. the category of finite dimensional Hilbert spaces.
> > They are equivalent ...
>
> Hmmm ... you mean just *any* linear transformation is allowed between two
> Hilbert spaces?
>

In applications to quantum mechanics people really want to work with both
unitary and self-adjoint operators, and often others as well.  So they work
with the category of finite-dimensional Hilbert spaces and *all* linear maps
between these.  As a mere category this is equivalent to the category of
finite-dimensional vector spaces - so to understand the "Hilbertness" of
Hilbert spaces, they introduce a dagger structure as well.

(The infinite-dimensional case would introduce extra wrinkles, like
unbounded self-adjoint operators.  It's possible that only after we treat
this case correctly can we declare that we know what's going on.  Perhaps
trying to treat both unitary and self-adjoint operators as morphisms in the
same category is simply a bad idea.  There are a lot of options worth
exploring.)


If so, I'm not so sure my Hilbert spaces are the same as yours :-) .
>

Indeed!  If you treat Hilbert spaces as "sets with structure", the obvious
morphisms are isometries - inner-product-preserving linear operators.  But
in quantum theory, Hilbert spaces are being used for something quite
different.  And so there's a struggle going on to understand this.

Best,
jb


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Quantum computation and categories

[Fred E.J. Linton]

Peter Selinger offered the thought that, considering

> ... the category of finite dimensional complex
> vector spaces vs. the category of finite dimensional Hilbert spaces.
> They are equivalent ...

Hmmm ... you mean just *any* linear transformation is 
allowed between two Hilbert spaces? Isn't the category 
of f.d. Hilbert spaces a subcategory of the category of 
Banach spaces (with linear maps of bound ≤ 1)?

If so, I'm not so sure my Hilbert spaces are the same as yours :-) .

Cheers, and Happy New Year, -- Fred




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

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

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

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