Where randomness is the only certainty

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.

Why have I come out of hibernation? Well, it’s because today I have a new paper together with Dan Shepherd and Richard Jozsa out on the arXiv (SciRate link):

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!

Oh, and while I’m at it Dan’s PhD thesis (SciRate link) is available on the arXiv today as well!

About these ads

2 responses

  1. aram

    congratulations! this result was indeed more ‘instantaneous’ than the reverse shannon theorem.

    May 11, 2010 at 4:31 pm

  2. That’s gotta be in the running for the prize for the most painful quantum information joke written on a blog this year… painful in so many ways…

    May 11, 2010 at 5:53 pm


Get every new post delivered to your Inbox.