Resource Convertibility (Part 3)

guest post by Tobias Fritz

In Part 1 and Part 2, we learnt about ordered commutative monoids and how they formalize theories of resource convertibility and combinability. In this post, I would like to say a bit about the applications that have been explored so far. First, the study of resource theories has become a popular subject in quantum information theory, and many of the ideas in my paper actually originate there. I’ll list some references at the end. So I hope that the toolbox of ordered commutative monoids will turn out to be useful for this. But here I would like to talk about an example application that is much easier to understand, but no less difficult to analyze: graph theory and the resource theory of zero-error communication.

A graph consists of a bunch of nodes connected by a bunch of edges, for example like this:

This particular graph is the pentagon graph or 5-cycle. To give it some resource-theoretic interpretation, think of it as the distinguishability graph of a communication channel, where the nodes are the symbols that can be sent across the channel, and two symbols share an edge if and only if they can be unambiguously decoded. For example, the pentagon graph roughly corresponds to the distinguishability graph of my handwriting, when restricted to five letters only:

So my ‘w’ is distinguishable from my ‘u’, but it may be confused for my ‘m’. In order to communicate unambiguously, it looks like I should restrict myself to using only two of those letters in writing, since any third of them may be mistaken for one of the other three. But alternatively, I could use a block code to create context around each letter which allows for perfect disambiguation. This is what happens in practice: I write in natural language, where an entire word is usually not ambiguous.

One can now also consider graph homomorphisms, which are maps like this:

The numbers on the nodes indicate where each node on the left gets mapped to. Formally, a graph homomorphism is a function taking nodes to nodes such that adjacent nodes get mapped to adjacent nodes. If a homomorphism G\to H exists between graphs G and H, then we also write H\geq G; in terms of communication channels, we can interpret this as saying that H simulates G, since the homomorphism provides a map between the symbols which preserves distinguishability. A ‘code’ for a communication channel is then just a homomorphism from the complete graph in which all nodes share an edge to the graph which describes the channel. With this ordering structure, the collection of all finite graphs forms an ordered set. This ordered set has an intricate structure which is intimately related to some big open problems in graph theory.

We can also combine two communication channels to form a compound one. Going back to the handwriting example, we can consider the new channel in which the symbols are pairs of letters. Two such pairs are distinguishable if and only if either the first letters of each pair are distinguishable or the second letters are,

(a,b) \sim (a',b') \:\Leftrightarrow\: a\sim a' \:\lor\: b\sim b'

When generalized to arbitrary graphs, this yields the definition of disjunctive product of graphs. It is not hard to show that this equips the ordered set of graphs with a binary operation compatible with the ordering, so that we obtain an ordered commutative monoid denoted Grph. It mathematically formalizes the resource theory of zero-error communication.

Using the toolbox of ordered commutative monoids combined with some concrete computations on graphs, one can show that Grph is not cancellative: if K_{11} is the complete graph on 11 nodes, then 3C_5\not\geq K_{11}, but there exists a graph G such that

3 C_5 + G \geq K_{11} + G

The graph G turns out to have 136 nodes. This result seems to be new. But if you happen to have seen something like this before, please let me know!

Last time, we also talked about rates of conversion. In Grph, it turns out that some of these correspond to famous graph invariants! For example, the rate of conversion from a graph G to the single-edge graph K_2 is Shannon capacity \Theta(\overline{G}), where \overline{G} is the complement graph. This is of no surprise since \Theta was originally defined by Shannon with precisely this rate in mind, although he did not use the language of ordered commutative monoids. In any case, the Shannon capacity \Theta(\overline{G}) is a graph invariant notorious for its complexity: it is not known whether there exists an algorithm to compute it! But an application of the Rate Theorem from Part 2 gives us a formula for the Shannon capacity:

\Theta(\overline{G}) = \inf_f f(G)

where f ranges over all graph invariants which are monotone under graph homomorphisms, multiplicative under disjunctive product, and normalized such that f(K_2) = 2. Unfortunately, this formula still not produce an algorithm for computing \Theta. But it nonconstructively proves the existence of many new graph invariants f which approximate the Shannon capacity from above.

Although my story ends here, I also feel that the whole project has barely started. There are lots of directions to explore! For example, it would be great to fit Shannon’s noisy channel coding theorem into this framework, but this has turned out be technically challenging. If you happen to be familiar with rate-distortion theory and you want to help out, please get in touch!

References

Here is a haphazard selection of references on resource theories in quantum information theory and related fields:

• Igor Devetak, Aram Harrow and Andreas Winter, A resource framework for quantum Shannon theory.

• Gilad Gour, Markus P. Müller, Varun Narasimhachar, Robert W. Spekkens and Nicole Yunger Halpern, The resource theory of informational nonequilibrium in thermodynamics.

