{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Basics of Hafnians and Loop Hafnians\n",
"*Author: Nicolás Quesada*"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In the [background section](../hafnian.html) of the The Walrus documentation, some basic ideas related to (loop) hafnians were introduced. This tutorial is a computational exploration of the same ideas."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from thewalrus.reference import hafnian as haf_ref\n",
"from thewalrus import hafnian\n",
"import numpy as np\n",
"import matplotlib.pyplot as plt\n",
"%config InlineBackend.figure_formats=['svg']"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## A simple loopless graph and the hafnian\n",
"\n",
"\n",
"Let's consider the following graph\n",
"\n",
"\n",
"\n",
"with adjacency matrix"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"A = np.array([[0,0,0,1,0,0],\n",
" [0,0,0,1,1,0],\n",
" [0,0,0,1,1,1],\n",
" [1,1,1,0,0,0],\n",
" [0,1,1,0,0,0],\n",
" [0,0,1,0,0,0]])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It is easy to verify by inspection that the graph in Fig. 1 has only one perfect matching given by the edges (1,4)(2,5)(3,6).\n",
"We can verify this by calculating the hafnian of the adjacency matrix $A$"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"haf_ref(A) # Using the reference implementation"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hafnian(A) # Using the default recursive method"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's see what happens if we rescale the adjacency matrix by a scalar $a$. We'll use the [SymPy](https://sympy.org) library for symbolic manipulation:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"from sympy import symbols"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"a**3"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a = symbols(\"a\")\n",
"haf_ref(a*A)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The example above shows that one can use the reference implementation not only with numpy arrays but also with symbolic sympy expressions."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## A graph with loops and the loop hafnian\n",
"\n",
"\n",
"Now let's consider a graph with loops:\n",
"\n",
"\n",
"\n",
"\n",
"The adjacency matrix is now"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"At = np.array([[1,0,0,1,0,0],\n",
" [0,0,0,1,1,0],\n",
" [0,0,0,1,1,1],\n",
" [1,1,1,0,0,0],\n",
" [0,1,1,0,1,0],\n",
" [0,0,1,0,0,0]])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that now the adjacency matrix has non zero elements in the diagonal.\n",
"It is also strightforward to see that the graph in Fig. 2 has two perfect matchings, namely, (1,4)(2,5)(3,6) and (1,1)(5,5)(2,4)(3,6)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"haf_ref(At, loop=True) # Using the reference implementation"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2.0000000000000107"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hafnian(At, loop=True) # Using the default recursive method"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can also use the loop hafnian to count the number of matching (perfect or otherwise)\n",
"by taking the adjacency matrix of the loop less graph, putting ones on its diagonal and calculating the loop hafnian of the resulting matrix. For the graph in Fig. 1 we find"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"15"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"haf_ref(A+np.diag([1,1,1,1,1,1]), loop=True)"
]
}
],
"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.8.5"
}
},
"nbformat": 4,
"nbformat_minor": 2
}