Random Graph Sampling asks a deceptively simple question: what happens when a quantum computer prepares a highly entangled state described by a graph, measures every qubit in a deliberately difficult basis, and returns bit strings from the resulting probability distribution?
This series develops the idea from first principles. It begins with ordinary graph theory, turns a graph into a quantum state, derives the stabilizers that make the state verifiable, and then implements the circuit in Qiskit. Only after the model and implementation are clear do we discuss the hardware experiment and its limitations.
What you will learn
- how a graph G = (V,E) becomes an entangled graph state;
- why random product-basis measurements create a non-trivial sampling problem;
- how the benchmark compiles a complex graph state onto a one-dimensional qubit chain;
- how to build and simulate a smaller version in Qiskit;
- why entanglement challenges tensor networks while non-Clifford “magic” challenges stabilizer methods;
- how stabilizer and spacetime checks test the experiment without classically calculating every output probability.
The article series
New to graph states? Begin with Start here: build and sample a six-qubit random graph state. It includes a drawn toy graph, hand-verifiable stabilizers and runnable Qiskit code.
- Random graphs, graph states and the sampling problem
- From a graph to a hardware-compatible circuit
- Implementing random-graph sampling in Qiskit
- Why entanglement and magic make simulation difficult
- How stabilizer checks validate a graph-state experiment
- Running the quantum and classical workflows
- What the experiment establishes — and what remains open
The exact benchmark QASM remains the source of truth. The code in this series is intentionally smaller and clearer: it teaches the construction without pretending that a tutorial circuit is byte-for-byte identical to the published instance.
GitHub repository · Evidence and results · Tracker discussion · Pro Student Quantum Advantage List