← Chapter 03: Probability Amplitudes and Interference

Quantum Computing · Chapter 03

Probability Amplitudes and Interference

How can two steps that each look random combine into a certain result?

Mithilesh Kumar

→ or Space to advance · N for notes · F for fullscreen

3.1

States and Transitions

One notation for what we know about a register and how a step changes it, applied to deterministic, nondeterministic, and probabilistic rules.

States

A one-bit register has two configurations, 0 and 1 (a \(k\)-bit register has \(2^k\)). Inspecting it, we always find exactly one.

A state records what we know before inspecting: a weight \(v_j\) for each configuration \(j\), written as a sum of kets

\[v_0\ket0+v_1\ket1 .\]
What we know\(v_0\)\(v_1\)State
The bit is 010\(\ket0\)
Either value is possible11\(\ket0+\ket1\)
A fair coin set the bit\(1/2\)\(1/2\)\(\tfrac12\ket0+\tfrac12\ket1\)

The form is the same; the meaning of the weights differs (possibility, or probability). Terms for the same configuration add: \(\tfrac14\ket0+\tfrac14\ket0=\tfrac12\ket0\). A state with weight 1 on one configuration is definite.

Transitions

A transition rule says which configurations may follow each configuration. Its state diagram has a circle per configuration and a weighted arrow \(i\to j\) for each allowed step.

For a step \(S\), the weight of the arrow from \(i\) to \(j\) is written

\[\bra jS\ket i\qquad\text{(read right to left: start at } i\text{, apply } S\text{, arrive at } j).\]

Absent arrows have weight 0. For NOT, written \(X\): \(\bra1X\ket0=\bra0X\ket1=1\) and \(\bra0X\ket0=\bra1X\ket1=0\).

A time-expanded diagram copies the configurations once per time step; a run of \(t\) steps is a path from time 0 to time \(t\). From 0, NOT gives the run \(0,1,0\).

Deterministic transitions: NOT applied twiceThe state diagram of NOT has one arrow from 0 to 1 and one from 1 to 0, each with weight 1. In the time-expanded diagram over two steps from 0, there is a single path, 0 to 1 to 0.State diagram0111Time-expanded diagram from 0t=0t=1t=211010101weight 1weight 0One arrow leaves each configuration, so the run has exactly one path.

Deterministic transitions

ConfigurationNext under NOTNext under RESET
010
100

From 0: NOT gives \(0,1,0\); RESET gives \(0,0,0\).

In both rules exactly one arrow leaves each configuration, so the start fixes the whole run: the rule is deterministic, and a definite state stays definite.

Tracing backward counts incoming arrows. Under NOT each configuration has one incoming arrow, so the previous configuration is known. Under RESET two arrows enter 0 and none enters 1, so the starting bit is lost.

Definition

A deterministic rule is reversible if every configuration also has exactly one incoming arrow.

Nondeterministic transitions

A nondeterministic rule may allow several successors. KEEP-OR-FLIP allows all four arrows on one bit, so from 0 two steps give four paths:

\[0\to0\to0,\quad 0\to1\to0,\quad 0\to0\to1,\quad 0\to1\to1.\]

A path is possible if every step is allowed; a configuration is reachable if some possible path ends there. Both 0 and 1 are reachable at time 2.

Nondeterministic acceptance is existential: accept if some run reaches an accepting configuration.

Nondeterminism is about possibility, not chance: more paths to an endpoint do not make it more likely. Frequencies need probabilities on the arrows.

Nondeterministic transitions: keep or flip, applied twiceThe keep-or-flip rule allows all four arrows. In the time-expanded diagram over two steps from 0, four paths are possible: two end at 0 and two end at 1.State diagram01yesyesyesyesTime-expanded diagram from 0t=0t=1t=2yesyesyesyesyesyes010101reachablereachableEvery arrow is allowed, so both end configurations are reachable.

Probabilistic transitions

Now the weight of \(i\to j\) is the conditional probability of \(j\) given \(i\):

\[\bra jS\ket i=P(j\mid i),\qquad \bra jS\ket i\ge0,\qquad \sum_j\bra jS\ket i=1.\]

The current configuration contains everything needed to predict the next step (the Markov property).

COIN replaces the bit by a fair coin flip: every arrow has weight \(1/2\). Two steps from 0: each path has probability \(\tfrac12\cdot\tfrac12=\tfrac14\), and two exclusive paths end at each configuration, so

\[P(c_2=0)=\tfrac14+\tfrac14=\tfrac12=P(c_2=1).\]
Probabilistic transitions: a fair coin step, applied twiceEvery arrow of the fair coin step has probability one half. In the time-expanded diagram over two steps from 0, each of the four paths has probability one quarter, and each end configuration has probability one half.State diagram011/21/21/21/2Time-expanded diagram from 0t=0t=1t=21/21/21/21/21/21/20101011/4+1/4=1/21/4+1/4=1/2Each path has probability 1/4; two paths reach each end.

3.2

Sum and Product Rules

All three models compute multi-step results the same way: multiply weights along a path, add the paths that meet.

The product rule along a path

A path \(i\to j\to k\) uses the arrow \(i\to j\) of step \(S\) and then the arrow \(j\to k\) of step \(T\). Its weight is the product

\[\bra kT\ket j\,\bra jS\ket i,\]

written right to left in the order the steps act.

  • Deterministic and nondeterministic rules (weights 0 or 1): the product is 1 exactly when every step on the path is allowed.
  • Probabilistic rules: the product is the probability of that history. The factors are conditional probabilities, combined by the Markov property, not independent events.

For COIN every two-step path has weight \(1/4\), and a \(t\)-step path has weight \(2^{-t}\).

The sum rule across paths

The total weight from \(i\) to \(k\) adds the weights of all paths, which differ only in the intermediate configuration \(j\):

\[\bra kTS\ket i=\sum_j\bra kT\ket j\,\bra jS\ket i .\]

Here \(TS\) is the two-step operation, \(S\) first (on the right).

  • Deterministic: the sum is 1 at the unique endpoint, 0 elsewhere.
  • Nondeterministic: the sum counts possible paths; positive means reachable.
  • Probabilistic: \(P_2(k\mid i)=\sum_jP(k\mid j)P(j\mid i)\), the probability of reaching \(k\).

The classical barrier

Every weight is nonnegative, so opening another path to \(k\) can only increase its total weight. No path can cancel another.

States and steps

A step updates a general state \(\sum_iv_i\ket i\) by the same rules: start at \(i\) with weight \(v_i\), follow the arrow to \(j\), and add over \(i\):

\[v_j^\prime=\sum_i\bra jS\ket i\,v_i,\qquad S\ket i=\sum_j\bra jS\ket i\,\ket j .\]

In ket form, \(\sum_iv_i\ket i\mapsto\sum_iv_iS\ket i\), collecting terms on each \(\ket j\). For example \(\mathrm{COIN}\ket0=\tfrac12\ket0+\tfrac12\ket1\), and any distribution \((v_0,v_1)\) becomes \((\tfrac12,\tfrac12)\): one coin flip erases the initial state.

A reversible deterministic rule permutes configurations, e.g. CNOT swaps \(\ket{10}\) and \(\ket{11}\). RESET and COIN map different states to the same state, so nothing acting on the result can undo them.

A probabilistic rule can be undone by another probabilistic rule only if it is already a reversible deterministic rule: nonnegative weights cannot re-concentrate a spread-out distribution.

3.3

Signed Weights

Keep the sum and product rules, but allow negative weights: contributions can now cancel.

Negative weights

Keep the diagrams, paths, and both rules, but allow a weight to be negative. Path weights are still products, so signs multiply:

\[\bigl(\tfrac12\bigr)\bigl(-\tfrac12\bigr)=-\tfrac14,\qquad \bigl(-\tfrac12\bigr)\bigl(-\tfrac12\bigr)=+\tfrac14 .\]

A path with an odd number of negative arrows contributes negatively; an even number, positively. An initial weight \(v_i\) contributes its sign too: the path \(i\to j\to k\) contributes \(\bra kS\ket j\bra jS\ket i\,v_i\).

A negative contribution is not a negative probability or a negative count of paths. It is a signed contribution to the sum at the endpoint, deciding whether the path reinforces or opposes the others arriving there.

For now this is a mathematical extension of the bookkeeping; Section 3.4 connects weights to observed probabilities.

Cancellation across paths

Two paths from \(i\) to \(k\), with weights \(a,c\) along the first and \(b,d\) along the second, give

\[\bra kSS\ket i=ca+db .\]

