Implementing random-graph sampling in Qiskit

A useful implementation should work at three levels: a small circuit that teaches the idea, a parser that reproduces the exact benchmark, and a guarded hardware path. The repository keeps those levels separate so that a tutorial run cannot be mistaken for the full experiment.

1. Build a small self-contained example

The following program combines the brickwork graph-state prefix, the face-state basis rotation and computational-basis measurement:

import math
import random

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

def random_graph_sampling_circuit(n, depth, seed=1729):
    rng = random.Random(seed)
    qc = QuantumCircuit(n)

    # |0...0> -> |+...+>
    qc.h(range(n))

    # Clifford graph-state prefix on a nearest-neighbour chain
    for layer in range(depth):
        for q in range(layer % 2, n - 1, 2):
            qc.cz(q, q + 1)

        for q in range(n):
            if rng.getrandbits(1):
                qc.s(q)
            qc.sx(q)

    # Non-Clifford face-state measurement basis
    theta = math.acos(1 / math.sqrt(3))
    for q in range(n):
        qc.tdg(q)
        qc.h(q)
        qc.rz(theta, q)
        qc.h(q)

    qc.measure_all()
    return qc

circuit = random_graph_sampling_circuit(n=8, depth=8)
backend = AerSimulator(method="statevector")
result = backend.run(
    circuit,
    shots=2048,
    seed_simulator=1729,
).result()

counts = result.get_counts()
print(counts)

The dictionary printed at the end maps bit strings to observed frequencies. Repeating the experiment estimates the distribution; it never constructs a list of all ideal probabilities on hardware.

2. Inspect the exact benchmark instead of regenerating it

The large instance has fixed random choices. Re-running a constructor with the same high-level recipe is not sufficient unless the original random stream, gate conventions and simplifications are identical. The repository therefore loads the supplied QASM and checks its cryptographic hash and circuit invariants.

/home/bram/.venvs/qiskit/bin/python \
  scripts/random_graph_sampling_runner.py inspect

/home/bram/.venvs/qiskit/bin/python \
  scripts/random_graph_sampling_runner.py validate

inspect reports width, depth and gate structure. validate checks the frozen files, nearest-neighbour CZ topology, ancilla connections and common measurement-basis suffix. A changed QASM file should fail validation rather than silently define a new experiment.

3. Run a bounded local smoke test

/home/bram/.venvs/qiskit/bin/python \
  scripts/random_graph_sampling_runner.py smoke \
  --start 0 \
  --qubits 8 \
  --shots 1024 \
  --seed 1729

The smoke command keeps only operations wholly contained in a selected interval. This produces a new small circuit that is practical to simulate exactly. It tests parsing, gate order, state construction and sampling. It is not the reduced density matrix or marginal distribution of the full circuit.

4. Compile before touching hardware

A hardware workflow should first transpile the circuit against a chosen backend and inspect the resulting layout, native two-qubit gates and depth. A fixed transpiler seed makes compilation reproducible:

compiled = transpile(
    circuit,
    backend=hardware_backend,
    optimization_level=3,
    seed_transpiler=1729,
)

print(compiled.layout)
print(compiled.count_ops())
print(compiled.depth())

Only after these checks should a separate submit command create a paid or scarce hardware job. The repository’s hardware runners therefore distinguish planning, validation, submission and retrieval.

What to change when experimenting

• Increase n to study width.
• Increase depth to spread stabilizers and entanglement.
• Remove the face-state rotation to recover an efficiently simulable Clifford circuit.
• Change the graph ensemble if the scientific question concerns Erdős–Rényi or random regular graphs rather than the supplied LNN ansatz.
• Keep the seed fixed when comparing simulators or noise models.

Part 4 explains which circuit features create classical difficulty and why “large state vector” is not, by itself, a hardness argument.