• Fernando G.S.L. Brandão, Michał Horodecki, Nelly Huei Ying Ng, Jonathan Oppenheim and Stephanie Wehner, The second laws of quantum thermodynamics.

• Iman Marvian and Robert W. Spekkens, The theory of manipulations of pure state asymmetry: basic tools and equivalence classes of states under symmetric operations.

• Elliott H. Lieb and Jakob Yngvason, The physics and mathematics of the second law of thermodynamics.

This entry was posted on Monday, April 13th, 2015 at 1:00 am and is filed under chemistry, mathematics, networks, physics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

17 Responses to Resource Convertibility (Part 3)

  1. nad says:
    13 April, 2015 at 8:53 am

    Formally, a graph homomorphism is a function taking nodes to nodes such that adjacent nodes get mapped to adjacent nodes.

    Thanks for the posts. I am not sure whether your meaning of adjacent is the same as mine. I understand the above as that a triangle with vertices A,B,C can’t be mapped to a single edge via a graph homomorphism.

    Reply
    • John Baez says:
      13 April, 2015 at 11:39 am

      There are many different definitions of ‘graph’, each with its own concept of ‘homomorphism’, but I think Tobias is using this one here:

      A (simple) graph is a finite set N together with a set E of 2-element subsets of N. We call the elements of N nodes and we call the elements of E edges. If \{x,y\} is an edge we say the nodes x and y are adjacent, and we say \{x,y\} is an edge from x to y.

      So, there can’t be an edge from a node to itself. There can be at most one edge from x to y. If there’s an edge from x to y, it’s also an edge from edge from y to x.

      It can be helpful to call this a ‘simple graph’ to distinguish it from all the other kinds of graphs. I hardly ever use simple graphs: I prefer directed multigraphs, because they’re actually simpler! But a lot of people call simple graphs just ‘graphs’. A lot of people call directed multigraphs just ‘graphs’, too.

      Reply
      • nad says:
        13 April, 2015 at 12:06 pm

        So, there can’t be an edge from a node to itself.

        Yes that’s also what I understood from the above explanation, but I wasn’t sure so I asked. That is if you convert a triangle to an edge with vertices x,y then because either x or y has to be labeled by two letters, like x=A,B and y=C the conversion can’t be anymore a homomorphism as described above.

        For example, the rate of conversion from a graph G to the single-edge graph K_2 is Shannon capacity \Theta(\overline{G}),

        I have so far not really understood what the Shannon capacity for a graph is, but by the above I understand now that the rate of conversion to an edge can’t be used as a definition of the Shannon capacity of a triangle. So what would be an easy description for the Shannon capacity of a triangle?

        Reply
        • nad says:
          13 April, 2015 at 12:09 pm

          …can’t be used as a definition of the Shannon capacity of a triangle.

          (where I had understood that “conversions” are homomorphisms ?)

      • John Baez says:
        13 April, 2015 at 12:26 pm

        Nad wrote:

        So what would be an easy description for the Shannon capacity of a triangle?

        I’ll let Tobias answer that, but I’ll note that an easy description of the Shannon capacity still doesn’t make it easy to compute the Shannon capacity. Nobody knows the Shannon capacity of a 7-cycle: that is, a graph that looks like a heptagon!

        Reply
    • Tobias Fritz says:
      13 April, 2015 at 11:55 am

      Yep, you’re both completely correct! Sorry if it wasn’t clear to begin with.

      Reply
  2. John Baez says:
    13 April, 2015 at 12:23 pm

    So here’s a general vague question. How are your ideas on the Shannon capacity of a graph related to Tom Leinster’s?

    • Tom Leinster, The Shannon capacity of a graph, 1, The n-Category Café, 10 August 2013.

    • Tom Leinster, The Shannon capacity of a graph, 2, The n-Category Café, 18 August 2013.

    Maybe there’s nothing much to say… but some people, including Nad, might like the first part, since it gives a nice explanation of the idea of Shannon capacity.

    Reply
    • nad says:
      13 April, 2015 at 2:46 pm

      but some people, including Nad, might like the first part, since it gives a nice explanation of the idea of Shannon capacity.

      Indeed Tom’s explanation is much better then the Wikipedia article – at least I find that. So on a first glance it seems for a triangle (a 3-cycle) in Tom’s sense the Shannon capacity would be zero, because for the triangle and for all strong products of itself the cardinality of the largest indepent set seems to be zero. However Tobias used the complementary type of graphs (for Tom’s graph an edge means “rather undistinguishable” and for Tobias an edge means “distinguishable” within a communication). I guess the complementary graph of a 3-cycle (Tobias graph) would be three distinct points (Tom graph). Those 3 points would all belong to an independent set. If I understood correctly if one takes the strong product of this graph of three points than one would have a graph with 9 seperate points taking the square root is again 3 a.s.o. so the Shannon capacity should be 3. Is that right?

      Reply
      • Tobias Fritz says:
        13 April, 2015 at 2:59 pm

        Well done — that’s exactly right!

        Having to take complementary graph is a bit of an annoyance. But there’s a reason that I work with ‘distinguishability graphs’ instead of the usual ‘confusability graphs’: converting one communication channel into another corresponds to a graph homomorphism of distinguishability graphs, but not of confusability graphs. When using the channel to communicate, we’re interested in converting the channel into a perfect channel, which distinguishes all input symbols perfectly. So we’re interested in independent sets in the confusability graph, or in cliques in the distinguishability graph. When using the same channel repeatedly, the maximal throughput of bits per channel use is described by the Shannon capacity.

        Reply
  3. cullina says:
    13 April, 2015 at 9:56 pm

    I think that I found a small error in the post. In your counterexample to cancellativity in Grph, 3 C_5 + G \geq K_{11} + G even though 3 C_5 \not\geq K_{11} , you say G has 26 vertices. In your paper, you have G = 3 C_5 \vee K_{11} , which has 5^3 + 11 = 136 vertices.

    Reply
    • cullina says:
      14 April, 2015 at 7:04 am

      I think that I have a smaller counterexample. Let q be a prime power such that q = 1 \mod 4 and let P_q be the Paley graph, or quadratic residue graph, on q vertices. Paley graphs are vertex transitive and self-complementary, so by Theorem 12 in Lovasz’s paper “On the Shannon capacity of a graph”, \omega(2 P_q) = q . The web page at http://www.research.ibm.com/people/s/shearer/indpal.html lists independence number (which equal clique number in this case) for small Paley graphs. In particular, \omega(P_{17}) = 3 . Thus P_{17} \not\geq K_4 while 2 P_{17} \geq K_{17} \geq 2 K_4 and P_17 + (P_{17} \vee K_4) \geq K_4 + (P_{17} \vee K_4) .

      Reply
    • Tobias Fritz says:
      14 April, 2015 at 1:39 pm

      Very cool!! David Roberson and I are working on exploring the ordered commutative monoid of graphs in more detail. Since your observation also goes in that direction, maybe you’re interested in helping out? If so, just send me an email. (It seems that we’re both working on other projects first, so we’re likely to be quite slow.)

      You’re right, I should have said 136 vertices in the original post…

      In order to get the subscripts right on this blog, you can write P_{17} instead of P_17. The 7’s in cullina’s second comment all belong to the subscript.

      Reply
      • John Baez says:
        14 April, 2015 at 1:42 pm

        I have fixed the subscripts in cullina’s second comment. It would be great if this post of yours could lead to a collaboration!

        I will also fix the original post so that it says G has 136 vertices. Not everybody reads the comments to find errors!

        Reply
  4. Tobias Fritz says:
    15 April, 2015 at 12:40 am

    The paper has now appeared on the arXiv:
    http://arxiv.org/abs/1504.03661

    Reply
  5. Tobias Fritz says:
    4 January, 2017 at 10:06 am

    Here’s a quick status update on the project outlined in this series of blog posts.

    Carlo Sparaciari, Jonathan Oppenheim and I have applied these ideas to thermodynamics. While I’m not quite convinced that our starting assumptions are “right” from the physics perspective, our results recover standard equilibrium thermodynamics and extend certain aspects of it to situations arbitrarily far away from equilibrium. More concretely, what we have considered are questions like this: what is the maximal amount of work that can be extracted from many copies of any given non-equilibrium state of a closed system? (It’s enough to consider closed systems only: if you also have a heat bath available, then you should consider that bath to be part of your given non-equilibrium state.) For example, your non-equilibrium may state consist of one thermal state at low temperature and another thermal state at high temperature, in which case our maximal work corresponds to the maximal efficiency of a heat engine operating between two large but finite thermal baths. Basically the same methods apply when you have more than two baths at different temperatures.

    Currently I’m working on generalizing the resource-theoretic toolbox further and applying it to optimal transportation and randomness as a resource.

    Reply
  6. Applied Category Theory Course: Resource Theories | Azimuth says:
    12 May, 2018 at 1:49 am

    We are lucky to have Tobias in our course, helping the discussions along! He’s already posted some articles on resource theory here on this blog. We’re having fun bouncing between the relatively abstract world of monoidal preorders and their very concrete real-world applications to chemistry, scheduling, manufacturing and other topics. Here are the lectures so far:

    • Lecture 18 – Chapter 2: Resource Theories
    • Lecture 19 – Chapter 2: Chemistry and Scheduling
    • Lecture 20 – Chapter 2: Manufacturing
    • Lecture 21 – Chapter 2: Monoidal Preorders
    • Lecture 22 – Chapter 2: Symmetric Monoidal Preorders

    Reply

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

This site uses Akismet to reduce spam. Learn how your comment data is processed.