GraphDecoder Info

GraphDecoder.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit import *\n",
    "\n",
    "import networkx as nx\n",
    "import random\n",
    "\n",
    "from qiskit.ignis.verification.topological_codes import RepetitionCode\n",
    "from qiskit.ignis.verification.topological_codes import GraphDecoder\n",
    "from qiskit.ignis.verification.topological_codes import lookuptable_decoding, postselection_decoding"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using Graphs and Pairing Nodes\n",
    "\n",
    "Graph theoretic decoders for qubit codes mostly involve:\n",
    "* Turning the measured syndrome into a graph.\n",
    "* Finding pairs of nodes on that graph.\n",
    "\n",
    "So first let's forget about error correction, and just looking at pairing nodes on graphs.\n",
    "\n",
    "In Python, the easiest way to handle graphs is using `networkx`. We set up an empty graph object as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.Graph()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can label the nodes in multiple different ways (tuples are used in `GraphDecoder`). In this example we'll use integers.\n",
    "\n",
    "Here is how to add nodes to the graph (for some chosen number of nodes `n`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 6\n",
    "nodes = range(n)\n",
    "\n",
    "for node in nodes:\n",
    "    G.add_node(node)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Edges can be added between selected pairs of nodes, or between all pairs of nodes. Here we'll do the latter for simplicity.\n",
    "\n",
    "We can associate a 'weight' with each edge. In `GraphDecoder` these are based on a notion of 'distance' between the nodes. We specifically set the weight as the negative of the distance, for reasons we'll see later.\n",
    "\n",
    "In this example we'll just randomly assigne distances to pairs of nides"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "distance = {}\n",
    "for source in nodes:\n",
    "    for target in nodes:\n",
    "        if source<target:\n",
    "            distance[source,target] = random.random()\n",
    "            G.add_edge(source, target, weight=-distance[source,target])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below you can see an example of how to access information in a graph, specifically for the case of printing out the information that we just put in."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "For edge (0, 1) the weight is -0.4636200563509957\n",
      "For edge (0, 2) the weight is -0.2703687802850956\n",
      "For edge (0, 3) the weight is -0.18912529213997165\n",
      "For edge (0, 4) the weight is -0.20563602093097288\n",
      "For edge (0, 5) the weight is -0.4322998807770213\n",
      "For edge (1, 2) the weight is -0.036081580266390856\n",
      "For edge (1, 3) the weight is -0.5720122803580528\n",
      "For edge (1, 4) the weight is -0.8073928381779355\n",
      "For edge (1, 5) the weight is -0.4018143188135981\n",
      "For edge (2, 3) the weight is -0.5315892772313549\n",
      "For edge (2, 4) the weight is -0.7614403319602776\n",
      "For edge (2, 5) the weight is -0.6432407781368953\n",
      "For edge (3, 4) the weight is -0.8779096843460943\n",
      "For edge (3, 5) the weight is -0.8800502977228088\n",
      "For edge (4, 5) the weight is -0.423829647223823\n"
     ]
    }
   ],
   "source": [
    "for edge in G.edges:\n",
    "    edge_info = G[edge[0]][edge[1]]\n",
    "    print('For edge', edge, 'the weight is',edge_info['weight'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we will look at how to pair nodes.\n",
    "\n",
    "For this we can use the concept of a 'perfect matching': a subset of the edges such that each node is part of one and only one edge. This therefore represents a disjoint pairing. For each matching we can then define the total weight, which is the sum of the weights for all the edges it includes.\n",
    "\n",
    "Using the `max_weight_matching` method from `networkx`, we can easily find a matching with the maximum possible total weight. For a minimum weight matching (which we refer to from now on as MWPM), we can simply negate the weights. This is what is done by `GraphDecoder` in order to find a matching with minimum total distance, and is the reason why we negate the distances here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Minimum weight matching of the graph\n",
      "(4, 5) {'weight': -0.423829647223823}\n",
      "(0, 3) {'weight': -0.18912529213997165}\n",
      "(1, 2) {'weight': -0.036081580266390856}\n"
     ]
    }
   ],
   "source": [
    "matches = nx.max_weight_matching(G, maxcardinality=True)\n",
    "print('\\nMinimum weight matching of the graph')\n",
    "for edge in matches:\n",
    "    edge_info = G[edge[0]][edge[1]]\n",
    "    print(edge, edge_info)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graphs for Repetition Codes\n",
    "\n",
    "Let's look at an example of a repetition code, and the graphs that they generate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = 4\n",
    "T = 2\n",
    "code = RepetitionCode(d,T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "circuits = code.get_circuit_list()\n",
    "job = execute( circuits, Aer.get_backend('qasm_simulator') )\n",
    "raw_results = {}\n",
    "for log in ['0','1']:\n",
    "    raw_results[log] = job.result().get_counts(log)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'0000 000 000': 1024}"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "raw_results['0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "results = code.process_results( raw_results )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'0 0  000 000 000': 1024}"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "results['0']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To understand what information is being conveyed in these strings, see the explanation [here](https://qiskit.org/textbook/ch-quantum-hardware/error-correction-repetition-code.html).\n",
    "\n",
    "The format of these strings are that different types of syndrome elements are separated by a double space, and syndromes of the same type but for different measurement rounds are separated by a single space. Note that this format is slightly different for the final logical readout (on the left) for which a single space separates the two copies of the logical readout (one from each side of the code).\n",
    "\n",
    "Each syndrome element can therefore be specified by a coordinate `(d,s,n)`, where `d` specifices which double space separated block the syndrome element is in, `s` specifies the single space separated block within that, and `n` specifies the position within the resulting bit string. All are numbered from the left.\n",
    "\n",
    "We can turn these strings into graphs by creating a decoder object for our code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "decoder = GraphDecoder(code)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When creating a decoder object, a process is run in which every possible single qubit Pauli error is inserted into the code. This always results in pairs of non-trivial syndrome elements (or changes to the two logical values), which is is used to define edges on a graph `S`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((0, 1, 0), (1, 0, 2))\n",
      "((0, 1, 0), (1, 1, 2))\n",
      "((0, 1, 0), (1, 2, 2))\n",
      "((1, 0, 2), (1, 1, 2))\n",
      "((1, 0, 2), (1, 0, 1))\n",
      "((1, 0, 2), (1, 1, 1))\n",
      "((1, 1, 2), (1, 2, 2))\n",
      "((1, 1, 2), (1, 1, 1))\n",
      "((1, 1, 2), (1, 2, 1))\n",
      "((1, 0, 1), (1, 1, 1))\n",
      "((1, 0, 1), (1, 0, 0))\n",
      "((1, 0, 1), (1, 1, 0))\n",
      "((1, 1, 1), (1, 2, 1))\n",
      "((1, 1, 1), (1, 1, 0))\n",
      "((1, 1, 1), (1, 2, 0))\n",
      "((1, 0, 0), (1, 1, 0))\n",
      "((1, 0, 0), (0, 0, 0))\n",
      "((1, 1, 0), (1, 2, 0))\n",
      "((1, 1, 0), (0, 0, 0))\n",
      "((0, 0, 0), (1, 2, 0))\n",
      "((1, 2, 2), (1, 2, 1))\n",
      "((1, 2, 1), (1, 2, 0))\n"
     ]
    }
   ],
   "source": [
    "for edge in decoder.S.edges:\n",
    "    print(edge)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we have a string such as `'0 0  000 000 011'`, it is an output with a specific set of non-trivial syndrome elements for a specific set of errors. From this we construnct a new graph whose nodes corresoond only to the non-trivial syndrome elements (and possibly changed logical values) in this string. We place edges between all sets of nodes, whose distance is defined as the distance between these nodes in the graph `S`.\n",
    "\n",
    "This is done by the `make_error_graph()` method of the decoder object. Let's try it with the simplest case."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "For edge ((0, 0, 0), (0, 1, 0)) the weight is -4\n"
     ]
    }
   ],
   "source": [
    "graph = decoder.make_error_graph('0 0  000 000 000')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The output here is, in general, a dictionary including various 'subgraphs', on which decoding could be run independently. For the repetition code there is just one 'subgraph', which is called `'0'` (fairly arbitrarily).\n",
    "\n",
    "Here are the edges of this graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for edge in graph['0'].edges:\n",
    "    edge_info = graph['0'][edge[0]][edge[1]]\n",
    "    print('For edge', edge, 'the weight is',edge_info['weight'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The most likely origin of the result `0 0  000 000 000` is that a logical `0` was encoded and no errors occured. The next most likely is that `1` was encoded, and then errors simulataneously flipped all code qubits at some point (leaving no trace in the syndrome measurements. The edge `((0, 0, 0), (0, 1, 0))` with distance `d=4` represents the latter possibility.\n",
    "\n",
    "If we look for a MWPM of this graph, there is one unique solution: the single edge of the graph. However, when the pairing found by the decoding includes logical values, we interpret this as meaning that those logical values are incorrect. This is not the most likely case here, and so just applying MWPM is not advisable.\n",
    "\n",
    "Instead we must account for the fact that the matching we require should not be completely perfect. It should indeed cover all the genuine non-trivial syndrome elements, but the elements corresponding to logical values do not need to be included. This is dealt when we run decoding using the `matching()` method by adding extra 'fictional' nodes for them to match with instead, and setting the weights such that the end result represents the most likely set of errors. See elsewhere for more details on that.\n",
    "\n",
    "Here's another example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "For edge ((0, 0, 0), (0, 1, 0)) the weight is -4\n",
      "For edge ((0, 0, 0), (1, 2, 2)) the weight is -3\n",
      "For edge ((0, 1, 0), (1, 2, 2)) the weight is -1\n"
     ]
    }
   ],
   "source": [
    "graph = decoder.make_error_graph('0 1  000 000 001')\n",
    "\n",
    "for edge in graph['0'].edges:\n",
    "    edge_info = graph['0'][edge[0]][edge[1]]\n",
    "    print('For edge', edge, 'the weight is',edge_info['weight'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we see an error which flips one of the end qubits. It is detected by a syndrome measurement and changes one of the logical values. The lowest distance edge corresponds to this case.\n",
    "\n",
    "Another example.\n",
    "\n",
    "This is a good example on which to actually run the `matching` method. Note that it doesn't give us the list of pairs as output. Instead it looks to see if one of the logical values was paired with any of the non-trivial syndrome elements in the matching. If so, the value is flipped. The corrected logical values are then returned."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "decoder.matching('0 1  000 000 001')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, let's look at another example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "For edge ((0, 0, 0), (0, 1, 0)) the weight is -4\n",
      "For edge ((0, 0, 0), (1, 1, 1)) the weight is -2\n",
      "For edge ((0, 0, 0), (1, 2, 1)) the weight is -2\n",
      "For edge ((0, 1, 0), (1, 1, 1)) the weight is -2\n",
      "For edge ((0, 1, 0), (1, 2, 1)) the weight is -2\n",
      "For edge ((1, 1, 1), (1, 2, 1)) the weight is -1\n"
     ]
    }
   ],
   "source": [
    "graph = decoder.make_error_graph('0 0  000 010 010')\n",
    "\n",
    "for edge in graph['0'].edges:\n",
    "    edge_info = graph['0'][edge[0]][edge[1]]\n",
    "    print('For edge', edge, 'the weight is',edge_info['weight'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we see that one of the syndrome measurements detects something in one round (corresponding to a non-trivial syndrome element) but it is not detected in the next (the change in value making a non-trivial syndrome element). The most likely cause is a single error on the corresponding ancilla."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}