Python library¶
This is the top level module of the The Walrus Python interface, containing functions for computing the hafnian, loop hafnian, and torontonian of matrices.
Algorithm terminology¶
 Eigenvalue hafnian algorithm
The algorithm described in A faster hafnian formula for complex matrices and its benchmarking on a supercomputer, [4]. This algorithm scales like \(\mathcal{O}(n^3 2^{n/2})\), and supports calculation of the loop hafnian.
 Recursive hafnian algorithm
The algorithm described in Counting perfect matchings as fast as Ryser [9]. This algorithm scales like \(\mathcal{O}(n^4 2^{n/2})\). This algorithm does not currently support the loop hafnian.
 Repeated hafnian algorithm
The algorithm described in From moments of sum to moments of product, [6]. This method is more efficient for matrices with repeated rows and columns, and supports calculation of the loop hafnian.
 Approximate hafnian algorithm
The algorithm described in Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor, [17]. This algorithm allows us to efficiently approximate the hafnian of matrices with nonnegative elements. This is done by sampling determinants; the larger the number of samples taken, the higher the accuracy.
 Batched hafnian algorithm
An algorithm that allows the calculation of hafnians of all reductions of a given matrix up to the cutoff (resolution) provided. Internally, this algorithm makes use of the multidimensional Hermite polynomials as per The calculation of multidimensional Hermite polynomials and GramCharlier coefficients [24].
 Lowrank hafnian algorithm
An algorithm that allows to calculate the hafnian of an \(r\)rank matrix \(\bm{A}\) of size \(n \times n\) by factorizing it as \(\bm{A} = \bm{G} \bm{G}^T\) where \(\bm{G}\) is of size \(n \times r\). The algorithm is described in Appendix C of A faster hafnian formula for complex matrices and its benchmarking on a supercomputer, [4].
 Banded hafnian algorithm
An algorithm that calculates the hafnian of a matrix \(\bm{A}\) of size \(n \times n\) with bandwidth \(w\) by calculating and storing certain subhafnians dictated by the bandwidth. The algorithm is described in Section V of Efficient sampling from shallow Gaussian quantumoptical circuits with local interactions, [22].
 Sparse hafnian algorithm
An algorithm that calculates the hafnian of a sparse matrix by taking advantage of the Laplace expansion and memoization, to store only the relevant paths that contribute nonzero values to the final calculation.
Python wrappers¶

Returns the hafnian of a matrix. 

Returns the hafnian of matrix with repeated rows/columns. 

Calculates the hafnian of 

Returns the Torontonian of a matrix. 

Returns the permanent of a matrix via the Ryser formula. 

Calculates the permanent of matrix \(A\), where the ith row/column of \(A\) is repeated \(rpt_i\) times. 

Returns the multidimensional Hermite polynomials \(H_k^{(R)}(y)\). 

Returns the loop hafnian of a banded matrix. 
Pure Python functions¶

Calculates the reduction of an array by a vector of indices. 

Get version number of The Walrus 

Returns the hafnian of the low rank matrix \(\bm{A} = \bm{G} \bm{G}^T\) where \(\bm{G}\) is rectangular of size \(n \times r\) with \(r \leq n\). 

hafnian
(A, loop=False, recursive=True, rtol=1e05, atol=1e08, quad=True, approx=False, num_samples=1000)[source]¶ Returns the hafnian of a matrix.
For more direct control, you may wish to call
haf_real()
,haf_complex()
, orhaf_int()
directly. Parameters
A (array) – a square, symmetric array of even dimensions.
loop (bool) – If
True
, the loop hafnian is returned. Default isFalse
.recursive (bool) – If
True
, the recursive algorithm is used. Note: the recursive algorithm does not currently support the loop hafnian. Ifloop=True
, then this keyword argument is ignored.rtol (float) – the relative tolerance parameter used in
np.allclose
.atol (float) – the absolute tolerance parameter used in
np.allclose
.quad (bool) – If
True
, the hafnian algorithm is performed with quadruple precision.approx (bool) – If
True
, an approximation algorithm is used to estimate the hafnian. Note that the approximation algorithm can only be applied to matricesA
that only have nonnegative entries.num_samples (int) – If
approx=True
, the approximation algorithm performsnum_samples
iterations for estimation of the hafnian of the nonnegative matrixA
.
 Returns
