Quantum Computing Basics

Overview

This lecture provides a foundational overview of quantum computing, covering essential mathematics, the mechanics of quantum computers, core quantum principles, and explains key quantum algorithms that demonstrate quantum speedup over classical approaches.

Essential Mathematics for Quantum Computing

• Complex numbers consist of a real part and an imaginary part, written as a + ib.
• The magnitude of a complex number a + ib is √(a² + b²); its angle (θ) is arctan(b/a).
• Complex numbers can be expressed in polar (r cos θ + i r sin θ) and exponential (re^{iθ}) forms.
• Matrices are 2D arrays of numbers; m × n matrices have m rows and n columns.
• Matrix multiplication is defined only when columns of the first equal rows of the second.
• Identity matrix leaves other matrices unchanged; inverse matrix undoes a transformation.
• Unitary matrices (U U† = I) preserve vector length; Hermitian matrices (H = H†) have real eigenvalues.
• Eigenvectors are unchanged by their matrix except for a scalar (eigenvalue).

Qubits and Quantum States

• A qubit (quantum bit) is represented as a two-element column vector: |ψ⟩ = α|0⟩ + β|1⟩.
• Superposition means a qubit exists in both |0⟩ and |1⟩ simultaneously until measured.
• Measurement collapses a qubit to |0⟩ or |1⟩; |α|² and |β|² give measurement probabilities.
• Direct (ket) notation is used to write quantum states, e.g., |ψ⟩.
• The Bloch sphere visualizes single qubit states and relative phase.

Quantum Gates and Operations

• X, Y, and Z gates rotate qubit states π radians around the respective axes on Bloch sphere.
• Gates are represented by matrices and applied via matrix multiplication to qubit vectors.
• The Hadamard (H) gate creates equal superpositions and is its own inverse.
• S and T gates add relative phases of π/2 and π/4 radians, respectively.

Multi-Qubit Systems and Entanglement

• Multi-qubit states are formed via tensor products.
• Controlled gates (e.g., CNOT) apply an operation to a target qubit based on the control qubit's state.
• Entanglement means qubits’ states depend on each other; Bell states are maximally entangled.
• Phase kickback allows relative phase transfer via controlled operations.

Quantum Circuits and Measurement

• Quantum circuits visually represent qubit states and the sequence of gates/measurements.
• Measurement of one qubit can collapse the overall quantum state, often requiring normalization.

Quantum Algorithms and Oracles

• All quantum operations (except measurement) must be reversible (unitary).
• Function oracles encode classical functions into quantum gates for algorithmic use.
• No-cloning theorem: Unknown quantum states cannot be copied exactly.

Notable Quantum Algorithms

• Deutsch’s algorithm determines if a 1-bit function is constant or balanced with one query.
• Deutsch-Jozsa algorithm generalizes this to n-bit functions, needing only one query versus ~2^{n-1}+1 classically.
• Bernstein-Vazirani algorithm finds a hidden string S in a single query using phase oracles.
• Quantum Fourier Transform (QFT) encodes information in the phases of qubit superpositions.
• Quantum Phase Estimation finds the eigenvalue (phase) of a unitary operator.
• Shor’s algorithm uses QFT and QPE to efficiently factor large integers, threatening RSA encryption.

Key Terms & Definitions

• Qubit — Quantum bit, can be in superposition of |0⟩ and |1⟩.
• Superposition — State where a qubit is partly |0⟩ and partly |1⟩.
• Entanglement — Quantum correlation where qubits’ states depend on each other.
• Unitary Matrix — Matrix preserving length and allowing reversible operations.
• Oracle — Quantum gate encoding a binary function for algorithms.
• Bloch Sphere — 3D graphical representation of qubit states.

Action Items / Next Steps

• Practice converting complex numbers between standard, polar, and exponential forms.
• Review matrix operations: addition, multiplication, conjugate transpose, and inversion.
• Solve exercises on quantum circuits, superposition, and entanglement (see problem set for resources).
• Study the mathematical derivations and proofs of QFT and quantum phase estimation applications.