Day 4 — Running Circuits

Math Prep

Solve this BEFORE lesson.md. Day 4 is about running circuits on real IBM hardware (backends, ISA circuits, execution modes). The math that makes the lesson make sense: why a tiny native gate set suffices, what connectivity costs, and what a "shot" actually is.

Requires: Day 1–3 math prep. Video back-up: Watrous Lesson 03 Quantum Circuits, Lesson 06 Quantum Algorithmic Foundations; notes in resource-artifactory/notes/video-notes/.

1. Universality — why `{rz, sx, x, cz}` is enough

A gate set is universal if any $n$ -qubit unitary can be approximated to arbitrary accuracy by circuits over that set. Two math facts power this:

Single-qubit universality: any 1q unitary $= e^{i\gamma} R_z(\phi) R_y(\theta) R_z(\lambda)$ (Euler, Day 2), and the $R_y$ can be traded for $R_z$ 's and $\sqrt{X}$ 's. So rz + sx generate all 1q gates exactly (angles are continuous).
Two-qubit escalation: any multi-qubit unitary decomposes into 1q gates + CNOTs (or CZ/ECR — interconvertible with 1q gates, Day 2 table). A general 2-qubit unitary needs at most 3 CNOTs; a general $n$ -qubit unitary needs $O(4^n)$ elementary gates (why arbitrary unitary gates get expensive fast).

ISA (Instruction Set Architecture) circuit = a circuit already expressed in the backend's native gates AND respecting its qubit connectivity. The math above guarantees the transpiler can always get there; the lesson's rule "primitives accept ISA circuits only" is the engineering consequence.

Discrete sets like $\{H, T, CX\}$ are also universal, but only approximately — the Solovay–Kitaev theorem says any 1q gate can be approximated to error $\varepsilon$ with $O(\log^c(1/\varepsilon))$ gates from the set. (Relevant to fault tolerance, not to IBM's continuous-angle hardware.)

2. Connectivity math — heavy-hex and SWAP overhead

IBM devices use a heavy-hex lattice: qubits have degree ≤ 3; most have 2 neighbors. Consequences you can quantify:

A 2q gate between qubits at graph distance $d$ costs $d-1$ SWAPs = $3(d-1)$ CNOT-equivalents (Day 2: SWAP = 3 CX).
Each 2q gate has error ~ $10^{-2}$ – $10^{-3}$ on current hardware, vs ~ $10^{-4}$ for 1q gates — routing dominates error. This is why optimization_level and layout matter, and why depth/2q-count are THE metrics to minimize.

Error accumulation model (rough but exam-useful): total success probability ≈ product of per-gate fidelities, $\prod_g f_g \approx e^{-\sum_g (1-f_g)}$ . A circuit with 100 2q gates at 99.5% fidelity: $0.995^{100} \approx 0.61$ — 39% of shots corrupted. Decoherence adds a time budget: populations relax on timescale $T_1$ and phases randomize on $T_2$ — deep circuits fail even with perfect gates.

3. The measurement postulate, precisely

Given $|\psi\rangle = \sum_x \alpha_x |x\rangle$ on $n$ qubits:

Measuring all qubits: outcome bitstring $x$ with $P(x) = |\alpha_x|^2$ ; state collapses to $|x\rangle$ .
Measuring a subset $S$ : $P(\text{outcome } s) = \sum_{x:\, x_S = s} |\alpha_x|^2$ (sum over consistent completions), and the post-measurement state is the renormalized projection:

|\psi'\rangle = \frac{(\Pi_s \otimes I)|\psi\rangle}{\sqrt{P(s)}}

Example: $\tfrac{1}{\sqrt2}(|00\rangle + |11\rangle)$ , measure q0, get 1 (prob ½) ⇒ state becomes $|11\rangle$ — the other qubit is now determined. That's the "spooky" correlation, and also just linear algebra.

Measurement is irreversible and not unitary; repeating the same measurement repeats the same outcome (the state is already collapsed). This is why reset (measure + conditional X) is allowed mid-circuit but can't be inverted.

4. Shots = sampling a multinomial distribution

One execution of a circuit = one sample from $P(x) = |\alpha_x|^2$ . Running $N$ shots gives counts $\{n_x\}$ , $\sum n_x = N$ ; the estimate $\hat p_x = n_x/N$ has standard error

\sigma_{\hat p_x} = \sqrt{\frac{p_x(1-p_x)}{N}} \;\lesssim\; \frac{1}{2\sqrt N}

So: 4× more shots ⇒ 2× less statistical noise. 1024 shots ⇒ ~1.5% worst-case error; 10 000 shots ⇒ ~0.5%. Shots reduce statistical error only — they do nothing against gate/decoherence (systematic) error. That split — statistical (shots) vs systematic (mitigation) — is the conceptual backbone of Days 5–6.

5. Expectation values from counts (bridge to Day 5/6)

From counts you can estimate any diagonal observable:

\widehat{\langle Z_i \rangle} = \frac{N_{\text{bit } i = 0} - N_{\text{bit } i = 1}}{N},\qquad \widehat{\langle Z_i Z_j\rangle} = \frac{N_{\text{parity even}} - N_{\text{parity odd}}}{N}

Non-diagonal observables (X, Y terms) require a basis change before measuring: measure X by applying H then measuring Z (because $X = HZH$ ); measure Y by applying $S^\dagger$ then H then measuring Z. One circuit per measurement basis — that's why Estimator decomposes observables into Pauli terms and groups commuting ones.

PROBLEMS

P1. Verify that $R_z(\pi/2)\,\sqrt{X}\,R_z(\pi/2)$ equals H up to a global phase.

P2. On a line topology 0–1–2–3–4, what is the CNOT-equivalent cost of cx(0, 4) if the router SWAPs qubit 0's state along to qubit 3 (no swap-back)?

P3. A circuit has 60 two-qubit gates, each with fidelity 0.99. Estimate the probability that a shot is error-free. Would doubling shots help the bias in your results?

P4. $|\psi\rangle = \tfrac{1}{2}|00\rangle + \tfrac{1}{2}|01\rangle + \tfrac{1}{\sqrt2}|11\rangle$ (labels $|q_1 q_0\rangle$ ). Measure q0 only. Give both outcome probabilities and the post-measurement state for outcome 1.

P5. You estimate $p = 0.5$ with 1024 shots. Give the standard error. How many shots for standard error 0.005?

P6. Why can't you measure $\langle X \rangle$ directly from computational-basis counts of the bare circuit? Give the 1-gate fix and the formula.

P7. (Concept) A backend's native set is {ecr, id, rz, sx, x}. Your circuit uses h and cx. Must the transpiler change it? Could two different transpilations both be correct?

ANSWERS

A1. $\sqrt X = \tfrac12\begin{pmatrix}1+i&1-i\\1-i&1+i\end{pmatrix}$ ; sandwich with $R_z(\pi/2) = \mathrm{diag}(e^{-i\pi/4}, e^{i\pi/4})$ on both sides. Multiplying out gives $e^{-i\pi/4}\cdot\tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$ — H up to global phase $e^{-i\pi/4}$ . (Transpile h onto a {rz,sx} target and you'll see exactly rz(π/2) sx rz(π/2).)

A2. Distance 0→4 is 4 ⇒ 3 SWAPs (0→1→2→3) then 1 CNOT: $3\times3 + 1 = \textbf{10}$ CNOT-equivalents.

A3. $0.99^{60} \approx e^{-0.6} \approx 0.55$ . Doubling shots does not help — gate error is systematic; more shots only sharpen your estimate of the (biased) distribution.

A4. $P(q_0{=}0) = |\tfrac12|^2 = \tfrac14$ (only $|00\rangle$ has $q_0=0$ ); $P(q_0{=}1) = |\tfrac12|^2 + |\tfrac{1}{\sqrt2}|^2 = \tfrac34$ . Post-measurement (outcome 1): $\frac{\tfrac12|01\rangle + \tfrac{1}{\sqrt2}|11\rangle}{\sqrt{3/4}} = \tfrac{1}{\sqrt3}|01\rangle + \sqrt{\tfrac{2}{3}}|11\rangle$ .

A5. $\sigma = \sqrt{0.25/1024} = \tfrac{0.5}{32} \approx 0.0156$ . For $\sigma = 0.005$ : $N = 0.25/0.005^2 = 10\,000$ shots.

A6. Computational-basis counts only reveal $|\alpha_x|^2$ — blind to phases, and $\langle X\rangle$ lives in the phases ( $|+\rangle$ vs $|-\rangle$ both give 50/50 Z-counts). Fix: append h (rotates X-basis to Z-basis), then $\langle X\rangle = P(0) - P(1)$ of the new counts.

A7. Yes — h and cx are not native, so they must be rewritten into rz/sx and ecr(+1q) forms. And yes — decompositions are not unique (different layouts, routings, equivalent sequences); correctness = same unitary (up to global phase) / same measurement statistics, not same gate list.

Self-check: you can explain "ISA circuit" in one sentence of math, cost out a routed CNOT, split statistical vs systematic error, and give the basis-change trick for measuring X.

1. Universality — why {rz, sx, x, cz} is enough