Is it possible to "calculate" the absolute value of a permanent using Boson Sampling?

Question

In boson sampling, if we start with 1 photon in each of the first $M$ modes of an interferometer, the probability of detecting 1 photon in each output mode is: $|\textrm{Perm}(A)|^2$, where the columns and rows of $A$ are the first $M$ columns of the interferometer's unitary matrix $U$, and all of its rows.

This makes it look like for any unitary $U$, we can construct the appropriate interferometer, construct the matrix $A$, and calculate the absolute value of the permanent of $A$ by taking the square root of the probability of detecting one photon in each mode (which we get from the boson sampling experiment). Is this true, or is there some catch? People have told me that you can't actually get information about a permanent from boson sampling.

Also, what happens to the rest of the columns of $U$: How exactly is it that the experimental outcome only depends on the first $M$ columns of $U$ and all of its rows, but not at all on the other columns of $U$? Those columns of $U$ do not affect the outcome of the experiment in the first $M$ modes at all?

Answer 1

It appears to be true, up to a point. As I read Aaronson and Arkhipov's paper, it says that if you start with 1 photon in each of the first $M$ modes of an interferometer, and find the probability $P_S$ that a set $s_i$ photons is output in each mode $i\in\{1,\ldots, N\}$ where $\sum_is_i=M$, is $$ P_s=\frac{|\text{Per(A)}|^2}{s_1!s_2!\ldots s_M!}. $$ So, indeed, if you take a particular instance where $s_i=0$ or 1 for every possible output, then, yes the probability is equal to the permanent of $A$, where $A$ is the first $M$ columns of $U$ and a specific subset of $M$ rows specified by the locations $s_i=1$. So, this is not quite as specified in the question: it is not all rows, but only some subset, so that $A$ is a square matrix, corresponding to the bits that the experiment "sees", i.e. the input rows and output rows. The photons never populate anything else, and so are blind to the other elements of the unitary matrix $U$.

This should be fairly obvious. Let's say I have some $3\times 3$ matrix $V$. If I start in some basis state $|0\rangle$ and find its product, $V|0\rangle$, then knowing that tells me very little about the outputs $V|1\rangle$ and $V|2\rangle$, aside from what can be said from the knowledge that $V$ is unitary, and hence columns and rows are orthonormal.

The issue that one must be careful of is the accuracy: you run this once and all you get is a single sample according to the probability distribution $P_s$. You run this a few times, and you start to build up information about the different probabilities. You run this enough times, and you can get an arbitrarily accurate answer, but how many is enough? There are two different ways that you can measure the error in an estimate of a value $p$. You can demand either an additive error $p\pm\epsilon$ or a multiplicative error, $p(1\pm\epsilon)$. Since we expect that a typical probability will be exponentially small in $n+m$, the multiplicative error demands far greater accuracy, which cannot be achieved efficiently via sampling. On the other hand, the additive error approximation can be achieved.

While a multiplicative error is what people usually want to calculate, the additive error can also be an interesting entity. For example, in the evaluation of the Jones polynomial.

Aaronson points us back further in time for where this connection between Boson sampling and the Permanent was first made:

It has been known since work by Caianiello in 1953 (if not earlier) that the amplitudes for $n$-boson processes can be written as the permanents of $n\times n$ matrices.

Instead, their main contribution

is to prove a connection between the ability of classical computers to solve the approximate BosonSampling problem and their ability to approximate the permanent

i.e. to understand the approximation problem associated with, e.g. finite sampling, and to describe the computational complexity consequences associated: that we believe such a thing is hard to evaluate classically.

Answer 2

You cannot efficiently recover the absolute values of the amplitudes, but if you allow for arbitrary many samples, then you can estimate them to whatever degree of accuracy you like.

More specifically, if the input state is a single photon in each of the first $n$ modes, and one is willing to draw an arbitrary number of samples from the output, then it is in principle possible to estimate the permanent of $A$ to whatever degree of accuracy one likes, by counting the fraction of the times the $n$ input photons come out in the first $n$ different output ports. It is to be noted though that this does not really have much to do with BosonSampling, as the hardness result holds in the regime of the number of modes much larger than the number of photons, and it's about the efficiency of the sampling.

BosonSampling

I'll try a very brief introduction to what boson sampling is, but it should be noted that I cannot possibly do a better job at this than Aaronson himself, so it's probably a good idea to have a look at the related blog posts of his (e.g. blog/?p=473 and blog/?p=1177), and links therein.

BosonSampling is a sampling problem. This can be a little bit confusing in that people are generally more used to think of problems having definite answers. A sampling problem is different in that the solution to the problem is a set of samples drawn from some probability distribution.

Indeed, the problem a boson sampler solves is that of sampling from a specific probability distribution. More specifically, sampling from the probability distribution of the possible outcome (many-boson) states.

Consider as a simple example a case with 2 photons in 4 modes, and let's say we fix the input state to be $(1,1,0,0)\equiv|1,1,0,0\rangle$ (that is, a single photon in each of the two first two input modes). Ignoring the output states with more than one photon in each mode, there are $\binom{4}{2}=6$ possible output two-photon states: $(1,1,0,0), (1,0,1,0), (1,0,0,1), (0,1,1,0), (0,1,0,1)$ and $(0,0,1,1)$. Let us denote for convenience with $o_i, i=1,.,6$ the $i$-th one (so, for example, $o_2=(1,0,1,0)$). Then, a possible solution to BosonSampling could be the series of outcomes: $$o_1, o_4, o_2, o_2, o_5.$$

To make an analogy to a maybe more familiar case, it's like saying that we want to sample from a Gaussian probability distribution. This means that we want to find a sequence of numbers which, if we draw enough of them and put them into a histogram, will produce something close to a Gaussian.

Computing permanents

It turns out that the probability amplitude of a given input state $|\boldsymbol r\rangle$ to a given output state $|\boldsymbol s\rangle$ is (proportional to) the permanent of a suitable matrix built out of the unitary matrix characterizing the (single-boson) evolution.

More specifically, if $\boldsymbol R$ denotes the mode assignment list${}^{(1)}$ associated to $|\boldsymbol r\rangle$, $\boldsymbol S$ that of $|\boldsymbol s\rangle$, and $U$ is the unitary matrix describing the evolution, then the probability amplitude $\mathcal A(\boldsymbol r\to\boldsymbol s)$ of going from $|\boldsymbol r\rangle$ to $|\boldsymbol s\rangle$ is given by $$\mathcal A(\boldsymbol r\to\boldsymbol s) = \frac{1}{\sqrt{\boldsymbol r!\boldsymbol s!}} \operatorname{perm} U[\boldsymbol R|\boldsymbol S], $$ with $U[\boldsymbol R|\boldsymbol S]$ denoting the matrix built by taking from $U$ the rows specified by $\boldsymbol R$ and the columns specified by $\boldsymbol S$.

Thus, considering the fixed input state $|\boldsymbol r_0\rangle$, the probability distribution of the possible outcomes is given by the probabilities $$p_{\boldsymbol s} = \frac{1}{\boldsymbol r_0! \boldsymbol s!} \lvert \operatorname{perm}U[\boldsymbol R|\boldsymbol S] \rvert^2.$$

BosonSampling is the problem of drawing "points" according to this distribution.

This is not the same as computing the probabilities $p_s$, or even computing the permanents themselves. Indeed, computing the permanents of complex matrices is hard, and it is not expected even for quantum computers to be able to do it efficiently.

The gist of the matter is that sampling from a probability distribution is in general easier than computing the distribution itself. While a naive way to sample from a distribution is to compute the probabilities (if not already known) and use those to draw the points, there might be smarter ways to do it. A boson sampler is something that is able to draw points according to a specific probability distribution, even though the probabilities making up the distribution itself are not known (or better said, not efficiently computable).

Furthermore, while it may look like the ability to efficiently sample from a distribution should translate into the ability of efficiently estimating the underlying probabilities, this is not the case as soon as there are exponentially many possible outcomes. This is indeed the case of boson sampling with uniformly random unitaries (that is, the original setting of BosonSampling), in which there are $\binom{m}{n}$ possible $n$-boson in $m$-modes output states (again, neglecting states with more than one boson in some mode). For $m\gg n$, this number increases exponentially with $n$. This means that, in practice, you would need to draw an exponential number of samples to even have a decent chance of seeing a single outcome more than once, let alone estimate with any decent accuracy the probabilities themselves (it is important to note that this is not the core reason for the hardness though, as the exponential number of possible outcomes could be overcome with smarter methods).

