DisCoCat in DisCoPy

In the previous tutorial, we learnt the basics of monoidal categories and how to represent them in DisCoPy. In this tutorial, we look at the Distributional Compositional Categorical model [CSC2010], which uses functors to map diagrams from the rigid category of pregroup grammars to vector space semantics.

Download code

Pregroup grammars

Pregroup grammar is a grammatical formalism devised by Joachim Lambek in 1999 [Lam1999]. In pregroups, each word is a morphism with type \(I \to T\) where \(I\) is the monoidal unit and \(T\) is a rigid type, referred to as the pregroup type. Here are some examples for pregroup type assignments:

• a noun is given the base type \(n\).

• an adjective consumes a noun on the noun’s left to return another noun, so it is given the type \(n\cdot n^l\).

• a transitive verb consumes a noun on its left and another noun on its right to give a sentence, so is given the type \(n^r \cdot s \cdot n^l\).

In the context of pregroups, the adjoints \(n^l\) and \(n^r\) can be thought of as the left and right inverses of a type \(n\) respectively. In a pregroup derivation, the words are concatenated using the monoidal product \(\otimes\) and linked using cups, which are special morphisms that exist in any rigid category. A sentence is grammatically sound if its derivation has a single uncontracted sentence wire.

In DisCoPy, words are defined using the Word class. A Word is just a Box where the input type is fixed to be the monoidal unit \(I\) (or Ty()). A pregroup derivation diagram can be drawn using either the monoidal.Diagram.draw() method or the grammar.draw() method.

from discopy import grammar
from discopy.grammar import Word
from discopy.rigid import Cap, Cup, Id, Ty

n, s = Ty('n'), Ty('s')

words = [
    Word('she', n),
    Word('goes', n.r @ s @ n.l),
    Word('home', n)
]

cups = Cup(n, n.r) @ Id(s) @ Cup(n.l, n)

assert Id().tensor(*words) == words[0] @ words[1] @ words[2]
assert Ty().tensor(*[n.r, s, n.l]) == n.r @ s @ n.l

diagram = Id().tensor(*words) >> cups
grammar.draw(diagram)

Note

In lambeq, method create_pregroup_diagram() provides an alternative, more compact way to create pregroup diagrams, by explicitly defining a list of cups and swaps. For example, the above diagram can be also generated using the following code:

from lambeq import create_pregroup_diagram
from discopy import Ty

words = [Word('she', n), Word('goes', n.r @ s @ n.l), Word('home', n)]
morphisms = [(Cup, 0, 1), (Cup, 3, 4)]
diagram = create_pregroup_diagram(words, Ty('s'), morphisms)

where the numbers in morphisms define the indices of the corresponding wires at the top of the diagram (n @ n.r @ s @ n.l @ n). In contrast, the .cup() method in DisCoPy can be used to define diagrams using chaining, and uses indices at the bottom of the diagram:

words = Word('she', n) @ Word('goes', n.r @ s @ n.l) @ Word('home', n)
same_diagram = words.cup(0, 1).cup(1, 2)

The .cup() method can be applied to non-adjacent qubits, which implicitly introduces swaps. For example:

n, s, p = map(Ty, "nsp")
words = Word('A', n @ p) @ Word('V', n.r @ s @ n.l) @ Word('B', p.r @ n)

words.cup(1, 5).cup(0, 1).cup(1, 2).draw()

Note that only diagrams of the form word @ ... @ word >> cups_and_swaps can be drawn using grammar.draw(). Applying functors or normal forms will often cause the diagram to deviate from this form, in which case monoidal.Diagram.draw() should be used.

from discopy import drawing
from pytest import raises

# In the original diagram, words appear before the cups
print("Before normal form:", diagram.boxes)

diagram_nf = diagram.normal_form()
print("After normal form:", diagram_nf.boxes)

drawing.equation(diagram, diagram_nf, figsize=(10, 4), symbol='->')

# In the normalised diagram, boxes are not in the right order
# anymore, so cannot be drawn using grammar.draw()
with raises(ValueError):
    grammar.draw(diagram_nf)

