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

DOI10.1016/j.jcp.2022.110990OpenAlexW2936569433MaRDI QIDQ2133747

Per Håkan Lundow, Klas Markström

Publication date: 5 May 2022

Published in: Journal of Computational Physics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1904.06229

zbMATH Keywords

permanentlinear opticsboson sampling

Mathematics Subject Classification ID

Theory of computing (68Qxx) Graph theory (05Cxx) Combinatorics (05-XX)

Uses Software

• Mathematica

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How to generate random matrices from the classical compact groups
• The Classical Complexity of Boson Sampling
• The complexity of computing the permanent
• An efficient tree decomposition method for permanents and mixed discriminants
• On the permanent of random Bernoulli matrices
• An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents
• Exact and Approximate Compression of Transfer Matrices for Graph Homomorphisms
• A Note on the Generation of Random Normal Deviates
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Two Algorithmic Results for the Traveling Salesman Problem
• Combinatorial bounds via measure and conquer
• Quantum complexity theory
• The $1$-Vertex Transfer Matrix and Accurate Estimation of Channel Capacity
• Pracniques: simulation of Boolean functions in a decimal computer
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Compression of transfer matrices

This page was built for publication: Efficient computation of permanents, with applications to boson sampling and random matrices