With \(a=b=c=\tfrac12\) and \(d=-\tfrac12\): \(\tfrac14-\tfrac14=0\). Both paths are present and nonzero, yet the endpoint receives nothing: cancellation.

  • Partial: \(\tfrac14-\tfrac18=\tfrac18\). Reinforcing: \(\tfrac14+\tfrac14=\tfrac12\).
  • Opening a path can now lower an endpoint’s weight; blocking one can raise it.
  • Only contributions at the same endpoint combine: \(\tfrac14\ket0-\tfrac14\ket1\) keeps both terms.
Cancellation at a common endpointTwo paths to the same configuration k contribute ca and db. With a=b=c=1/2 and d=−1/2, the contributions cancel although both paths are present. i → j1: a=1/2; i → j2: b=1/2; j1 → k: c=1/2; j2 → k: d=−1/2Cancellation at a common endpointa=1/2b=1/2c=1/2d=−1/2ij₁j₂kW(i→ k)=ca+db=1/4−1/4=0

Constructing the Hadamard step

Look for a one-bit step that spreads a definite input over both configurations but undoes itself. Give three arrows weight \(c\) and the arrow \(1\to1\) weight \(-c\).

Two steps from 0:

  • to 0: paths \(0\to0\to0\) and \(0\to1\to0\) give \(c^2+c^2=2c^2\);
  • to 1: paths \(0\to0\to1\) and \(0\to1\to1\) give \(c^2-c^2=0\).

Returning weight 1 to 0 requires \(2c^2=1\), so \(c=1/\sqrt2\). This is the Hadamard step:

\[H\ket0=\frac{\ket0+\ket1}{\sqrt2},\qquad H\ket1=\frac{\ket0-\ket1}{\sqrt2}.\]
Signed Hadamard transition with weight cThree arrows carry weight c and the arrow from 1 to 1 carries minus c. Over two steps from 0, two paths to 0 contribute c squared each, giving 2c squared; the paths to 1 contribute c squared and minus c squared, giving zero. Returning the original weight one therefore requires 2c squared equals one.State diagram01ccc−cTime-expanded diagram from 0t=0t=1t=2ccccc−c010101c²+c²=2c²c²−c²=0Returning to weight one requires 2c²=1.

Properties of the Hadamard step

  • From 1, the paths to 0 give \(\tfrac12-\tfrac12=0\) and the paths to 1 give \(\tfrac12+\tfrac12=1\). So \(\bra kHH\ket i=1\) if \(k=i\) and 0 otherwise: \(HH=I\).
  • In general \(H(v_0\ket0+v_1\ket1)=\frac{v_0+v_1}{\sqrt2}\ket0+\frac{v_0-v_1}{\sqrt2}\ket1\), and a second \(H\) returns \(v_0\ket0+v_1\ket1\).
  • Unlike COIN, the state after one step keeps the distinction between inputs in the sign of \(\ket1\). Replace \(-1/\sqrt2\) by \(+1/\sqrt2\), and both inputs map to the same state: cancellation and reversibility are lost.

The weights cannot be probabilities: they can be negative and need not add to 1. But from either input the squared weights do add to one:

\[c^2+c^2=c^2+(-c)^2=\tfrac12+\tfrac12=1 .\]

This suggests reading probabilities from squared weights while the signed weights govern composition. It motivates the quantum probability rule; it does not derive it.

3.4

Complex Amplitudes and Interference

A square root of NOT forces complex weights; we then state the probability rule, the conditions that preserve it, and the role of phase and path records.

A square root of NOT

Is there a step \(\sqrt X\) with \(\sqrt X\sqrt X=X\)? Neither \(I\) nor \(X\) works, since both square to \(I\).

Try a symmetric step with stay-weight \(a\) and switch-weight \(b\). Two steps return to the start with weight \(a^2+b^2\) and reach the other configuration with weight \(ab+ba\). We need

\[a^2+b^2=0,\qquad 2ab=1 .\]

With real \(a,b\), squares are nonnegative, so \(a=b=0\), contradicting \(2ab=1\). We need numbers whose squares can point in opposite directions.

In the complex plane, \(u+iv\) is the arrow \((u,v)\); multiplying by \(i\) turns an arrow by a quarter turn, so \(i^2=-1\).

Square root of NOT with weights a and bEach self-loop carries stay-weight a and each arrow between configurations carries switch-weight b. Over two steps from 0, staying twice contributes a squared and switching twice contributes b squared at 0. Staying then switching contributes ab and switching then staying contributes ba at 1. For the combined step to be NOT, a squared plus b squared must be zero and 2ab must be one.State diagram01bbaaTime-expanded diagram from 0t=0t=1t=2ababba010101a²+b²ab+ba=2abNOT requires a²+b²=0 and 2ab=1.

Complex amplitudes and the Born rule

Choose

\[a=\frac{1+i}{2},\qquad b=\frac{1-i}{2}.\]

Then \(a^2=\tfrac i2\), \(b^2=-\tfrac i2\), so \(a^2+b^2=0\), and \(2ab=\tfrac{(1+i)(1-i)}{2}=1\). Two steps give NOT exactly. Complex weights are called amplitudes; they obey the same sum and product rules.

Ordinary squares of amplitudes can be imaginary. The conjugate \(z^*=u-iv\) gives a nonnegative number:

\[zz^*=(u+iv)(u-iv)=u^2+v^2=|z|^2 .\]

Born rule

A configuration with amplitude \(v_j\) is observed with probability \(p(j)=|v_j|^2\).

Probabilities sum to one exactly when the state is normalized:

\[\sum_j|v_j|^2=1 .\]

For \(\sqrt X\): \(|a|^2=|b|^2=\tfrac14+\tfrac14=\tfrac12\), so one step from a definite bit gives probabilities \(\tfrac12,\tfrac12\).

Phase

Write a nonzero amplitude as an arrow of length \(r=|z|\) at angle \(\phi\) from the positive real axis. With Euler’s formula \(e^{i\phi}=\cos\phi+i\sin\phi\),

\[z=re^{i\phi},\qquad e^{i\alpha}e^{i\beta}=e^{i(\alpha+\beta)},\qquad |z|^2=r^2 .\]
  • \(\phi\) is the phase of the amplitude; multiplying amplitudes along a path adds their phases (angle-addition formulas).
  • Probability keeps the magnitude and discards the phase.
  • Positive and negative real weights are the phases \(0\) and \(\pi\); complex amplitudes supply every angle between.

Two states with identical probabilities can therefore differ in phase, and that difference can change the probabilities after a later step.

Conservation of probability

Along one path, magnitudes multiply: \(|z_1z_2|^2=|z_1|^2|z_2|^2\). Where paths meet, add amplitudes first, then square: \(|A+B|^2=|A|^2+|B|^2+AB^*+A^*B\).

For any step \(S\), updating \(v'_j=\sum_i\bra jS\ket i\,v_i\) and summing \(|v'_j|^2\) over all outputs \(j\) requires two conditions to keep total probability equal to 1:

\[\sum_j|\bra jS\ket i|^2=1\ \text{(each input)},\qquad \sum_j\bigl(\bra jS\ket i\bigr)^*\bra jS\ket k=0\ \ (i\ne k).\]

Interpreting \((\bra jS\ket i)^*\bra jS\ket k\) as a forward arrow \(k\to j\) followed by a reversed, conjugated arrow \(j\to i\) shows that return paths \(i\to j\to i\) add to 1 and cross paths \(k\to j\to i\) cancel to 0—so conservation of probability automatically makes \(S\) reversible. For \(\sqrt X\): \(a^*b+b^*a=-\tfrac i2+\tfrac i2=0\).

Path visualization of the cross-sum conditionLeft: in one step S from a superposition of 0 and 1, arrows of weight a and c meet at output 0 while arrows of weight b and d meet at output 1. Right: expanding the total probability pairs each forward arrow from 0 to j with a conjugated reversed arrow from j to 1; the two cross paths 0 to 0 to 1 (weight c star a) and 0 to 1 to 1 (weight d star b) must cancel to zero, while the return paths to 0 add to 1.1. Two inputs interfere at each output jInput i, kOutput jabcd0v₀1v₁0v'₀ = av₀ + cv₁cross term: a*c + c*a1v'₁ = bv₀ + dv₁cross term: b*d + d*bGain at j=0 must balance loss at j=1.2. Cross paths 0 → j → 1 must cancelStart 0Via jEnd iforward Sconjugated reversea*b*abc*d*010101|a|² + |b|² = 1(return paths add)c*a + d*b = 0(cross paths cancel)Paths 0 → 0 → 1 (weight c*a) and 0 → 1 → 1 (weight d*b) cancel to 0.

Interference and phase

For an endpoint \(k\): \(p(k)=\bigl|\sum_{\text{paths to }k}\text{amplitude}\bigr|^2\). Two Hadamard steps from 0: paths to 0 give \(\tfrac12+\tfrac12\), paths to 1 give \(\tfrac12-\tfrac12\). Squaring first would give \(\tfrac12\) at each. This is interference.