Before normal form: [Word('she', Ty('n')), Word('goes', Ty(Ob('n', z=1), 's', Ob('n', z=-1))), Word('home', Ty('n')), Cup(Ty('n'), Ty(Ob('n', z=1))), Cup(Ty(Ob('n', z=-1)), Ty('n'))]
After normal form: [Word('she', Ty('n')), Word('goes', Ty(Ob('n', z=1), 's', Ob('n', z=-1))), Cup(Ty('n'), Ty(Ob('n', z=1))), Word('home', Ty('n')), Cup(Ty(Ob('n', z=-1)), Ty('n'))]

In the example above, the application of normal form to the diagram introduces a cup before the word “home”, so the normalised version cannot be drawn with grammar.draw() anymore.

Functors

Given monoidal categories \(\mathcal{C}\) and \(\mathcal{D}\), a monoidal functor \(F: \mathcal{C} \to \mathcal{D}\) satisfies the following properties:

• monoidal structure of objects is preserved: \(F(A \otimes B) = F(A) \otimes F(B)\)

• adjoints are preserved: \(F(A^l) = F(A)^l\), \(F(A^r) = F(A)^r\)

• monoidal structure of morphism is preserved: \(F(g \otimes f) = F(g) \otimes F(f)\)

• compositonal structure of morphisms is preserved: \(F(g \circ f) = F(g) \circ F(f)\)

Put simply, a functor is a structure-preserving transformation. In a free monoidal category, applying a functor to a diagram amounts to simply providing a mapping for each generating object and morphism. In DisCoPy, a functor is defined by passing mappings (dictionaries or functions) as arguments ob and ar to the Functor class.

Functors are one of the most powerful concepts in category theory. In fact, the encoding, rewriting and parameterisation steps of lambeq’s pipeline are implemented individually as functors, resulting in an overall functorial transformation from parse trees to tensor networks and circuits. More specifically:

• lambeq.CCGParser uses a functor to transform a biclosed CCG diagram to a rigid DisCoCat diagram [YK2021].

• lambeq.Rewriter functorially transforms a rigid DisCoCat diagram to a simpler rigid DisCoCat diagram.

• lambeq.TensorAnsatz functorially transforms a rigid DisCoCat diagram to a tensor diagram, which can be evaluated as a tensor network using NumPy, JAX or PyTorch.

• lambeq.CircuitAnsatz functorially transforms a rigid DisCoCat diagram to a quantum circuit, for evaluation on a quantum device.

Below we present two examples of functors, implemented in DisCoPy.

Example 1: “Very” functor

This functor adds the word “very” in front of every adjective in a DisCoCat diagram. Since the mapping is from a rigid.Diagram to another rigid.Diagram, a rigid.Functor should be used. Further, the word “very” modifies an adjective to return another adjective, so it should have type \((n \otimes n^l) \otimes (n \otimes n^l)^l = n \otimes n^l \otimes n^{ll} \otimes n^l\).

from lambeq import BobcatParser
parser = BobcatParser(verbose='suppress')

from discopy.rigid import Diagram, Functor

# determiners have the same type as adjectives
# but we shouldn't add 'very' behind them
determiners = ['a', 'the', 'my', 'his', 'her', 'their']

# type for an adjective
adj = n @ n.l
very = Word('very', adj @ adj.l)
cups = Diagram.cups(adj.l, adj)

def very_ob(ty):
    return ty

def very_ar(box):
    if box != very:
        if box.name not in determiners:
            if box.cod == adj:
                return very @ box >> Id(adj) @ cups
    return box

very_functor = Functor(ob=very_ob, ar=very_ar)

diagram = parser.sentence2diagram('a big bad wolf')
new_diagram = very_functor(diagram)

drawing.equation(diagram, new_diagram, figsize=(10, 4), symbol='->')

Example 2: Twist functor

