Fundamentals of Quantum Computing

1. The Wave Function ψ

In classical mechanics, the state of a particle is fully described by its position and velocity. Quantum mechanics replaces this with a wave function ψ(x,t) — a complex-valued mathematical function that encodes all knowable information about the particle.

The physical interpretation, given by Born's Rule, is that the probability of finding a particle near position x at time t is:

The wave function must be normalised — the total probability of finding the particle somewhere must equal 1:

2. Wave-Particle Duality

One of the most astonishing results of quantum mechanics is that matter exhibits both wave and particle behaviour. Louis de Broglie (1924) proposed that any particle with momentum p has an associated wavelength:

This was confirmed by the famous double-slit experiment: when electrons are fired one at a time toward a screen with two slits, they produce an interference pattern — possible only if each electron passes through both slits simultaneously as a wave. When we observe which slit the electron uses, the interference pattern vanishes.

3. The Schrödinger Equation

The evolution of the wave function over time is governed by the time-dependent Schrödinger equation:

Here, ℏ = h/2π is the reduced Planck constant and V(x) is the potential energy. For time-independent problems we seek stationary states satisfying:

This is an eigenvalue equation: ψ is the eigenfunction and E is the eigenvalue (energy).

4. Particle in a 1D Box — Eigenfunctions and Eigenvalues

The simplest quantum system: a particle trapped between x = 0 and x = L, with V = 0 inside and V = ∞ outside. Solving the TISE gives quantised solutions:

• Energy is quantised — only discrete values E₁, E₂, E₃,… are allowed
• The ground state (n=1) has nonzero zero-point energy — a consequence of the uncertainty principle
• Eigenfunctions are orthonormal: ∫ψₘ*ψₙ dx = δₘₙ
• Higher n → more nodes → higher energy

1. Limits of Classical Computing

Classical computers process information as bits (0 or 1). They are extraordinarily capable, but face fundamental physical limits:

• Moore's Law slowdown: Transistors are approaching atomic scale — quantum tunnelling causes errors
• Exponential scaling: Simulating n quantum particles requires 2ⁿ classical bits — infeasible beyond ~50 particles
• NP-hard problems: Factoring large numbers, combinatorial optimisation — no known efficient classical algorithm

2. Classical vs. Quantum Computing

3. Decoherence

Decoherence is the process by which quantum systems lose their quantum properties through interaction with the environment. It is the primary obstacle to building practical quantum computers.

• Caused by thermal noise, electromagnetic interference, vibration, cosmic rays
• Superconducting qubits require cooling to ~15 millikelvin (colder than deep space)
• Coherence time: typical qubits maintain their state for microseconds to milliseconds
• Quantum error-correcting codes (surface codes) use multiple physical qubits per logical qubit

4. Key Applications

Cryptography: Shor's algorithm can factor an n-bit integer in O(n³) quantum time vs O(exp(n^⅓)) classically — breaking RSA. Quantum Key Distribution (BB84) enables provably secure communication.

Optimisation: Grover's algorithm searches N-element databases in O(√N) vs O(N) classically. QAOA (Quantum Approximate Optimisation Algorithm) tackles logistics, finance, and drug design.

Simulation: Quantum computers can exactly simulate quantum systems (molecules, materials) in polynomial time — enabling drug discovery and materials science breakthroughs.

1. The Classical Bit

The classical bit is the fundamental unit of classical information. It takes exactly one of two values:

Physically realised as: high/low voltage in CMOS circuits, magnetic polarisation in hard drives, optical intensity in fibre optics. The state is always definite and non-destructive to read.

2. The Qubit

A qubit (quantum bit) is the fundamental unit of quantum information. Unlike a classical bit, it can exist in a superposition of |0⟩ and |1⟩:

where α, β ∈ ℂ are complex probability amplitudes satisfying the normalisation condition:

Upon measurement, the qubit collapses: it becomes |0⟩ with probability |α|² or |1⟩ with probability |β|².

3. Comparison: Bits vs. Qubits

1. Dirac (Bra-Ket) Notation

Paul Dirac introduced a compact, powerful notation for quantum states. A ket |ψ⟩ represents a quantum state as a column vector; a bra ⟨ψ| is its conjugate transpose (row vector):

A general qubit: |ψ⟩ = α|0⟩ + β|1⟩. The corresponding bra: ⟨ψ| = (α*, β*).

2. Inner Product and Outer Product

The inner product ⟨φ|ψ⟩ is a complex scalar (overlap amplitude):

