English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We consider quantum computations comprising only commuting gates, known asIQP computations, and provide compelling evidence that the task of samplingtheir output probability distributions is unlikely to be achievable by anyefficient classical means. More specifically we introduce the class post-IQP oflanguages decided with bounded error by uniform families of IQP circuits withpost-selection, and prove first that post-IQP equals the classical class PP.Using this result we show that if the output distributions of uniform IQPcircuit families could be classically efficiently sampled, even up to 41%multiplicative error in the probabilities, then the infinite tower of classicalcomplexity classes known as the polynomial hierarchy, would collapse to itsthird level. We mention some further results on the classical simulationproperties of IQP circuit families, in particular showing that if the outputdistribution results from measurements on only O(log n) lines then it may infact be classically efficiently sampled.

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