the hafnian of matrix A.
 Return type
np.int64 or np.float64 or np.complex128

hafnian_banded
(A, loop=False, rtol=1e05, atol=1e08)[source]¶ Returns the loop hafnian of a banded matrix.
For the derivation see Section V of ‘Efficient sampling from shallow Gaussian quantumoptical circuits with local interactions’, Qi et al..
 Parameters
A (array) – a square, symmetric array of even dimensions.
 Returns
the loop hafnian of matrix
A
. Return type
np.int64 or np.float64 or np.complex128

hafnian_batched
(A, cutoff, mu=None, rtol=1e05, atol=1e08, renorm=False, make_tensor=True)[source]¶ Calculates the hafnian of
reduction(A, k)
for all possible values of vectork
below the specified cutoff.Here,
\(A\) is am \(n\times n\) square matrix
\(k\) is a vector of (nonnegative) integers with the same dimensions as \(A\), i.e., \(k = (k_0,k_1,\ldots,k_{n1})\), and where \(0 \leq k_j < \texttt{cutoff}\).
The function
hafnian_repeated()
can be used to calculate the reduced hafnian for a specific value of \(k\); see the documentation for more information.Note
If
mu
is notNone
, this function instead returnshafnian(np.fill_diagonal(reduction(A, k), reduction(mu, k)), loop=True)
. This calculation can only be performed if the matrix \(A\) is invertible. Parameters
A (array) – a square, symmetric \(N\times N\) array.
cutoff (int) – maximum size of the subindices in the Hermite polynomial
mu (array) – a vector of length \(N\) representing the vector of means/displacement
renorm (bool) – If
True
, the returned hafnians are normalized, that is, \(haf(reduction(A, k))/\ \sqrt{prod_i k_i!}\) (or \(lhaf(fill\_diagonal(reduction(A, k),reduction(mu, k)))\) ifmu
is not None)make_tensor – If
False
, returns a flattened one dimensional array instead of a tensor with the values of the hafnians.rtol (float) – the relative tolerance parameter used in
np.allclose
.atol (float) – the absolute tolerance parameter used in
np.allclose
.
 Returns
the values of the hafnians for each value of \(k\) up to the cutoff
 Return type
(array)

hafnian_repeated
(A, rpt, mu=None, loop=False, rtol=1e05, atol=1e08)[source]¶ Returns the hafnian of matrix with repeated rows/columns.
The
reduction()
function may be used to show the resulting matrix with repeated rows and columns as perrpt
.As a result, the following are identical:
>>> hafnian_repeated(A, rpt) >>> hafnian(reduction(A, rpt))
However, using
hafnian_repeated
in the case where there are a large number of repeated rows and columns (\(\sum_{i}rpt_i \gg N\)) can be significantly faster.Note
If \(rpt=(1, 1, \dots, 1)\), then
>>> hafnian_repeated(A, rpt) == hafnian(A)
For more direct control, you may wish to call
haf_rpt_real()
orhaf_rpt_complex()
directly. Parameters
A (array) – a square, symmetric \(N\times N\) array.
rpt (Sequence) – a length\(N\) positive integer sequence, corresponding to the number of times each row/column of matrix \(A\) is repeated.
mu (array) – a vector of length \(N\) representing the vector of means/displacement. If not provided,
mu
is set to the diagonal of matrixA
. Note that this only affects the loop hafnian.loop (bool) – If
True
, the loop hafnian is returned. Default isFalse
.rtol (float) – the relative tolerance parameter used in
np.allclose
.atol (float) – the absolute tolerance parameter used in
np.allclose
.
 Returns
the hafnian of matrix A.
 Return type
np.int64 or np.float64 or np.complex128

