How does Stim's detector sampler work?

Question

I'm just getting started with Stim (and hence working through its Getting Started Notebook) and am wondering how the detector sampler actually works. The notebook states

A detector doesn't say whether the parity should be even or should be odd, only that it should always be the same. You annotate that a pair of measurements is always different in the same way that you annotate that a pair of measurements is always the same; it's the consistency that's key.

Which I understand, except am curious how it knows what it should be "the same" as on its very first shot. If i write shots=10 in the detector sampler does it actually run multiple shots per shot or is it working just on the probability model with the errors?

For example, the simple Bell pair measurement with an X error:

import stim

circuit = stim.Circuit()
circuit.append("H",[0])
circuit.append("CNOT",[0,1])

#add x error:
p = 0.25
circuit.append_operation("X_error",[0,1],p)
circuit.append("M",[0,1])
circuit.append("DETECTOR",[stim.target_rec(-1),stim.target_rec(-2)])

sampler = circuit.compile_detector_sampler()

print(sampler.sample(shots=10))

Answer 1

curious how it knows what it should be "the same" as on its very first shot

The expected value of the detector is equal to its value when running the circuit without noise. This hypothetical noiseless shot would of course never be reported as one of the samples, since the requested samples are supposed to contain noise!

The consistency of a detector can be verified to ridiculously high confidence by sampling the circuit 1024 times without noise and checking all shots agreed on the value of the detector (noiseless shots still contain randomness due to anticommuting measurements; you want to verify this variation from anticommutation is not affecting the detectors). A detector's consistency can also be verified by backtracking where the detector's measurements' observables came from, reconstructing the detecting region of the detector and confirming it does not anticommute with any dissipative operations.

The underlying reason that detectors are defined in terms of consistency is because it's much much cheaper to do a simulation that merely determines whether measurements are flipped rather than whether measurements are 0 or 1. Determining 0-vs-1 requires full stabilizer simulation, with $O(q^2)$ time per anticommuting measurement and $O(q)$ time per other gate. Determining flipped-vs-not-flipped takes $O(1)$ time for all operations. It is ridiculously faster. When you ask stim for detection events, the definition of detectors has the consequence that detectors only care about being flipped. Thus, stim can immediately use the much cheaper simulation strategy and speed up this important use case.

Under the hood, the detection event simulator uses the pauli frame simulator to track errors being injected into the circuit and how they propagate into measurement-flips, and then aggregating the measurement-flips into detector-flips when encountering a DETECTOR instruction.