{
  "cells": [
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "%matplotlib inline"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\n\n# Minimizing the pattern space\n\nHere, we demonstrate the effect of :meth:`graphix.pattern.Pattern.minimize_space()`.\nThis method reduces the maximum number of qubits that must be prepared at each step of MBQC operation,\nby delaying the preparation and entanglement of qubits as much as the logical dependency structure allows.\nThis reduces the qubit count (or memory size for classical simulators such as graphix) requirement\nfor any quantum algorithms running on MBQC.\n\nWe will demonstrate this by simulating QFT on three qubits.\nFirst, import relevant modules and define additional gates we'll use:\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import numpy as np\n\nfrom graphix import Circuit\n\n\ndef cp(circuit, theta, control, target):\n    \"\"\"Controlled phase gate, decomposed\"\"\"\n    circuit.rz(control, theta / 2)\n    circuit.rz(target, theta / 2)\n    circuit.cnot(control, target)\n    circuit.rz(target, -1 * theta / 2)\n    circuit.cnot(control, target)\n\n\ndef swap(circuit, a, b):\n    \"\"\"swap gate, decomposed\"\"\"\n    circuit.cnot(a, b)\n    circuit.cnot(b, a)\n    circuit.cnot(a, b)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now let us define a circuit to apply QFT to three-qubit ``|011>`` state (input=6).\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "circuit = Circuit(3)\nfor i in range(3):\n    circuit.h(i)\n\n# prepare ``|011>`` state\ncircuit.x(1)\ncircuit.x(2)\n\n# QFT\ncircuit.h(0)\ncp(circuit, np.pi / 2, 1, 0)\ncp(circuit, np.pi / 4, 2, 0)\ncircuit.h(1)\ncp(circuit, np.pi / 2, 2, 1)\ncircuit.h(2)\nswap(circuit, 0, 2)\n\n# transpile and plot the graph\npattern = circuit.transpile().pattern\npattern.draw_graph(flow_from_pattern=False)\nnodes, _ = pattern.get_graph()\nprint(len(nodes))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "This is a graph with 49 qubits, whose statevector is very hard to simulate in ordinary computers.\nAs such, instead of preparing the graph state at the start of the compuation, we opt to prepare\nqubits as late as possible, so that (destructive) measurements will reduce the burden while we wait.\nFor this, we first standardize and shift signals, to simplify the interdependence of measurements.\nAfter that, we can call :meth:`~graphix.pattern.Pattern.minimize_space()` to perform the optimization.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "pattern.standardize()\npattern.shift_signals()\npattern.print_pattern(lim=20)\nprint(pattern.max_space())"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "now compare with below:\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "pattern.minimize_space()\npattern.print_pattern(lim=20)\nprint(pattern.max_space())"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The maximum space has gone down to 4 which should be very easily simulated on laptops.\nLet us check the answer is correct, by comparing with statevector simulation.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "out_state = pattern.simulate_pattern()\nstate = circuit.simulate_statevector().statevec\nprint(\"overlap of states: \", np.abs(np.dot(state.psi.flatten().conjugate(), out_state.psi.flatten())))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Finally, check the output state:\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "st_expected = [np.exp(2 * np.pi * 1j * 3 * i / 8) / np.sqrt(8) for i in range(8)]\nout_stv = out_state.flatten()\nprint(np.round(st_expected, 3))\nprint(np.round(out_stv * st_expected[0] / out_stv[0], 3))  # global phase is arbitrary"
      ]
    }
  ],
  "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.10.13"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}