# On experimentally relevant quantum speedups

This is a Perspective on "Achieving quantum supremacy with sparse and noisy commuting quantum computations" by Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd, published in Quantum 1, 8 (2017).

By Bill Fefferman (University of Maryland/NIST).

One of the most active areas of research in quantum information is “quantum supremacy”. The central goal is to exhibit a provable quantum speedup over classical computation using the restrictive resources of existing or near-term quantum experiments. Starting with work of Bremner, Jozsa, and Shepherd it has been established that even non-universal commuting classes of quantum computations known as “Instantaneous Quantum Polynomial-time” (or IQP) circuits are capable of sampling from distributions that cannot be exactly sampled classically, under mild complexity assumptions.

As quantum supremacy leaps from the domain of theory to experiment, the major open questions involve understanding which intermediate models are capable of demonstrating supremacy, and how to account for experimentally realistic noise in these models. As a starting point, a primary objective has been to strengthen these sampling separations to hold even if the classical sampler is not required to sample exactly from the quantum outcome distribution but instead samples from a distribution close in total variation distance.

Follow-up work of Bremner, Montanaro and Shepherd addressed this stronger scenario. They show that the outcome distribution of IQP circuits cannot be approximately sampled classically, assuming a conjecture concerning the hardness of estimating the complex-temperature partition function of certain random instances of the Ising model. Understanding the feasibility and implications of this conjecture, as well as related conjectures of Aaronson and Arkhipov regarding estimating the permanent of random matrices, has since become one of the most important challenges in quantum complexity theory.

While not settling these conjectures, the present paper makes important contributions to our understanding of approximate sampling hardness results. The first main result extends the prior work to give similar conjectural evidence that approximate sampling from the output distribution of so-called “sparse” IQP circuits is classically hard. A randomly chosen “sparse” IQP circuit on n qubits consists of $O(n \log(n) )$ 2-qubit gates and can be implemented on a square lattice with a shallow depth circuit, with high probability. These structural properties reduce the experimental barrier of implementing such supremacy results and bring the proposal closer to the realm of currently implementable experiments.

The second result studies IQP sampling under a natural noise model, in which independent depolarizing noise is applied to every qubit at the end of the circuit. It is proven that the resulting output distribution becomes easy to sample from classically, illuminating the fragile nature of supremacy results. However, the authors develop new means for protecting against this depolarizing noise model, using ideas from classical error-correcting codes. Crucially, this result is achieved without the full overhead required by traditional quantum fault tolerance. It is very likely that these error-correcting tools will find use in future results on noise-tolerant quantum supremacy proposals.

Taken as a whole, these results give a fresh perspective to some of the most foundational questions in quantum computation—where quantum speedups come from, and under which experimentally motivated settings we can hope to observe these speedups. As such, this work offers a solid contribution to the quantum supremacy literature, and develops useful tools for analyzing candidates for future supremacy experiments.