Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Efficient computation of permanents, with applications to Boson sampling and random matrices
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
2022 (Engelska)Ingår i: Journal of Computational Physics, ISSN 0021-9991, E-ISSN 1090-2716, Vol. 455, artikel-id 110990Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
Academia Press, 2022. Vol. 455, artikel-id 110990
Nyckelord [en]
Boson sampling, Linear optics, Permanent
Nationell ämneskategori
Datavetenskap (datalogi) Sannolikhetsteori och statistik
Identifikatorer
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
Forskningsfinansiär
Vetenskapsrådet, 2014-4897Swedish National Infrastructure for Computing (SNIC)Tillgänglig från: 2022-02-24 Skapad: 2022-02-24 Senast uppdaterad: 2023-09-05Bibliografiskt granskad

Open Access i DiVA

fulltext(750 kB)382 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 750 kBChecksumma SHA-512
314c45a82901470f3f0b17ea2655bb481d9eee83277a1e4ee895510265efab454e30d27b5142fc3575a7804e721e2a9a04670d6506d64159155c6b2c7b0063b8
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Person

Lundow, Per-HåkanMarkström, Klas

Sök vidare i DiVA

Av författaren/redaktören
Lundow, Per-HåkanMarkström, Klas
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
Journal of Computational Physics
Datavetenskap (datalogi)Sannolikhetsteori och statistik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 382 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 263 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf