/ mathematical foundationsBack to lab

AXIOMS → DERIVATIONS → EXPERIMENTS

Quantum computing proofs.

Finite-dimensional complex vectors. Conjugate inner products. Ideal gates. Each derivation states its assumptions before its conclusion.

DERIVATION 01

Unitaries preserve normalization

Assumptions / A normalized vector |ψ⟩ and U†U=I in a finite-dimensional complex Hilbert space.

‖Uψ‖² = ⟨ψ|U†U|ψ⟩ = ⟨ψ|ψ⟩ = 1
  1. The inner product uses the conjugate transpose, so (Uψ)†=ψ†U†.
  2. Substitute U†U=I. The norm is unchanged, and inverse evolution is U†.

Example / H†H=I. H|0⟩=(|0⟩+|1⟩)/√2 has total probability 1.

Study the related lesson →

DERIVATION 02

Born probabilities form a distribution

Assumptions / Orthogonal projectors Pₖ with ΣPₖ=I and a normalized |ψ⟩.

p(k)=⟨ψ|Pₖ|ψ⟩=‖Pₖψ‖² ≥ 0
Σₖ p(k)=⟨ψ|I|ψ⟩=1
  1. Projectors satisfy Pₖ†Pₖ=Pₖ, making each expectation a squared norm.
  2. Completeness makes the sum one. For p(k)>0, divide Pₖ|ψ⟩ by √p(k) to normalize the post-measurement state. Zero-probability outcomes cannot occur.

Example / [√3/2,i/2] gives probabilities 3/4 and 1/4.

Study the related lesson →

DERIVATION 03

Global phase is unobservable

Assumptions / A real χ and any measurement effect E.

⟨eⁱχψ|E|eⁱχψ⟩
= e⁻ⁱχeⁱχ ⟨ψ|E|ψ⟩ = ⟨ψ|E|ψ⟩
  1. The bra contributes the conjugate phase, cancelling the ket’s phase.
  2. A relative phase does not cancel across all components. Later gates can convert it into distinct probabilities.

Example / |+⟩ and |−⟩ share Z-basis bars; H maps them to different basis states.

Study the related lesson →

DERIVATION 04

Hermitian observables have real eigenvalues

Assumptions / A=A† and nonzero |v⟩ with A|v⟩=λ|v⟩.

λ⟨v|v⟩ = ⟨v|A|v⟩
= ⟨v|A|v⟩* = λ*⟨v|v⟩
  1. An expectation of a Hermitian operator equals its own complex conjugate.
  2. Since ⟨v|v⟩>0, divide to obtain λ=λ*. For two distinct eigenvalues, (λ−μ)⟨w|v⟩=0 establishes orthogonality.

Example / Z has real eigenvalues +1 and −1 and orthogonal eigenvectors |0⟩,|1⟩.

Study the related lesson →

DERIVATION 05

Two-qubit separability and Bell mixedness

Assumptions / A normalized pure state a|00⟩+b|01⟩+c|10⟩+d|11⟩.

M=[a b; c d]
product state ⇔ rank(M)=1 ⇔ ad−bc=0
Tr_B(|Φ⁺⟩⟨Φ⁺|)=I/2
  1. A product state’s coefficient matrix is an outer product of two vectors, hence rank one. Conversely any nonzero rank-one matrix factors that way.
  2. The Bell coefficient determinant is 1/2, so it is entangled. Taking the partial trace kills |00⟩⟨11| cross terms because ⟨1|0⟩=0, leaving equal local populations.

Example / Bell’s joint purity is 1; each subsystem purity is Tr((I/2)²)=1/2.

Study the related lesson →

DERIVATION 06

No universal unitary cloner

Assumptions / A unitary supposedly clones any pure state using the same blank register.

U|ψ,0⟩=|ψ,ψ⟩
U|φ,0⟩=|φ,φ⟩
s=⟨ψ|φ⟩ → s=s²
  1. Unitarity preserves the input inner product s. Tensor products multiply inner products, so the supposed outputs have overlap s².
  2. For |ψ⟩=|0⟩ and |φ⟩=|+⟩, s=1/√2 differs from s²=1/2: contradiction. Orthogonal known states can be copied, but not every unknown quantum state.

Example / CX copies computational-basis bits into a blank, but entangles a superposition instead of making two independent copies.

Study the related lesson →

DERIVATION 07

Entanglement does not enable signaling

Assumptions / A joint ρ_AB and a trace-preserving local channel on Alice with ΣKₘ†Kₘ=I; outcomes are not communicated.

ρ′_B=Tr_A Σₘ(Kₘ⊗I)ρ_AB(Kₘ†⊗I)
=Tr_A ρ_AB=ρ_B
  1. Inside the partial trace over Alice, move her factors cyclically and sum Kₘ†Kₘ to identity. Bob’s reduced density matrix is unchanged.
  2. Conditioning on a communicated outcome can change Bob’s conditional description, but learning that outcome requires a classical message.

Example / Bob sees 50/50 on a Bell pair whether Alice measures or not, until their records are compared.

Study the related lesson →

DERIVATION 08

Grover’s two-dimensional rotation

Assumptions / One marked item in N candidates, an exact phase oracle and diffuser D=2|s⟩⟨s|−I.

sin θ=1/√N
P(success after k iterations)=sin²((2k+1)θ)
  1. Split the uniform state into the marked direction and normalized unmarked direction. Its marked coefficient is sin θ.
  2. The oracle and diffuser are reflections; their product rotates by 2θ. The first peak occurs near k=π/(4θ)−1/2, giving O(√N) queries.

Example / N=4 gives θ=π/6; k=1 yields sin²(π/2)=1. Extra iterations can reduce success.

Study the related lesson →

DERIVATION 09

The variational energy bound

Assumptions / A Hermitian H with eigenbasis |n⟩ and lowest eigenvalue E₀; a normalized trial state.

|ψ⟩=Σₙcₙ|n⟩
⟨H⟩=Σₙ|cₙ|²Eₙ ≥ E₀Σₙ|cₙ|²=E₀
  1. Expand the state in the orthonormal energy eigenbasis; cross terms vanish.
  2. The energy is a convex combination of eigenvalues and cannot be below their minimum. Finite-shot estimates can fluctuate below it, so distinguish the true expectation from an estimate.

Example / For H=Z and Ry(θ)|0⟩, E(θ)=cos θ≥−1.

Study the related lesson →

DERIVATION 10

The quantum Fourier transform is unitary

Assumptions / Fₖₓ=exp(2πikx/N)/√N for integer indices 0,…,N−1.

(F†F)ₓᵧ=(1/N)Σₖexp(2πik(y−x)/N)=δₓᵧ
  1. For x=y, all N summands are one. For x≠y, the geometric-series ratio r is a nontrivial Nth root of unity.
  2. The sum (1−rᴺ)/(1−r) vanishes. Thus columns are orthonormal and F†F=I; the inverse uses the negative phase sign.

Example / N=4, x=1 gives [1,i,−1,−i]/2: distinct phases, equal probabilities.

Study the related lesson →

Further reading: Nielsen & Chuang, Quantum Computation and Quantum Information; John Preskill’s lecture notes on quantum computation. These are finite-dimensional derivations, not models of every hardware imperfection.