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⟩ 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 n bits is described by a probability vector p∈R2n with px≥0 and ∑xpx=1. A random gate is a stochastic matrixS: nonnegative entries, each column summing to 1, and p↦Sp.
A quantum computer is described by an amplitude vector α∈C2n with ∑x∣αx∣2=1. A gate is a unitaryU, and α↦Uα. Probabilities appear only at the end, through the Born ruleP(y)=∣αy∣2.
Feature
Randomized classical
Quantum
State
px≥0, ∥p∥1=1
αx∈C, ∥α∥2=1
Gates
stochastic: Syx≥0, ∑ySyx=1
unitary: U†U=I
One fair "mixing" step
F=21(1111)
H=21(111−1)
Twice
F2=F: still random
H2=I: back to the start
Can contributions cancel?
No: all terms are ≥0
Yes: terms carry signs and phases
Think first Can any stochastic matrix map the uniform distribution (21,21) back to the point mass (1,0), the way H maps ∣+⟩ back to ∣0⟩?
Only by erasing its input. The second row needs 21S10+21S11=0 with S10,S11≥0, so both vanish, and then every input is sent to 0. A stochastic matrix can "un-randomize" only by forgetting. H un-randomizes ∣+⟩ 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∣ 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:
Amplitudes of all paths with the same endpoints add. That is the precise meaning of interference.
DerivationHH = I, path by path
⟨y∣HH∣x⟩=m∈{0,1}∑⟨y∣H∣m⟩⟨m∣H∣x⟩
Insert I=∣0⟩⟨0∣+∣1⟩⟨1∣ between the gates: two paths, through m=0 and m=1.
⟨m∣H∣x⟩=2(−1)mx
Every Hadamard matrix element is ±21; the sign is − only for m=x=1.
⟨y∣HH∣x⟩=21m∑(−1)m(x⊕y)
Multiply along each path and use (−1)my(−1)mx=(−1)m(x⊕y).
=21(1+(−1)x⊕y)=δxy
For y=x the two paths reinforce; for y=x they are +21 and −21 and cancel.
Predict before you look
Insert a phase gate P(φ)=diag(1,eiφ) between the two Hadamards. The paths 0→0→1 and 0→1→1 now have amplitudes 21 and −21eiφ. For φ=2π/3, what is P(1) in percent?
Show the answer
75 %
21(1−eiφ)2=21(1−cosφ)=sin22φ. At φ=2π/3 this is sin2(π/3)=43. This is exactly the Mach–Zehnder formula P(D1)=sin2(φ/2).
The interference term
DerivationTwo paths, one outcome
P=∣a+b∣2=(a+b)∗(a+b)
Two indistinguishable paths with amplitudes a=∣a∣eiα and b=∣b∣eiβ.
=∣a∣2+∣b∣2+2Re(a∗b)
Expand. The cross term is what classical probability lacks.
=∣a∣2+∣b∣2+2∣a∣∣b∣cos(β−α)
Only the relative phase β−α matters; a common phase drops out.
(∣a∣−∣b∣)2≤P≤(∣a∣+∣b∣)2
Constructive at β−α=0, destructive at π. Complete cancellation needs equal magnitudes and opposite phases.
With many paths, P=∣∑kak∣2=∑k∣ak∣2+∑j=kaj∗ak. 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∣2. Averaging over phases is one face of decoherence.
Check your understanding
Two indistinguishable paths to an outcome have amplitudes of magnitude 0.6 and 0.2. As their relative phase is varied, the probability of the outcome ranges over:
exactly 0.40, whatever the phase
0 to 0.64
0.04 to 0.36
0.16 to 0.64
Show the answer
D.0.16 to 0.64
P runs from (0.6−0.2)2=0.16 (opposite phases) to (0.6+0.2)2=0.64 (aligned phases). Unequal magnitudes can never cancel completely.
Many paths at once: the Hadamard transform
On n qubits, H⊗n connects every input to every output with the same magnitude and a sign:
Sandwich a phase oracleOf∣x⟩=(−1)f(x)∣x⟩ between two Hadamard layers. There are 2n paths from ∣0n⟩ to each output ∣y⟩, one through each x:
⟨y∣H⊗nOfH⊗n∣0n⟩=2n1x∑(−1)f(x)+x⋅y.
For y=0n this is the average of (−1)f(x). If f is constant it is ±1 (all paths aligned). If f is balanced it is exactly 0 (perfect cancellation). That is the Deutsch–Jozsa algorithm: one query decides what classically needs 2n−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 k leaves a record ∣ek⟩, the joint amplitude for outcome y is ∑kak∣ek⟩, and
Each interference term is weighted by the overlap of the records. Orthogonal records (⟨ej∣ek⟩=0) leave only the classical sum.
Check your understanding
Two paths reach outcome y with amplitudes 21 and 21. Along the first an ancilla is left in ∣0⟩, along the second in ∣1⟩. What is P(y)?
1
21
0
41
Show the answer
B.21
The records are orthogonal, so the cross term vanishes: P(y)=41+41=21. With identical records the paths would reinforce to 21+212=1.
Key takeaways
Gates are unitary maps on amplitude vectors; probabilities appear only at the end, as ∣amplitude∣2.
Every circuit amplitude is a sum over computational paths of products of gate matrix elements.
∣a+b∣2=∣a∣2+∣b∣2+2Re(a∗b): constructive, destructive, and, under random phases, the classical sum.
⟨y∣H⊗n∣x⟩=(−1)x⋅y/2n turns a function into a signed average: constant f reinforces, balanced f cancels.
Paths interfere only to the extent that their records overlap: each cross term carries a factor ⟨ej∣ek⟩.
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 HZH acting on ∣0⟩, what are the amplitudes of the two paths that end in ∣0⟩?
+21 and +21
+21 and −21
+21 and −21
+41 and −41
Show the answer
B.+21 and −21
Via m=0: 21⋅1⋅21=21. Via m=1: 21⋅(−1)⋅21=−21, the minus coming from Z. They cancel, and the paths to ∣1⟩ reinforce, so HZH∣0⟩=∣1⟩.
Question 2
What is ⟨111∣H⊗3∣101⟩?
+81
−81
81
0
Show the answer
A.+81
x⋅y=1⋅1+0⋅1+1⋅1=2≡0(mod2), so the sign is + and the magnitude is 2−3/2=81.
Question 3
In H⊗nOfH⊗n∣0n⟩, the function f equals 1 on exactly a quarter of all inputs. What is the probability of measuring 0n?
43
21
41
161
Show the answer
C.41
The amplitude is the average of (−1)f(x): 43⋅(+1)+41⋅(−1)=21. The probability is its square, 41.
Question 4
The relative phase θ between two paths is uniformly random from run to run. Why does the average of a+beiθ2 equal ∣a∣2+∣b∣2?
Because random phases make the amplitudes themselves vanish
Because the Born rule stops applying to noisy systems
Because a random phase is a global phase and is unobservable
Because the interference term 2∣a∣∣b∣cos(θ+const) averages to zero
Show the answer
D. Because the interference term 2∣a∣∣b∣cos(θ+const) averages to zero
The only θ-dependent part is the cross term, proportional to cos(θ+const), whose average over a full period is 0. What remains is the classical sum of probabilities.