  We consider the computation of the permanent of a binary n by n matrix. It is
well- known that the exact computation is a #P complete problem. A variety of
Markov chain Monte Carlo (MCMC) computational algorithms have been introduced
in the literature whose cost, in order to achieve a given level of accuracy, is
O(n^7 log^4(n)). These algorithms use a particular collection of probability
distributions, the `ideal' of which, (in some sense) are not known and need to
be approximated. In this paper we propose an adaptive sequential Monte Carlo
(SMC) algorithm that can both estimate the permanent and the ideal sequence of
probabilities on the fly, with little user input. We provide theoretical
results associated to the SMC estimate of the permanent, establishing its
convergence and analyzing the relative variance of the estimate, in particular
computating explicit bounds on the relative variance which depend upon n. Using
this latter result, we provide a lower-bound on the computational cost, in
order to achieve an arbitrarily small relative variance; we find that this cost
is O(n^4 log^4(n)). Some numerical simulations are also given.