Transition probability: P(|φ⟩→|ψ⟩) = |⟨φ|ψ⟩|²

The outer product |ψ⟩⟨φ| is a matrix (operator):

3. Matrix Representation of Quantum States

Quantum gates are unitary matrices (U†U = I). Key single-qubit gates:

Applying H to |0⟩: H|0⟩ = (|0⟩+|1⟩)/√2 — creates an equal superposition.

4. Tensor Products

To combine multiple qubits, we use the tensor product ⊗:

A general 2-qubit state: |ψ⟩ = α₀₀|00⟩ + α₀₁|01⟩ + α₁₀|10⟩ + α₁₁|11⟩

1. Vector Spaces and Hilbert Space

Quantum states live in a complex Hilbert space ℋ — a complete inner product space over ℂ. For a single qubit, ℋ = ℂ². Key properties:

• Closed under addition and scalar multiplication
• Inner product ⟨φ|ψ⟩ defines lengths and angles
• Completeness ensures convergence of limits

2. Complex Vectors and Qubits in ℂ²

Any normalised vector in ℂ² represents a valid qubit state. Using the global phase freedom, we can write:

The two real parameters θ and φ completely specify any single-qubit pure state — this is why a qubit maps bijectively to the surface of the Bloch sphere.

3. Bloch Sphere Representation

Every pure single-qubit state corresponds to a unique point on the Bloch sphere (unit sphere in ℝ³). Key points:

• North pole (θ=0): |0⟩
• South pole (θ=π): |1⟩
• Equator: equal superpositions — e.g. |+⟩=(|0⟩+|1⟩)/√2 and |−⟩=(|0⟩−|1⟩)/√2

1. Measurement in Quantum Mechanics

When we measure a qubit |ψ⟩ = α|0⟩ + β|1⟩ in the computational basis:

After measurement, the state collapses irreversibly to |0⟩ or |1⟩. Measurement is non-unitary and destructive.

2. Pauli Gates (X, Y, Z)

The three Pauli matrices form the basis of all single-qubit operations:

X (bit flip): X|0⟩=|1⟩, X|1⟩=|0⟩ — quantum NOT gate. Z (phase flip): Z|0⟩=|0⟩, Z|1⟩=-|1⟩. Y combines both: Y = iXZ.

3. Hadamard Gate

The most important single-qubit gate — creates superposition from basis states:

H is self-inverse: H² = I. Geometrically, H rotates the Bloch sphere 180° about the axis (X+Z)/√2.

4. Phase Shift Gates (S, T) and Rotation Gates

Phase gates shift the relative phase between |0⟩ and |1⟩ without changing measurement probabilities:

Rotation gates rotate the Bloch sphere about a specified axis by angle θ:

1. Two-Qubit State Space

Two qubits together live in the tensor product space ℂ²⊗ℂ² = ℂ⁴. The computational basis is:

A general two-qubit state: |ψ⟩ = α₀₀|00⟩ + α₀₁|01⟩ + α₁₀|10⟩ + α₁₁|11⟩, with Σ|αᵢⱼ|² = 1.

2. Tensor Products and Two-Qubit Operations

If qubit A is in state |a⟩ and qubit B is in |b⟩, the combined state is |a⟩⊗|b⟩. A 2-qubit gate is a 4×4 unitary matrix. Single-qubit gates extend to 2-qubit space via tensor products:

3. The CNOT Gate

The Controlled-NOT (CNOT) gate is the most important two-qubit gate. It flips the target qubit if and only if the control qubit is |1⟩:

CNOT + Hadamard = ability to create entangled (Bell) states from product states.

1. Quantum Entanglement

A two-qubit state is entangled if it cannot be written as a product of individual qubit states: |ψ⟩ ≠ |a⟩⊗|b⟩. Entangled particles exhibit correlations that have no classical explanation.

2. The Four Bell States

The maximally entangled two-qubit states are the Bell states (Bell basis):

Each Bell state is maximally entangled — measuring one qubit instantly fixes the other qubit's value.

3. Preparing Entangled States

To prepare |Φ⁺⟩ from |00⟩: apply H to the first qubit, then CNOT:

This two-gate circuit (H + CNOT) is the fundamental entanglement-generating circuit in quantum computing.

1. Projection Operators

A quantum measurement in basis {|eₖ⟩} is described by projection operators Pₖ = |eₖ⟩⟨eₖ|. They satisfy:

