jupyter_notebooks/Tutorials/12 Germ Selection.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Germ Selection\n",
    "The purpose of this tutorial is to illustrate \"germ selection\".  Germ selection is the process by which a complete set of germ gate sequences is constructed.  The defining property which makes a set of gate sequences a \"complete germ set\" is the amplification of *all* possible gate errors.  More precisely, the repetition of a complete set of germs, sandwiched between preparation and measurement fiducial sequences, will yield a sensitivity to *all* gate errors that scales with the number of times each germ is repeated.  This completeness is relative to the set of gates under consideration, typically a set of desired or \"target\" gates.\n",
    "\n",
    "In this tutorial, we find a complete germ set for the standard $X(\\pi/2)$, $Y(\\pi/2)$, $I$ gate set.\n",
    "\n",
    "Before proceeding, however, we note the following:  This tutorial notebook is slightly different from others.  At present, germ selection is a bit of a \"dark art\".  While we have a simple function (pygsti.algorithms.germselection.test_germ_list_infl) for determining whether or not a germ set is \"amplificationally complete\" (AC), we do not at present have a method for *optimally* selecting such a set (in particular, selecting a set that is as small as possible).  This is in part because the germ list scoring function does a good job of distinguishing between AC and non-AC sets, it does less well distinguishing between sets that are both AC.\n",
    "\n",
    "This notebook demonstrates how to generate an AC germ set, as well as demonstrating the functionality of several auxiliary functions we've developed to assist in the process.  However, it should not be taken as optimal; in particular, one may find better (smaller) AC germ sets by repeatedly running the germ selection function, seeded with an AC germ set plus a collection of further candidate germs, as demonstrated below.\n",
    "\n",
    "For more details on the theory of germ selection, please see arXiv:1605.07674."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from __future__ import print_function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import pygsti\n",
    "from pygsti.construction import std1Q_XYI as std\n",
    "import time\n",
    "%matplotlib inline\n",
    "from matplotlib import pyplot as plt\n",
    "import numpy as _np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#A germ set is AC if and only if there are a number of non-zero eigenvalues (to machine precision) of J^\\dagger J equal\n",
    "#to the number of non-SPAM non-gauge parameters in a gate set, where J is the \"twirled derivative\" of the germ set with\n",
    "#respect to the gate set.\n",
    "\n",
    "#The gate set(s) we wish to test should have random unitary noise added to it, in order to break any accidental degeneracies.\n",
    "#Additionally, even though experimental gate sets will have stochastic error,\n",
    "#the gate set used for testing MUST have only unitary error, otherwise the selection procedure will fail.\n",
    "#When actually running germ selection, the germ selection function can add random unitary noise; however,\n",
    "#this does not automatically happen when calling test_germ_list_infl to test if a particular germ set is AC for a particular\n",
    "#gate set.  Hence we manually randomize:\n",
    "\n",
    "gs_real = std.gs_target.randomize_with_unitary(.1,seed=0)\n",
    "\n",
    "#Let's see if a couple different germ sets are AC:\n",
    "\n",
    "print(\"Is the standard germ set AC?\", pygsti.algorithms.germselection.test_germ_list_infl(gs_real,std.germs))\n",
    "print(\"Is the germ set {Gx, Gy, Gi} AC?\", pygsti.algorithms.germselection.test_germ_list_infl(gs_real,pygsti.construction.gatestring_list([('Gx',),('Gy',),('Gi',)])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Let's plot the sorted* eigenvalues of AC and non-AC germ sets.\n",
    "#The horizontal line delineates gauge from non-gauge parameters.  We can never be sensitive to gauge parameters,\n",
    "#but to be AC, we must be sensitive to all other parameters.\n",
    "\n",
    "#*Due to numerical stability issues, some of the vanishingly small eigenvalues are negative;\n",
    "#we plot their absolute values here.\n",
    "\n",
    "plt.semilogy(sorted(_np.abs(pygsti.algorithms.germselection.test_germ_list_infl(gs_real,std.germs,returnSpectrum=True)[1])),'o',label='Std. XYI germs')\n",
    "plt.semilogy(sorted(_np.abs(pygsti.algorithms.germselection.test_germ_list_infl(gs_real,pygsti.construction.gatestring_list([('Gx',),('Gy',),('Gi',)]),returnSpectrum=True)[1])),'o',label='{Gx,Gy,Gi}')\n",
    "plt.axvline(pygsti.algorithms.germselection.num_non_spam_gauge_params(gs_real))\n",
    "plt.legend(loc='best')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's now try to actually pick out a gate set.  The germ selection output will strongly depend on several different inputs to the function optimize_integer_germs_slack (argument name given in parenthesis):\n",
    "\n",
    "1.  The gate set(s) to be optimized for.  (gatesetList)\n",
    "2.  How strong the unitary randomization added is. (randomizationStrength; default is 1e-3.  Can be turned off by setting to 0 or by setting randomize=False; this should only be done if the input gate set(s) have already been subjected to some random unitary errors.\n",
    "3.  How many different randomized instances of the input gate set to be tested (numCopies; only to be used if only one gate set is passed in.  The larger this number (or the larger the size of gatesetList), the more robust the output germ list will be in general, but the slower the runtime.\n",
    "4.  How much adding a germ to the germ set \"costs\". (l1Penalty; default is 1e-2.  Increasing this *may* nudge the optimizer towards picking a smaller germ set.)\n",
    "5.  How much making an individual germ longer \"costs\". (gatePenalty; default is 0.  Increasing this *may* nudge the optimizer towards picking a germ set with shorter germs.\n",
    "6.  Whether the entire non-gauge portion of the spectrum to contributes to the germ score, or only the smallest eigenvalue.  (scoreFunc = 'all' or 'worst', respectively.)\n",
    "7.  The relaxation scheme used to reduce the germ list size:\n",
    "\n",
    "    7a.  The absolute score a germ set is allowed to achieve (fixedSlack) OR\n",
    "    \n",
    "    7b.  The relative score a germ set is allowed to achieve (slackFrac)\n",
    "8.  Whether or not the germ set *must* contain each bare gate as a germ (forceSingletons)\n",
    "\n",
    "The output should depend much more weakly (but not necessarily not at all) on the tolerance value (tol) passed to the optimizer.\n",
    "\n",
    "Here we demonstrate particular choices for the above inputs.  However, we make no claims of optimality for these choices.  End users are encouraged to experiment themselves with these inputs.  They are also welcome to email pygsti@sandia.gov; the pyGSTi development team will try to assist."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The germ selection algorithm works by throwing unnecessary germs away from an initial (large) list that is assumed to be complete.  In this example, our initial list includes all gatestrings up to length six that are distinct up to powers and cycles.  Since germ sequences are repeated and sandwiched between fiducial sequences, a germ that is a power of another germ (i.e. the other germ repeated some number of times) or that is a cyclic permutation of another germ is effectively the same as the other germ.  (I.e., if Gx is included as a germ, then GxGx will not be.\n",
    "Similarly, if GxGyGi is included as a germ, then GxiGxGy will not be.)\n",
    "The `list_all_gatestrings_without_powers_and_cycles` function provides a convenient way to list sequences gate sequences that are distinct up to such powers and cycles. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "max_length = 6\n",
    "gates = std.gs_target.gates.keys()\n",
    "\n",
    "testGermList = pygsti.construction.list_all_gatestrings_without_powers_and_cycles(gates,max_length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print(\"testGermList has\", len(testGermList), \"germs in it.\")\n",
    "print(\"testGermList is\", \"not \"*(1-pygsti.algorithms.germselection.test_germ_list_infl(gs_real,testGermList))+\"AC.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "#Can we reduce the number of germs and still be AC?\n",
    "#Let's start with:\n",
    "#All 196 germs (germsList=testGermList, initialWeights=None),\n",
    "#slackFrac=0.1, forceSingletons=True.\n",
    "#Let's also try to score against 5 randomized gate sets (numCopies=5)\n",
    "\n",
    "start = time.time()\n",
    "germList1 = pygsti.algorithms.germselection.optimize_integer_germs_slack(std.gs_target,testGermList,numCopies=5,\n",
    "                                                                         initialWeights=None,slackFrac=0.1,\n",
    "                                                                         forceSingletons=True,\n",
    "                                                                         maxIter=300,\n",
    "                                                                         verbosity=2)\n",
    "end = time.time()\n",
    "print()\n",
    "print(\"Germ selection completed in\", end-start, \"seconds.\")\n",
    "print(\"germList1 is\", \"not \"*(1-pygsti.algorithms.germselection.test_germ_list_infl(gs_real,germList1))+\"AC.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#We have a germ set now!  Let's see what it looks like:\n",
    "for germ in germList1:\n",
    "    print(germ)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "#Can we reduce this set in size and make some of the germs shorter by:\n",
    "#1.  Adding extra random germs of varying lengths\n",
    "#2.  Turning up the gatePenalty parameter\n",
    "#3.  Relaxing slackFrac to 0.25?\n",
    "\n",
    "testGermList1 = germList1 +\\\n",
    "                            pygsti.construction.list_random_gatestrings_onelen(std.gates,2,10,0)+\\\n",
    "                            pygsti.construction.list_random_gatestrings_onelen(std.gates,3,10,0)+\\\n",
    "                            pygsti.construction.list_random_gatestrings_onelen(std.gates,4,10,1)+\\\n",
    "                            pygsti.construction.list_random_gatestrings_onelen(std.gates,5,10,2)\n",
    "\n",
    "testGermList1 = pygsti.listtools.remove_duplicates(testGermList1)\n",
    "\n",
    "start = time.time()\n",
    "germList2 = pygsti.algorithms.germselection.optimize_integer_germs_slack(std.gs_target,testGermList1,numCopies=5,\n",
    "                                                                         initialWeights=None,slackFrac=0.25,\n",
    "                                                                         gatePenalty = 1e0,\n",
    "                                                                         forceSingletons=True,\n",
    "                                                                         maxIter=300,\n",
    "                                                                         verbosity=2)\n",
    "end = time.time()\n",
    "print()\n",
    "print(\"Germ selection completed in\", end-start, \"seconds.\")\n",
    "print(\"germList2 is\", \"not \"*(1-pygsti.algorithms.germselection.test_germ_list_infl(gs_real,germList1))+\"AC.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for germ in germList2:\n",
    "    print(germ)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Success!  Let's see if this germ set is AC for a bunch of random gate sets:\n",
    "\n",
    "num_fails = 0\n",
    "for i in range(100):\n",
    "    if not pygsti.alg.germselection.test_germ_list_infl(std.gs_target.randomize_with_unitary(0.01,i),germList2):\n",
    "        num_fails += 1\n",
    "print('Germ set fails on', num_fails, 'gate sets out of 100.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Success!  We've selected a single-qubit germ set that has only 11 germs and is robust against noise.\n",
    "#Further testing is possible by simulating GST data on a unitarily noisy gate set using these germs, and\n",
    "#examinining whether or not 1/L scaling is achieved.\n",
    "\n",
    "#Also, you can write your newfound germs to file:  \n",
    "#pygsti.io.write_gatestring_list(\"mygerms.lst\",germList2,\"List of germs from tutorial\")"
   ]
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}