In this functor, cups and caps are treated specially and are not passed to the ar function; instead they are passed to methods ar_factory.cups(left, right) and ar_factory.caps(left, right), respectively. By default, the rigid.Functor uses rigid.Diagram to implement the factory pattern, with methods such as cups(), caps(), id(), and swap(). For example, for a functor F that uses the default arrow factory Diagram, F(Cup(a, a.r)) == Diagram.cups(F(a), F(a.r)).

Here is an example of how to map a cup to a custom diagram, such as a “twisted” cup. Note that it is up to the user to ensure the new cups and caps satisfy the snake equations.

from discopy.rigid import Functor
from discopy import Diagram

def twist_ob(ty):
    return ty

def twist_ar(box):
    return box

class TwistedDiagram(Diagram):
    @staticmethod
    def cups(left, right):
        swaps = Diagram.swap(left, right)
        cups = Diagram.cups(right, left)
        return swaps >> cups

    @staticmethod
    def caps(left, right):
        return TwistedDiagram.cups(left, right).dagger()


twist_functor = Functor(ob=twist_ob, ar=twist_ar, ar_factory=TwistedDiagram)

diagram = parser.sentence2diagram('This is twisted')
new_diagram = twist_functor(diagram)

grammar.draw(diagram)
grammar.draw(new_diagram)

snake = Id(n) @ Cap(n.r, n) >> Cup(n, n.r) @ Id(n)
drawing.equation(twist_functor(snake), Id(n), figsize=(4, 2))

Note

Twisting the nested cups for “is” and “twisted” together is not a functorial operation, so it cannot be implemented using a rigid.Functor.

Classical DisCoCat: Tensor networks

The classical version of DisCoCat sends diagrams in the category of pregroup derivations to tensors in the category of vector spaces FVect. FVect is a monoidal category with vector spaces (e.g. \(\mathbb{R}^2 \otimes \mathbb{R}^2\)) as objects and linear maps between vector spaces as morphisms. It is in fact a compact closed category, which is a special case of rigid categories where \(A^l = A^r = A^*\).

Using the discopy.tensor module, you can define a free category of vector spaces: objects are defined with the Dim class and morphisms with the Box class. Composite morphisms are constructed by freely combining the generating morphisms using the << and >> operators. This is similar to how rigid.Diagrams and monoidal.Diagrams are defined. The concrete value of the tensor is passed to the data attribute as an unshaped list; DisCoPy will reshape it later based on the input and output dimensions.

Apart of diagrams, the discopy.tensor module has another class that can be tensored and composed: tensor.Tensor. The key difference is that tensor.Boxes in the diagrams compose together to make tensor.Diagrams, while tensor.Tensors compose together to make another tensor.Tensor. In other words, tensor.Tensor computes tensor contractions directly, while tensor.Diagram delays the computation until eval() is called.

from discopy.tensor import Box, Tensor, Id, Dim

# Dim(1) is the unit object, so disappears when tensored with another Dim
print(f'{Dim(1) @ Dim(2) @ Dim(3)=}')

id_box = Box('Id Box', Dim(2), Dim(2), data=[1,0,0,1])
id_tensor = Tensor(Dim(2), Dim(2), array=[1,0,0,1])

# the actual values of id_box and id_tensor are equal
assert (id_box.array == id_tensor.array).all()
drawing.equation(id_box, id_tensor, figsize=(4, 1))
print(id_box.array)

Dim(1) @ Dim(2) @ Dim(3)=Dim(2, 3)

[[1 0]
 [0 1]]

f_box = Box('f Box', Dim(2, 2), Dim(2), data=range(8))
f_tensor = Tensor(Dim(2, 2), Dim(2), array=range(8))

combined_diagram = id_box @ Id(Dim(2)) >> f_box
combined_tensor = id_tensor @ Tensor.id(Dim(2)) >> f_tensor

# tensor diagram evaluates to the tensor
assert combined_diagram.eval() == combined_tensor
drawing.equation(combined_diagram, combined_tensor, figsize=(6, 2))
print(combined_tensor)
print(combined_tensor.array)

