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.

September 29, 2010

Jacob Biamonte on Tensor Networks

Posted by John Baez

One of the unexpected pleasures of starting work at the Centre for Quantum Technologies was realizing that the math I learned in loop quantum gravity and category theory can also be useful in quantum computation and condensed matter physics!

In loop quantum gravity I learned a lot about “spin networks”. When I sailed up to the abstract heights of category theory, I discovered that these were a special case of “string diagrams”. And now, going back down to earth, I see they have a special case called “tensor networks”.

Jacob Biamonte is a postdoc who splits his time between Oxford and the CQT, and he’s just finished a paper on tensor networks:

He’s eager to get your comments on this paper, since while it’s aimed at people who already know about tensor networks, it uses a lot of things we talk about here: for example, algebras and coalgebras in symmetric monoidal categories! So, if you folks can’t understand this paper, or find it insufficiently precise, he’d like to hear from you.

Heck, he’d also like to hear from you if you love the paper! But as usual, the most helpful feedback is not just a pat on the back, but a suggestion for how to make things better.

Let me just get you warmed up here…

There’s a general theory of string diagrams, which are graphs with edges labelled by objects and vertices labelled by morphisms in some symmetric monoidal category with duals. Any string diagram determines a morphism in that category. If you hang out here, there’s a good chance you already know and love this stuff. I’ll assume you do.

To get examples, we can take any compact Lie group, and look at its category of finite-dimensional unitary representations. Then the string diagrams are called spin networks. When the group is SU(2)SU(2), we get back the original spin networks considered by Penrose. These are important in loop quantum gravity.

But when the group is the trivial group, it turns out that our string diagrams are important in quantum computation and condensed matter physics! And now they go by a different name: tensor networks!

The idea, in a nutshell, is that you can draw a string diagram with all its edges labelled by some Hilbert space HH, and vertices labelled by linear operators. Suppose you have a diagram with no edges coming in and nn edges coming out. Then this diagram describes a linear operator

ψ:H n \psi : \mathbb{C} \to H^{\otimes n}

or in other words, a state

ψH n \psi \in H^{\otimes n}

This is called a tensor network state. Similarly, if we have a diagram with nn edges coming in and mm coming out, it describes a linear operator

T:H nH m T : H^{\otimes n} \to H^{\otimes m}

And the nice thing is, we can apply this operator to our tensor network state ψ\psi and get a new tensor network state TψT \psi. Even better, we can do this all using pictures!

Tensor networks have led to new algorithms in quantum computation, and new ways of describing time evolution operators in condensed matter physics. But most of this work makes no explicit reference to category theory. Jacob’s paper is, among other things, an attempt to bridge this cultural gap. It also tries to bridge the gap between tensor networks and Yves Lafont’s string diagrams for Boolean logic.

Here’s the abstract of Jacob’s paper:

We present a set of new tools which extend the problem solving techniques and range of applicability of network theory as currently applied to quantum many-body physics. We use this new framework to give a solution to the quantum decomposition problem. Specifically, given a quantum state S with k terms, we are now able to construct a tensor network with poly(k) rank three tensors that describes the state S. This solution became possible by synthesizing and tailoring several powerful modern techniques from higher mathematics: category theory, algebra and coalgebra and applicable results from classical network theory and graphical calculus. We present several examples (such as categorical MERA networks etc.) which illustrate how the established methods surrounding tensor network states arise as a special instance of this more general framework, which we call Categorical Tensor Network States.

Take a look and say what you think! Jacob will be watching this blog, and will respond to any questions you have.

Posted at September 29, 2010 10:49 AM UTC

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

44 Comments & 0 Trackbacks

Re: Jacob Biamonte on Tensor Networks

Seems to be some problem with the link to the paper.

Posted by: Eric on September 29, 2010 1:15 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Could be just me, but the server doesn’t seem to be responding, so the link is probably fine:

http://www.comlab.ox.ac.uk

Posted by: Eric on September 29, 2010 1:38 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

The link seems to be working fine now.

I bet the server crashed when millions of nn-Café readers simultaneously tried to download Jacob’s paper.

Posted by: John Baez on September 29, 2010 2:39 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

That must be it :)

The link still doesn’t work for me though. I’ll try when I get home.

Posted by: Eric on September 29, 2010 2:52 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Wow, lots of downloads!: the comlab link seems to work again, but here’s a backup just in case.

Posted by: Jacob Biamonte on September 29, 2010 4:53 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

