Achieving quantum supremacy with sparse and noisy commuting quantum computations

Michael Bremner, Ashley Montanaro, Daniel J Shepherd

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

305 Downloads (Pure)

Abstract

The class of commuting quantum circuits known as IQP (instantaneous quantum polynomial-time) has been shown to be hard to simulate classically, assuming certain complexity-theoretic conjectures. Here we study the power of IQP circuits in the presence of physically motivated constraints. First, we show that there is a family of sparse IQP circuits that can be implemented on a square lattice of n qubits in depth O(√n log n), and which is likely hard to simulate classically. Next, we show that, if an arbitrarily small constant amount of noise is applied to each qubit at the end of any IQP circuit whose output probability distribution is suffciently anticoncentrated, there is a polynomial-time classical algorithm that simulates sampling from the resulting distribution, up to constant accuracy in total variation distance. However, we show that purely classical error-correction techniques can be used to design IQP circuits which remain hard to simulate classically, even in the presence of arbitrary amounts of noise of this form. These results demonstrate the challenges faced by experiments designed to demonstrate quantum supremacy over classical computation, and how these challenges can be overcome.
Original languageEnglish
Pages (from-to)8
Number of pages23
JournalQuantum
Volume1
DOIs
Publication statusPublished - 25 Apr 2017

Structured keywords

  • QITG
  • Bristol Quantum Information Institute

Fingerprint Dive into the research topics of 'Achieving quantum supremacy with sparse and noisy commuting quantum computations'. Together they form a unique fingerprint.

Cite this