Simple Algorithm
Quantum Computing · Excited State · 20 min

Amplitudes Add, Probabilities Don’t

Constructive and destructive interference, path by path.

Flip a fair coin and flip it again: still random. Apply a Hadamard and apply it again: the identity. The whole difference is one minus sign, and learning to follow it path by path is the single most useful calculation in quantum computing.

What you’ll learn

  • Contrast stochastic evolution of probability vectors with unitary evolution of amplitude vectors.
  • Expand any circuit amplitude as a sum over computational-basis paths.
  • Derive the interference term and the conditions for perfect constructive and destructive interference.
  • Compute ⟨y∣H⊗n∣x⟩\bra{y}H^{\otimes n}\ket{x} and use it to explain the cancellations behind Deutsch–Jozsa.
  • Explain quantitatively why paths that leave different records do not interfere.

Two kinds of linear algebra

A randomized classical computer on nn bits is described by a probability vector p∈R2np \in \R^{2^n} with px≥0p_x \ge 0 and ∑xpx=1\sum_x p_x = 1. A random gate is a stochastic matrix SS: nonnegative entries, each column summing to 11, and p↦Spp \mapsto Sp.

A quantum computer is described by an amplitude vector α∈C2n\alpha \in \C^{2^n} with ∑x∣αx∣2=1\sum_x \abs{\alpha_x}^2 = 1. A gate is a unitary UU, and α↦Uα\alpha \mapsto U\alpha. Probabilities appear only at the end, through the Born rule P(y)=∣αy∣2P(y) = \abs{\alpha_y}^2.

FeatureRandomized classicalQuantum
Statepx≥0p_x \ge 0, ∥p∥1=1\norm{p}_1 = 1αx∈C\alpha_x \in \C, ∥α∥2=1\norm{\alpha}_2 = 1
Gatesstochastic: Syx≥0S_{yx}\ge 0, ∑ySyx=1\sum_y S_{yx} = 1unitary: U†U=IU^\dagger U = \id
One fair "mixing" stepF=12(1111)F = \tfrac12\begin{pmatrix}1&1\\1&1\end{pmatrix}H=12(111−1)H = \tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}
TwiceF2=FF^2 = F: still randomH2=IH^2 = \id: back to the start
Can contributions cancel?No: all terms are ≥0\ge 0Yes: terms carry signs and phases
Think first Can any stochastic matrix map the uniform distribution (12,12)(\tfrac12, \tfrac12) back to the point mass (1,0)(1, 0), the way HH maps ∣+⟩\ket{+} back to ∣0⟩\ket{0}?

Only by erasing its input. The second row needs 12S10+12S11=0\tfrac12 S_{10} + \tfrac12 S_{11} = 0 with S10,S11≥0S_{10}, S_{11} \ge 0, so both vanish, and then every input is sent to 00. A stochastic matrix can "un-randomize" only by forgetting. HH un-randomizes ∣+⟩\ket{+} while staying invertible: the information is stored in the signs, and cancellation retrieves it.

Paths through a circuit

Insert the resolution of the identity I=∑m∣m⟩ ⁣⟨m∣\id = \sum_{m} \dyad{m} between every pair of gates. Each sequence of intermediate basis states is a path, and the amplitude of a path is the product of the gate matrix elements along it:

⟨y∣UT⋯U1∣x⟩=∑x1,…,xT−1⟨y∣UT∣xT−1⟩⋯⟨x2∣U2∣x1⟩⟨x1∣U1∣x⟩.\bra{y}U_T\cdots U_1\ket{x} = \sum_{x_1,\dots,x_{T-1}} \bra{y}U_T\ket{x_{T-1}}\cdots\bra{x_2}U_2\ket{x_1}\bra{x_1}U_1\ket{x}.

Amplitudes of all paths with the same endpoints add. That is the precise meaning of interference.