A common factor \(e^{i\theta}\) on every amplitude (global phase) changes no probability, now or later. A relative phase between amplitudes does. For

\[\frac{\ket0+e^{i\phi}\ket1}{\sqrt2}\ \xrightarrow{\ H\ }\ p(0)=\Bigl|\frac{1+e^{i\phi}}2\Bigr|^2=\frac{1+\cos\phi}{2}.\]

\(\phi=0\): \(p(0)=1\); \(\phi=\pi\): 0; \(\phi=\pi/2\): \(\tfrac12\). The phase flip \(Z\) (\(\ket1\mapsto-\ket1\)) adds \(\pi\): \(H,Z,H\) sends 0 to 1 with certainty.

Relative phase changes how paths combinePrepare equal-magnitude amplitudes with relative phase φ, then apply H. Only the routes to final configuration zero are shown. The phase changes their sum, even though it leaves the initial probabilities unchanged. start → zero: 1/√2; start → one: e^(iφ)/√2; zero → end: 1/√2; one → end: 1/√2Relative phase changes how paths combine1/√2e^(iφ)/√21/√21/√20010PreparationHp(0)=|(1+e^(iφ))/2|²=(1+cosφ)/2

Path information destroys interference

Add a record bit, initially 0. Configurations are now pairs: first bit, then record. Apply \(H\) to the first bit, then CNOT (first bit controls the record):

\[\begin{aligned}\ket{00}&\xrightarrow{H}\tfrac{1}{\sqrt2}\bigl(\ket{00}+\ket{10}\bigr)\xrightarrow{\mathrm{CNOT}}\tfrac{1}{\sqrt2}\bigl(\ket{00}+\ket{11}\bigr)\\&\xrightarrow{H}\tfrac12\bigl(\ket{00}+\ket{01}+\ket{10}-\ket{11}\bigr).\end{aligned}\]

The contributions \(+\tfrac12\) and \(-\tfrac12\) that used to cancel now end at different configurations, 10 and 11, so they cannot cancel. Probability that the first bit is 1: \(\tfrac14+\tfrac14=\tfrac12\).

Rule

Any part of the system that distinguishes the paths belongs to the configuration. Ignoring the record does not merge 10 and 11.

A retained record keeps the endpoints distinctEach left node has amplitude one over square root of two. Recording sends 00 to 00 and 10 to 11. The final H reaches 00, 10, 01, and 11 with amplitudes one half, one half, one half, and minus one half. A retained record keeps the endpoints distinct After first H Record written After final H Amplitude Each amplitude: 1/√2 1 1 CNOT 1/√2 1/√2 1/√2 −1/√2 00 +1/2 10 +1/2 01 +1/2 11 −1/2 00 00 10 11 Nodes name complete configurations; edge labels are transition weights.

Restoring interference by uncomputation

Apply a second CNOT before the final \(H\). Since CNOT is its own inverse, \(\ket{00}\mapsto\ket{00}\) and \(\ket{11}\mapsto\ket{10}\): the record returns to 0 on both branches, with amplitudes unchanged.

Now the final \(H\) again has two routes to each endpoint:

  • to \(\ket{10}\): \(+\tfrac12-\tfrac12=0\);
  • to \(\ket{00}\): \(\tfrac12+\tfrac12=1\).

The run returns to \(\ket{00}\) with certainty. This is why uncomputation (Section 2.4.3) is essential: records must be undone by reversing the gates that made them, not ignored.

Undo the record before the final HEach left node has amplitude one over square root of two. A second controlled NOT sends 00 to 00 and 11 to 10. The final H contributes plus one half twice to 00, and opposite one halves to 10. Undo the record before the final H After recording Record undone After final H Amplitude Each amplitude: 1/√2 1 1 CNOT 1/√2 −1/√2 1/√2 1/√2 00 1/2 + 1/2 = 1 10 1/2 − 1/2 = 0 00 00 11 10 Nodes name complete configurations; edge labels are transition weights.

Summary

  1. States assign a weight to each configuration; a step assigns weights \(\bra jS\ket i\) to arrows; multi-step weights follow the product rule along paths and the sum rule across paths.
  2. With nonnegative weights paths can only add. Signed weights allow cancellation, which yields the self-inverse Hadamard step.
  3. A square root of NOT needs complex amplitudes; probabilities are \(|v_j|^2\), and a valid step satisfies normalization and the cross-sum condition.
  4. Relative phase steers interference; any record that distinguishes paths destroys it unless it is uncomputed.

Notes