snake-removal#
Removing snakes to simplify quantum circuit models.#
The snake removal procedure implemented in rigid.normal_form() takes a diagram in a free rigid category and removes all the cups and caps that can be yanked using the snake equation, following the scheme from Dunn, Vicary (2019).
Antonin’s lemma: Given a diagram in a free rigid category such that the domain and codomain of every box and of the diagram itself are built from the basic types Ty(‘s’) and Ty(‘n’) only using tensor, it must have rigid.normal_form() equal to a diagram where all cups and caps have been removed. Delpeuch (2019).
We start by generating grammatical sentences from a simple language, then we define the functor A which decomposes each word into simpler components. By Antonin’s lemma, applying this functor followed by normal_form() will return simplified diagrams, without changing their semantics. We use this procedure to simplify the interpretation of sentences as parametrised quantum circuits.
Language generation#
[1]:
from discopy import Ty, Box, Diagram, Word
# Pregroup types for words are built using adjoints of basic types
s, n = Ty('s'), Ty('n')
Alice = Word('Alice', n)
loves = Word('loves', n.r @ s @ n.l)
Bob = Word('Bob', n)
who = Word('who', n.r @ n @ s.l @ n)
is_rich = Word('is rich', n.r @ s)
vocab = [Alice, who, is_rich, loves, Bob]
[2]:
from time import time
from discopy.grammar import brute_force, draw
gen, n_sentences = brute_force(*vocab), 15
sentences, parsing = list(), dict()
print("Brute force search for grammatical sentences:")
start = time()
for i in range(n_sentences):
diagram = next(gen)
sentence = ' '.join(str(w)
for w in diagram.boxes if isinstance(w, Word)) + '.'
sentences.append(sentence)
parsing.update({sentence: diagram})
print(sentence)
print("{:.2f} seconds to generate {} sentences.\n".format(time() - start, n_sentences))
Brute force search for grammatical sentences:
Alice is rich.
Bob is rich.
Alice loves Alice.
Alice loves Bob.
Bob loves Alice.
Bob loves Bob.
Alice who is rich is rich.
Bob who is rich is rich.
Alice who is rich loves Alice.
Alice who is rich loves Bob.
Alice who loves Alice is rich.
Alice who loves Bob is rich.
Bob who is rich loves Alice.
Bob who is rich loves Bob.
Bob who loves Alice is rich.
9.59 seconds to generate 15 sentences.
[3]:
print("Pregroup parsing for the sentence: '{}'".format(sentences[12]))
draw(parsing[sentences[12]])
Pregroup parsing for the sentence: 'Bob who is rich loves Alice.'
Snake removal#
[4]:
from discopy import Cup, Cap, Functor
# The types of the following boxes are built from the basic types Ty('s') and Ty('n') only using tensor.
love_box = Box('loves', n @ n, s)
is_rich_box = Box('is rich', n, s)
copy = Box('copy', n, n @ n)
update = Box('update', n @ s, n)
# Define the Autonomization functor that decomposes a word into word_boxes:
ob = {n: n, s: s}
ar = {Alice: Alice,
Bob: Bob,
loves: Cap(n.r, n) @ Cap(n, n.l) >> Diagram.id(n.r) @ love_box @ Diagram.id(n.l),
is_rich: Cap(n.r, n) >> Diagram.id(n.r) @ is_rich_box,
who: Cap(n.r, n) >> Diagram.id(n.r) @ (copy >> Diagram.id(n) @ Cap(s, s.l) @ Diagram.id(n) >>
update @ Diagram.id(s.l @ n))
}
A = Functor(ob, ar, ob_factory=Ty, ar_factory=Diagram)
[5]:
print("Autonomization of 'loves':")
(loves @ Box('-->', Ty(), Ty()) @ A(loves)).interchange(1, 2, left=True).interchange(2, 3).draw()
Autonomization of 'loves':
[6]:
print("Autonomization of 'who':")
(who @ Box('-->', Ty(), Ty()) @ A(who)).interchange(1, 2, left=True).interchange(2, 3).draw()
Autonomization of 'who':
[7]:
from discopy import *
print("Removing snakes from autonomisation of '{}'".format(sentences[12]))
diagrams = list(A(parsing[sentences[12]]).normalize())
parsing[sentences[12]].to_gif(*diagrams, aspect='auto', path='../docs/imgs/unsnake-sentence.gif')
Removing snakes from autonomisation of 'Bob who is rich loves Alice.'
---------------------------------------------------------------------------
FileNotFoundError Traceback (most recent call last)
<ipython-input-7-bc8447f81364> in <module>
3 print("Removing snakes from autonomisation of '{}'".format(sentences[12]))
4 diagrams = list(A(parsing[sentences[12]]).normalize())
----> 5 parsing[sentences[12]].to_gif(*diagrams, aspect='auto', path='../docs/imgs/unsnake-sentence.gif')
~/Documents/work/qnlp/discopy/discopy/drawing.py in to_gif(diagram, *diagrams, **params)
719 if loop:
720 frames = frames + frames[::-1]
--> 721 frames[0].save(path, format='GIF', append_images=frames[1:],
722 save_all=True, duration=timestep,
723 **{'loop': 0} if loop else {})
~/Documents/cqcenv/lib/python3.8/site-packages/PIL/Image.py in save(self, fp, format, **params)
2146 fp = builtins.open(filename, "r+b")
2147 else:
-> 2148 fp = builtins.open(filename, "w+b")
2149
2150 try:
FileNotFoundError: [Errno 2] No such file or directory: '../docs/imgs/unsnake-sentence.gif'
[ ]:
# Check that sentences after autonomisation and snake removal do not contain cups or caps
def has_cups_or_caps(diagram):
for box in diagram.boxes:
if isinstance(box, Cup) or isinstance(box, Cap):
return True
return False
autonomised_sentences = [A(parsing[sentences[i]]).normal_form() for i in range(n_sentences)]
for i in range(n_sentences):
assert not has_cups_or_caps(autonomised_sentences[i])
Quantum circuit models#
[ ]:
from discopy.quantum import Circuit, qubit, Id, CX, H, Rx, Ket, sqrt, SWAP, CircuitFunctor
import jax.numpy as np
# Ansatzes for transitive and intransitive verbs:
def intransitive_ansatz(phase):
return Ket(0) >> Rx(phase)
def transitive_ansatz(phase):
return sqrt(2) @ Ket(0) @ Ket(0) >> H @ Rx(phase) >> CX
# The ansatz for 'who' is the GHZ state which can be realised with the following circuit:
def who_ansatz():
return sqrt(2) @ Ket(0, 0, 0)\
>> Circuit.id(1) @ H @ Circuit.id(1)\
>> Circuit.id(1) @ CX\
>> (SWAP >> CX) @ Circuit.id(1)
# The ansatzes for the boxes 'copy' and 'update' are simpler to realise then the GHZ state:
def copy_ansatz():
return Circuit.id(1) @ Ket(0) >> CX
def update_ansatz():
return Circuit.id(1)
# Gather the ansatzes above into a CircuitFunctor:
ob = {s: qubit ** 0, n: qubit ** 1}
ar = lambda params: {
Alice: Ket(0),
loves: transitive_ansatz(params['loves']),
who: who_ansatz(),
Bob: Ket(1),
is_rich: intransitive_ansatz(params['is_rich']),
copy: copy_ansatz(),
update: update_ansatz(),
love_box: transitive_ansatz(- params['loves']).dagger(),
is_rich_box: intransitive_ansatz(- params['is_rich']).dagger()}
F = lambda params: CircuitFunctor(ob, ar({'loves': params[0], 'is_rich': params[1]}))
# Initialise parameters
params0 = np.array([0.5, 1.])
F0 = F(params0)
def draw_functor(d0, d1):
return (d0 @ Box('-->', Ty(), Ty()) @ d1).interchange(1, 2, left=True).draw(aspect='auto')
print("Image of 'loves':")
draw_functor(loves, F0(loves).normal_form())
print("The image of 'who' is the GHZ state:")
draw_functor(who, F0(who).normal_form())
print("Image of the box 'copy':")
draw_functor(copy, F0(copy).normal_form())
[ ]:
from discopy.grammar import eager_parse
noun_phrase = eager_parse(Bob, who, is_rich, target=n)
print("Pregroup diagram for noun phrase 'Bob who is rich':")
draw(noun_phrase)
print("Image under the Circuit model:")
F0(noun_phrase).normal_form().draw(draw_type_labels=False, aspect='auto', fontsize=7)
print('depth = {}'.format(F(params0)(noun_phrase).depth() - 2))
print('width = {}'.format(F(params0)(noun_phrase).width()))
[ ]:
print("Diagram for 'Bob who is rich' after snake removal:")
A(noun_phrase).normal_form().draw(aspect='auto')
print("Image under the Circuit model")
circuit = F0(A(noun_phrase).normal_form()).normal_form()
circuit.draw(draw_type_labels=False, aspect='auto')
print('depth = {}'.format(circuit.depth() - 2))
print('width = {}'.format(circuit.width()))
[ ]:
# Check that the two circuits above generate the same distribution:
assert np.allclose((F0(noun_phrase).measure()), F0(A(noun_phrase).normal_form()).measure())
[ ]:
print("Circuit for '{}':".format(sentences[12]))
circuit = F0(parsing[sentences[12]])
circuit.draw(draw_type_labels=False, aspect='auto', fontsize=7)
print('depth = {}'.format(circuit.depth() - 2))
print('width = {}'.format(circuit.width()))
print("\nCircuit for '{}' after snake removal:".format(sentences[12]))
circuit = F0(autonomised_sentences[12])
circuit.draw(draw_type_labels=False, aspect='auto', fontsize=10)
print('depth = {}'.format(circuit.depth() - 2))
print('width = {}'.format(circuit.width()))
[ ]:
# Check that the above circuits generate the same distribution:
assert np.allclose(F0(parsing[sentences[12]]).measure(), F0(autonomised_sentences[12]).measure())
[13]:
!ls ../_static/imgs
EckmannHilton.gif hypergraph snake-removal.gif
alice-loves-bob.png jane_boys.gif spiral-normal-form.png
autonomisation.gif ket-fusion.gif spiral.gif
bell-state.png monoidal spiral.png
cat quantum tensor
circuit-normal_form.gif rigid test-pixels2diagram.png
crack-eggs.png scalars.gif typed-snake-equation.png
drawing sentence-as-diagram.png unsnake-sentence.gif
foliate.gif simple-rewrite.gif who-ansatz.png
grammar snake-equation.png
[ ]: