A quantum computer never shows you its amplitudes. You prepare the same state many times, measure it each time (one shot), and get back counts: how often each outcome came out. The simulator you are building needs to imitate this.
A state of n qubits is a list state of 2^n complex amplitudes, with \sum_i |a_i|^2 = 1. Measuring all qubits gives outcome i with probability p_i = |a_i|^2 (the Born rule), where |a_i| is abs(state[i]). Outcomes are reported as bit strings of length n: outcome i is i written in binary with leading zeros, and qubit 0 is the leftmost bit. In 3 qubits, outcome 3 is "011"; in 1 qubit the outcomes are "0" and "1".
So that every run gives the same counts, use exactly this procedure. Use rng = random.Random(seed). For each shot draw r = rng.random() and pick the first outcome i whose running total p[0] + ... + p[i] is greater than r (if rounding leaves no such i, pick the last outcome with nonzero probability).
Write measure_shots(state, shots, seed) that returns a dict mapping each bit string that came out at least once to its count. Outcomes that never came out are not in the dict.
Examples
Input: state = [0.6, 0.8j], shots = 10, seed = 7
Output: {'0': 5, '1': 5}
Explanation: p = [0.36, 0.64]. The first draws are 0.324, 0.151, 0.651, ...
(rounded): 0.324 < 0.36 gives '0', 0.151 gives '0', 0.651 is not below 0.36
but is below 0.36 + 0.64 = 1.0, so it gives '1', and so on.
Input: state = [0, 1], shots = 3, seed = 5
Output: {'1': 3}
Explanation: '0' has probability 0 and never comes out, so it is not a key.
Input: state = [0.5, 0.5, 0.5, -0.5], shots = 8, seed = 1
Output: {'00': 1, '01': 3, '10': 1, '11': 3}
The order of the keys does not matter. Press Run with c = measure_shots(state, 1000, 1) and plot(sorted(c), [c[k] for k in sorted(c)], kind="bar") to see a histogram.
Constraints
0 <= shots <= 20000; the state has 1 to 10 qubits
Goals
- Sample measurement outcomes from Born-rule probabilities with a seeded random generator
- Label each outcome by its bit string, qubit 0 leftmost
- Collect the outcomes into counts, as a real quantum computer reports them