• Register
PhysicsOverflow is a next-generation academic platform for physicists and astronomers, including a community peer review system and a postgraduate-level discussion forum analogous to MathOverflow.

Welcome to PhysicsOverflow! PhysicsOverflow is an open platform for community peer review and graduate-level Physics discussion.

Please help promote PhysicsOverflow ads elsewhere if you like it.


PO is now at the Physics Department of Bielefeld University!

New printer friendly PO pages!

Migration to Bielefeld University was successful!

Please vote for this year's PhysicsOverflow ads!

Please do help out in categorising submissions. Submit a paper to PhysicsOverflow!

... see more

Tools for paper authors

Submit paper
Claim Paper Authorship

Tools for SE users

Search User
Reclaim SE Account
Request Account Merger
Nativise imported posts
Claim post (deleted users)
Import SE post

Users whose questions have been imported from Physics Stack Exchange, Theoretical Physics Stack Exchange, or any other Stack Exchange site are kindly requested to reclaim their account and not to register as a new user.

Public \(\beta\) tools

Report a bug with a feature
Request a new functionality
404 page design
Send feedback


(propose a free ad)

Site Statistics

205 submissions , 163 unreviewed
5,054 questions , 2,207 unanswered
5,347 answers , 22,728 comments
1,470 users with positive rep
818 active unimported users
More ...

  Computational complexity of quantum optics

+ 16 like - 0 dislike

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

Table from Bartlett and Sanders, 2003

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)
asked Feb 9, 2012 in Theoretical Physics by Chris Ferrie (660 points) [ no revision ]
retagged Mar 7, 2014 by dimension10
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)

2 Answers

+ 7 like - 0 dislike

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)
answered Feb 9, 2012 by Chris Granade (260 points) [ no revision ]
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)
+ 3 like - 0 dislike

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)
answered Feb 23, 2012 by Chris Ferrie (660 points) [ no revision ]

Your answer

Please use answers only to (at least partly) answer questions. To comment, discuss, or ask for clarification, leave a comment instead.
To mask links under text, please type your text, highlight it, and click the "link" button. You can then enter your link URL.
Please consult the FAQ for as to how to format your post.
This is the answer box; if you want to write a comment instead, please use the 'add comment' button.
Live preview (may slow down editor)   Preview
Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
If you are a human please identify the position of the character covered by the symbol $\varnothing$ in the following word:
Then drag the red bullet below over the corresponding character of our banner. When you drop it there, the bullet changes to green (on slow internet connections after a few seconds).
Please complete the anti-spam verification

user contributions licensed under cc by-sa 3.0 with attribution required

Your rights