Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy

Details Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy

2010-05-09

arxiv.org/abs/1005.1407v1

Physics

Quantum Physics

13 pages

Scientific paper

10.1098/rspa.2010.0301

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.

Affiliated with

Also associated with

No associations

Rating

Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-612158