{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Circuit optimization using ZX-calculus\n",
"\n",
"Circuit optimisation consists in finding an equivalent quantum circuit (i.e. one that implements the same unitary evolution) and satisfies any of the following:\n",
"\n",
"- has less number of gates of a relevant kind (some gates are more costly than others, for instance, T-reduction or CNOT-reduction),\n",
"- has a shorter sequence of consecutive gates (known as depth-reduction),\n",
"- uses less qubits...\n",
"\n",
"In this lab session we will be working with PyZX, a library in Python that allows us to manage ZX-diagrams and use the ZX-calculus to optimise circuits. PyZX's documentation can be found at: https://pyzx.readthedocs.io/en/latest/index.html.\n",
"\n",
"[*This Jupyter notebook is a modified version of the one available at https://github.com/Quantomatic/pyzx, created by Aleks Kissinger and John van de Wetering. Changes are due to Pablo Andrés-Martínez and Robert I. Booth.*]\n"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import random\n",
"import pyzx as zx"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Clifford circuits\n",
"\n",
"We will first consider Clifford circuits: circuits whose phases are all multiples of $\\pi/2$. Clifford circuits are easy to manage because the axioms of the original ZX-calculus are enough to prove any equivalence of Clifford circuits (mathematically, we say the ZX-calculus is complete for Clifford circuits).\n",
"\n",
"In order to use PyZX, we start by importing the library and configuring matplotlib to display the figures in a nice way."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Then we can create a random Clifford circuit and visualise it."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"qubit_amount = 4\n",
"depth = 15\n",
"random.seed(1337)\n",
"circ = zx.generate.cliffords(qubit_amount, depth)\n",
"zx.draw_matplotlib(circ,labels=True,h_edge_draw='box')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The green and red nodes represent Z- and X-phase gates respectively, the yellow boxes are Hadamard gates, and the vertical lines going between two different colored nodes are CNOT gates.\n",
"\n",
"Internally this circuit is represented as a graph:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Graph(46 vertices, 49 edges)\n",
"All edges: [(0, 4), (1, 5), (2, 6), (3, 7), (4, 13), (5, 11), (6, 8), (7, 9), (8, 10), (9, 12), (10, 14), (11, 18), (12, 15), (13, 19), (14, 15), (14, 17), (15, 16), (16, 17), (16, 24), (17, 20), (18, 19), (18, 21), (19, 23), (20, 22), (21, 29), (22, 25), (23, 28), (24, 27), (25, 26), (26, 31), (27, 33), (28, 29), (28, 30), (29, 35), (30, 31), (30, 37), (31, 32), (32, 33), (32, 34), (33, 41), (34, 36), (35, 39), (36, 37), (36, 40), (37, 38), (38, 42), (39, 43), (40, 44), (41, 45)]\n",
"\n",
"The neighbours of vertex 14: [15, 10, 17]\n"
]
}
],
"source": [
"print(circ)\n",
"print(\"All edges: \", list(circ.edges()))\n",
"print(\"\\nThe neighbours of vertex 14: \", list(circ.neighbors(14)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Using this graph representation we can use the rules of the ZX-calculus to simplify it:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = circ.copy()\n",
"zx.clifford_simp(g)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.normalize() # Reposition nodes horizontally to look nicer\n",
"zx.draw_matplotlib(g)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The blue lines represent wires that have a Hadamard gate on them."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise\n",
"\n",
"Let's see a bit more detail on what goes into rewriting this circuit. The objective of the exercise is that, starting from the original circuit, you derive the reduced graph shown above. To make things easier and to display the derivation steps nicely, we've implemented the class `Steps` that will be managing PyZX's backend so you don't have to worry about it."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from ipywidgets import widgets\n",
"from IPython.display import display, Markdown\n",
"\n",
"import pyzx.rules as r\n",
"\n",
"class Steps:\n",
" def __init__(self,g):\n",
" self.current = g.copy()\n",
" self.stepList = [zx.draw_matplotlib(self.current,h_edge_draw='box')]\n",
" self.stepNames = ['start']\n",
" \n",
" def applyXTimes(self,name,match,rule,x):\n",
" for i in range(x):\n",
" self.applyOnce(name,match,rule)\n",
" \n",
" def applyOnce(self,name,match,rule):\n",
" m = match(self.current)\n",
" if len(m) > 0:\n",
" zx.rules.apply_rule(self.current,rule,[m[0]])\n",
" self.stepList.append(zx.draw_matplotlib(self.current,h_edge_draw='box'))\n",
" self.stepNames.append(name)\n",
" \n",
" def to_gh(self):\n",
" zx.to_gh(self.current)\n",
" self.stepList.append(zx.draw_matplotlib(self.current,h_edge_draw='box'))\n",
" self.stepNames.append('to_gh')\n",
" \n",
" def plotter(self,rewrite):\n",
" display(self.stepList[rewrite])\n",
" display(Markdown(\"**Rewrite step**: \" + self.stepNames[rewrite]))\n",
" \n",
" def drawSteps(self):\n",
" self.current.normalize()\n",
" self.stepList.append(zx.draw_matplotlib(self.current))\n",
" self.stepNames.append('rearrange')\n",
" w = widgets.interactive(self.plotter, rewrite=(0,len(self.stepList)-1))\n",
" slider = w.children[0]\n",
" slider.value = 0\n",
" return w"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Your task is to use the function `applyXTimes` to apply ZX rules on the diagram until it reaches the reduced form given above. You will need to apply some combination of the rules listed below, possibly interleaving them:\n",
"- removal of identities (phases with angle 0) `s.applyXTimes('id', r.match_ids, r.remove_ids, x)`,\n",
"- spider contraction `s.applyXTimes('spider', r.match_spider, r.spider, x)`;\n",
"- local complementation `s.applyXTimes('lcomp', r.match_lcomp, r.lcomp, x)`;\n",
"- pivoting `s.applyXTimes('pivot', r.match_pivot, r.pivot, x)`.\n",
"\n",
"Argument `x` indicates how many consecutive times the same rule should be applied. Write your code in the snippet below. The last line on the snippet must be `display(s.drawSteps())`, which will display the derivation you've come up with. A sliding bar should allow you to scroll over the different steps of your derivation (this requires that you have succesfully enabled ipywidgets).\n",
"\n",
"**Note**: The final diagram you get might not be exactly the same as the reduced graph shown above (it depends on the order you apply the rules). Nevertheless, it is certain that their corresponding matrices will be equivalent: the rules of the ZX-calculus preserve equality of the 'matrix semantics'."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s = Steps(circ) #Create an instance of the Steps class we just defined\n",
"\n",
"\n",
"### APPLY THE FIRST ROUND OF RULES HERE ###\n",
"s.applyXTimes('spider', r.match_spider, r.spider, 2)\n",
"\n",
"\n",
"\n",
"\n",
"s.to_gh() #Convert all X-phases (red nodes) into Z-phases surrounded by H-boxes. This is a necessary step.\n",
"\n",
"### APPLY THE SECOND ROUND OF RULES HERE ###\n",
"s.applyXTimes('spider', r.match_spider, r.spider, 3)\n",
"\n",
"\n",
"\n",
"\n",
"display(s.drawSteps())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
" Answer (Click me!)\n",
"\n",
"This is just one way that works, there are many equivalent ones:\n",
" \n",
"```python\n",
"s = Steps(circ) #Create an instance of the Steps class we just defined\n",
"\n",
"### APPLY THE FIRST ROUND OF RULES HERE ###\n",
"s.applyXTimes('spider', r.match_spider, r.spider, 20)\n",
"\n",
"s.to_gh() #Convert all X-phases (red nodes) into Z-phases surrounded by H-boxes. This is a necessary step.\n",
"\n",
"### APPLY THE SECOND ROUND OF RULES HERE ###\n",
"s.applyXTimes('spider', r.match_spider, r.spider, 3)\n",
"s.applyXTimes('pivot', r.match_pivot, r.pivot, 15)\n",
"s.applyXTimes('lcomp', r.match_lcomp, r.lcomp, 15)\n",
"s.applyXTimes('pivot', r.match_pivot, r.pivot, 15)\n",
"\n",
"display(s.drawSteps())\n",
"```\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Recovering the circuit\n",
"\n",
"Even though this graph is a lot compacter than the one we started out with, it no longer looks like a circuit. To fix this we need to be clever."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"circ2 = zx.extract_circuit(g.copy())\n",
"zx.draw(circ2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here, we have used function `zx.extract.clifford_extract(circ2,1,2)` to ask PyZX to find a way to implement our compact diagram using quantum gates. This diagram is found using, almost exclusively, the spider rule and the colour change rule. The last two arguments of the function identify the segment of the diagram we want to extract as a circuit; in this case, the whole diagram (from the first column of the green phases to the second one).\n",
"\n",
"To verify that this circuit is still equal to the original circuit, we can transform them into numpy tensors and compare these tensors for equality:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t1 = circ.to_tensor()\n",
"t2 = circ2.to_tensor()\n",
"# This checks whether t1 and t2 are equal up to some number: t1 == z*t2 for some complex number z\n",
"zx.compare_tensors(t1,t2,preserve_scalar=False) "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that `circ2` is a variable of type `zx.Circuit`, and we can list the gates with:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(circ2.gates)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This printed a description of the sequence of gates from left to right. We can also represent the circuit in one of several quantum circuit description languages, such as Quipper:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"scrolled": true
},
"outputs": [],
"source": [
"print(circ2.to_quipper())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Approximately universal circuits\n",
"\n",
"Now lets try the same thing with a more complicated Clifford+T circuit (i.e. it may include $\\pi/4$ phases)."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"qubit_amount = 6\n",
"depth = 70\n",
"random.seed(1338)\n",
"circ = zx.generate.cliffordT(qubit_amount, depth,p_t=0.2)\n",
"zx.draw_matplotlib(circ,figsize=(17,2),h_edge_draw='box')"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = circ.copy()\n",
"zx.clifford_simp(g, quiet=True)\n",
"g.normalize()\n",
"zx.draw_matplotlib(g)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Once we get the reduced diagram, we ask PyZX to extract the circuit:"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Circuit on 6 qubits with 62 gates.\n",
" 8 is the T-count\n",
" 54 Cliffords among which \n",
" 28 2-qubit gates (2 CNOT, 26 other) and\n",
" 22 Hadamard gates.\n"
]
}
],
"source": [
"g2 = g.copy()\n",
"c = zx.extract.extract_circuit(g2)\n",
"print(c.stats())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can convert this back into a PyZX-graph:"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"zx.draw_matplotlib(c.to_graph())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And verify that it is still equal to the original graph:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"zx.compare_tensors(c.to_tensor(), circ.to_tensor(),preserve_scalar=False)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Finally, lets represent this circuit in the QASM circuit description language:"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"OPENQASM 2.0;\n",
"include \"qelib1.inc\";\n",
"qreg q[6];\n",
"cx q[2], q[5];\n",
"cx q[5], q[2];\n",
"cx q[2], q[5];\n",
"cx q[1], q[4];\n",
"cx q[4], q[1];\n",
"cx q[1], q[4];\n",
"h q[5];\n",
"h q[4];\n",
"h q[3];\n",
"h q[1];\n",
"h q[1];\n",
"h q[3];\n",
"cz q[2], q[5];\n",
"cz q[2], q[3];\n",
"cz q[1], q[2];\n",
"h q[2];\n",
"h q[5];\n",
"cz q[2], q[5];\n",
"cz q[2], q[3];\n",
"cz q[1], q[2];\n",
"rz(1.25*pi) q[2];\n",
"h q[0];\n",
"h q[2];\n",
"h q[4];\n",
"cz q[1], q[5];\n",
"cz q[1], q[4];\n",
"cz q[1], q[3];\n",
"cz q[1], q[2];\n",
"cz q[0], q[1];\n",
"rz(0.5*pi) q[1];\n",
"h q[1];\n",
"cz q[1], q[3];\n",
"rz(1.5*pi) q[3];\n",
"h q[3];\n",
"cz q[0], q[5];\n",
"cz q[0], q[4];\n",
"cz q[0], q[3];\n",
"h q[0];\n",
"cx q[0], q[2];\n",
"cz q[3], q[5];\n",
"cz q[2], q[5];\n",
"cz q[0], q[5];\n",
"rz(0.75*pi) q[5];\n",
"h q[5];\n",
"rz(1.25*pi) q[5];\n",
"h q[5];\n",
"cx q[5], q[1];\n",
"cz q[2], q[3];\n",
"rz(1.25*pi) q[2];\n",
"h q[2];\n",
"cz q[0], q[3];\n",
"cz q[0], q[2];\n",
"rz(0.75*pi) q[4];\n",
"rz(0.25*pi) q[0];\n",
"h q[4];\n",
"h q[0];\n",
"cz q[3], q[5];\n",
"cz q[3], q[4];\n",
"cz q[1], q[5];\n",
"rz(0.5*pi) q[5];\n",
"h q[5];\n",
"rz(0.75*pi) q[4];\n",
"rz(0.25*pi) q[3];\n",
"h q[2];\n",
"rz(0.5*pi) q[0];\n",
"h q[0];\n",
"\n"
]
}
],
"source": [
"print(c.to_basic_gates().to_qasm())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Implementing a basic rewrite"
]
},
{
"attachments": {
"remove_ids.png": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAVUAAACMCAIAAABDKK0qAAALg0lEQVR4nO3df2zU5R0H8HdLD2G9nlhKAUlsKaUNuk5+TAFrqfwQzHpdUHHBWcJPK9ZUF5xbZGiT6kaTQSokUn+RLIuKEuew2qTAaCl0m3Rb0IMi15ZSC6LYjipckdlrb398v9e7SoH2+jx33H3er1xyD3r3eZ677/Pufe/766I8Hg9CoaKiwm63OxyOjIyMkAyArqSsrKygoCBUE4N61dbWZmVlac1ItKa6RHT9Y/6J5GL+ieRi/onkYv6J5GL+ieRi/onkYv6J5GL+ieRi/onkYv6J5GL+ieRi/onkYv6J5GL+ieRi/onkYv6J5GL+ieRi/onkYv6J5GL+ieRi/onkYv6J5GL+ieRi/onkYv6J5GL+ieRi/onkYv6J5GL+ieRi/onkYv6J5GL+ieRi/onkYv6J5GL+ieRi/onkYv6J5GL+ieQKWf57enpsNlt3d3eoBkBX4vF4bDab2+0O9UBIu5ig9dTe3l5eXr5v375jx441NDRcvHgRwLRp02w2W1pa2m233Xbvvffm5OSMGjUqaEMiQ2tra3l5eU1NTX19fVNTU1dXFwCLxZKQkJCamjpt2rRFixYtXLhw5MiRoR4pqebRr7q62m63R0VFXXMwMTExS5YsqaurC8KoqKen5/333589e/ZA5klsbGx+fn5jY2OoRy3IwYMHATgcDn1d6M1/Q0PDwoUL+5lNo4A0YDqQClj7+f9Lly49c+aM1rEJV1dXd/vtt1/+zicAU4DpQBJw+cf9sGHDnn766QsXLoR6+CKEd/5feeWVESNG+OaOFcgDdgJtgKfv7QzwJvCLPjPupptueuedd/QNT6zu7u7nn3/ef3VsLFAAfAScv2zJNAGvAvf13VB0yy231NTUhPp1RL5wzX9XV9eqVat882U0sBnovGxyXX77FvgdEOt76rp163p6enQMUiaXyzVv3rzetzcF2A50DWDJnAHWAMP8VgTKyspC/WoiXFjm3+12P/zww74E24EvBzC//G+fA3N9BQoLC5UPUiaXy+X/bf8xwDXIJfMf4Md+KwIvv/xyqF9TJAvL/D/55JO+CVIyyPnVe3MDv/WV2bx5s/JxSuN2u+12u/F+jgDeDHTJXASWeJdLdHT0Bx98EOpXFrHCL/9vvfWWL7VlgU6x3tvvffPswIEDaocqTXFxsfFm3gDsG9pi6QZ6V/BiY2OdTmeoX1xkCrP8f/311wkJCea8eG7I4Tdua33bnLjZOWAOhyMmxjzWY4eKxfI/v69o99xzD7fR6BCE/Ks8/m/Dhg3t7e0AcDdQpKjoFuAnANDa2vriiy8qKipOYWGhcTxfPrBURcHhwNvAOADA/v37d+zYoaIqBZ2qPyQtLS3mJ4wFOK7ow9+4/dscqtVq7ejoUDVgOaqqqow3MLG/PXxDuf3ZO4tSUlK6urpC/UIjTTh9/m/bts08Ynw5kK6qKgBgBvAAALhcrtdff11paRFKS0uNxrNAnNLKeUAGAKC5uXnPnj1Ka1MwKMv/zp07zdavVZX085R5z/XMwTp37lxlZSWAEcCqaz56kKKAX3nbfTb9UphQk/+jR4+2tLQAwFTVH/6GLCAZAA4fPnz27FkNHUSsPXv2GOfzPATYNNR/ALgBALB3716eMhh21OS/urrabP1MSb3LRAH3mc0DBw7o6SMyffzxx0YjR0/9UcAdAIC2trb6+no9nZAuavLvdDrN1k+V1OvPTPPe4XBo6yMCffLJJ0ZjhrYuMr2NI0eOaOuEtFCTf3PlH3pW/g1p5v2pU6e09RGBWltbAViAidq66K3smwYUJtTk//Tp02ZrjJJ6/fFuuf7mm2+09RGBjLcr3u/UHeUSvQ2Xy6WtE9JCTf59l/EarqTe1Rhbs2iAjLdL62LRv8xJFzX5j4+PN1vnlNTrj/cvjM2mYzN2xDLeLn2LRXdx0kpN/pOTk81Wi5J6/Tlp3o8bN05bHxFo7NixADqBdm1deL/7ISkpSVsnpIWa/KekpJgtfTuAjpr3kydP1tZHBJoyZYrR0LdkDnsbt956q7ZOSAs1+Z8507t3bp+Sev35m3mfmZl51cdRH3fcYeye17VkPMBBAEBMTExGRoaeTkgXNfnPzs42L/VXCXQqKdnXGeDvAJCQkMBJNijz5883Gm8DHg31DwJfAQDuuusu32YgChNq8j9y5MicnBwAuAT8SUnJvrab2/8WL14cHc3fLBqEjIyM9PR0ACeA/Rrq956PtXjxYg3lSS9lWVqzZo3Z2gRcUlUVAHAeeMlsPv7440pLi1BQUGA0ilVXdgLG+VgWi+WRRx5RXZ60U5b/RYsWmdeTbwE2qqoKAHjO3MU0f/786dOnKy0twsqVK8eMGQNgP/AXdWU9wFPe3bJr165NTEy8xhPo+qMs/1FRUVu2bDH/8Qfgn4rq7gW2AkB0dPSmTZsUFZUlLi7uhRdeMNqPAZ8rKvsSsBsAEB8fX1Sk6npPFFQqv0tnZ2evWLECANzAQ8CJIVc84rvW7Pr166dOnTrkikLl5+dnZ2cD+C+wBPh2yAXL/a7zUFpaOnr06CGXpFBQezmh8+fP9+5wRgrQOISLSzmA8WalOXPm8PJSQ9Tc3Nx7dda7+/sRpoHfKvx+qGnZsmWhfmURK5yu/2WIi4srLy+fMGECADQDM4GPAiq0A5gNfAkAkyZNeu+993ovX0uBmThx4ocffmj8hm8tMAOoG3wRD/BH4OfAdwCAuXPnvvHGG2rHScGkfl9aampqZWXl+PHjAeAckAus9u4jHohm4CHgl+ZxBCkpKdXV1cbmKxqiWbNmVVRUGH8CWr1XaR742ZT/Au4GfuPd5peZmblr167hw3n6TzjTtF5x6tSpO++809eNFVgL1ALdV1indANVwErA4nvSggUL2traNI1QrE8//XTSpEm9b3IC8CzguPLa/nfAX4Ef7NxfsWJFZ2dnqF9KhAvC+n+Ux6PjqDAAcLvdxcXFJSUlfc7YTQDmAGnAWOBHgAv4EnACNcB536OsVuvGjRufeOIJ/5+pJVU6OzvXrVv32muv+f/HCcBcIBkYA4wAOoCvgCPAP7xr+4abb75569atDz74YHCHLFFtbW1WVpbD4dB3zKvG/BsaGxuLiorefffdnp6egTzeYrEsX768uLjY/AZxPfF4PM8888zx48f1XYPAarXm5eXdf//9mur7O3ToUFFR0e7duwf4eKvVWlhYuH79eqvVqnVgAYiwRWMIQv51rf//wOnTp0tKSmbNmnWlo3ctFkt2dnZpaenZs2eDM6QAdHR0BOHo49zc3GC+qPr6+g0bNlxlhhkHd2/fvt3lcgVzYIMSkYsmvNf/+3XhwgWn09nQ0OB0OquqqnJzc5OTk9PS0tLT043tUte5pqamhoaG77//XlN9m802Y8aMG2+8UVP9q+jo6Dh27NiJEyccDsehQ4eWLVuWmJiYlpY2efJki8Vy7eeHWuQtmkhY/7+SiooKu92ud92GAlJWVlZQUBCqiUG9gpB/nktHJBfzTyQX808kF/NPJBfzTyQX808kF0+qG4Tu7u68vLzPPvtM30FmcXFxq1evfvTRRzXVj1RcNIFh/gehs7Nz165dly6pvbzhDyUlJUXYJAsCLprAMP+DYLPZvvjii5MnT2r9kOEPnASAiyYwzP/gxMfH8yr31ycumgBw+x+RXMw/kVzMP5FczD+RXMw/kVzMP5FczD+RXMw/kVzMP5FczD+RXMw/kVzMP5FczD+RXMw/kVzMP5FczD+RXMw/kVzMP5FczD+RXMw/kVzMP5FczD+RXMw/kVzMP5FczD+RXMw/kVzMP5FczD+RXMw/kVzMP5FczD+RXMw/kVzMP5FczD+RXMw/kVzMP5FczD+RXMw/kVzMP5FczD+RXMw/kVzMP5FczD+RXMw/kVzMP5FczD+RXMw/kVzMP5FczD+RXMw/kVzMP5Fc/wcSzH/9f+rztgAAAABJRU5ErkJggg=="
}
},
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, let's take a look at implementing ZX-calculus rewrites within PyZX. For the sake of simplicity, we'll have a look at one of the simplest possible rules, which is used to remove red and green identities from a diagram:\n",
"\n",
"\n",
"Let's first import a test diagram to apply this rule to:"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"identity_lhs = zx.Graph()\n",
"\n",
"# Adds vertices to the diagram with spacing\n",
"identity_lhs.add_vertex()\n",
"identity_lhs.add_vertex(row=0)\n",
"identity_lhs.add_vertex(row=1)\n",
"\n",
"# Sets the type of the vertices\n",
"identity_lhs.set_inputs({0})\n",
"identity_lhs.set_outputs({2})\n",
"identity_lhs.set_type(1, zx.VertexType.Z)\n",
"\n",
"# Adds edges to the diagram\n",
"identity_lhs.add_edges({(0,1), (1,2)})\n",
"\n",
"zx.draw_matplotlib(identity_lhs, labels=True)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In PyZX, we would apply the \"identity\" rule to a diagram `g` by calling:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"g = identity_lhs.copy() # makes a copy of the diagram so we can reuse the original later\n",
"zx.simplify.simp(g, \"id\", zx.rules.match_ids, zx.rules.remove_ids) # applies the rewrite\n",
"zx.draw(g, labels=True)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's take a look at what the function `zx.rules.match_ids` actually does."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"zx.rules.match_ids(identity_lhs)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's parse this result: `match_ids` returns a list of quadruples, each of which takes the form of a sequence of 3 vertices followed by a `zx.EdgeType` integer. The three vertices correspond to a green or red spider matching the LHS of the \"identity\" rule, i.e. the central vertex 1 of our diagram `identity_lhs`. The two other vertices in the tuple are the neighbours of this central vertex.\n",
"\n",
"The last element of the tuple is a little trickier. In PyZX, there are 2 types of edges: plain edges, and edges that carry a Hadamard box. If the central vertex is connected to its neighbours with edges that carry a Hadamard box, this needs to be carried forward when we do the rewrite. Luckily, `match_ids` also computes what the final edge type should be in the diagram, and returns this value as the corresponding integer, matching either `zx.EdgeType.SIMPLE` or `zx.EdgeType.HADAMARD`.\n",
"\n",
"`remove_ids` should communicate this information to `zx.simplify.simp` as its return. Let see what it actually does:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"g = identity_lhs.copy()\n",
"zx.rules.remove_ids(g, zx.rules.match_ids(identity_lhs))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`remove_ids` returns another quadruple `(edges_to_edit, vertices_to_remove, vertices_to_add, isolated_vertices)` consisting in:\n",
"* `edges_to_add`: a dictionary of edges to add to `g`; the keys of the dictionary are pairs `(x,y)` corresponding to the edges to add, and the value associated to an edge (=key) is a pair `[a,b]` where `a` is the number of edges of type `zx.EdgeType.SIMPLE` and `b` is the number of edges of type `zx.EdgeType.HADAMARD`.\n",
"* `vertices_to_remove`: a list of vertices to remove from `g`;\n",
"* `edges_to_remove`: a list of vertices to add to `g`;\n",
"* `isolated_vertices`: a boolean which says whether the rule will result in isolated vertices in the graph."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Can you now implement your own version of `remove_ids`? It should take two arguments: the diagram `g` to apply the rewrite rule to, and the result of calling `match_ids` on `g`. For each match, we want to apply the corresponding rewrite, by: \n",
"1. deleting the central vertex;\n",
"2. connecting the two neighbours by an edge of the correct type.\n",
"\n",
"Deleting the central vertex removes all connected edges, so we do not need to take care of edge removal when applying the identity rule. Since the identity rule should also never result in isolated vertices, we can safely ignore the two last return values:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def my_remove_ids(g, matches):\n",
" edges_to_edit = dict()\n",
" vertices_to_remove = []\n",
" \n",
" for v, neighbor0, neighbor1, edge_type in matches:\n",
" # Your code here:\n",
" ...\n",
" \n",
" return (edges_to_edit, vertices_to_remove, [], False)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
" Answer (Click me!)\n",
" \n",
"```python\n",
"def my_remove_ids(g, matches):\n",
" edges_to_add = dict()\n",
" vertices_to_remove = []\n",
" \n",
" for v, neighbor0, neighbor1, edge_type in matches:\n",
" vertices_to_remove.append(v)\n",
" e = g.edge(neighbor0, neighbor1)\n",
" if not e in edges_to_add:\n",
" edges_to_add[e] = [0,0]\n",
" if edge_type == zx.EdgeType.SIMPLE: \n",
" edges_to_add[e][0] += 1\n",
" else: edges_to_add[e][1] += 1\n",
" \n",
" return (edges_to_add, vertices_to_remove, [], False)\n",
"```\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Try it out:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"g = identity_lhs.copy()\n",
"zx.simplify.simp(g, \"id\", zx.rules.match_ids, my_remove_ids)\n",
"zx.draw(g)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Bonus: Optimising T-count\n",
"\n",
"The Clifford+T gateset is universal for quantum computation: every circuit can be built using gates from it. Among its gates, the most expensive ones are the CNOT gate (the only two-qubit gate in the set) and the T gate, which corresponds to a Z-phase of angle $\\pi/4$. A stardard objective in quantum circuit optimisation is the reduction of the T-count: the number of T gates in the circuit. This section provides an introduction to *phase teleportation*, a procedure for T-count reduction based on the ZX-calculus. This procedure was first proposed in a scientific paper from 2019: https://arxiv.org/pdf/1903.10477.pdf.\n",
"\n",
"As it happened with the previous section, we first need to take a moment to define the ZX-diagrams we are interested in and the rules that can be applied to them. We shall explore these using Quantomatic. **Follow the last section of the lab session's PDF**, then continue from here.\n",
"\n",
"### Example\n",
"\n",
"Here we apply phase teleportation to reduce the T-count of a particular quantum circuit. The circuit is a 3-control Toffoli, which is a 4-qubit gate where the first three wires act as control and the fourth has an X gate applied to it if and only if the controls are all simultaneously in state $\\lvert 1 \\rangle$. The circuit that implements such a gate using the Clifford+T gateset is shown below as a ZX-diagram. The wire at the bottom carries and auxiliary 'helper' qubit and should be initialised to $\\lvert 0 \\rangle$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"circ = zx.circuit.Circuit.load(\".assets/CCCNOT\").to_basic_gates()\n",
"\n",
"print(\"The original circuit:\")\n",
"display(zx.draw_matplotlib(circ,h_edge_draw='box'))\n",
"g = circ.to_graph()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As you can see, there are plenty of $T$ gates (and $T^\\dagger$, phases with $-\\pi/4$ angle). The code below executes the different stages of the phase teleportation procedure. We use an updated version of our `Steps` class to display the circuit after each stage."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"class BonusSteps(Steps):\n",
" \n",
" def apply_clifford_simp(self):\n",
" zx.simplify.clifford_simp(self.current)\n",
" self.stepList.append(zx.draw(self.current))\n",
" self.stepNames.append('clifford')\n",
" \n",
" def apply_pivot_gadget_simp(self):\n",
" zx.simplify.pivot_gadget_simp(self.current)\n",
" self.stepList.append(zx.draw(self.current))\n",
" self.stepNames.append('pivot gadget')\n",
" \n",
" def apply_gadget_simp(self):\n",
" zx.simplify.gadget_simp(self.current)\n",
" self.stepList.append(zx.draw(self.current))\n",
" self.stepNames.append('gadget fusion')\n",
"\n",
"bs = BonusSteps(g)\n",
"\n",
"print(\"List of rules applied during the derivation:\\n\")\n",
"bs.apply_clifford_simp()\n",
"bs.apply_pivot_gadget_simp()\n",
"bs.apply_gadget_simp()\n",
"bs.apply_clifford_simp()\n",
"\n",
"display(bs.drawSteps())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In order to apply phase teleportation we first need to identify the phase gadgets in the circuit and bring them as close together as possible. To do so, we use Clifford circuit simplification (described in the first section of this sheet) and a special version of pivoting. Then, we attempt to apply the `gadget_fusion` rule we introduced in the last Quantomatic exercise. This will reduce the number of Z-phases of angle $\\pi/4$ (and $-\\pi/4$), i.e. it will decrease the number of T gates (and their inverse) in the circuit. Normally, after fusing gadgets we would again do a round of Clifford simplification and gadgetization (using pivoting) and try to fuse gadgets again, repeating this cycle until it's not possible to fuse any more gadgets.\n",
"\n",
"Once all possible gadget fusions are done, we backtrack all the rewriting process, but with the angles on some of the gadgets changed. In the end, we recover the circuit we started with, obtaining the *exact* same structure but some of the T gates having disappeared, being converted to $\\pi/2$ or $0$ rotations thanks to the fusion of their corresponding phase gadgets."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(\"The circuit after phase teleportation:\")\n",
"circ2 = zx.simplify.teleport_reduce(g)\n",
"display(zx.draw(circ2))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Looking at the initial and final circuits, it seems like we found a way to teleport $\\pi/4$ phases from their original place to a distant point on the circuit, cancelling them with the T gate there. Even in such a small example, the T-count reduction is significant:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(\"Original T-count:\\t\", zx.tcount(circ))\n",
"print(\"Final T-count:\\t\\t\", zx.tcount(circ2))"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.10"
}
},
"nbformat": 4,
"nbformat_minor": 4
}