In some particular cases, it is possible to efficiently estimate the permanent of matrices using a boson sampling set-up. This will only be feasible if one of the submatrices has a large (i.e. not exponentially small) permanent associated with it, so that the input-output pair associated with it will happen frequently enough for an estimate to be feasible in polynomial time. This is a very atypical situation, and will not arise if you draw unitaries at random. For a trivial example, consider matrices that are very close to identity - the event in which all photons come out in the same modes they came in will correspond to a permanent which can be estimated experimentally. Besides only being feasible for some particular matrices, a careful analysis of the statistical error incurred in evaluating permanents in this way shows that this is not more efficient than known classical algorithms for approximating permanents (technically, within a small additive error) ${}^{(2)}$.

Columns involved

Let $U$ be the unitary describing the one-boson evolution. Then, basically by definition, the output amplitudes describing the evolution of a single photon entering in the $k$-th mode are in the $k$-th column of $U$.

The unitary describing the evolution of the many-boson states, however, is not actually $U$, but a bigger unitary, often denoted by $\varphi_n(U)$, whose elements are computed from permanents of matrices built out of $U$.

Informally speaking though, if the input state has photons in, say, the first $n$ modes, then naturally only the first $n$ columns of $U$ must be necessary (and sufficient) to describe the evolution, as the other columns will describe the evolution of photons entering in modes that we are not actually using.

---

(1) This is just another way to describe a many-boson state. Instead of characterizing the state as the list of occupation numbers for each mode (that is, number of bosons in first mode, number in second, etc.), we characterize the states by naming the mode occupied by each boson. So, for example, the state $(1, 0, 1, 0)$ can be equivalently written as $(1, 3)$, and these are two equivalent ways to say that there is one boson in the first and one boson in the third mode.

(2): S. Aaronson and T. Hance. "Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent". https://eccc.weizmann.ac.il/report/2012/170/

Answer 3

Just a couple of more comments to expand on the already thorough answers.

---

Initially relating to the error associated with the calculation of the permanent, much of the theory of the complexity of quantum sampling problems boils down to noting that a classical algorithm in $\sf{BPP}^\sf{NP}$ for certain $\sf{\#P}$ problems (that count the number of solutions to some $\sf{P}$ problem) can give an estimate up to a multiplicative error by using what's been called approximate counting or Stockmeyer counting.

I like to envision this as the Bitcoin mining algorithm - in particular, the $\sf{BPP}$ part of the algorithm is to come up with a random seed or random hash function $h$, while the $\sf{NP}$ oracle finds a solution $x$ to the $\sf{P}$ problem that also hashes on $f(x)=00\ldots 0$, proving that there are enough $x$ to be able to hash on to $00\ldots 0$, getting a bound on the number of such $x$.

Crucially this only works for multiplicative accuracy, and works, for example, to bound the permanent of the matrix if the matrix had only nonnegative entries. But a general matrix, especially a unitary matrix lifted from a bunch of beam-splitters and phase-shifters, will certainly have negative entries. This precludes Stockmeyer counting from ever getting any good handle on a multiplicative error, much less an additive error, on the permanent of such a matrix.

It's akin to the sign problem in Quantum Monte-Carlo. It's amazing that quantum algorithms, even such as the challenging Jones polynomial algorithm, can give additive approximations to big problems with both positive and negative entries, again highlighting the importance of interference in quantum algorithms.

---

Also another big breakthrough has been referred to as "Scattershot BosonSampling". For example conventionally the first $m$ modes correspond to the first $m$ columns of the lifted unitary - but, it's exponentially unlikely that all $m$ and only $m$ of those photons would fire.

The observation was made that we can have a bunch of sources of photons through spontaneous parametric down-conversion (SPDC) arbitrarily firing at any of the $n$ modes, and still have $n\choose m$ different columns to elect. The SPDC can herald the presence of the photons being emitted from the respective modes, and instead of post-selecting only on which output modes (which rows) fired, we also post-select on the input modes (the columns).

This scattershot trick seems very similar to a Texas sharpshooter who fires bullets at the broadside of a barn, and then later paints the bullseye around where the bullet landed!

---

Either way, although we cannot efficiently calculate the permanent of a (unitary) matrix, BosonSampling allows us to sample matrices that are more likely to have a large permanent. There may or may not be value in such permanents - not likely anything to the scale of, e.g., solving graph problems of industrial relevance, however.