DerivationHH = I, path by path
  1. ⟨y∣HH∣x⟩=∑m∈{0,1}⟨y∣H∣m⟩⟨m∣H∣x⟩\bra{y}HH\ket{x} = \sum_{m\in\{0,1\}} \bra{y}H\ket{m}\bra{m}H\ket{x}

    Insert I=∣0⟩ ⁣⟨0∣+∣1⟩ ⁣⟨1∣\id = \dyad{0} + \dyad{1} between the gates: two paths, through m=0m = 0 and m=1m = 1.

  2. ⟨m∣H∣x⟩=(−1)mx2\bra{m}H\ket{x} = \frac{(-1)^{mx}}{\sqrt2}

    Every Hadamard matrix element is ±12\pm\tfrac{1}{\sqrt2}; the sign is −- only for m=x=1m = x = 1.

  3. ⟨y∣HH∣x⟩=12∑m(−1)m(x⊕y)\bra{y}HH\ket{x} = \frac12\sum_{m}(-1)^{m(x\oplus y)}

    Multiply along each path and use (−1)my(−1)mx=(−1)m(x⊕y)(-1)^{my}(-1)^{mx} = (-1)^{m(x\oplus y)}.

  4. =12(1+(−1)x⊕y)=δxy= \frac12\left(1 + (-1)^{x\oplus y}\right) = \delta_{xy}

    For y=xy = x the two paths reinforce; for y≠xy \neq x they are +12+\tfrac12 and −12-\tfrac12 and cancel.

Predict before you look

Insert a phase gate P(φ)=diag⁡(1,eiφ)P(\varphi) = \diag(1, e^{i\varphi}) between the two Hadamards. The paths 0→0→10\to0\to1 and 0→1→10\to1\to1 now have amplitudes 12\tfrac12 and −12eiφ-\tfrac12 e^{i\varphi}. For φ=2π/3\varphi = 2\pi/3, what is P(1)P(1) in percent?

Show the answer

75 %

∣12(1−eiφ)∣2=12(1−cos⁡φ)=sin⁡2φ2\abs{\tfrac12(1 - e^{i\varphi})}^2 = \tfrac12(1-\cos\varphi) = \sin^2\tfrac{\varphi}{2}. At φ=2π/3\varphi = 2\pi/3 this is sin⁡2(π/3)=34\sin^2(\pi/3) = \tfrac34. This is exactly the Mach–Zehnder formula P(D1)=sin⁡2(φ/2)P(\text{D1}) = \sin^2(\varphi/2).

The interference term

DerivationTwo paths, one outcome
  1. P=∣a+b∣2=(a+b)∗(a+b)P = \abs{a + b}^2 = (a+b)^*(a+b)

    Two indistinguishable paths with amplitudes a=∣a∣eiαa = \abs{a}e^{i\alpha} and b=∣b∣eiβb = \abs{b}e^{i\beta}.

  2. =∣a∣2+∣b∣2+2 Re(a∗b)= \abs{a}^2 + \abs{b}^2 + 2\,\mathrm{Re}(a^*b)

    Expand. The cross term is what classical probability lacks.

  3. =∣a∣2+∣b∣2+2∣a∣∣b∣cos⁡(β−α)= \abs{a}^2 + \abs{b}^2 + 2\abs{a}\abs{b}\cos(\beta - \alpha)

    Only the relative phase β−α\beta-\alpha matters; a common phase drops out.

  4. (∣a∣−∣b∣)2  ≤  P  ≤  (∣a∣+∣b∣)2(\abs{a}-\abs{b})^2 \;\le\; P \;\le\; (\abs{a}+\abs{b})^2

    Constructive at β−α=0\beta - \alpha = 0, destructive at π\pi. Complete cancellation needs equal magnitudes and opposite phases.

With many paths, P=∣∑kak∣2=∑k∣ak∣2+∑j≠kaj∗akP = \abs{\sum_k a_k}^2 = \sum_k \abs{a_k}^2 + \sum_{j\ne k} a_j^* a_k. If the relative phases fluctuate randomly from run to run (a drifting arm length, a noisy field), every cross term averages to zero and you recover the classical rule P=∑k∣ak∣2P = \sum_k \abs{a_k}^2. Averaging over phases is one face of decoherence.

Check your understanding

Two indistinguishable paths to an outcome have amplitudes of magnitude 0.60.6 and 0.20.2. As their relative phase is varied, the probability of the outcome ranges over:

  1. exactly 0.400.40, whatever the phase
  2. 00 to 0.640.64
  3. 0.040.04 to 0.360.36
  4. 0.160.16 to 0.640.64