I imagine some people are looking at your paper now, but maybe you could jump-start the conversation by saying a bit more about what you actually do in this paper. For example, I was feeling too busy to explain the basic idea of encoding Boolean logic in quantum gates.

Posted by: John Baez on September 30, 2010 6:40 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

This is an exciting topic! Matrix product states (tensor network states) arose from the field of quantum information science as a way to efficiently express the states of quantum many-body systems (here’s a review). These methods are important because computer simulations are the backbone of just about everything - quantum systems seem very difficult to simulate using classical computers. No one is totally sure why this is, but that’s another story that tensor networks might help us write.

A key idea behind using a tensor network based computer algorithm to describe a large class of quantum states efficiently is to use the SVD iteratively: skipping details, you simply throw away small singular values (hence truncate the Hilbert space). In many cases this provides highly accurate descriptions of quantum states. My friends and collaborators, Stephen Clark and Dieter Jaksch made some nice slides for our course that outline the current approach:

Lecture 8 Slides (PDF) - Stephen Clark

Background slides by Dieter Jaksch (PPT and PDF)

Lecture 9 Slides (PDF) - Stephen Clark

They look a lot like string diagrams, right?! That’s what got me excited about this topic! There was a bit of a blur and then I met John Baez: after hearing about spin networks I got even more excited and started to understand just how long this stuff had been around!

I wanted to say something more to the tensor networks and quantum information community than “BTW category theory is awesome and you’re already using category theory” this is because I didn’t want to hear: “if I’m already using it, why do I need it?”. Do we need it? Yeah, I think I’ve shown a few reasons why we now do!

The current tensor network approach revolves around ways to approximate quantum states; what I did was create a way to control the type of states created (to zoom in and expose internal structure internal to the network tensors). It’s pretty fun.

Say you have a quantum state, the quantum AND-state: |000>+|010>+|100>+|111> and if we draw this as a network (AND-gate with two-inputs and one-output), and place a |1> on the output and run the network backwards, this leads to the state |00> + |01> + |10>. The idea is we can now “wire” these quantum logic tensors together to create larger and larger tensor network states. Now I’ll say more after I can figure out how to embed figures here!

Posted by: Jacob on September 30, 2010 9:40 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Ha, should have been…, given an AND-state: |000>+|010>+|100>+|111> and if we draw this as a network (AND-gate with two-inputs and one-output), and place a |0> [not a |1>!!!] on the output and run the network backwards, this leads to the state |00> + |01> + |10>! Placing a |1> on the output and running the network backwards would result in the product state |1>|1>.

We can even create a full logic family of states, NAND-states, NOR-states, etc., where the input is on the first two left qubits and the output is on the third (right most) qubit. These were used in examples in the paper.

Posted by: Jaocb on September 30, 2010 10:25 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

To get us kick started, sometimes pictures speak a lot, and in this case well maybe 200 words tops:

This is a quantum AND-tensor. It’s actually corresponds to a valid quantum operation - you can realise this gate in a lab, but that’s not important for us here.

What’s nice is that we can start to hook these quantum logic-tensors together and build larger and larger tensors that represent quantum states.

This let’s us do a few nice things. For example, in the current approach, matrix product states look like this:
Matrix Product W-State

Now using our quantum logic-tensors, where able to translate a quantum state into a tensor network. For instance, here is what the internal structure of a so-called W-state (|00…1>+|01…0>+|10…0>)
looks like:

Categorical Tensor Network W-state

Posted by: Jacob on September 30, 2010 2:13 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Tensor networks have led to new algorithms

Maybe just for the readers who are wondering, and since you didn’t mention it this time: “tensor networks” are known and intensively studied since the end of the 19th century. At least. The traditional notation for a tensor network does not use lines, but uses indices. A typical tensor network would be denoted

R μ νλκG λκν αg αβ R^{\mu}{}_{\nu \lambda \kappa} G^{\lambda \kappa \nu}{}_{\alpha}g^{\alpha \beta}

etc.

The claim is that just by changing this standard notation, one gains insight. The observation of the usefulness of this change of notation is usually attributed to Penrose.

Posted by: Urs Schreiber on September 30, 2010 8:35 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Cool, one can find the paper typically cited for these ideas online here:

Paper by Penrose

Take a look at those diagrams!

The standard citation is:

Applications of negative dimensional tensors, Roger Penrose, in Combinatorial Mathematics and its Applications, Academic Press (1971).

Posted by: Jacob on September 30, 2010 9:46 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

The claim is that just by changing this standard notation, one gains insight.

