Project: A Random-Circuit Sampler

A random-circuit sampler is a program that generates a circuit whose gate sequence is chosen (pseudo-)randomly and then measures all qubits to collect an output probability distribution. Sampling from random circuits sits at the heart of Google's 2019 quantum supremacy experiment and is the basis for the quantum volume benchmark used to compare processors.

Why random circuits matter

For an ideal quantum computer, a depth- $d$ random circuit over $n$ qubits generates a distribution over the $2^n$ bitstrings that converges toward the Porter-Thomas distribution — the distribution you would expect if you chose a Haar-random unitary and measured it. The key property is that the output probabilities are highly non-uniform: a few bitstrings receive much more weight than the $1/2^n$ uniform baseline, and many receive less. A classical simulator cannot reproduce this pattern efficiently for large $n$ and $d$ , which is the core claim behind quantum advantage.

More concretely, if $p_x$ is the probability of bitstring $x$ under an ideal random circuit, then the average collision probability satisfies

$\mathbb{E}\!\left[\sum_x p_x^2\right] \approx \frac{2}{2^n + 1},$

which exceeds the uniform value $1/2^n$ by a factor of roughly $2$ . This "anti-concentration" threshold is a signature that the circuit has reached sufficient depth.

Anatomy of a random circuit

A typical random circuit layer looks like this:

Single-qubit gates — choose a random gate from a fixed set (for example $\{H, T, S, X\}$ ) for each qubit. These spread amplitude across basis states.
Two-qubit entangling gates — apply CX or CZ between randomly chosen pairs. These create correlations between qubits that a product-state simulator cannot capture.
Measurement — read out all qubits to obtain a bitstring sample.

Repeating steps 1-2 for $d$ layers before measuring gives a circuit of depth $d$ . For the distribution to anti-concentrate, $d$ only needs to grow like $O(n)$ , which is surprisingly shallow.

A minimal example: 3 qubits

Consider a simple 3-qubit circuit:

$|\psi\rangle = \underbrace{H^{\otimes 3}}_{\text{superpose}} \; \underbrace{CX_{01}}_{\text{entangle}} \; \underbrace{S_2}_{\text{phase}}$

Starting from $|000\rangle$ :

$H^{\otimes 3}|000\rangle = \frac{1}{2\sqrt{2}}\sum_{x \in \{0,1\}^3} |x\rangle$

After $CX_{01}$ (qubit 0 is most significant), the controlled-NOT entangles qubits 0 and 1 by permuting the basis states — every amplitude keeps its original magnitude, so the marginal probabilities remain equal. The $S$ gate on qubit 2 multiplies the amplitude of every state with qubit 2 in $|1\rangle$ by $i$ , creating a relative phase between the $|{\cdots}0\rangle$ and $|{\cdots}1\rangle$ components, but again without changing any $|{amplitude}|^2$ . Both operations therefore leave the measurement probability of each of the 8 bitstrings equal at $\tfrac{1}{8}$ . The entanglement and phase are nonetheless physically significant: the $S$ phase is detectable via interference in a more complex circuit, and the entanglement means the joint state of qubits 0 and 1 cannot be written as a product state. Real random-circuit samplers use many alternating layers of single-qubit gates and entangling gates precisely so that the interference effects accumulate over depth and eventually break uniformity toward the Porter-Thomas distribution.

Analyzing the output

Once you have a distribution $\{p_x\}$ , useful statistics include:

Heavy outputs — bitstrings $x$ with $p_x$ above the median. A high heavy-output probability indicates the device is operating close to ideal.
Linear XEB fidelity — defined as $F_{\text{XEB}} = 2^n \langle p_x \rangle_{\text{sampled}} - 1$ , where the expectation is over sampled bitstrings weighted by the ideal probability. For a noiseless device $F_{\text{XEB}} \approx 1$ ; for a fully depolarised device $F_{\text{XEB}} \approx 0$ .
Collision probability $\sum_x p_x^2$ — can be estimated from samples and compared to the uniform baseline $1/2^n$ .

Try it

Build the 3-qubit circuit described above: Hadamard every qubit, entangle with a CNOT, add a phase with $S$ , then measure. The grader checks the output probability distribution against the reference solution.

Run your code to see the quantum state.

After running, inspect the histogram. The 8 bitstrings will all appear with equal height (probability $\tfrac{1}{8}$ each) — because the CX and S operations in this shallow, single-layer circuit preserve the uniform probability distribution created by $H^{\otimes 3}$ . The entanglement and relative phase are still physically present in the amplitudes; they would produce interference (and non-uniform probabilities) if additional gate layers were added. This is precisely why real random-circuit samplers require many alternating layers: depth is needed for the circuit to reach the non-uniform Porter-Thomas regime that random-circuit sampling benchmarks test.