{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Circuit optimization using PatternManager - example of QAOA for MaxCut\n",
"\n",
"This notebook provides an example of minimizing the duration of a quantum circuit. In this notebook, a quantum circuit implementing an instance of Q.A.O.A. is used and the `PatternManager` tool will be used to minimize the duration of this circuit. Since the purpose of this notebook is to explain the optimization tool `PatternManager`, details on the implementation of the circuit are not explained.\n",
"\n",
"In this notebook, a variational circuit is used to solve MaxCut for the graph printed below. Solving MaxCut for a graph $\\mathcal{G} = (\\mathcal{V}, \\mathcal{E})$ consists in finding a subset $S$ of $\\mathcal{V}$ such as the number of edges in $\\mathcal{E}$ linking a vertex of $S$ to a vertex of $\\mathcal{V} \\backslash S$ is maximal.\n",
"\n",
"<img src=\"images/graph.png\" width=\"500px\" height=\"auto\" alt=\"Graph of interaction\" title=\"Graph of interaction\"/>\n",
"\n",
"The circuit used in this example can be split in 3 parts:\n",
" 1. An Hadamard gate on each qubit\n",
" 2. For each pair of qubits $i$ and $j$, there is an E gate if and only if $i$ and $j$ are connected in the graph above\n",
" 3. An $R_X$ on each qubit\n",
" \n",
"An E gate can be defined by the following pattern:\n",
"\n",
"<img src=\"images/E_gate.png\" width=\"500px\" height=\"auto\" alt=\"Porte E\" title=\"E gate definition\"/>\n",
" \n",
"Our circuit (limited to the first 8 qubits) looks like:\n",
"\n",
"<img src=\"images/algo.png\" width=\"750px\" height=\"auto\" alt=\"Algorithm\" title=\"Algorithm limited to the first 8 qubits\"/>\n",
"\n",
"\n",
"## Initial circuit\n",
"The circuit should be created before starting the optimization. The following code defines an abstract gate `E` corresponding to the definition above. The circuit is then defined using these `E` gates. Since `PatternManager` is used to optimize the depth of the circuit, the initial order of `E` corresponds to the order which maximizes the duration of the circuit."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"scrolled": false
},
"outputs": [],
"source": [
"from qat.lang.AQASM import Program, H, CNOT, PH, RX, QRoutine\n",
"from qat.lang.AQASM.misc import build_gate\n",
"from qat.pbo.utils import depth\n",
"import numpy as np\n",
"\n",
"\n",
"# Define an abstract gate E\n",
"@build_gate(\"E\", [float], 2)\n",
"def E(alpha):\n",
" \"\"\"\n",
" Build a E gate\n",
" \"\"\"\n",
" routine = QRoutine()\n",
" routine.apply(CNOT, [0, 1])\n",
" routine.apply(PH(alpha), [1])\n",
" routine.apply(CNOT, [0, 1])\n",
"\n",
"\n",
"# Define the worst order of E gates\n",
"edges = [(10, 15), (9, 15), (9, 14), (4, 9), (0, 4), (0, 5),\n",
" (1, 5), (5, 10), (10, 16), (11, 16), (11, 17),\n",
" (6, 11), (1, 6), (2, 6), (2, 7), (7, 12), (12, 17),\n",
" (12, 18), (13, 18), (8, 13), (3, 8)]\n",
"\n",
"# Define program\n",
"prog = Program()\n",
"qbits = prog.qalloc(19)\n",
"alpha = prog.new_var(float, r\"\\alpha\")\n",
"beta = prog.new_var(float, r\"\\beta\")\n",
"\n",
"# Wall of hadamard\n",
"for qb in qbits:\n",
" prog.apply(H, qb)\n",
" \n",
"# E gates\n",
"for vertex_1, vertex_2 in edges:\n",
" prog.apply(E(alpha), qbits[vertex_1], qbits[vertex_2])\n",
" \n",
"# Wall of RX\n",
"for qb in qbits:\n",
" prog.apply(RX(beta), qb)\n",
"\n",
"# Get initial circ\n",
"initial_circ = prog.to_circ()\n",
"initial_circ.display()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Using metrics\n",
"\n",
"The tool `PatternManager` is used to optimize any *score function* given by the user. A *score function* is a function that that the user wants to maximize. The `qat.nnize` modules provide tools to define score functions.\n",
"\n",
"The `DurationMetric` class can be used as a *score function*, this class will compute the opposite of the duration of the circuit (this tool computes the opposite of the duration because maximizing the opposite of the duration is equivalent to minimizing the duration: the opposition of the duration is then the metric we want to maximize).\n",
"\n",
"In our example, each gate will have the same duration: 1 unit of time."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from qat.nnize.metrics import DurationMetric\n",
"\n",
"# Define the metric\n",
"duration_metric = DurationMetric()\n",
"\n",
"# Define the default duration\n",
"duration_metric.set_gate_time({\"-DEFAULT-\": 1})\n",
"\n",
"# The metric has to compute the duration of the circuit\n",
"duration_metric.minimize_overall_time()\n",
"\n",
"# Duration of the initial circuit\n",
"print(\"Duration of the initial circuit:\",\n",
" -duration_metric(initial_circ))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Circuit optimization\n",
"\n",
"The optimization problem consists in maximizing the function `duration_metric`. This function is called **global metric**, the tool `PatternManager` will use this metric to perform the optimization.\n",
"\n",
"Since E gates commute on any qubits, few rules will be defined. The tool `PatternManager` will use these rules to optimize the duration of the circuit. The rules are defined by:\n",
"\n",
"<img src=\"images/patterns.png\" width=\"500px\" height=\"auto\" alt=\"Rewriting rules\" title=\"Patterns\"/>\n",
"\n",
"There are 3 commutation rules above, so 3 groups will be defined for the optimizer. A group is a set of equivalent patterns (i.e. a small subcircuit), the optimizer can replace any pattern in the circuit by a pattern of the same group. Groups define the action space of the optimizer.\n",
"\n",
"`PatternManager` will use an heuristic to perform the optimization. Two different methods may be used:\n",
"- The gradient descent (use `\"gradient\"`) $\\rightarrow$ Used by default\n",
"- The simulated annealing (use `\"annealing\"`) $\\rightarrow$ Used here"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from qat.pbo import PatternManager, VAR\n",
"from qat.lang.AQASM import AbstractGate\n",
"\n",
"# Define the optimizer\n",
"manager = PatternManager(global_metric=duration_metric)\n",
"\n",
"# Define abstract variables\n",
"theta = VAR()\n",
"gamma = VAR()\n",
"\n",
"# Group 1 - first commutation rule\n",
"group1 = manager.new_group()\n",
"# The following two lines define interchangeable patterns\n",
"group1.add_pattern([('E', [1, 2], theta), ('E', [0, 1], gamma)])\n",
"group1.add_pattern([('E', [0, 1], gamma), ('E', [1, 2], theta)])\n",
"\n",
"# Group 2 - second commutation rule\n",
"group2 = manager.new_group()\n",
"\n",
"group2.add_pattern([('E', [0, 1], theta), ('E', [0, 2], gamma)])\n",
"group2.add_pattern([('E', [0, 2], gamma), ('E', [0, 1], theta)])\n",
"\n",
"# Group 3 - third commutation rule\n",
"group3 = manager.new_group()\n",
"\n",
"x3 = VAR()\n",
"group3.add_pattern([('E', [0, 2], theta), ('E', [1, 2], gamma)])\n",
"group3.add_pattern([('E', [1, 2], gamma), ('E', [0, 2], theta)])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The optimizer can be then called on the circuit to minimize the duration of the circuit. A trace can be passed to the optimizer to log the values of the metric during the optimization.\n",
"\n",
"Since the E gate is not a common gate, the constructor of the E gate should be given to the optimizer."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Create a trace list\n",
"trace = list()\n",
"\n",
"# Add E gate constructor\n",
"manager.add_abstract_gate(E)\n",
"\n",
"# Start optimization\n",
"final_circ = manager.replace_pattern(initial_circ, method='annealing', trace=trace)\n",
"\n",
"# Print final circuit\n",
"print(\"Final duration:\", -duration_metric(final_circ))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The trace of the optimization can be plotted using matplotlib."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt\n",
"\n",
"plt.figure(figsize=(10, 5))\n",
"plt.xlabel(\"Nb iterations\")\n",
"plt.ylabel(\"Duration\")\n",
"plt.plot(range(len(trace)), [-depth for depth in trace])\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Compilation\n",
"Before starting compilation, E gates must be replaced by their implementation. The `GraphCircuit` tool will be used to replace `E` gates."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from qat.pbo import GraphCircuit\n",
"\n",
"# Init graph circuit\n",
"theta = VAR()\n",
"graph = GraphCircuit()\n",
"graph.load_circuit(final_circ)\n",
"\n",
"# Replace pattern\n",
"graph.replace_pattern(\n",
" [(\"E\", [0, 1], theta)],\n",
" [(\"CNOT\", [0, 1]), (\"PH\", [1], theta), (\"CNOT\", [0, 1])],\n",
" pos=all\n",
")\n",
"\n",
"# Get circuit\n",
"final_circ = graph.to_circ()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"One wants to compile this optimized circuit on the Rigetti Forest 19Q. Only few gates may be used on this quantum computer. The allowed gates are:\n",
"- Gate $R_Z(x)$ for $x \\in \\mathbb{R}$\n",
"- Gate $R_X(x)$ for $x \\in \\left\\{ \\pm \\pi, \\pm \\frac{\\pi}{2} \\right\\}$ (these $R_X$ gates are called \"compliant $R_X$\")\n",
"- Gate $CZ$\n",
"\n",
"Since our algorithm does not use these gates, some changes may be defined. `PatternManager` could be used to solve this optimization problem. It is possible to define patterns which must disappear.\n",
"- The gate $PH$ must disappear: $PH(x) \\rightarrow R_Z(x)$\n",
"- The gate $H$ must disappear: $H \\rightarrow R_Z \\left (\\frac{\\pi}{2} \\right) \\cdot R_X \\left (\\frac{\\pi}{2} \\right) \\cdot R_Z \\left (\\frac{\\pi}{2} \\right)$\n",
"- The gate $CNOT$ must disappear: $CNOT \\rightarrow \\left(\\mathbb{1} \\otimes H \\right) \\cdot CZ \\cdot \\left(\\mathbb{1} \\otimes H \\right)$\n",
"\n",
"### Groups\n",
"**Group 1** Only non-compliant $R_X(x)$ are transformed into $H \\cdot R_Z(x) \\cdot H$\n",
"\n",
"**Group 2** $PH(x)$ gates are replaced by $R_Z(x)$ gates\n",
"\n",
"**Group 3** $CNOT$ gates are replaced by $(\\mathbb{1} \\otimes H) \\cdot CZ \\cdot (\\mathbb{1} \\otimes H)$\n",
"\n",
"**Group 4** $H$ gates are replaced by $R_Z \\left (\\frac{\\pi}{2} \\right) \\cdot R_X \\left (\\frac{\\pi}{2} \\right) \\cdot R_Z \\left (\\frac{\\pi}{2} \\right)$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from math import pi\n",
"\n",
"# Define a compiler: no metric needed\n",
"compiler = PatternManager()\n",
"theta = VAR()\n",
"\n",
"# Group 1: remove non compliant RX gates\n",
"constraint_angle = VAR()\n",
"\n",
"for angle in [pi, -pi, pi/2, -pi/2]:\n",
" constraint_angle.add_prohibited_value(angle)\n",
" \n",
"group_1 = compiler.new_group()\n",
"\n",
"group_1.pattern_to_remove([(\"RX\", [0], constraint_angle)])\n",
"group_1.add_pattern([(\"H\", [0]), (\"RZ\", [0], constraint_angle), (\"H\", [0])])\n",
"\n",
"# Group 2: remove PH gate\n",
"group_2 = compiler.new_group()\n",
"\n",
"group_2.pattern_to_remove([(\"PH\", [0], theta)])\n",
"group_2.add_pattern([(\"RZ\", [0], theta)])\n",
"\n",
"# Group 3: remove CNOT\n",
"group_3 = compiler.new_group()\n",
"\n",
"group_3.pattern_to_remove([(\"CNOT\", [0, 1])])\n",
"group_3.add_pattern([(\"H\", [1]), (\"CSIGN\", [0, 1]), (\"H\", [1])])\n",
"\n",
"# Group 4: remove H\n",
"group_4 = compiler.new_group()\n",
"\n",
"group_4.pattern_to_remove([(\"H\", [0])])\n",
"group_4.add_pattern([(\"RZ\", [0], pi/2), (\"RX\", [0], pi/2), (\"RZ\", [0], pi/2)])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The object `compiler` can be used to compile our circuit. Moreover, this object is also a plugin, it can be linked to any QPU.\n",
"\n",
"## Checking compilation\n",
"First, a function which prints the gate set will be used to check the compilation output:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from qat.core.util import extract_syntax\n",
"\n",
"def print_gate_set(circuit):\n",
" gate_set = set()\n",
" \n",
" for operator in circuit.ops:\n",
" name, params = extract_syntax(\n",
" circuit.gateDic[operator.gate],\n",
" circuit.gateDic\n",
" )\n",
" gate_set.add((name, *params))\n",
" \n",
" print(gate_set)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Then, our compiler can compile our circuit using:\n",
" - in the first example, RX gates with accepted angles\n",
" - in the second example, RX gates with non-accepted angles"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"scrolled": false
},
"outputs": [],
"source": [
"# Case 1: using RX gates with accepted angles\n",
"first_circ = compiler.replace_pattern(\n",
" final_circ.bind_variables({r\"\\alpha\": pi/4, r\"\\beta\": pi})\n",
")\n",
"\n",
"print(\"\\nCase 1 with compliant RX\")\n",
"print_gate_set(first_circ)\n",
"\n",
"# Case 2: using RX gates with non accepted angles\n",
"second_circ = compiler.replace_pattern(\n",
" final_circ.bind_variables({r\"\\alpha\": pi/4, r\"\\beta\": pi/6})\n",
")\n",
"\n",
"print(\"\\nCase 2 with non-compliant RX\")\n",
"print_gate_set(second_circ)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"authors": [
"Arnaud Gazda"
],
"documentation-tags": {
"icon": "git-compare"
},
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"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.12.3"
},
"qlmaas": false,
"tags": [
"pattern"
]
},
"nbformat": 4,
"nbformat_minor": 2
}