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?

This post has been migrated from (A51.SE)

Comments

Chris Granade's answer suggests that the KLM row of the measurement column should be "photon counting, postselection". Does someone know off the top of their head whether the other schemes require postselection as well?

This post has been migrated from (A51.SE)

---

Perhaps a stupid question, but isn't the fact that you can violate a Bell inequality with single photons and homodyne detection an evidence that the last entry of the table is not efficiently simulatable?

This post has been migrated from (A51.SE)

---

@MateusAraújo - The most convincing evidence that computational complexity has nothing to do with locality comes from two facts: (1) that the qubit stabilizer formalism is classically efficiently simulatable via Gottesman-Knill theorem but one can violate a Bell inequality with stabilizer states; (2) the qutrit stabilizer formalism is also classical efficiently simulatable but one can also find a local hidden variable reproducing it.

This post has been migrated from (A51.SE)

---

Risking to detract further from your question, but: is it known a system which has a local hidden-variable model but which is not efficiently simulatable? That would really surprise me.

This post has been migrated from (A51.SE)

---

@MateusAraújo - I think any classical chaotic system will do, no?

This post has been migrated from (A51.SE)

---

No, since we're talking about simulating quantum systems. What about simulating chaotic quantum systems?

This post has been migrated from (A51.SE)

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.

This post has been migrated from (A51.SE)

Comments

Great answer! So the x's in the last column should also have a footnote or, more accurately, be question marks since we don't know whether P = BQP or not?

This post has been migrated from (A51.SE)

---

Thanks! The last column is at best hypothetical, since we don't have a proof that P ≠ BQP. The A&A result is one of the strongest results I've seen for separating classical and quantum computation, though, in that it provides a concrete complexity-theoretic consequence of the existence an efficient classical simulator. Maybe a more descriptive column would be "consequences of efficient classical simulation?"

This post has been migrated from (A51.SE)

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.

This post has been migrated from (A51.SE)