Tensor(dom=Dim(2, 2), cod=Dim(2), array=[0., 1., 2., 3., 4., 5., 6., 7.])
[[[0. 1.]
  [2. 3.]]

 [[4. 5.]
  [6. 7.]]]

In the category of vector spaces, cups, caps and swaps take on concrete values as tensors.

Tensor.cups(Dim(3), Dim(3)).array

array([[1., 0., 0.],
       [0., 1., 0.],
       [0., 0., 1.]])

Tensor.swap(Dim(2), Dim(2)).array

array([[[[1., 0.],
         [0., 0.]],

        [[0., 0.],
         [1., 0.]]],


       [[[0., 1.],
         [0., 0.]],

        [[0., 0.],
         [0., 1.]]]])

To implement a functor from rigid.Diagram to tensor.Tensor, use a tensor.Functor. This functor will automatically contract the resulting tensor network.

from discopy.tensor import Functor
import numpy as np

def one_ob(ty):
    dims = [2] * len(ty)
    return Dim(*dims) # does Dim(2,2,..)

def one_ar(box):
    dom = one_ob(box.dom)
    cod = one_ob(box.cod)
    tensor = np.ones(dom @ cod)
    print(f'"{box}" becomes')
    print(tensor)
    return tensor

one_functor = Functor(ob=one_ob, ar=one_ar)
one_functor(diagram)

"This" becomes
[1. 1.]
"is" becomes
[[[[1. 1.]
   [1. 1.]]

  [[1. 1.]
   [1. 1.]]]


 [[[1. 1.]
   [1. 1.]]

  [[1. 1.]
   [1. 1.]]]]
"twisted" becomes
[[1. 1.]
 [1. 1.]]

Tensor(dom=Dim(1), cod=Dim(2), array=[8., 8.])

Sometimes, defining a functor from rigid.Diagram to tensor.Diagram offers more flexibility, since a tensor.Diagram can be instantiated with concrete values to be evaluated later using a custom tensor contractor. Such a functor can be defined using a rigid.Functor with tensor.Dim and tensor.Diagram as ob_factory and ar_factory, respectively. See the implementation of TensorAnsatz for an example.

Quantum DisCoCat: Quantum circuits

The quantum version of DisCoCat sends diagrams in the category of pregroup derivations to circuits in the category of Hilbert spaces FHilb. This is a compact closed monoidal category with Hilbert spaces (e.g. \(\mathbb{C}^{2^n}\)) as objects and unitary maps between Hilbert spaces as morphisms.

The discopy.quantum module is a framework for the free category of quantum circuits: objects are generated using the quantum.circuit.Ob class and morphisms by using quantum.gates. In DisCoPy, rotation values range from \(0\) to \(1\) rather than from \(0\) to \(2\pi\). The circuit can then either be evaluated using tensor contraction with the eval() method, or exported to pytket using the to_tk() method, which supports multiple hardware backends.

from discopy.quantum import qubit, Id
from discopy.quantum.gates import CX, Rz, X

circuit = Id(4)
circuit >>= Id(1) @ CX @ X
circuit >>= CX @ CX
circuit >>= Rz(0.1) @ Rz(0.2) @ Rz(0.3) @ Rz(0.4)

# from discopy 0.4.1, can do:
same_circuit = (Id(4).CX(1, 2).X(3).CX(0, 1).CX(2, 3)
                .Rz(0.1, 0).Rz(0.2, 1).Rz(0.3, 2).Rz(0.4, 3))
assert circuit == same_circuit

circuit.draw()
circuit.to_tk()

tk.Circuit(4).CX(1, 2).X(3).CX(0, 1).CX(2, 3).Rz(0.2, 0).Rz(0.4, 1).Rz(0.6, 2).Rz(0.8, 3)

To apply multi-qubit gates to non-consecutive qubits, use swaps to permute the wires, apply the gate, then unpermute the wires. These swaps are only logical swaps and do not result in more gates when converted to tket format.

from discopy import Circuit
from discopy.quantum.gates import SWAP

