Table of Contents
Quantum computing is advancing rapidly, with companies like Google, IBM, and Microsoft racing to prove their hardware can perform computations beyond the reach of classical supercomputers. But how do we measure quantum progress? How can we objectively say one quantum processor is “better” than another?
One of the most significant milestones in quantum computing history was Google’s 2019 announcement of “quantum supremacy”—a term used to describe a quantum device performing a task that no classical computer could realistically complete in a reasonable amount of time. This claim was based on a technique known as Random Circuit Sampling (RCS). Since then, RCS has become a widely used benchmark for quantum processors, allowing researchers to compare different machines and test whether they truly push the boundaries of computational feasibility.
What is Random Circuit Sampling (RCS)?
At its core, Random Circuit Sampling (RCS) is a way to test how well a quantum computer can generate the output of a complex quantum circuit. The goal is simple:
- Take a quantum computer.
- Run a randomly generated quantum circuit.
- Measure the results.
- Compare them to what an ideal quantum computer should produce.
If the quantum computer’s output closely matches the theoretical expectations, it demonstrates that the system is performing quantum operations correctly.
But why random circuits? Why not use structured computations like Shor’s algorithm for factoring numbers or Grover’s search algorithm?
The answer lies in hardness. Many quantum algorithms can be approximated or simulated efficiently by classical computers—especially when they exploit symmetries or special mathematical structures. However, randomly generated quantum circuits do not have an easy classical shortcut. If a quantum computer can generate their outputs accurately and efficiently, it provides strong evidence that the machine is operating in a way that classical computers cannot feasibly replicate.
This is why RCS became the foundation of Google’s claim of quantum supremacy in 2019: they needed a task that would be exponentially harder for a classical supercomputer to simulate, and random quantum circuits fit the bill.
Why is RCS an Important Benchmark for Quantum Computing?
Hard for Classical Computers to Simulate
A key reason RCS is so valuable is that simulating a quantum circuit’s output distribution on a classical computer quickly becomes infeasible as the number of qubits grows.
Consider a 53-qubit quantum circuit—the size used in Google’s 2019 quantum supremacy experiment. The state of this system can be described by a vector of size $$2^{53}$$ (~9 quadrillion) complex numbers. Tracking the exact evolution of this state requires manipulating exponentially many parameters, making brute-force classical simulations prohibitively expensive.
Quantum computers, however, naturally evolve in this exponentially large state space. Thus, if a quantum computer can generate the correct probability distribution significantly faster than a classical supercomputer, it indicates a strong computational advantage.
No Structure to Exploit
Another key feature of RCS is that random quantum circuits do not have mathematical shortcuts. Algorithms like Shor’s factoring algorithm have special structure that can sometimes be classically approximated or even solved efficiently in specific cases. In contrast, random circuits lack symmetry or optimization tricks, making them a fair and unbiased test of quantum computational power.
A Proxy for Quantum Error Rates
Quantum computers are inherently noisy. Every qubit operation introduces some level of error, and these errors compound as the circuit gets deeper.
RCS serves as a natural stress test—if a quantum computer can execute a deep random circuit accurately, it means its error rates are low enough to sustain complex operations.
This makes RCS a valuable tool for:
- Measuring how errors accumulate in a quantum processor.
- Understanding the effects of decoherence over long computations.
- Benchmarking quantum hardware improvements over time.
The Mathematics Behind RCS
RCS is fundamentally a statistical sampling problem. The main goal is to compare the experimental results from a quantum processor against the ideal theoretical probability distribution of the circuit’s possible outputs.
Computing the Ideal Output Distribution
Given a quantum circuit C, it applies a unitary transformation $$U_C$$ to an initial quantum state:
$$|\psi\rangle = U_C |0\rangle$$
When measured, the quantum processor samples from the probability distribution:
$$p_{\mathrm{ideal}}(x) = |\langle x | \psi \rangle|^2$$
where $$x$$ represents an output bitstring.
Cross-Entropy Benchmarking
To measure how well a quantum processor reproduces this distribution, researchers use a statistical metric called Cross-Entropy Benchmarking (XEB). This is defined as:
$$F_{\mathrm{XEB}} = \frac{2^n}{N} \sum_{i=1}^{N} p_{\mathrm{ideal}}(x_i) – 1$$
where:
• $$n$$ is the number of qubits.
• $$N$$ is the number of sampled bitstrings.
• $$p_{\mathrm{ideal}}(x_i)$$ is the ideal probability of the observed bitstrings.
If the quantum processor is perfect, $$F_{\mathrm{XEB}} \approx 1$$. If it is purely random (i.e., failing completely), $$F_{\mathrm{XEB}} \approx 0$$.
This fidelity measure allows researchers to quantify how much noise and error affect quantum computation.
The Rise of RCS: From Theory to Google’s Quantum Supremacy
While RCS has theoretical foundations dating back to studies of quantum complexity theory, it gained major attention in 2019 when Google used it to claim quantum supremacy.
In the experiment:
- Google’s Sycamore processor (53 qubits) executed a random circuit for 200 seconds.
- The same simulation would have taken 10,000 years on a classical supercomputer (claimed by Google).
- IBM later disputed this, arguing it could be done in a few days on a clever classical simulator.
Despite the debate, RCS became the go-to method for demonstrating when a quantum processor reaches “beyond-classical” performance.
Challenges and Criticism of RCS
Despite its importance, RCS has its limitations:
- Not a Practical Computation: RCS is a stress test, not a useful algorithm. No real-world problem gets solved—only a demonstration of computational hardness.
- Classical Simulation Techniques Are Improving: Every time quantum hardware advances, classical algorithms get better at simulating quantum circuits, making the bar for “quantum advantage” harder to clear.
- It’s Not a Universal Benchmark: RCS measures one aspect of performance (raw computational power), but other factors—like quantum error correction—matter for long-term scalability.
Conclusion
Random Circuit Sampling remains one of the most powerful tools for benchmarking quantum computing progress. It helped demonstrate the first quantum supremacy claim and continues to push quantum processors to their limits.
However, the ultimate goal isn’t just random sampling—it’s solving real-world problems. As quantum computing advances, the next milestone will be demonstrating useful quantum advantage in fields like chemistry, materials science, and optimization.
Until then, RCS will continue to be a key battleground where quantum devices prove their power.
