Scott Aaronson gave a thought-provoking lecture in our Theory seminar three weeks ago. (Actually, this was eleven months ago.) The slides are here . The lecture discussed two results regarding the computational power of quantum computers. One result from this paper gives an oracle-evidence that there are problems in BQP outside the polynomial hierarchy. The method is based on “magnification” of results on bounded depth circuits. (It is related to the Linial-Nisan conjecture.)
The second result that we are going to discuss in this post (along with some of my provoked thoughts) is a recent result of Scott Aaronson and Alex Arkhipov which asserts that if the power of quantum computers can be simulated by digital computers then the polynomial hierarchy collapses. More precisely, their result asserts that if sampling probability distribution created by quantum computers (this is abbreviated as QSAMPLE) is in P then the polynomial hieararchy collapses to its third level.
The beautiful and important paper of Aaronson and Arkhipov is now out. Its main point of view is related to what I describe in the sixth section about “photon machines”. Update: Let me mention related idependent results by Michael J. Bremner, Richard Jozsa, Dan J. Shepherd in the paper entitled: “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy“.
Here is the plan for this post
1) The polynomial hierarchy and results about hierarchy collapse
2) The Aaronson Arkhipov (AA) theorem and its proof
3) Two problems posed by AA
Those are: does P=BQP already leads to a collapse of the polynomial hierarchy? And does APPROXIMATE-QSAMPLE already leads to a collapse?
4) Does fault tolerance allow QSAMPLE (on the nose)? (Answer: yes)
5) Is there a quantum analog to Aaronson and Arkhipov’s result and what is the computational power of quantum computers?
Three Two competing scenarios
7) Aaronson and Arkhipov photon machines and the complexity class BOSONSAMPLING.