The probability of outcome k when measuring |ψ⟩ is: P(k) = ⟨ψ|Pₖ|ψ⟩. After measurement with outcome k, the state becomes: |ψ_after⟩ = Pₖ|ψ⟩/√P(k).

2. Hermitian Operators and Observables

Every physical observable is represented by a Hermitian (self-adjoint) operator Ô = Ô†. Key properties:

• All eigenvalues of Ô are real — they are the possible measurement outcomes
• Eigenvectors corresponding to distinct eigenvalues are orthogonal
• Hermitian operators are diagonalisable in an orthonormal basis

The expected value (average outcome) of repeated measurements is: ⟨Ô⟩ = ⟨ψ|Ô|ψ⟩.

3. Generalised Measurement — POVMs

More general measurements are described by Positive Operator-Valued Measures (POVMs): a set of positive operators {Mₖ} with ΣMₖ = I, giving outcome probabilities P(k) = ⟨ψ|Mₖ|ψ⟩. POVMs allow more flexible measurement schemes than projective measurements.

1. The EPR Paradox (1935)

Einstein, Podolsky, and Rosen argued that quantum mechanics is incomplete. Their thought experiment: if two particles are prepared in an entangled state, measuring particle A instantly determines particle B's state, no matter how far apart they are. EPR concluded that particle B must have had a definite value all along — described by hidden variables not present in QM.

2. Bell's Theorem (1964)

John Bell proved that any local hidden variable theory predicts correlations bounded by:

where E(a,b) is the correlation between measurements along directions a and b. Quantum mechanics predicts correlations that violate this inequality — they are stronger than any local hidden variable theory allows.

3. CHSH Inequality and Experimental Tests

The experimentally testable CHSH inequality:

Quantum mechanics predicts S_max = 2√2 ≈ 2.828. Landmark experiments by Aspect (1982), Hensen (2015, loophole-free), and others consistently find S > 2, violating Bell's inequality and ruling out local hidden variable theories.

1. Quantum Circuit Representation

A quantum circuit is a diagram representing a sequence of quantum gate operations on qubits. Conventions:

• Each horizontal wire represents one qubit
• Time flows left to right
• Gates are boxes or symbols placed on the wires
• Measurement is denoted by a meter symbol

2. Classical vs. Quantum Computations

1. Controlled Gates

A controlled gate applies a single-qubit unitary U to the target qubit only when the control qubit is |1⟩. General controlled-U matrix (2-qubit):

CNOT: U=X (flip target). CZ: U=Z (phase flip target). Both are symmetric in some bases.

Toffoli gate (CCNOT): two control qubits, one target. Flips target only when both controls = |1⟩. This makes it universal for classical reversible computation.

2. Universal Gate Sets

A set of gates is universal if any n-qubit unitary can be approximated to arbitrary precision. Key universal sets:

• {H, T, CNOT} — most common in fault-tolerant quantum computing
• {CNOT, all single-qubit gates} — universal for exact computation
• Toffoli + Hadamard — universal

1. Superdense Coding

Superdense coding allows Alice to send 2 classical bits to Bob by transmitting just 1 qubit, given pre-shared entanglement. Protocol:

• Alice and Bob share a Bell pair |Φ⁺⟩ = (|00⟩+|11⟩)/√2
• Alice encodes 2 bits by applying I, X, Z, or iY to her qubit
• Alice sends her qubit to Bob (1 qubit transmission)
• Bob applies CNOT then H to decode — recovers 2 classical bits

2. Quantum Teleportation

Quantum teleportation transmits an unknown qubit state from Alice to Bob using 2 classical bits and a pre-shared Bell pair — without transmitting the qubit itself:

1. Alice and Bob share |Φ⁺⟩
2. Alice applies CNOT then H to her target qubit and her half of the Bell pair
3. Alice measures both qubits — gets 2 classical bits (00, 01, 10, or 11)
4. Alice sends the 2 bits to Bob over classical channel
5. Bob applies the appropriate correction (I, X, Z, or XZ) to his qubit
6. Bob now has the exact state |ψ⟩ — teleportation complete!

3. Quantum Cryptography (BB84)

The BB84 protocol by Bennett and Brassard (1984) enables provably secure key exchange:

• Alice sends qubits in random bases (+/×) with random bits
• Bob measures in random bases
• They publicly compare bases (not bits) and keep matching results
• They check a subset for errors — any eavesdropping by Eve introduces ~25% error rate (detectable)

Security is guaranteed by the laws of physics — specifically the no-cloning theorem and the measurement disturbance principle.