Classical vs Quantum Computation (Week 1)
Posted by John Baez
Here are yesterday’s notes on classical versus quantum computation:
-
Week 1 (Oct. 5) -
Types and operations. Categories as theories. Monoidal categories versus categories with finite products - also known as “cartesian categories”.
- Homework: show that every category with finite products can be made into a monoidal category - see above notes for details.
Last week’s notes are here; next week’s notes are here.
Faithful readers of this blog will see that among other things, I’m preparing the students for Lawvere’s mindblowing theory of doctrines. I’m also teaching them the tao of mathematics, by showing a bunch of ways you could get the definition of monoidal category wrong.
As I explained in the seminar, a good graduate course in mathematics should require not just that students prove theorems, but also guess the right definitions. Good definitions slice the concepts neatly, instead of hacking away at them. To make good definitions, you have to learn the tao of mathematics. For example:
- The Indians contributed nothing to mathematics - and it’s been incredibly useful ever since. Definitions involving sets should apply to the empty set without special exceptions. Similarly, definitions should apply to all natural numbers, not just > 0. For example, when you have binary associative product, which lets you define -ary products for all > 0, you should also have a unit, which lets you define 0-ary products. This comes up in the definition of “monoid”, and also - as we saw in this lecture - the definition of “monoidal category”. A monoidal category has a tensor product - so it wants to have a unit, too!
- Don’t say two objects in a category are equal, and don’t just say they’re isomorphic: specify an isomorphism between them. And, if this isomorphism depends on a parameter, it should be a natural isomorphism. This too comes up in the definition of monoidal category, when we’re trying to impose the laws governing the tensor product and unit.
These are just two of many rules of thumb a good mathematician should know. Like all rules of thumb, they admit exceptions - but they’re still important to know.
Right now math grad students have to pick up these rules of thumb in a hit-or-miss way. Maybe someday we’ll write a book about them!
Re: Classical vs Quantum Computation (Week 1)
Through the notes (top of page 10), you write:
The kind of operation that we get directly from the lambda calculus, such as λxyz.t, has many inputs but only one output. For this, we don’t need a tensor category but rather (merely) a multicategory. Here, there is no notion of tensor product, but instead the fundamental notion is multimorphism, a generalisation of a function of many variables (as in the category of sets) or multilinear transformation (as in a category of linear spaces).
Of course, I know that you’re working towards CCCs, so you’ll eventually give your categories far more structure than this —enough structure to handle the pairing operations in lambda calculus. So there’s no harm in skipping multicategories (which, after all, are more complicated to define than monoidal categories —see my attempt to write it out). But it’s worth pointing out to interested people that they’re there.
(PS: Also, the TeXnician in me must point out that there should be a comma after “i.e.”. Please forgive me.)