Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Efficient computation of permanents, with applications to Boson sampling and random matrices
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2022 (English)In: Journal of Computational Physics, ISSN 0021-9991, E-ISSN 1090-2716, Vol. 455, article id 110990Article in journal (Refereed) Published
Abstract [en]

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. Next we perform a simulation study of several conjectures regarding the distribution of the permanent for random matrices. Here we focus on permanent anti-concentration conjecture, which has been used to find the classical computational complexity of Boson sampling. We find a good agreement with the basic versions of these conjectures, and based on our data we propose refined versions of some of them. For small systems we also find noticeable deviations from a proposed strengthening of a bound for the number of photons in a Boson sampling system.

Place, publisher, year, edition, pages
Academia Press, 2022. Vol. 455, article id 110990
Keywords [en]
Boson sampling, Linear optics, Permanent
National Category
Computer Sciences Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:umu:diva-192500DOI: 10.1016/j.jcp.2022.110990ISI: 000762463300004Scopus ID: 2-s2.0-85124124557OAI: oai:DiVA.org:umu-192500DiVA, id: diva2:1640481
Funder
Swedish Research Council, 2014-4897Swedish National Infrastructure for Computing (SNIC)Available from: 2022-02-24 Created: 2022-02-24 Last updated: 2023-09-05Bibliographically approved

Open Access in DiVA

fulltext(750 kB)440 downloads
File information
File name FULLTEXT01.pdfFile size 750 kBChecksum SHA-512
314c45a82901470f3f0b17ea2655bb481d9eee83277a1e4ee895510265efab454e30d27b5142fc3575a7804e721e2a9a04670d6506d64159155c6b2c7b0063b8
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Lundow, Per-HåkanMarkström, Klas

Search in DiVA

By author/editor
Lundow, Per-HåkanMarkström, Klas
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Journal of Computational Physics
Computer SciencesProbability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar
Total: 440 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 277 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf