Permanent-functions {BosonSampling}

Functions for evaluating matrix permanents

Description

These three functions are used in the classical Boson Sampling problem

Usage

cxPerm(A)
rePerm(B)
cxPermMinors(C)

Arguments

A

a square complex matrix.

B

a square real matrix.

C

a rectangular complex matrix where nrow(C) = ncol(C) + 1.

Details

Permanents are evaluated using Glynn's formula (equivalently that of Nijenhuis and Wilf (1978))

Value

cxPerm(A) returns a complex number: the permanent of the complex matrix A.
rePerm(B) returns a real number: the permanent of the real matrix B.
cxPermMinors(C) returns a complex vector of length ncol(C)+1: the permanents of all ncol(C)-dimensional square matrices constructed by removing individual rows from C.

References

Glynn, D.G. (2010) The permanent of a square matrix. European Journal of Combinatorics, 31(7):1887–1891.
Nijenhuis, A. and Wilf, H. S. (1978). Combinatorial algorithms: for computers and calculators. Academic press.

Examples

  set.seed(7)
  n <- 20
  A <- randomUnitary(n)
  cxPerm(A)
  #
  B <- Re(A)
  rePerm(B)
  #
  C <- A[,-n]
  v <- cxPermMinors(C)
  #
  # Check Laplace expansion by sub-permanents
  c(cxPerm(A),sum(v*A[,n]))