<p>After a two-week self-taught crash-course on continuous variable quantum computation (start with <a href="http://arxiv.org/abs/1110.3234" rel="nofollow noreferrer">this</a> review article), I am $\cos^2(\frac\pi8)$% confident in the following answer:</p>

<ol>
<li>I believe it is fair to say that the last entry in the table is an "X" due to <a href="http://arxiv.org/abs/0903.3233" rel="nofollow noreferrer">Quantum Computing with Continuous-Variable Clusters</a> by Gu <em>et al</em>.  They show that non-Gaussian cluster states can be acted upon by homodyne measurements for UQC.</li>
<li>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).</li>
<li>See Chris Granade's <a href="http://theoreticalphysics.stackexchange.com/a/909/493" rel="nofollow noreferrer">answer</a> above.</li>
</ol>

<p>UPDATE: I should have also asked if any new rows can be added.  In any case, indeed one can:
<img src="https://i.sstatic.net/heXVK.png" alt="enter image description here"></p>

<p>That is from <a href="http://arxiv.org/abs/1210.1783" rel="nofollow noreferrer">Veitch et al</a>.   See also <a href="http://arxiv.org/abs/1208.3660" rel="nofollow noreferrer">Mari and Eisert</a>.</p>

CC BY-SA 3.0
2012-02-23T17:47:17.797Z
2013-02-10T16:18:11.610Z
2013-02-10T16:18:11.610Z
Chris Ferrie
<p>With respect to your third question, Aaronson and Arkhipov (A&amp;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&gt;=\left|1,\dots,1,\ 0,\dots,0\right&gt;\quad (n\text{ 1s}).
$$
In addition, A&amp;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&amp;A.)</p>

<p>Thus, in the language of the table, the A&amp;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&amp;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.</p>

<p>As for BQP-universality of the A&amp;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.</p>

<p>Aaronson explores the postselected linear optics case more in his <a href="http://www.scottaaronson.com/papers/sharp.pdf">followup paper</a> 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&amp;A use in their BosonSampling masterpiece.</p>

CC BY-SA 3.0
2012-02-11T17:50:33.010Z
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?
Chris Ferrie
CC BY-SA 3.0
2012-02-13T04:25:56.533Z
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?"
Chris Granade
CC BY-SA 4.0
2019-01-29T21:20:34.923Z
A followup question that probably deserves a question on its own: do you know if there's a natural way to prove that linear optics by itself is not universal for BQP? Or is there a barrier to proving this (eg. by implying other things we don't know how to show but are still probably true)?
Abhinav
CC BY-SA 3.0
2012-02-09T17:39:42.313Z
2012-02-09T17:39:42.313Z
Chris Granade
<p>In <a href="http://arxiv.org/abs/quant-ph/0302125" rel="noreferrer">"Requirement for quantum computation"</a>, Bartlett and Sanders summarize some of the known results for continuous variable quantum computation in the following table:  </p>

<p><img src="https://i.sstatic.net/vBXE6.jpg" alt="Table from Bartlett and Sanders, 2003"></p>

<p>MY question is three-fold:</p>

<ol>
<li>Nine years later, can the last cell be filled in?</li>
<li>If a column is added with the title "Universal for BQP", how would the rest of the column look?</li>
<li>Can Aaronson and Arkhipov's <a href="http://arxiv.org/abs/1011.3245" rel="noreferrer">95 page masterpiece</a> be summarized into a new row?</li>
</ol>

CC BY-SA 3.0
2012-02-11T17:51:33.930Z
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?
Chris Ferrie
CC BY-SA 3.0
2012-02-15T15:56:40.400Z
@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.
Chris Ferrie
CC BY-SA 3.0
2012-02-15T17:39:51.183Z
@MateusAraújo - I think any classical chaotic system will do, no?
Chris Ferrie
<quantum-computing>
Computational complexity of quantum optics
Chris Ferrie
# Computational complexity of quantum optics

(Asked by: username_0 on 2012-02-09)

In ["Requirement for quantum computation"](http://arxiv.org/abs/quant-ph/0302125), Bartlett and Sanders summarize some of the known results for continuous variable quantum computation in the following table:

![Table from Bartlett and Sanders, 2003](https://i.sstatic.net/vBXE6.jpg)

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](http://arxiv.org/abs/1011.3245) be summarized into a new row?

**Tags:** quantum-computing
> **Comments:**
> **username_0**: 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?  
> **username_0**: @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.  
> **username_0**: @MateusAraújo - I think any classical chaotic system will do, no?  

---

## 2 answers

### Answer by username_1 on 2012-02-09. Score: 15 | Accepted answer

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](http://www.scottaaronson.com/papers/sharp.pdf) 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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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?"  
> **username_2**: A followup question that probably deserves a question on its own: do you know if there's a natural way to prove that linear optics by itself is not universal for BQP? Or is there a barrier to proving this (eg. by implying other things we don't know how to show but are still probably true)?  

---

### Answer by username_0 on 2012-02-23. Score: 9

After a two-week self-taught crash-course on continuous variable quantum computation (start with [this](http://arxiv.org/abs/1110.3234) 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](http://arxiv.org/abs/0903.3233) 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](http://theoreticalphysics.stackexchange.com/a/909/493) above.

UPDATE: I should have also asked if any new rows can be added. In any case, indeed one can:
![enter image description here](https://i.sstatic.net/heXVK.png)

That is from [Veitch et al](http://arxiv.org/abs/1210.1783). See also [Mari and Eisert](http://arxiv.org/abs/1208.3660).


---