One insight is that tensor interchange phenomena can be modeled by homotopies in 2 dimensions, and with that one gains power and speed by visualizing these on a sheet of paper. The 1-dimensional notation masks that.

Posted by: Todd Trimble on September 30, 2010 12:45 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Hi Todd, do you happen to have a reference for this? I’m still trying to get a handle on what’s been done in related areas, and this sounds interesting. Should be a few nice tricks there to take a look at. Many thanx from Matsudo Japan.

Posted by: Jacob on September 30, 2010 2:00 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Hi there, Matsudo Japan. I think Todd is just making the point that the 2d graphical notation is powerful from a practical perspective, especially when it comes to identities like the yanking rule.

I took a look at your paper. Can you explain Theorem 35 a bit? How can you create, for example, (|0+i|1)/2(|0\rangle + i |1\rangle) / \sqrt{2} just using GHZ and AND?

Posted by: Jamie Vicary on September 30, 2010 2:58 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Hey Jamie - let’s do your example and when I wake up tomorrow (it’s real late in Japan), I’ll talk more about the theorem.

So, first, I’m going to solve your example 2nd - late isn’t it? Let’s consider a network realisation of

S = |01> + |10> + α\alpha|11>

We first write down a function f Sf_S such that

f S(0,1)=f S(1,0)=f S(1,1)=1f_S(0,1) = f_S(1,0) = f_S(1,1) = 1

and f S(00)=0f_S(00)=0 (in this case, f Sf_S is the logical OR-gate). We post select the network on |1>, which results in the state

|01> + |10> + α\alpha|11> (see (a) in the following Figure).

The next step is to realise a diagonal operator, that acts on identity on all inputs, except |11> which gets sent to α\alpha|11>.

To do this, we design a function f df_d such that

f d(0,1)=f d(1,0)=f d(0,0)=0f_d(0,1)=f_d(1,0)=f_d(0,0)=0

and f d(1,1)=1f_d(1,1)=1 (in this case, f df_d is the logical AND-gate). This diagonal, takes the form (b) in the Figure. The final state

S=|01> + |10> + α\alpha|11>

is realised by connecting both networks, leading to the network in (c).

Now for your state, post select one of the outputs (open legs in (c) above) to |0> + |1> and here set f Sf_S to XOR, f df_d again to AND, and α\alpha := i. I’m clearly ignoring the normalisation factors.

Posted by: Jacob on September 30, 2010 6:11 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

(If I may presume to speak for myself) a standard reference is one you surely know, The Geometry of Tensor Calculus by Joyal and Street, where monoidal categories freely generated from a tensor scheme are represented in terms of isotopy classes of progressive planar string diagrams.

It’s more than a matter of practical utility (although that is a huge part of the appeal of string diagram calculus): the links between geometry and categorical algebra run deep. The yanking move is a good case in point: this is the first in the line of (higher) categorical adjunctions whose equations correspond to isotopies that exhibit cancellation of critical points in Morse Theory. Unfortunately, this type of thing has never been written up properly as far as I am aware. Some of my own stammering attempts at developing surface diagram calculus are partially written up here.

Posted by: Todd Trimble on September 30, 2010 4:24 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Some of my own stammering attempts at developing surface diagram calculus are partially written up here.

This might be a better link (although I’m having some technical difficulties at the moment).

Posted by: Eric Forgy on September 30, 2010 5:14 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Cool, thanx!

Posted by: Jacob on September 30, 2010 7:51 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Todd wrote:

One insight is that tensor interchange phenomena can be modeled by homotopies in 2 dimensions, and with that one gains power and speed by visualizing these on a sheet of paper. The 1-dimensional notation masks that.

Jake wrote:

Hi Todd, do you happen to have a reference for this? I’m still trying to get a handle on what’s been done in related areas, and this sounds interesting.

I think you already know the fact Todd is telling you; he’s probably just saying it in a way you find unfamilar.

“Modelling tensor interchange phenomena by homotopies in 2 dimensions” is just a super-groovy way to say that you can wiggle string diagrams around without changing their meaning, most fundamentally like this:

This is a graphical depiction of a particular consequence of the so-called interchange law:

(fg)(fg)=(ff)(gg) (f \otimes g) \circ (f' \otimes g') = (f \circ f') \otimes (g \otimes g')

which in turn comes from the fact that \otimes is a functor.

The classic references where all this stuff was made completely precise are these papers by Joyal and Street:

Read these papers and do them proper homage!

Posted by: John Baez on October 1, 2010 2:36 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

The link to ‘Geometry of tensor calculus II’ is not correct.

Posted by: David Roberts on October 1, 2010 8:20 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Thanks — fixed.

Posted by: John Baez on October 1, 2010 8:32 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

For viewing enjoyment, here is the Urs example tensor:

Posted by: Jacob on October 2, 2010 12:51 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

How is this related to the categorical quantum mechanics that Bob Coeke and his group have been working on for a while? I’ve never gotten deep into it, but I thought it was the same idea of using monoidal categories and graphical calculus to describe quantum computation.

Posted by: Mike Shulman on September 30, 2010 9:07 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Yeah, that’s GREAT stuff! We don’t consider quantum computing or observables in this work, but yeah, as mentioned in the paper, parts are related to categorical quantum mechanics and also current existing graphical methods in quantum many-body physics as well as a few other areas, such as Lafont’s early work on Boolean circuits. We of course make use of \dagger-compactness present in categorical quantum theory. Here’s an article written by my friends Bob and Ross Duncan (wow, check out how serious Ross is about his diagrams here on interacting quantum observables.)

So my work uses the same categories: the results, aim (outcome) and focus are otherwise utilising some different and also some related concepts. In particular, the aim here is to address topics of interest in the tensor network literature, and to make a contribution to the state of the art in graphical languages for physics (e.g. not just formalising the existing ad hoc stuff!). All of this stuff is clearly based on monoidal categories and should also be important for those working in categorical quantum theory.

I’m going to talk more about why it’s important to now have a method to translate a given quantum state into a tensor network, and how this places a nice handle on a few things and extends the state of the art in tensor network theory.

Posted by: Jaocb Biamonte on September 30, 2010 10:33 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

The most interesting part from above is to check out how serious Ross Duncan is about his diagrams:

ross

Posted by: Jacob on September 30, 2010 10:49 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Oh, hey, we can even put Ross here:
ross

Posted by: Jacob Biamonte on October 1, 2010 11:07 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Mike wrote:

How is this related to the categorical quantum mechanics that Bob Coecke and his group have been working on for a while? I’ve never gotten deep into it, but I thought it was the same idea of using monoidal categories and graphical calculus to describe quantum computation.

All that is the same… but there’s also something different going on here.

For starters, it turns out there’s a community of people who use ‘tensor network states’ to study condensed matter physics, and they’ve got some ideas that haven’t fully been integrated with those of the ‘categorical quantum mechanics’ crowd. For a lightning introduction, try Section II of

This paper is actually about classical stochastic systems, but Section II nicely summarizes the story for quantum systems. Since some lazy rascals won’t actually click the link and read this paper, I’ll summarize the summary for you:

‘Matrix product states’ are a special class of states in the Hilbert space that we use to describe a bunch of atoms in a row: HHHH \otimes H \otimes \cdots \otimes H As I sketched in my blog entry, these states are special because they are easy to draw using string diagrams. But they are also special in that each atom’s quantum state is only entangled with those of its nearest neighbors… or perhaps next-nearest neighbors, etc.

In fact these two special properties are closely related.

Now, it might seem very limiting to focus attention on this special class of states. Luckily, it turns out that the lowest-energy states of a row of atoms is often close to a state of this form! Why? Because entanglement drops off quickly with distance.

Using this idea, we can carry out an interesting approach to renormalization, called the Multiscale Entanglement Renormalization Ansatz or MERA. It has the advantage of letting us efficiently simulate the dynamics of a chain of atoms using a computer!

This might be a pretty good place to get the idea:

And the really cool thing is that these chains of atoms — also called ‘spin chains’ — can often be simulated nicely using quantum computers! General-purpose quantum computation is still in its infancy (at best), but these particular systems can be simulated using a special-purpose gizmo called an optical lattice.

So, there’s a lot of fun stuff going on here: category theory, renormalization, condensed matter physics, and actual laboratory work using quantum computers!

Posted by: John Baez on October 1, 2010 9:04 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

This paper is actually about classical stochastic systems, but Section II nicely summarizes the story for quantum systems.

I often think of quantum systems as classical stochastic systems (wick rotated).

If you had said “quantum stochastic system” my head would have probably done a 360 like in the Exorcist.

Posted by: Eric on October 1, 2010 9:32 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

QUANTUM STOCHASTIC SYSTEM!

Now let’s watch Eric’s head do a wicked rotation.

(Quantum stochastic systems do exist, that’s what that Lindblad equation describes. But I’ve got a lot of questions about that, and so far nobody is answering.)

Posted by: John Baez on October 1, 2010 10:32 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Hi John,

A little more precisely: the matrix product states are exactly the states with a bounded Schmidt rank across every cut. That is, pick any division of the chain into left and right, do a Schmidt decomposition of the wavefunction across that cut, and the matrix product states are those with bounded Schmidt rank on every such cut (the bound on the Schmidt rank is called the “bond dimension” of the matrix product state, and the larger this number is, the more accurate the results typically are since you have a bigger class of states, but the more CPU time it takes).

This works because in many cases the states we are actually interested in have very rapidly decaying Schmidt coefficients across every cut. So, truncating to the largest few Schmidt coefficients makes small error.

The decay on Schmidt coefficients follows from something called an “area law”, a system-size independent bound on entanglement. I managed to prove an area law for arbitrary local 1 dimensional Hamiltonians with a spectral gap (see http://arxiv.org/abs/0705.2024 ) with no other assumptions, so in fact it is a very general property. Conversely, states without a gap can fail to obey an area law, in that the entanglement can then diverge with system size.

One subtle point (since you mentioned “entanglement drops off with distance”) is the difference between entanglement and correlations. For example, we also know that a local Hamiltonian with a spectral gap has exponentially decaying correlations. So, one might hope to use that to prove an area law. The handwaving argument is: if the correlations decay rapidly then one can only entangle with nearby spins. However, this doesn’t work: there exist families of states, with uniform bounds on the correlation length and Hilbert space dimension on each site, but with arbitrarily large entanglement. This construction is based on “quantum expanders” (introduced by Ben-Aroya and Ta-Shma in a computer science context and by myself in a mathematical physics context) which generalize expander graphs.

Matt

Posted by: matt on October 1, 2010 6:04 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

This is a fun (deep topic!). So here are a few links to help readers track down some background:

(i) here is the paper Matt mentioned: proves an area law for arbitrary local 1 dimensional Hamiltonians with a spectral gap with no other assumptions. (see also, Entropy and entanglement in quantum ground states also by Matt Hastings)

(ii) here is a review on Entanglement in Many-Body Systems by Amico, Fazio, Osterloh and Vedral.

(iii) here here is a review “Area laws for the entanglement entropy” by Eisert, Cramer and Plenio.

I’m still working on connecting up the categorical network theory to the area laws stuff - I say connect, but really I mean “say something new about area laws” using these tricks. Stephen Clark had a few ideas in this direction - if anyone else has any ideas, please send something over. I hope to run into a few of the masters of this trade at seminars and workshops this year.

To that end, I’ll go to CQT this year for QIP (maybe if these great comments keep rolling in my preprint will evolve enough to be accepted :)

QIP 2011 - Call for submissions

14th workshop on Quantum Information Processing
Tutorials January 8-9, NUS, Singapore
Workshop January 10-14, The Capella, Sentosa Singapore

Conference Website: here

Paper Submission: here

Never been to The Capella, but Sentosa is where they keep the sand!

Posted by: Jacob on October 2, 2010 12:01 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Jacob,

Maybe you would be interested to look at http://arxiv.org/pdf/0707.2260 by Perez-Garcia and others. The concept of “injectivity”, as they generalized it to 2d from earlier work in 1d, seems to me to be very deep. Just a guess, but perhaps you would be interested.

Matt

Posted by: matt on October 4, 2010 8:50 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

I should mention just a bit more about graphical methods in quantum physics! This stuff has been around for ages, even outside of the tensor network stuff, which is much more recent. Quantum computation reserach took graphical methods in quantum mechanics to a very high level over the last 20+ years in what’s called the the quantum circuit model.

David Deutsch is one of the pioneers here, in 2008 he became a FRS, the Society described Deutsch’s contributions as:

“…the theory of quantum logic gates and quantum computational networks”

Here’s a picture of a quantum logic gate from wikipedia:

Having this theory in place is one of the things that enabled a lot of these new great ideas about tensor network states!

Posted by: Jacob on October 2, 2010 2:28 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

What I think is the main drawback of the quantum circuit model (despite the fact that as Jake stresses, it “enabled a lot of these new great ideas about tensor network states” and many other things) is the `total arity’ of the bipartite gate which is required for universal quantum computing. This total arity is 2 inputs + 2 outputs = 4 (think `duals’ here!). On the other hand, a (co)multiplication of say a commutative Frobenius algebra (CFA), by which the nodes in such a bipartite gate can be modeled, has total arity three, which is exactly the arity of the so successful typical calculus and algebra operations.

