Average-case complexity versus approximate simulation of commuting quantum computations

Michael Bremner, Ashley Montanaro, Daniel Shepherd

Research output: Contribution to journalArticle (Academic Journal)peer-review

169 Citations (Scopus)
378 Downloads (Pure)


We use the class of commuting quantum computations known as IQP (Instantaneous Quantum Polynomial time) to strengthen the conjecture that quantum computers are hard to simulate classically. We show that, if either of two plausible average-case hardness conjectures holds, then IQP computations are hard to simulate classically up to constant additive error. One conjecture elates to the hardness of estimating the complex-temperature partition function for random instances of the Ising model; the other concerns approximating the
number of zeroes of random low-degree polynomials. We observe that both conjectures can be shown to be valid in the setting of worst-case complexity. We arrive at these conjectures by deriving spin-based generalisations of the Boson Sampling problem that avoid the so-called permanent anticoncentration conjecture.
Original languageEnglish
Article number080501
Number of pages5
JournalPhysical Review Letters
Publication statusPublished - 18 Aug 2016


Dive into the research topics of 'Average-case complexity versus approximate simulation of commuting quantum computations'. Together they form a unique fingerprint.

Cite this