Show the answer

D. 0.160.16 to 0.640.64

PP runs from (0.6−0.2)2=0.16(0.6 - 0.2)^2 = 0.16 (opposite phases) to (0.6+0.2)2=0.64(0.6+0.2)^2 = 0.64 (aligned phases). Unequal magnitudes can never cancel completely.

Many paths at once: the Hadamard transform

On nn qubits, H⊗nH^{\otimes n} connects every input to every output with the same magnitude and a sign:

⟨y∣H⊗n∣x⟩=∏i=1n(−1)xiyi2=(−1)x⋅y2n,x⋅y=∑ixiyi mod 2.\bra{y}H^{\otimes n}\ket{x} = \prod_{i=1}^{n}\frac{(-1)^{x_i y_i}}{\sqrt2} = \frac{(-1)^{x\cdot y}}{\sqrt{2^n}}, \qquad x\cdot y = \textstyle\sum_i x_i y_i \bmod 2.

Sandwich a phase oracle Of∣x⟩=(−1)f(x)∣x⟩O_f\ket{x} = (-1)^{f(x)}\ket{x} between two Hadamard layers. There are 2n2^n paths from ∣0n⟩\ket{0^n} to each output ∣y⟩\ket{y}, one through each xx:

⟨y∣H⊗nOfH⊗n∣0n⟩=12n∑x(−1)f(x)+x⋅y.\bra{y}H^{\otimes n}O_fH^{\otimes n}\ket{0^n} = \frac{1}{2^n}\sum_{x}(-1)^{f(x) + x\cdot y}.

For y=0ny = 0^n this is the average of (−1)f(x)(-1)^{f(x)}. If ff is constant it is ±1\pm1 (all paths aligned). If ff is balanced it is exactly 00 (perfect cancellation). That is the Deutsch–Jozsa algorithm: one query decides what classically needs 2n−1+12^{n-1}+1 deterministic queries.

When paths stop interfering

"Indistinguishable" has a precise meaning: the paths must end in the same state of everything, including any ancilla or environment they touched. If path kk leaves a record ∣ek⟩\ket{e_k}, the joint amplitude for outcome yy is ∑kak∣ek⟩\sum_k a_k\ket{e_k}, and

P(y)=∥∑kak∣ek⟩∥2=∑k∣ak∣2+∑j≠kaj∗ak ⟨ej∣ek⟩P(y) = \Big\lVert \sum_k a_k \ket{e_k} \Big\rVert^2 = \sum_k \abs{a_k}^2 + \sum_{j\neq k} a_j^* a_k\, \braket{e_j|e_k}
Each interference term is weighted by the overlap of the records. Orthogonal records (⟨ej∣ek⟩=0\braket{e_j|e_k} = 0) leave only the classical sum.
Check your understanding

Two paths reach outcome yy with amplitudes 12\tfrac12 and 12\tfrac12. Along the first an ancilla is left in ∣0⟩\ket{0}, along the second in ∣1⟩\ket{1}. What is P(y)P(y)?

  1. 11
  2. 12\tfrac12
  3. 00
  4. 14\tfrac14
Show the answer

B. 12\tfrac12

The records are orthogonal, so the cross term vanishes: P(y)=14+14=12P(y) = \tfrac14 + \tfrac14 = \tfrac12. With identical records the paths would reinforce to ∣12+12∣2=1\abs{\tfrac12 + \tfrac12}^2 = 1.

Key takeaways

  • Gates are unitary maps on amplitude vectors; probabilities appear only at the end, as ∣amplitude∣2\abs{\text{amplitude}}^2.
  • Every circuit amplitude is a sum over computational paths of products of gate matrix elements.
  • ∣a+b∣2=∣a∣2+∣b∣2+2 Re(a∗b)\abs{a+b}^2 = \abs{a}^2 + \abs{b}^2 + 2\,\mathrm{Re}(a^*b): constructive, destructive, and, under random phases, the classical sum.
  • ⟨y∣H⊗n∣x⟩=(−1)x⋅y/2n\bra{y}H^{\otimes n}\ket{x} = (-1)^{x\cdot y}/\sqrt{2^n} turns a function into a signed average: constant ff reinforces, balanced ff cancels.
  • Paths interfere only to the extent that their records overlap: each cross term carries a factor ⟨ej∣ek⟩\braket{e_j|e_k}.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

In the circuit HZHHZH acting on ∣0⟩\ket{0}, what are the amplitudes of the two paths that end in ∣0⟩\ket{0}?

  1. +12+\tfrac12 and +12+\tfrac12
  2. +12+\tfrac12 and −12-\tfrac12
  3. +12+\tfrac{1}{\sqrt2} and −12-\tfrac{1}{\sqrt2}
  4. +14+\tfrac14 and −14-\tfrac14
Show the answer

B. +12+\tfrac12 and −12-\tfrac12

Via m=0m=0: 12⋅1⋅12=12\tfrac{1}{\sqrt2}\cdot 1\cdot\tfrac{1}{\sqrt2} = \tfrac12. Via m=1m=1: 12⋅(−1)⋅12=−12\tfrac{1}{\sqrt2}\cdot(-1)\cdot\tfrac{1}{\sqrt2} = -\tfrac12, the minus coming from ZZ. They cancel, and the paths to ∣1⟩\ket{1} reinforce, so HZH∣0⟩=∣1⟩HZH\ket0 = \ket1.

Question 2

What is ⟨111∣H⊗3∣101⟩\bra{111}H^{\otimes 3}\ket{101}?

  1. +18+\tfrac{1}{\sqrt8}
  2. −18-\tfrac{1}{\sqrt8}
  3. 18\tfrac18
  4. 00
Show the answer

A. +18+\tfrac{1}{\sqrt8}

x⋅y=1⋅1+0⋅1+1⋅1=2≡0(mod2)x\cdot y = 1\cdot1 + 0\cdot1 + 1\cdot1 = 2 \equiv 0 \pmod 2, so the sign is ++ and the magnitude is 2−3/2=182^{-3/2} = \tfrac{1}{\sqrt8}.

Question 3

In H⊗nOfH⊗n∣0n⟩H^{\otimes n}O_fH^{\otimes n}\ket{0^n}, the function ff equals 11 on exactly a quarter of all inputs. What is the probability of measuring 0n0^n?

  1. 34\tfrac34
  2. 12\tfrac12
  3. 14\tfrac14
  4. 116\tfrac{1}{16}
Show the answer

C. 14\tfrac14

The amplitude is the average of (−1)f(x)(-1)^{f(x)}: 34⋅(+1)+14⋅(−1)=12\tfrac34\cdot(+1) + \tfrac14\cdot(-1) = \tfrac12. The probability is its square, 14\tfrac14.

Question 4

The relative phase θ\theta between two paths is uniformly random from run to run. Why does the average of ∣a+b eiθ∣2\abs{a + b\,e^{i\theta}}^2 equal ∣a∣2+∣b∣2\abs{a}^2 + \abs{b}^2?

  1. Because random phases make the amplitudes themselves vanish
  2. Because the Born rule stops applying to noisy systems
  3. Because a random phase is a global phase and is unobservable
  4. Because the interference term 2∣a∣∣b∣cos⁡(θ+const)2\abs{a}\abs{b}\cos(\theta + \text{const}) averages to zero
Show the answer

D. Because the interference term 2∣a∣∣b∣cos⁡(θ+const)2\abs{a}\abs{b}\cos(\theta + \text{const}) averages to zero

The only θ\theta-dependent part is the cross term, proportional to cos⁡(θ+const)\cos(\theta + \text{const}), whose average over a full period is 00. What remains is the classical sum of probabilities.

Go deeper

Further reading

  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §1.4 (Cambridge, 10th anniv. ed., 2010).
  • R. P. Feynman & A. R. Hibbs, Quantum Mechanics and Path Integrals (McGraw-Hill, 1965).
  • D. Deutsch & R. Jozsa, "Rapid solution of problems by quantum computation", Proc. R. Soc. Lond. A 439, 553 (1992).
  • S. Aaronson, Quantum Computing Since Democritus, Ch. 9 (Cambridge, 2013).