Principles of quantum computing
Foundations of quantum computing: qubits, superposition, measurement postulates, entanglement, gates and circuits, no‑cloning, and simple algorithms (Deutsch, Grover idea).
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Quantum computing promises exponential or quadratic speedups for certain problems (e.g., factoring, unstructured search), which impacts cybersecurity, optimization, signal processing, and materials simulation. Engineers need the basic principles to understand emerging hardware (superconducting qubits, trapped ions), to model quantum systems, and to judge when a quantum approach is practical.
Key ideas
- Superposition: A qubit can exist in a linear combination of basis states simultaneously. On measurement in the computational basis, it gives a classical outcome probabilistically.
- Global and relative phase: Multiplying a state by a global phase e^{iϕ} does not change any measurement probabilities. Relative phase between components (phase difference between α and β) affects interference.
- Normalization: The total probability is 1, so amplitudes satisfy |α|² + |β|² = 1 for a single qubit.
- Bloch sphere: Any single-qubit pure state can be written as |ψ⟩ = cos(θ/2)|0⟩ + e^{iφ} sin(θ/2)|1⟩, represented by point (θ, φ) on a unit sphere. Poles are |0⟩ (north) and |1⟩ (south). Equator states have equal probabilities with varying relative phase.
- Composite systems and tensor product: For two qubits A and B with states |ψ⟩ₐ and |φ⟩ᵦ, the joint state is |ψ⟩ₐ ⊗ |φ⟩ᵦ. The computational basis is {|00⟩, |01⟩, |10⟩, |11⟩}.
- Entanglement: A joint state is entangled if it cannot be written as a tensor product of single-qubit states. Example Bell state: |Φ+⟩ = (|00⟩ + |11⟩)/√2.
- Measurement postulate (projective measurement): Measuring in an orthonormal basis {|i⟩} yields outcome i with probability |⟨i|ψ⟩|², and post-measurement state is |i⟩ (assuming ideal, projective, von Neumann measurement). Measurement is inherently probabilistic and generally irreversible.
- Unitary evolution: Closed quantum systems evolve via unitary operators U satisfying U†U = I. Quantum gates are finite-dimensional unitaries acting on qubits.
- Pauli operators: X (bit-flip), Z (phase-flip), Y (combined). They generate rotations and are basic gates.
- Hadamard gate (H): Creates equal superpositions and is central to interference-based algorithms.
- Controlled gates: A gate applied to a target qubit conditioned on the control qubit’s state, e.g., CNOT flips target if control is |1⟩.
- No-cloning theorem: It is impossible to construct a unitary operation that copies an arbitrary unknown quantum state.
- Quantum circuit model: Computation is a sequence of gates acting on qubits, followed by measurements. This is the standard abstraction for algorithms like Deutsch–Jozsa, Grover, and Shor.
- Oracle (black-box) model: Many quantum algorithms are phrased in terms of querying an oracle U_f that encodes a classical function f in a reversible way.
- Quantum speedup ideas: Interference to amplify correct answers (Grover), and periodicity finding via the Quantum Fourier Transform (Shor).
Exact statements and common derivations:
- Postulates of quantum mechanics for quantum computation (finite-dimensional version)
- State space postulate: The state of an isolated quantum system is a unit vector |ψ⟩ in a complex Hilbert space ℋ with an inner product. For n qubits, ℋ = (ℂ²)^{⊗ n}.
- Evolution postulate: The time evolution of a closed system is unitary: |ψ(t)⟩ = U(t)|ψ(0)⟩, with U(t) = e^{−iHt/ħ} for Hamiltonian H (time-independent case).
- Measurement postulate: Measurement is described by a set of orthogonal projectors {P_i} with P_i P_j = δ_{ij} P_i, P_i = P_i†, and ∑_i P_i = I. Outcome i occurs with probability p_i = ⟨ψ|P_i|ψ⟩ and state collapses to P_i|ψ⟩/√p_i.
- Composition postulate: The state space of a composite system is the tensor product of subsystems. Assumptions: Ideal, noiseless, closed-system dynamics before measurement; measurement is projective; bases are orthonormal.
- No-cloning theorem (statement and standard proof)
- Statement: There is no unitary operation U and fixed “blank” state |b⟩ such that U(|ψ⟩ ⊗ |b⟩) = |ψ⟩ ⊗ |ψ⟩ for all single-qubit states |ψ⟩.
- Proof (by contradiction): Assume such U and |b⟩ exist. Then for arbitrary normalized |ψ⟩ and |φ⟩, ⟨ψ|φ⟩ = ⟨ψ|φ⟩ ⟨b|b⟩ = ⟨ψ,b|φ,b⟩. Apply U†U = I and the cloning property: ⟨ψ,b|U†U|φ,b⟩ = ⟨ψ,ψ|φ,φ⟩ = (⟨ψ|φ⟩)². Hence (⟨ψ|φ⟩)² = ⟨ψ|φ⟩. This implies that ⟨ψ|φ⟩ is 0 or 1. But we can choose |ψ⟩ and |φ⟩ with 0 < |⟨ψ|φ⟩| < 1 (e.g., |0⟩ and (|0⟩+|1⟩)/√2). Contradiction. Therefore such U cannot exist.
- Gate actions (matrix forms) and simple derivations
- Pauli matrices: X = [[0,1],[1,0]], Z = [[1,0],[0,−1]], Y = [[0,−i],[i,0]]. Show unitarity: e.g., X†X = I.
- Hadamard: H = (1/√2) [[1,1],[1,−1]]. Derive H|0⟩ = (|0⟩+|1⟩)/√2 and H|1⟩ = (|0⟩−|1⟩)/√2 by matrix multiplication.
- Phase gates: S = diag(1,i); T = diag(1,e^{iπ/4}). They add relative phase on |1⟩.
- Controlled-NOT (CNOT): On basis {|00⟩,|01⟩,|10⟩,|11⟩}, CNOT maps |c,t⟩ → |c, t ⊕ c⟩. Its matrix is 4×4 with ones on rows/columns corresponding to |00⟩→|00⟩, |01⟩→|01⟩, |10⟩→|11⟩, |11⟩→|10⟩.
- Single-qubit rotations: R_x(θ) = e^{−iθX/2}, R_y(θ) = e^{−iθY/2}, R_z(θ) = e^{−iθZ/2}. These correspond to rotations by angle θ on the Bloch sphere about x, y, z axes.
- Oracle encoding and Deutsch algorithm idea
- Reversible encoding: For a Boolean f: {0,1} → {0,1}, define U_f|x,y⟩ = |x, y ⊕ f(x)⟩. This is unitary and reversible.
- Deutsch’s algorithm: With one query to U_f and Hadamards, it distinguishes constant functions (f(0)=f(1)) from balanced functions (f(0)≠f(1)) with certainty, using interference.
Diagrams to describe in exam answers (draw and label clearly):
- Bloch sphere: Draw a sphere with axes labeled x, y, z. Mark north pole |0⟩, south pole |1⟩. Draw a radius at polar angle θ from +z and azimuth φ from +x on equator. Label the point |ψ⟩ and angles θ, φ.
- Basic quantum circuit: Horizontal lines for two qubits q0 (top), q1 (bottom). A box labeled H on q0 line. A CNOT with a solid control dot on q0 and a ⊕ (X) on q1 connected by a vertical line. Measurement meters at the right with classical output bits.
- Tensor-product grid: A 2×2 table of basis states for two qubits listing |00⟩, |01⟩, |10⟩, |11⟩, and arrows showing how CNOT maps |10⟩ to |11⟩ and |11⟩ to |10⟩.
Notes connecting to other syllabus topics (names only): The mathematical idea of superposition connects to “Wave–particle duality and de Broglie waves.” Measurement uncertainty relates to “Heisenberg’s uncertainty principle.” Time evolution e^{−iHt/ħ} uses “Schrödinger’s equation.” Tunnelling is key in some qubit devices (see “Quantum tunnelling and the scanning tunnelling microscope”). Superconducting qubits relate to “Superconductivity, Josephson effect and SQUID.”
Formulas
|ψ⟩ = α|0⟩ + β|1⟩
- |ψ⟩: state vector (dimensionless, normalized), α, β: complex amplitudes (dimensionless). For a single qubit pure state.
|α|² + |β|² = 1
- Probability normalization for a qubit, dimensionless. Applies to normalized states.
p(i) = |⟨i|ψ⟩|²
- p(i): probability (dimensionless) of outcome i when measuring |ψ⟩ in basis {|i⟩}. Applies to projective measurement.
|ψ⟩ → U|ψ⟩, U†U = I
- U: unitary operator (dimensionless matrix). Evolution of closed quantum system or application of a gate.
U(t) = e^(−iHt/ħ)
- H: Hamiltonian (J), t: time (s), ħ: reduced Planck’s constant (J·s). Time evolution for time-independent H.
|ψ⟩ = cos(θ/2)|0⟩ + e^(iφ) sin(θ/2)|1⟩
- θ, φ: angles (rad). Bloch-sphere parametrization of a pure qubit state.
H = (1/√2) [[1, 1], [1, −1]]
- H: Hadamard matrix (dimensionless). Single-qubit gate in computational basis.
X = [[0, 1], [1, 0]] , Y = [[0, −i], [i, 0]] , Z = [[1, 0], [0, −1]]
- Pauli matrices (dimensionless). Basic single-qubit gates/observables.
R_n(θ) = e^(−i θ σ_n / 2)
- σ_n ∈ {X, Y, Z} (dimensionless), θ (rad). Rotation about Bloch axis n by angle θ.
U_f |x, y⟩ = |x, y ⊕ f(x)⟩
- U_f: oracle unitary (dimensionless), x, y ∈ {0,1}. Reversible embedding of a Boolean function.
h = 6.62607015 × 10^(−34) J·s , ħ = h / (2π)
- Planck constant (exact, SI), reduced Planck’s constant.
CNOT |c, t⟩ = |c, t ⊕ c⟩
- c: control bit, t: target bit (dimensionless). Definition of controlled-NOT action on computational basis.
Worked examples
Example 1: State evolution and measurement probabilities in a simple circuit Given: Two qubits initialized to |ψ₀⟩ = |00⟩. Apply H on qubit 0 (top), then CNOT with control qubit 0 and target qubit 1. Measure both in the computational basis. Find the final state before measurement and the probabilities of each outcome.
Solution:
- Apply H on qubit 0:
H|0⟩ = (|0⟩ + |1⟩)/√2. So after H ⊗ I, the joint state is |ψ₁⟩ = (|0⟩ + |1⟩)/√2 ⊗ |0⟩ = (|00⟩ + |10⟩)/√2. - Apply CNOT (control = qubit 0):
- CNOT|00⟩ = |00⟩,
- CNOT|10⟩ = |11⟩. Therefore |ψ₂⟩ = (|00⟩ + |11⟩)/√2, which is the Bell state |Φ+⟩.
- Measurement probabilities: In the basis {|00⟩, |01⟩, |10⟩, |11⟩}, the amplitudes are 1/√2 for |00⟩ and 1/√2 for |11⟩, zero for others. So p(00) = |1/√2|² = 1/2, p(11) = 1/2, p(01) = 0, p(10) = 0. Final answer: Final state before measurement is (|00⟩ + |11⟩)/√2; outcomes 00 and 11 occur with probability 1/2 each.
Example 2: Bloch-sphere parameters from amplitudes Given: A single-qubit state |ψ⟩ = √(3/4)|0⟩ + e^{iπ/3} √(1/4)|1⟩. Express |ψ⟩ in Bloch angles θ and φ.
Solution:
- Compare with
|ψ⟩ = cos(θ/2)|0⟩ + e^(iφ) sin(θ/2)|1⟩. - From amplitudes: cos(θ/2) = √(3/4) = √3/2; sin(θ/2) = √(1/4) = 1/2.
- Then θ/2 = arccos(√3/2) = π/6, thus θ = π/3 (rad).
- The phase of |1⟩ component is φ = π/3 (rad). Final answer: θ = π/3 rad, φ = π/3 rad.
Example 3: Deutsch algorithm trace for a specific oracle Given: Oracle U_f for f(x) = x (balanced). Start with two qubits in |1⟩ (bottom) and |0⟩ (top). Apply H on both, then U_f, then H on the top qubit. Measure the top qubit. Show the steps and the final outcome.
Solution:
- Initialize: |ψ₀⟩ = |0⟩|1⟩.
- Apply H ⊗ H:
- H|0⟩ = (|0⟩+|1⟩)/√2,
- H|1⟩ = (|0⟩−|1⟩)/√2. So |ψ₁⟩ = (1/2)(|0⟩+|1⟩) ⊗ (|0⟩−|1⟩).
- Apply U_f with f(x)=x: U_f|x,y⟩ = |x, y ⊕ x⟩. Acting on superposition:
- For x=0, y part unchanged: (|0⟩ ⊗ (|0⟩−|1⟩)).
- For x=1, y flips: (|1⟩ ⊗ (|1⟩−|0⟩)) = −(|1⟩ ⊗ (|0⟩−|1⟩)). Therefore |ψ₂⟩ = (1/2)[ |0⟩ ⊗ (|0⟩−|1⟩) − |1⟩ ⊗ (|0⟩−|1⟩) ] = (1/2)(|0⟩−|1⟩) ⊗ (|0⟩−|1⟩).
- Apply H on the top qubit only:
- H(|0⟩−|1⟩) = (1/√2)[ (|0⟩+|1⟩) − (|0⟩−|1⟩) ] = (1/√2)(2|1⟩) = √2 |1⟩. Hence the exact post-H state is |ψ₃⟩ = |1⟩ ⊗ (|0⟩−|1⟩)/√2 (the top qubit is |1⟩ with certainty and the bottom is unchanged apart from a global factor).
- Measure the top qubit: It is |1⟩ with probability 1. Balanced functions yield top outcome 1; constant would yield 0. Final answer: Top qubit measures 1 with certainty, identifying f as balanced.
Theory model answer outline: Prove no-cloning theorem
- Write the statement (as above).
- Assume a universal cloner U and blank |b⟩. Show it works for |0⟩ and |1⟩, then for an arbitrary superposition α|0⟩+β|1⟩, linearity of U implies U(α|0⟩+β|1⟩,|b⟩) = α|0⟩|0⟩ + β|1⟩|1⟩, which is not equal to (α|0⟩+β|1⟩)⊗(α|0⟩+β|1⟩) unless αβ=0. Alternatively, use the inner-product preservation proof to show (⟨ψ|φ⟩)² = ⟨ψ|φ⟩, contradiction. Conclude impossibility. Mention implication: cannot perfectly copy unknown quantum data; must use error-correction and teleportation for state transfer.
Common mistakes
- Confusing global and relative phase: Treating a global phase e^{iϕ} as observable.
- Mixing measurement basis: Computing probabilities using amplitudes from a different basis than the measurement basis.
- Applying CNOT to the wrong control/target order or wrong basis ordering.
- Assuming cloning possible or that measurement “reads without disturbance.”
- Treating classical reversible XOR as the same as quantum phase kickback; missing that U_f must be reversible and unitary.
- Writing non-unitary “gates” (matrices whose columns are not orthonormal).
- Forgetting tensor-product expansion when multiple qubits are involved.
- Misusing Bloch angles (using θ instead of θ/2 in amplitudes).
- Assuming speedup for all problems; not stating the oracle/query model assumptions for Deutsch/Grover.
For your exam
- Short notes: Hadamard gate and its role; Pauli matrices; Controlled gates (CNOT, CZ); No-cloning theorem significance; Quantum vs classical bits. Include matrix forms and actions on basis states.
- Derivations: Action of H on |0⟩ and |1⟩; proof of no-cloning; Bloch-sphere parametrization; unitarity of Pauli gates; effect of CNOT on Bell states. Show steps and justify with linear algebra.
- Numericals/Computations: Compute outcome probabilities after a small circuit; convert between amplitudes and Bloch angles; trace Deutsch algorithm for given f. Carry units for constants when using ħ in time-evolution questions; otherwise state “dimensionless.”
- Diagrams: Bloch sphere with θ, φ; two-qubit circuit with H and CNOT; measurement schematic. Label axes, states, control/target, and measurement outputs.
- Conceptual: Explain why measurement disturbs the state; why cloning is impossible; how interference gives advantage (e.g., Deutsch, Grover idea). Relate briefly to syllabus topics by name where relevant. A full-marks answer is precise, uses correct symbols, shows normalization, includes matrices/vectors, gives cleanly labeled diagrams, and states assumptions (ideal, noiseless, projective measurement) explicitly.
Quick check
- Write the state of a qubit on the Bloch sphere that gives equal probabilities of 0 and 1 but with a relative phase of π/2.
- What is the action of CNOT on |11⟩ and on |10⟩ (control is first qubit)?
- State the no-cloning theorem in one sentence. Answers: 1) |ψ⟩ = (|0⟩ + i|1⟩)/√2 (θ = π/2, φ = π/2). 2) CNOT|11⟩ = |10⟩ and CNOT|10⟩ = |11⟩. 3) No physical process represented by a unitary operation can make an exact copy of an arbitrary unknown quantum state.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?