search

XanaduAI / thewalrus

A library for the calculation of hafnians, Hermite polynomials and Gaussian boson sampling.
https://the-walrus.readthedocs.io
Apache License 2.0
101 stars 55 forks source link

Sparse loop hafnian #245

Closed ziofil closed 3 years ago

ziofil commented 3 years ago

Context: Loop hafnian computation does not exploit sparsity

Description of the Change: Loop hafnian computation now handles sparse matrices

Benefits: Fast computation of sparse matrices (few ms for 1000x1000 matrix with ~1000 non-zero entries)

Possible Drawbacks: Slower than default loop hafnian on matrices with fill factor above ~50%

Related GitHub Issues: None

codecov[bot] commented 3 years ago

Codecov Report

Merging #245 (3f6fb5c) into master (2624d91) will not change coverage. The diff coverage is 100.00%.

@@            Coverage Diff            @@
##            master      #245   +/-   ##
=========================================
  Coverage   100.00%   100.00%           
=========================================
  Files           21        21           
  Lines         1293      1315   +22     
=========================================
+ Hits          1293      1315   +22
Impacted Files Coverage Δ
thewalrus/__init__.py 100.00% <ø> (ø)
thewalrus/_hafnian.py 100.00% <100.00%> (ø)

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 2624d91...3f6fb5c. Read the comment docs.

nquesada commented 3 years ago

@ziofil : you will also need to update the CHANGELOG file.

josh146 commented 3 years ago

@ziofil @nquesada for some reason readthedocs won't let me double check, but is the new sparse_hafnian function appearing in the documentation, specifically the list of Hafnian algorithms?

nquesada commented 3 years ago

Thanks for catching this @josh146 ! You are right we need to update the algorithms docs to include this PR and also the previous one by Tim for banded matrices.