hafnian_sparse
(A, D=None, loop=False)[source]¶ Returns the hafnian of a sparse symmetric matrix.
This pure python implementation is very slow on full matrices, but faster the sparser a matrix is. As a rule of thumb, the crossover in runtime with respect to
hafnian()
happens around 50% sparsity. Parameters
A (array) – the symmetric matrix of which we want to compute the hafnian
D (set) – set of indices that identify a submatrix. If
None
(default) it computes the hafnian of the whole matrix.loop (bool) – If
True
, the loop hafnian is returned. Default isFalse
.
 Returns
(float) hafnian of
A
or of the submatrix ofA
defined by the set of indicesD
.

hermite_multidimensional
(R, cutoff, y=None, renorm=False, make_tensor=True, modified=False, rtol=1e05, atol=1e08)[source]¶ Returns the multidimensional Hermite polynomials \(H_k^{(R)}(y)\).
Here \(R\) is an \(n \times n\) square matrix, and \(y\) is an \(n\) dimensional vector. The polynomials are parametrized by the multiindex \(k=(k_0,k_1,\ldots,k_{n1})\), and are calculated for all values \(0 \leq k_j < \text{cutoff}\), thus a tensor of dimensions \(\text{cutoff}^n\) is returned.
This tensor can either be flattened into a vector or returned as an actual tensor with \(n\) indices.
Note
Note that if \(R = (1)\) then \(H_k^{(R)}(y)\) are precisely the well known probabilists’ Hermite polynomials \(He_k(y)\), and if \(R = (2)\) then \(H_k^{(R)}(y)\) are precisely the well known physicists’ Hermite polynomials \(H_k(y)\).
 Parameters
R (array) – square matrix parametrizing the Hermite polynomial family
cutoff (int) – maximum size of the subindices in the Hermite polynomial
y (array) – vector argument of the Hermite polynomial
renorm (bool) – If
True
, normalizes the returned multidimensional Hermite polynomials such that \(H_k^{(R)}(y)/\prod_i k_i!\)make_tensor (bool) – If
False
, returns a flattened one dimensional array containing the values of the polynomialmodified (bool) – whether to return the modified multidimensional Hermite polynomials or the standard ones
rtol (float) – the relative tolerance parameter used in
np.allclose
atol (float) – the absolute tolerance parameter used in
np.allclose
 Returns
the multidimensional Hermite polynomials
 Return type
(array)

perm
(A, quad=True, fsum=False)[source]¶ Returns the permanent of a matrix via the Ryser formula.
For more direct control, you may wish to call
perm_real()
orperm_complex()
directly. Parameters
A (array) – a square array.
quad (bool) – If
True
, the input matrix is cast to along double
matrix internally for a quadruple precision hafnian computation.fsum (bool) – Whether to use the
fsum
method for higher accuracy summation. Note that iffsum
is true, double precision will be used, and thequad
keyword argument will be ignored.
 Returns
the permanent of matrix A.
 Return type
np.float64 or np.complex128

permanent_repeated
(A, rpt)[source]¶ Calculates the permanent of matrix \(A\), where the ith row/column of \(A\) is repeated \(rpt_i\) times.
This function constructs the matrix
\[\begin{split}B = \begin{bmatrix} 0 & A\\ A^T & 0 \end{bmatrix},\end{split}\]and then calculates \(perm(A)=haf(B)\), by calling
>>> hafnian_repeated(B, rpt*2, loop=False)
 Parameters
A (array) – matrix of size [N, N]
rpt (Sequence) – sequence of N positive integers indicating the corresponding rows/columns of A to be repeated.
 Returns
the permanent of matrix A.
 Return type
np.int64 or np.float64 or np.complex128

reduction
(A, rpt)[source]¶ Calculates the reduction of an array by a vector of indices.
This is equivalent to repeating the ith row/column of \(A\), \(rpt_i\) times.
 Parameters
A (array) – matrix of size [N, N]
rpt (Sequence) – sequence of N positive integers indicating the corresponding rows/columns of A to be repeated.
 Returns
the reduction of A by the index vector rpt
 Return type
array
Contents
Downloads