Random circuit sampling and classical simulation of supremacy experiments

Short answer: Random circuit sampling (RCS) is the task behind Google's 2019 quantum supremacy claim, and later work has pushed back on how hard it is to simulate classically. A 2020 tensor-network paper estimated the 2019 task could be done in under 20 days on a Summit-comparable cluster, against an initial estimate of about 10,000 years. Google Quantum AI, for its part, says its later results support RCS as a benchmark. These are estimates and vendor claims, so treat them as unverified by us.

How do classical algorithms challenge quantum supremacy claims?

The assertion of quantum supremacy relies on the premise that random quantum circuits are intrinsically difficult to simulate on classical hardware. The task underlying the 2019 demonstration by Arute et al. was initially estimated to require approximately 10,000 years on Summit, then the world’s most powerful supercomputer, whereas the Sycamore quantum processor completed the same task in 200 seconds. However, a 2020 paper proposed a tensor network-based classical simulation algorithm. Using a cluster comparable to Summit, estimates suggest this simulator could perform the same task in less than 20 days. That is an estimate, not a completed run.

On moderately sized instances, this classical approach reduces runtime from years to minutes, operating several times faster than the Sycamore processor itself. The authors say their estimates are based on explicit simulations of parallel instances. Our reading is that improved classical algorithms can move the line at which a quantum advantage is claimed.

What are the boundaries of the quantum advantage region?

Research examining the constraints on quantum advantage for circuits with larger numbers of qubits and gates than those experimentally implemented reports distinct boundaries. At near-term gate fidelities, quantum supremacy is limited to circuits with a qubit count and circuit depth of only a few hundred. Beyond this threshold, two distinct boundaries emerge: a return of classical advantage and practically infeasible quantum runtimes. The former occurs when classical simulation becomes efficient enough to outpace the quantum device, while the latter arises when noise accumulates to a level that renders the quantum computation useless.

Decreasing error rates causes the region of quantum advantage to grow rapidly. At error rates required for early implementations of the surface code, the largest circuit size within the quantum supremacy regime coincides approximately with the smallest circuit size needed to implement error correction. The authors say the boundaries of quantum supremacy may fortuitously coincide with the advent of scalable, fault-tolerant quantum computing.

How does noise affect the reliability of random circuit sampling?

Random circuit sampling (RCS) is examined as a method for evaluating quantum computer performance specifically in the presence of noise. Google Quantum AI describes a Nature paper that addresses the question of how noise impacts the validity of RCS as a performance metric. Google says the work identifies two distinct phase transitions that govern the behaviour of quantum computers as noise strength and the number of processor qubits change.

Google says its work reaffirms the reliability of RCS for large-scale experiments as a performance metric for current devices, and that noisy quantum computers have the potential to outperform supercomputers even at current noise levels. It cites a twofold increase in circuit volume at the same fidelity compared with its 2019 results. These are Google's own claims and we have not verified them.

What are the practical limitations of current supremacy demonstrations?

The practical limitations of current supremacy demonstrations are defined by the interplay between hardware fidelity and classical simulation speed. At near-term gate fidelities, the region of quantum advantage is constrained to circuits with a few hundred qubits and gates. Larger circuits encounter the dual boundaries of classical simulation efficiency and quantum runtime infeasibility.

The coincidence between the largest circuit size in the supremacy regime and the smallest size needed for error correction at surface-code error rates is described by the authors as a notable coincidence. Until error rates are reduced to levels compatible with early surface code implementations, the region of advantage stays limited. Classical simulation algorithms, such as the tensor network-based methods, continue to erode the time advantage of quantum devices. The 2020 paper estimates that a task first put at about 10,000 years could be done in under 20 days, and for smaller instances in minutes. None of this describes a deployed or commercial system.

FAQ

What is random circuit sampling?

It is a task in which a quantum computer runs a random circuit and samples its output. It was the task behind Arute et al.'s 2019 quantum supremacy claim.

What did the 2019 claim say?

The task was initially estimated to need about 10,000 years on the Summit supercomputer, while the Sycamore processor did it in 200 seconds.

How did classical researchers respond?

A 2020 paper presented a tensor-network simulation algorithm and estimated that, on a Summit-comparable cluster, it could do the task in less than 20 days. On moderately sized instances it reports runtimes cut from years to minutes.

Where do the limits of quantum advantage lie?

A paper in npj Quantum Information reports that at near-term gate fidelities, supremacy is limited to circuits with a qubit count and depth of a few hundred, and that lower error rates grow the region of advantage.

What does Google say about RCS today?

Google Quantum AI says its Nature paper on phase transitions in RCS reaffirms RCS as a benchmark and that its latest results show a twofold increase in circuit volume at the same fidelity versus 2019. These are Google's own claims, which we have not verified.