# to apply a CNOT on qubits 2 and 0:
circuit1 = Id(3)
circuit1 >>= SWAP @ Id(1)
circuit1 >>= Id(1) @ SWAP
circuit1 >>= Id(1) @ CX
circuit1 >>= Id(1) @ SWAP
circuit1 >>= SWAP @ Id(1)

# or you can do
perm = Circuit.permutation([2, 0, 1], inverse=True)
circuit2 = perm >> Id(1) @ CX >> perm[::-1]

assert circuit1 == circuit2
circuit1.draw(figsize=(3, 3))

# no swaps introduced when converting to tket
circuit1.to_tk()

tk.Circuit(3).CX(2, 0)

Since discopy 0.4.0, we have long-ranged controlled gates.

from discopy.quantum import Controlled, Rz, X
(Controlled(Rz(0.5), distance=2) >> Controlled(X, distance=-2)).draw(figsize=(3, 2))
Controlled(Controlled(X), distance=2).draw(figsize=(3, 2))

So far, our circuits have been “pure” circuits, consisting of unitaries. Pure circuits can be evaluated locally to return a Tensor. Circuits containing Discards and Measures are considered “mixed”, and return CQMaps instead of Tensors when evaluated, as they are not unitaries but rather classical-quantum maps (for more details, see Chapter 5 in [HV2013]).

from discopy import Discard, Measure, Ket
from discopy import C, Q

print(C(Dim(2)) @ Q(Dim(2, 3)) @ C(Dim(2)))

print(Discard().eval())
print(Measure().eval())
print(Ket(0).eval())
# circuits that have measurements in them are no longer unitary
# and return CQMaps
print((Ket(0) >> Measure()).eval())

C(Dim(2, 2)) @ Q(Dim(2, 3))
CQMap(dom=Q(Dim(2)), cod=CQ(), array=[1.+0.j, 0.+0.j, 0.+0.j, 1.+0.j])
CQMap(dom=Q(Dim(2)), cod=C(Dim(2)), array=[1.+0.j, 0.+0.j, 0.+0.j, 0.+0.j, 0.+0.j, 0.+0.j, 0.+0.j, 1.+0.j])
Tensor(dom=Dim(1), cod=Dim(2), array=[1.+0.j, 0.+0.j])
CQMap(dom=CQ(), cod=C(Dim(2)), array=[1.+0.j, 0.+0.j])

Pure circuits can be coerced to evaluate into a CQMap by setting mixed=True.

CX.eval(mixed=True)

CQMap(dom=Q(Dim(2, 2)), cod=Q(Dim(2, 2)), array=[1.+0.j, 0.+0.j, 0.+0.j, ..., 0.+0.j, 0.+0.j, 0.+0.j])

Note that the tensor order of CQMaps is doubled, compared to that of simple Tensors:

print(CX.eval().array.shape)
print(CX.eval(mixed=True).array.shape)

(2, 2, 2, 2)
(2, 2, 2, 2, 2, 2, 2, 2)

To implement a functor from rigid.Diagram to quantum.Circuit, use a quantum.circuit.Functor.

from discopy.quantum.circuit import Functor, Id

def cnot_ob(ty):
    # this implicitly maps all rigid types to 1 qubit
    return qubit ** len(ty)

def cnot_ar(box):
    dom = len(box.dom)
    cod = len(box.cod)
    width = max(dom, cod)
    circuit = Id(width)
    for i in range(width - 1):
        circuit >>= Id(i) @ CX @ Id(width - i - 2)

    # Add Bras (post-selection) and Kets (states)
    # to get a circuit with the right amount of
    # input and output wires
    if cod <= dom:
        circuit >>= Id(cod) @ Bra(*[0]*(dom - cod))
    else:
        circuit <<= Id(dom) @ Ket(*[0]*(cod - dom))
    return circuit

cnot_functor = Functor(ob=cnot_ob, ar=cnot_ar)
diagram.draw()
cnot_functor(diagram).draw(figsize=(8, 8))