Computational complexity of quantum optics

Question

In "Requirement for quantum computation", Bartlett and Sanders summarize some of the known results for continuous variable quantum computation in the following table:

MY question is three-fold:

1. Nine years later, can the last cell be filled in?
2. If a column is added with the title "Universal for BQP", how would the rest of the column look?
3. Can Aaronson and Arkhipov's 95 page masterpiece be summarized into a new row?

Answer 1

With respect to your third question, Aaronson and Arkhipov (A&A for brevity) use a construction of linear optical quantum computing very closely related to the KLM construction. In particular, they consider the case of $n$ identical non-interacting photons in a space of $\text{poly}(n) \ge m \ge n$ modes, starting in the initial state $$ \left|1_n\right>=\left|1,\dots,1,\ 0,\dots,0\right>\quad (n\text{ 1s}). $$ In addition, A&A allow beamsplitters and phaseshifters, which are enough to generate all $m\times m$ unitary operators on the space of modes (importantly, though, not on the full state space of the system). Measurement is performed by counting the number of photons in each mode, producing a tuple $(s_1, s_2, \dots, s_m)$ of occupation numbers such that $\sum_i s_i = n$ and $s_i \ge 0$ for each $i$. (Most of these definitions can be found in pages 18-20 of A&A.)

Thus, in the language of the table, the A&A BosonSampling model would likely best be described as "$n$ photons, linear optics and photon counting." While the classical efficiency of sampling from this model is, strictly speaking, unknown, the ability to classically sample from the A&A model would imply a collapse of the polynomial hierarchy. Since any collapse of PH is generally considered extremely unlikely, it's not at all a stretch to say that BosonSampling is very probably not efficiently and classically simulatable.

As for BQP-universality of the A&A model, while linear optics of non-interacting bosons alone is not known to be universal for BQP, the addition of post-selected measurement is enough to obtain full BQP universality, via the celebrated KLM theorem. The acceptance probability of the postselection in the KLM construction scales as $1/16^\Gamma$, where $\Gamma$ is the number of controlled-Z gates that appear in a given circuit. Whether that is enough to conclude that the postselected linear optics model of BQP is efficient or not is thus a matter of what one defines to be efficient, but it is universal.

Aaronson explores the postselected linear optics case more in his followup paper on the #P-hardness of the permanent. This result was earlier proved by Valiant, but Aaronson presents a novel proof based on the KLM theorem. As a side note, I find that this paper makes a very nice introduction to many of the concepts that A&A use in their BosonSampling masterpiece.

Answer 2

After a two-week self-taught crash-course on continuous variable quantum computation (start with this review article), I am $\cos^2(\frac\pi8)$% confident in the following answer:

1. I believe it is fair to say that the last entry in the table is an "X" due to Quantum Computing with Continuous-Variable Clusters by Gu et al. They show that non-Gaussian cluster states can be acted upon by homodyne measurements for UQC.
2. The hypothetical column "Universal for BQP" would have an "X" for the first row and "checks" for rest - except the hypothetical row on the Aaronson and Arkhipov result, which would have a "?" (although it is probably an "X" according to the authors).
3. See Chris Granade's answer above.

UPDATE: I should have also asked if any new rows can be added. In any case, indeed one can:

That is from Veitch et al. See also Mari and Eisert.