🧠

Quantum Computing Overview

Jun 17, 2025

View transcript

Overview

This lecture provides a comprehensive introduction to quantum computing, covering foundational mathematics, quantum mechanics concepts, how qubits and gates work, key quantum phenomena, and the analysis of several fundamental quantum algorithms.

Essential Mathematics for Quantum Computing

  • Complex numbers have real and imaginary parts and can be written in standard, polar, or exponential form.
  • The magnitude of a complex number (a + ib) is (\sqrt{a^2 + b^2}).
  • Matrices are rectangular arrays (m x n); operations include addition, scalar multiplication, and matrix multiplication (only possible if inner dimensions match).
  • The identity matrix leaves other matrices unchanged when multiplied; a matrix's inverse undoes its transformation.
  • Unitary matrices satisfy (U^\dagger U = I) and preserve vector length; Hermitian matrices equal their conjugate transpose.

Qubits and Quantum States

  • Qubits (quantum bits) can exist in a superposition of 0 and 1, represented as column vectors, e.g., (\begin{bmatrix} \alpha \ \beta \end{bmatrix}).
  • Measurement collapses a qubit's state to either 0 or 1 based on the squared magnitudes of amplitudes as probabilities.
  • Dirac (bra-ket) notation is used for quantum states: (\alpha|0\rangle + \beta|1\rangle).
  • The Bloch sphere visualizes qubit states; latitude indicates the probability of measuring 0 or 1.
  • Relative phase (from complex coefficients) is crucial for quantum algorithms; global phase is physically irrelevant.

Quantum Gates and Operations

  • Common single-qubit gates: X (bit flip), Y, and Z (phase flip).
  • Hadamard gate (H) creates uniform superpositions; it's its own inverse.
  • S and T gates add specific phase shifts; their daggers are inverses.
  • Operations are matrix multiplications on column vectors.

Multi-Qubit Systems and Circuits

  • Multi-qubit states use tensor products; two qubits yield four possible basis states.
  • Quantum circuits represent sequences of gates applied to qubits.
  • Multi-qubit gates: CNOT (controlled X), Toffoli (controlled-controlled-X), and controlled versions of other gates.
  • Measuring one qubit in a multi-qubit state collapses the overall state accordingly; normalization ensures probabilities sum to 1.

Quantum Phenomena: Entanglement and Phase Kickback

  • Entanglement occurs when qubits' states are interdependent; Bell states are maximally entangled.
  • Phase kickback transfers phase information from a target to a control qubit via controlled operations.

Classical vs. Quantum Computation

  • Classical gates (AND, OR, NOT, XOR) can be made reversible by adding auxiliary bits.
  • All quantum operations (except measurement) must be reversible/unitary.

Foundational Quantum Algorithms

  • Deutsch's Algorithm: Determines if a function is constant or balanced with one quantum query.
  • Deutsch-Jozsa Algorithm: Generalizes Deutsch’s for n-bit inputs; distinguishes constant from balanced functions in one query.
  • Bernstein–Vazirani Algorithm: Finds a secret bit string by querying the function once.
  • Quantum Fourier Transform (QFT): Transforms basis state encoding to phase encoding; used in many algorithms.
  • Quantum Phase Estimation: Finds the phase (eigenvalue) of a unitary operator given its eigenvector.
  • Shor’s Algorithm: Factors large numbers efficiently using quantum period finding (undermining RSA encryption).

Key Terms & Definitions

  • Qubit — quantum analog of a classical bit, can be in a superposition.
  • Superposition — qubit state of being both 0 and 1 simultaneously.
  • Entanglement — quantum state where qubits cannot be described individually.
  • Unitary Matrix — matrix that preserves length and is reversible.
  • Hermitian Matrix — matrix equal to its conjugate transpose.
  • Bloch Sphere — geometric representation of qubit states.
  • Hadamard Gate — gate creating superposition; denoted as H.
  • CNOT Gate — flips target qubit if control qubit is 1.
  • Phase Kickback — phase acquired by control qubit in controlled operation.
  • Quantum Fourier Transform — changes computational basis to phase basis.
  • No-Cloning Theorem — quantum states cannot be copied exactly.

Action Items / Next Steps

  • Review problem sets on matrix operations and quantum gates.
  • Practice representing and manipulating multi-qubit states.
  • Study the step-by-step circuits of the discussed algorithms.
  • Prepare for deeper dives into Shor’s algorithm and quantum phase estimation.

Full transcript