\n

\nTherefore, in this particular example:\n\n- Wire 0: we are measuring both terms in the $X$ basis, apply the\n Hadamard gate\n- Wire 1: we are measuring both terms in the $Y$ basis, apply a\n $RX(\\pi/2)$ gate\n- Wire 2: we are measuring both terms in the $Z$ basis (the\n computational basis), no gate needs to be applied.\n\nLet's use PennyLane to verify this.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"obs = [\n qml.PauliX(0) @ qml.PauliY(1),\n qml.PauliX(0) @ qml.PauliZ(2)\n]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"First, let's naively use two separate circuit evaluations to measure the\ntwo QWC terms.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"dev = qml.device(\"default.qubit\", wires=3)\n\n@qml.qnode(dev)\ndef circuit1(weights):\n qml.templates.StronglyEntanglingLayers(weights, wires=range(3))\n return qml.expval(obs[0])\n\n\n@qml.qnode(dev)\ndef circuit2(weights):\n qml.templates.StronglyEntanglingLayers(weights, wires=range(3))\n return qml.expval(obs[1])\n\n\nweights = qml.init.strong_ent_layers_normal(n_layers=3, n_wires=3)\n\nprint(\"Expectation value of XYI = \", circuit1(weights))\nprint(\"Expectation value of XIZ = \", circuit2(weights))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, let's use our QWC approach to reduce this down to a *single*\nmeasurement of the probabilities in the shared eigenbasis of both QWC\nobservables:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"@qml.qnode(dev)\ndef circuit_qwc(weights):\n qml.templates.StronglyEntanglingLayers(weights, wires=range(3))\n\n # rotate wire 0 into the shared eigenbasis\n qml.RY(-np.pi / 2, wires=0)\n\n # rotate wire 1 into the shared eigenbasis\n qml.RX(np.pi / 2, wires=1)\n\n # wire 2 does not require a rotation\n\n # measure probabilities in the computational basis\n return qml.probs(wires=range(3))\n\n\nrotated_probs = circuit_qwc(weights)\nprint(rotated_probs)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We're not quite there yet; we have only calculated the probabilities of\nthe variational circuit rotated into the shared eigenbasis---the\n$|\\langle \\phi_n |\\psi\\rangle|^2$. To recover the *expectation values*\nof the two QWC observables from the probabilities, recall that we need\none final piece of information: their eigenvalues $\\lambda_{A, n}$ and\n$\\lambda_{B, n}$.\n\nWe know that the single-qubit Pauli operators each have eigenvalues\n$(1, -1)$, while the identity operator has eigenvalues $(1, 1)$. We can\nmake use of `np.kron` to quickly generate the eigenvalues of the full\nPauli terms, making sure that the order of the eigenvalues in the\nKronecker product corresponds to the tensor product.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"eigenvalues_XYI = np.kron(np.kron([1, -1], [1, -1]), [1, 1])\neigenvalues_XIZ = np.kron(np.kron([1, -1], [1, 1]), [1, -1])\n\n# Taking the linear combination of the eigenvalues and the probabilities\nprint(\"Expectation value of XYI = \", np.dot(eigenvalues_XYI, rotated_probs))\nprint(\"Expectation value of XIZ = \", np.dot(eigenvalues_XIZ, rotated_probs))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Compare this to the result when we used two circuit evaluations. We have\nsuccessfully used a single circuit evaluation to recover both\nexpectation values!\n\nLuckily, PennyLane automatically performs this QWC grouping under the\nhood. We simply return the two QWC Pauli terms from the QNode:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"@qml.qnode(dev)\ndef circuit(weights):\n qml.templates.StronglyEntanglingLayers(weights, wires=range(3))\n return [\n qml.expval(qml.PauliX(0) @ qml.PauliY(1)),\n qml.expval(qml.PauliX(0) @ qml.PauliZ(2))\n ]\n\n\nprint(circuit(weights))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Behind the scenes, PennyLane is making use of our built-in\nqml.grouping <pennylane.grouping> module, which contains functions\nfor diagonalizing QWC terms:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"rotations, new_obs = qml.grouping.diagonalize_qwc_pauli_words(obs)\n\nprint(rotations)\nprint(new_obs)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here, the first line corresponds to the basis rotations that were\ndiscussed above, written in terms of `RX` and `RY` rotations. Check out\nthe qml.grouping <pennylane.grouping> documentation for more\ndetails on its provided functionality and how it works.\n\nWhat happens, though, if we (in a moment of reckless abandon!) ask a\nQNode to simultaneously measure two observables that *aren't* qubit-wise\ncommuting? For example, let's consider $X\\otimes Y$ and $Z\\otimes Z$:\n\n``` {.sourceCode .python}\n@qml.qnode(dev)\ndef circuit(weights):\n qml.templates.StronglyEntanglingLayers(weights, wires=range(3))\n return [\n qml.expval(qml.PauliZ(0) @ qml.PauliY(1)),\n qml.expval(qml.PauliZ(0) @ qml.PauliZ(1))\n ]\n```\n\nThe QNode has detected that the two observables are not qubit-wise\ncommuting, and has raised an error.\n\nSo, a strategy begins to take shape: given a Hamiltonian containing a\nlarge number of Pauli terms, there is a high likelihood of there being a\nsignificant number of terms that qubit-wise commute. Can we somehow\npartition the terms into **fewest** number of QWC groups to minimize the\nnumber of measurements we need to take?\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Grouping QWC terms\n==================\n\nA nice example is provided in \\[\\#verteletskyi2020\\]\\_ showing how we\nmight tackle this. Say we have the following Hamiltonian defined over\nfour qubits:\n\n$$H = Z_0 + Z_0 Z_1 + Z_0 Z_1 Z_2 + Z_0 Z_1 Z_2 Z_3 + X_2 X_3 + Y_0 X_2 X_3 + Y_0 Y_1 X_2 X_3,$$\n\nwhere we are using the shorthand\n$P_0 P_2 = P\\otimes I \\otimes P \\otimes I$ for brevity. If we go through\nand work out which Pauli terms are qubit-wise commuting, we can\nrepresent this in a neat way using a graph:\n\n![](/demonstrations/measurement_optimize/graph1.png){width=\"70%\"}\n\nIn the above graph, every node represents an individual Pauli term of\nthe Hamiltonian, with edges connecting terms that are qubit-wise\ncommuting. Groups of qubit-wise commuting terms are represented as\n**complete subgraphs**. Straight away, we can make an observation: there\nis no unique solution for partitioning the Hamiltonian into groups of\nqubit-wise commuting terms! In fact, there are several solutions:\n\n![](/demonstrations/measurement_optimize/graph2.png){width=\"90%\"}\n\nOf course, of the potential solutions above, there is one that is more\noptimal than the others ---on the bottom left, we have partitioned the\ngraph into *two* complete subgraphs, as opposed to the other solutions\nthat require three complete subgraphs. If we were to go with this\nsolution, we would be able to measure the expectation value of the\nHamiltonian using two circuit evaluations.\n\nThis problem---finding the minimum number of complete subgraphs of a\ngraph---is actually quite well known in graph theory, where it is\nreferred to as the [minimum clique cover\nproblem](https://en.wikipedia.org/wiki/Clique_cover) (with 'clique'\nbeing another term for a complete subgraph).\n\nUnfortunately, that's where our good fortune ends---the minimum clique\ncover problem is known to be\n[NP-hard](https://en.wikipedia.org/wiki/NP-hardness), meaning there is\nno known (classical) solution to finding the optimum/minimum clique\ncover in polynomial time.\n\nThankfully, there is a silver lining: we know of polynomial-time\nalgorithms for finding *approximate* solutions to the minimum clique\ncover problem. These heuristic approaches, while not guaranteed to find\nthe optimum solution, scale quadratically with the number of nodes in\nthe graph/terms in the Hamiltonian \\[\\#yen2020\\]\\_, so work reasonably\nwell in practice.\n\nMany of these heuristic approaches have roots in another graph problem\nknown as [graph\ncolouring](https://en.wikipedia.org/wiki/Graph_coloring); the assignment\nof colours to the graph's vertices such that no adjacent vertices have\nthe same colour. How is this related to the minimum clique cover\nproblem, though? If we take our QWC graph above, and generate the\n[complement graph](https://en.wikipedia.org/wiki/Complement_graph) by\ndrawing edges between all *non*-adjacent nodes,\n\n![](/demonstrations/measurement_optimize/graph3.png){width=\"100%\"}\n\nwe see that solving the minimum clique cover problem on the QWC graph is\nequivalent to solving the graph colouring problem on the complement\ngraph using the minimum possible number of colours. While there are\nvarious different heuristic algorithms, a common one is [greedy\ncolouring](https://en.wikipedia.org/wiki/Graph_coloring#Greedy_coloring);\nin fact, the open-source graph package [NetworkX even provides a\nfunction for greedy\ncolouring](https://networkx.org/documentation/stable//reference/algorithms/generated/networkx.algorithms.coloring.greedy_color.html#networkx.algorithms.coloring.greedy_color),\n`nx.greedy_color`.\n\nLet's give this a go, using NetworkX to solve the minimum clique problem\nfor observable grouping. First, we'll need to generate the QWC graph\n(with each node corresponding to a Hamiltonian term, and edges\nindicating two terms that are QWC).\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import networkx as nx\nfrom matplotlib import pyplot as plt\n\nterms = [\n qml.PauliZ(0),\n qml.PauliZ(0) @ qml.PauliZ(1),\n qml.PauliZ(0) @ qml.PauliZ(1) @ qml.PauliZ(2),\n qml.PauliZ(0) @ qml.PauliZ(1) @ qml.PauliZ(2) @ qml.PauliZ(3),\n qml.PauliX(2) @ qml.PauliX(3),\n qml.PauliY(0) @ qml.PauliX(2) @ qml.PauliX(3),\n qml.PauliY(0) @ qml.PauliY(1) @ qml.PauliX(2) @ qml.PauliX(3)\n]\n\nG = nx.Graph()\n\n# add the terms to the graph\nG.add_nodes_from(terms)\n\n# add QWC edges\nG.add_edges_from([\n [terms[0], terms[1]], # Z0 <--> Z0 Z1\n [terms[0], terms[2]], # Z0 <--> Z0 Z1 Z2\n [terms[0], terms[3]], # Z0 <--> Z0 Z1 Z2 Z3\n [terms[1], terms[2]], # Z0 Z1 <--> Z0 Z1 Z2\n [terms[2], terms[3]], # Z0 Z1 Z2 <--> Z0 Z1 Z2 Z3\n [terms[1], terms[3]], # Z0 Z1 <--> Z0 Z1 Z2 Z3\n [terms[0], terms[4]], # Z0 <--> X2 X3\n [terms[1], terms[4]], # Z0 Z1 <--> X2 X3\n [terms[4], terms[5]], # X2 X3 <--> Y0 X2 X3\n [terms[4], terms[6]], # X2 X3 <--> Y0 Y1 X2 X3\n [terms[5], terms[6]], # Y0 X2 X3 <--> Y0 Y1 X2 X3\n])\n\n\ndef format_pauli_word(term):\n \"\"\"Convenience function that nicely formats a PennyLane\n tensor observable as a Pauli word\"\"\"\n if isinstance(term, qml.operation.Tensor):\n return \" \".join([format_pauli_word(t) for t in term.obs])\n\n return f\"{term.name[-1]}{term.wires.tolist()[0]}\"\n\nplt.margins(x=0.1)\nnx.draw(\n G,\n labels={node: format_pauli_word(node) for node in terms},\n with_labels=True,\n node_size=500,\n font_size=8,\n node_color=\"#9eded1\",\n edge_color=\"#c1c1c1\"\n)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can now generate the complement graph (compare this to our handdrawn\nversion above!):\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"C = nx.complement(G)\ncoords = nx.spring_layout(C)\n\nnx.draw(\n C,\n coords,\n labels={node: format_pauli_word(node) for node in terms},\n with_labels=True,\n node_size=500,\n font_size=8,\n node_color=\"#9eded1\",\n edge_color=\"#c1c1c1\"\n)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now that we have the complement graph, we can perform a greedy coloring\nto determine the minimum number of QWC groups:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"groups = nx.coloring.greedy_color(C, strategy=\"largest_first\")\n\n# plot the complement graph with the greedy colouring\nnx.draw(\n C,\n coords,\n labels={node: format_pauli_word(node) for node in terms},\n with_labels=True,\n node_size=500,\n font_size=8,\n node_color=[(\"#9eded1\", \"#aad4f0\")[groups[node]] for node in C],\n edge_color=\"#c1c1c1\"\n)\n\n\nnum_groups = len(set(groups.values()))\nprint(\"Minimum number of QWC groupings found:\", num_groups)\n\n\nfor i in range(num_groups):\n print(f\"\\nGroup {i}:\")\n\n for term, group_id in groups.items():\n if group_id == i:\n print(format_pauli_word(term))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Putting it all together\n=======================\n\nSo, we now have a strategy for minimizing the number of measurements we\nneed to perform for our VQE problem:\n\n1. Determine which terms of the Hamiltonian are qubit-wise commuting,\n and use this to construct a graph representing the QWC relationship.\n2. Construct the complement QWC graph.\n3. Use a graph colouring heuristic algorithm to determine a graph\n colouring for the complement graph with a minimum number of colours.\n Each coloured vertex set corresponds to a qubit-wise commuting group\n of Hamiltonian terms.\n4. Generate and evaluate the circuit ansatz (with additional rotations)\n per QWC grouping, extracting probability distributions.\n5. Finally, post-process the probability distributions with the\n observable eigenvalues to recover the Hamiltonian expectation value.\n\nLuckily, the PennyLane `grouping` module makes this relatively easy.\nLet's walk through the entire process using the provided grouping\nfunctions.\n\nSteps 1-3 (finding and grouping QWC terms in the Hamiltonian) can be\ndone via the\nqml.grouping.group\\_observables <pennylane.grouping.group\\_observables>\nfunction:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"obs_groupings = qml.grouping.group_observables(terms, grouping_type='qwc', method='rlf')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The `grouping_type` argument allows us to choose how the commuting terms\nare determined (more on that later!) whereas `method` determines the\ncolouring heuristic (in this case, `\"rlf\"` refers to Recursive Largest\nFirst, a variant of largest first colouring heuristic).\n\nIf we want to see what the required rotations and measurements are, we\ncan use the\nqml.grouping.diagonalize\\_qwc\\_groupings <pennylane.grouping.diagonalize\\_qwc\\_groupings>\nfunction:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"rotations, measurements = qml.grouping.diagonalize_qwc_groupings(obs_groupings)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"However, this isn't strictly necessary---recall previously that the\nQNode has the capability to *automatically* measure qubit-wise commuting\nobservables!\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"dev = qml.device(\"default.qubit\", wires=4)\n\n@qml.qnode(dev)\ndef circuit(weights, group=None, **kwargs):\n qml.templates.StronglyEntanglingLayers(weights, wires=range(4))\n return [qml.expval(o) for o in group]\n\nweights = qml.init.strong_ent_layers_normal(n_layers=3, n_wires=4)\nresult = [circuit(weights, group=g) for g in obs_groupings]\n\nprint(\"Term expectation values:\")\nfor group, expvals in enumerate(result):\n print(f\"Group {group} expectation values:\", expvals)\n\n# Since all the coefficients of the Hamiltonian are unity,\n# we can simply sum the expectation values.\nprint(\"