Umeå University's logo

umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet 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 (engelsk)Inngår i: Journal of Computational Physics, ISSN 0021-9991, E-ISSN 1090-2716, Vol. 455, artikkel-id 110990Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
Academia Press, 2022. Vol. 455, artikkel-id 110990
Emneord [en]
Boson sampling, Linear optics, Permanent
HSV kategori
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
Swedish Research Council, 2014-4897Swedish National Infrastructure for Computing (SNIC)Tilgjengelig fra: 2022-02-24 Laget: 2022-02-24 Sist oppdatert: 2023-09-05bibliografisk kontrollert

Open Access i DiVA

fulltext(750 kB)435 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 750 kBChecksum SHA-512
314c45a82901470f3f0b17ea2655bb481d9eee83277a1e4ee895510265efab454e30d27b5142fc3575a7804e721e2a9a04670d6506d64159155c6b2c7b0063b8
Type fulltextMimetype application/pdf

Andre lenker

Forlagets fulltekstScopus

Person

Lundow, Per-HåkanMarkström, Klas

Søk i DiVA

Av forfatter/redaktør
Lundow, Per-HåkanMarkström, Klas
Av organisasjonen
I samme tidsskrift
Journal of Computational Physics

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 435 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 276 treff
RefereraExporteraLink to record
Permanent link

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