For example the 4-ary CNOT gate breaks down into two 3-ary CFAs representing a pair of complementary observables (see this paper with Ross Duncan already mentioned above by Jake), which interact with each other as a bialgebra. One can also decorate each of the nodes representing observables with `phases’, which for abstract reasons form an abelian group, and give rise to a generalized `spider theorem’ (if I would know how, I’d had put the picture here on page 24 of this paper). These phased spiders are universal for representing linear maps in FHilb and hence also for quantum computation, and in contrast to the many equations between quantum gates the researchers in working with quantum circuits had to remember, now these are reduced to nothing more than the generalized spider law and the bialgebra interaction. The classical projection of this, i.e. no phases, is then a fragment of Yves Laffont’s decomposition of circuits in 3-ary nodes, mentioned above by Jake, involving XOR and copy. There is also earlier work by Carolyn Brown and Graham Hutton in this direction, who drew directly from the seminal Carboni-Walters paper, in Categories, allegories, and circuit design.

This language was used by Ross Duncan and Simon Perdrix in this paper to solve an open problem on translations and corresponding required resources between the quantum circuit computational model and the (to my opinion conceptually more fascinating) measurement-based quantum computational model (MBQC), due to Hans Briegel and Robert Raussendorf (check out the cobordisms on his whiteboard), and also Dan Browne. In the MBQC model `the collapse of the wave function does all the computational work’; no gates are applied, but only measurements on a large multipartite state, which can be diagrammatically represented by lattices of alternating nodes of those that make up the CNOT gate. The above mentioned language of two kinds of generalized spiders allowed to represent both the multipartite state and the measurements thereon within a very simple calculus. It even turned out the the topology of the graphical representation is key to the statement of Ross’ and Simon’s result.

The MBQC model turned out really hard to study since the bulk of the methods in the quantum computation community was so much relying on the circuit model, that methods didn’t carry over to MBQC. For example, it suffices to consider the totally unintuitive presentation of quantum teleportation (which is in fact an example of a MBQC setting) in terms of the circuit model, versus the presentation in a dagger compact category, where it directly relies on the basic axiom of the structure. The school reported on here at the cafe was in fact the closing event of a European Research Network which had as a main workpackage the use of categorical methods to make that bridge, replacing the standard circuit model methods (which had proved to be inadequate for MBQC) by categorical methods.

On a related note, in this paper with Aleks Kissinger we make a similar point on total arity, now for crafting multipartite qubit states, from two kinds of nodes, namely a special CFA that represent the threepartite GHZ-state and and `anti-special’ CFA that represent the threepartite W-state (these are the only kinds of non-degenerate threepartite states up to local operations and classical communication). Interestingly, this carries the classification of threepartite states over to a classification of CFAs on two-dimensional Hilbert space. This is kind of cool: from a result in quantum computing follows a representation theorem for (co)algebras.

Btw if you want to draw the pictures of this paper Aleks has produced a graphical interface that produces latex code.

Posted by: bob on October 2, 2010 2:39 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Yeah, awesome point. I totally forgot to mention that really basic point - I should have pointed out that in MERA quantum circuits, those blue tensors with 3 legs, those are what Bob calls 3-arity operators.


Posted by: Jacob on October 2, 2010 4:25 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

From another angle: the language of monads in Haskell gives a good machine readable notation for talking about tensor networks. Although I don’t think I explicitly say so, this talk I gave last year to a computer science audience is about using monads to code up tensor networks for probability, vector arithmetic, quantum computing and knot theory. It’s geared more towards writing working programs than explaining deep mathematics. As it uses none of the methods mentioned by Jacob it isn’t efficient. But it does give surprisingly readable code and is fun to play with. The notation used to represent a knot, say, is in fact the code to work out how to disentangle it.

Posted by: Dan Piponi on September 30, 2010 9:41 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Ah, I get it! “Tensor networks” are just about decomposing a morphism in Hilb into a string diagram whose nodes come from some small set of generating morphisms. Right?

Where is the actual proof of the decomposition? After Theorem 35 you say “The proof is constructive and proceeds based on the content of the main body of the text.” Does that mean the proof was contained somewhere in the text coming before the theorem statement? It doesn’t seem to come afterwards….

A couple other questions/comments:

p8: I would call (a) the “cap” and (b) the “cup”; I tend to think of a cup as sitting upright rather than upside down. Is the other way round conventional in quantum theory?

On p12, the phrase “where \otimes is regular multiplication with respect to a state vector and a complex number” confused me; maybe you mean that the isomorphism is given by multiplication?

p13: does “fix the canonical basis” mean “fix a particular arbitrarily chosen basis”? Is this standard terminology among quantum theorists?

p15: What does the parenthetical “(e.g. a monoid homomorphism)” mean? How is a monoid homomorphism a change of basis?

Posted by: Mike Shulman on October 1, 2010 10:50 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Mike wrote:

I would call (a) the “cap” and (b) the “cup”; I tend to think of a cup as sitting upright rather than upside down. Is the other way round conventional in quantum theory?

I sure hope not. People love to argue about whether to read diagrams up or down, so one man’s “unit” looks just like another woman’s “counit” — but only a monstrous fiend would adopt a convention where a “cap” looks like an upside-down hat and a “cup” looks like a turned-over cup.

Jake: tell me it ain’t so!

Does “fix the canonical basis” mean “fix a particular arbitrarily chosen basis”? Is this standard terminology among quantum theorists?

It’s standard to say “canonical basis” for the obvious basis of n\mathbb{C}^n, listed in the obvious order. But if Jake is dealing with an abstract Hilbert space HH, he has no right to say “canonical basis” — and it’s definitely not standard to do so.

On the other hand, it is standard for physicists to screw up math teminology in every conceivable way.

Posted by: John Baez on October 3, 2010 2:31 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

John wrote:

People love to argue about whether to read diagrams up or down, so one man’s “unit” looks just like another woman’s “counit” — but only a monstrous fiend would adopt a convention where a “cap” looks like an upside-down hat and a “cup” looks like a turned-over cup.

Jake: tell me it ain’t so!

it ain’t so: I have no idea how that typo happened! Have had drafts of this paper kicking around for about a year with loads of different plots, used reused etc. so please forgive me as I think the picture was changed without updating the text at some point.

It’s standard to say “canonical basis” for the obvious basis of ℂ n, listed in the obvious order. But if Jake is dealing with an abstract Hilbert space H, he has no right to say “canonical basis” — and it’s definitely not standard to do so.

Yes, again, dealing with the subject, this is perhaps the worst possible typo to have!

On the other hand, it is standard for physicists to screw up math terminology in every conceivable way.

I might quote you on that in the paper - this could be the most profound insight thus far related to this work!

Cheers and thanx!

Posted by: Jacob on October 3, 2010 10:46 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Jake threatened:

I might quote you on that in the paper…

Please don’t. Every time a joke of mine makes it into print I get more enemies — especially when it’s actually true.

Posted by: John Baez on October 3, 2010 12:27 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Hi Mike,

Ah, I get it! “Tensor networks” are just about decomposing a morphism in Hilb into a string diagram whose nodes come from some small set of generating morphisms. Right?

Yes, but not in the current approach. The main idea is to bound the dimension of the wires that connect nodes. This is where the approximation comes in: if the dimension of the connecting nodes where able to be as large as one would like, the description would not always be efficient. We can guarantee that the states description is efficient by placing this bound on the dimension of the connecting wires: when this is a good approximation is another story.

Now in my stuff, I’m trying to do just what you said, generate a network given a state. Translating states into networks has not been done in this way before. I’m able to do a lot, but getting information out about the state is another story (my networks are not always contractible).

Where is the actual proof of the decomposition?

It’s a construction of how to write the state in terms of a diagram. I’ll add that now, thanx.

p8: I would call (a) the “cap” and (b) the “cup”; I tend to think of a cup as sitting upright rather than upside down. Is the other way round conventional in quantum theory?

Hehehe, luckily that’s just a typo!

On p12, the phrase “where ⊗ is regular multiplication with respect to a state vector and a complex number” confused me; maybe you mean that the isomorphism is given by multiplication?

I mean that say S is some vector like |00> + |11> and M is some complex number. Then MS=MSM\otimes S = M\cdot S - just multiplication. How would you say this as a hardened category theorist?

p13: does “fix the canonical basis” mean “fix a particular arbitrarily chosen basis”? Is this standard terminology among quantum theorists?

No not standard, just a silly typo! It’s standard to just fix the computational basis in quantum information. What was I thinking when I wrote that I don’t know.

p15: What does the parenthetical “(e.g. a monoid homomorphism)” mean? How is a monoid homomorphism a change of basis?

Here I just removed “(e.g. a monoid homomorphism)” since it adds nothing to what I’m saying. All I mean is that XOR and COPY are both monoids, related by a unitary change of basis.

Thank you very much for catching these and for your feedback!

Cheers!

Posted by: Jacob on October 3, 2010 10:39 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

I mean that say SS is some vector like |00+|11{|00\rangle} + {|11\rangle} and MM is some complex number. Then MS=MSM\otimes S = M\cdot S—just multiplication. How would you say this as a hardened category theorist?

Assuming I understand you correctly, I would say it as I did before: “the isomorphism \mathbb{C}\otimes \mathcal{H} \cong \mathcal{H} is given by multiplication.”

To this “hardened category theorist,” at least, MSM\otimes S and MSM\cdot S cannot be equal, because they are elements of different vector spaces: the first is an element of \mathbb{C}\otimes \mathcal{H} and the second is an element of \mathcal{H}. Recall that for vector spaces VV and WW, their tensor product VWV\otimes W is a formal construction whose elements can be identified with equivalence classes of formal sums of formal symbols “vwv\otimes w” where vVv\in V and wWw\in W. The point is that there is a map from \mathbb{C}\otimes \mathcal{H} to \mathcal{H} which takes MSM\otimes S to MSM\cdot S, and this map is an isomorphism.

Posted by: Mike Shulman on October 3, 2010 11:45 PM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

Just to give yet another nice reason why so many people are interested in this stuff, I’m going to talk a bit more about MERA which was introduced here in 2006 by G. Vidal. MERA stands for Multi-scale Entanglement Renormalization Ansatz. Let’s consider the following:

which I’ve borrowed from the paper on Quantum MERA Channels by Giovannetti, Montangero and Fazio. Now the red 4-legged tensors are unitary maps and the blue ones are isometries. If you start with the green tensor on top, and go down, level by level, you can arrange things so you generate a highly entangled quantum state.

Why is this so important? We typically want to calculate expectation values and reduced density operators in quantum mechanics: a remarkable fact is that to do this, you plug one MERA network into it’s dual, and just about everything drops out!

The coloured area, those are the only tensors left over and hence all that we need to worry about! Now if we want to think about decay, we’ll start with index i = 1, and let j = 2, all the way to the right at say j = n. At each stage, we get a reduced density matrix, and from this we can plot correlations. How they decay with distance (as a function of j) is important.

Just to see where I’m at, I wrote down a few examples of MERA networks and tried to see if we could find some new things using higher algebra. The example in the paper is

and the 2- and 4-party reduced density operators are distance independent, using the diagrammatic reduction rules, they quickly are shown to take the form

Now with Stephen Clark, I’m working on finding some nice examples of how the higher algebra stuff can be used to find examples important for power-law decay. Stephen had some nice insights here. We got lot’s of stuff going on, so if anyone is interested or has a nice idea, please let me know!

Wow, nice day in Japan -

Posted by: Jacob on October 2, 2010 1:48 AM | Permalink | Reply to this

Re: Jacob Biamonte on Tensor Networks

It’s been a over a year since the last post and we’ve been working hard since. I’m back in Japan and got to thinking that I should post a quick update as we had several results published recently. Here is the list:

Categorical Tensor Network States, Jacob D. Biamonte‚ Stephen R. Clark and Dieter Jaksch, AIP Advances 1(4), 042172 (2011). arXiv:1012.0531

Categorical Quantum Circuits, Ville Bergholm and Jacob Biamonte, Journal of Physics A: Mathematical and Theoretical, 44(17), 25304 (2011). arXiv:1010.4840

Algebraically contractible topological tensor network states, S. J. Denny, J. D. Biamonte, D. Jaksch and S. R. Clark, Journal of Physics A: Mathematical and Theoretical 45 015309, (2012). arXiv:1108.0888

We also have some work under review. It’s on the arXiv:

Tensor networks and graphical calculus for open quantum systems, Christopher J. Wood, Jacob D. Biamonte and David G. Cory, in review (2011). arXiv:1111.6950

We’re still working away and about to finish a few more things. Background on a lot of this stuff can be found in the youtube series of lectures I gave at IQC (this is an updated version of the earlier course I gave on tensor network states at Oxford).

(Youtube series) Lectures on Tensor Network States, Jacob D. Biamonte, QIC 890/891 Selected Advanced Topics in Quantum Information, The University of Waterloo, Waterloo Ontario, Canada, (2011), http://www.qubit.org/iqc2011.

This is fun stuff and we look forward to future progress.

Posted by: Jacob Biamonte on December 15, 2011 3:36 AM | Permalink | Reply to this

Post a New Comment