New paper: Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Yes, I am still alive. I hope the 3 of you that still subscribe to my RSS feed weren’t too shocked this morning when you saw “Brissie to Brizzle” highlighted in Google Reader.
Title: Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Abstract: We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability distributions is unlikely to be achievable by any efficient classical means. More specifically we introduce the class post-IQP of languages decided with bounded error by uniform families of IQP circuits with post-selection, and prove first that post-IQP equals the classical class PP. Using this result we show that if the output distributions of uniform IQP circuit families could be classically efficiently sampled, even up to 41% multiplicative error in the probabilities, then the infinite tower of classical complexity classes known as the polynomial hierarchy, would collapse to its third level. We mention some further results on the classical simulation properties of IQP circuit families, in particular showing that if the output distribution results from measurements on only O(log n) lines then it may in fact, be classically efficiently sampled.
This paper is a sequel to a paper that Dan Shepherd and I wrote back in 2008, Instantaneous Quantum Computation.
For those of you that attended QIP in Zurich this year you might have seen our poster on these results (which was very kindly advertised by Scott Aaronson during one of his talks).
Those of you that are really keen will notice in the references of this paper that there is another related paper by Dan Shepherd that will appear imminently… It’s well worth a read if you are interested in the classical simulation of quantum systems!