Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations

Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd
Phys. Rev. Lett. 117, 080501 – Published 18 August 2016
PDFHTMLExport Citation

Abstract

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 relates 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 generalizations of the boson sampling problem that avoid the so-called permanent anticoncentration conjecture.

  • Figure
  • Received 8 May 2015

DOI:https://doi.org/10.1103/PhysRevLett.117.080501

© 2016 American Physical Society

Physics Subject Headings (PhySH)

Quantum Information, Science & Technology

Authors & Affiliations

Michael J. Bremner1,*, Ashley Montanaro2, and Dan J. Shepherd3

  • 1Centre for Quantum Computation and Intelligent Systems, Faculty of Engineering and Information Technology, University of Technology Sydney, Sydney, NSW 2007, Australia
  • 2School of Mathematics, University of Bristol, Bristol BS8 1TW, United Kingdom
  • 3CESG, Hubble Road, Cheltenham GL51 0EX, United Kingdom

  • *michael.bremner@uts.edu.au

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 117, Iss. 8 — 19 August 2016

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×