Efficient computation of permanents, with applications to boson sampling and random matrices

Understand

In order to find the outcome probabilities of quantum mechanical systems like the optical networks underlying Boson sampling, it is necessary to be able to compute the permanents of unitary matrices, a computationally hard task.

• Here we first discuss how to compute the permanent efficiently on a parallel computer, followed by algorithms which provide an exponential speed-up for sparse matrices and linear run times for matrices of limited bandwidth.
• The parallel algorithm has been implemented in a freely available software package, also available in an efficient serial version.
• As part of the timing runs for this package we set a new world record for the matrix order on which a permanent has been computed.