跳到主要内容

5 Quantum Computing

Motivation: Why Quantum Computing?​

Classical Computing Limitations​

  • Heat dissipation limit
  • Landauer’s Principle
  • Moore’s Law slowdown
  • Hard computational problems

Extended Church–Turing Thesis​

  • Any efficiently computable function can be efficiently simulated by a probabilistic Turing machine
  • Classical alternatives (GPU, TPU, optical computing) give polynomial, not exponential speedups

Quantum Bits (Qubits)​

Qubit Representation​

∣ψ⟩=α∣0⟩+β∣1⟩\begin{equation*} |\psi\rangle = \alpha |0\rangle + \beta |1\rangle \end{equation*}
  • Normalization:
∣α∣2+∣β∣2=1\begin{equation*} |\alpha|^2 + |\beta|^2 = 1 \end{equation*}
  • Measurement probabilities:
    • ( P(0) = |\alpha|^2 )
    • ( P(1) = |\beta|^2 )

Core Quantum Principles​

Superposition​

  • A qubit can exist in multiple states simultaneously

Interference​

  • Probability amplitudes can reinforce or cancel each other

Measurement​

  • Measurement collapses the quantum state

Quantum Algorithms​

Grover’s Algorithm​

  • Unstructured search
  • Speedup: O(N)→O(N)\begin{equation*} O(N) \rightarrow O(\sqrt{N}) \end{equation*}

Shor’s Algorithm​

  • Integer factorization
  • Uses Quantum Fourier Transform (QFT)
  • Polynomial-time quantum algorithm
  • Breaks RSA cryptography

Quantum Complexity Classes​

BPP​

  • Classical probabilistic polynomial time
  • Correct with probability ≥ 2/3

BQP​

  • Quantum polynomial time
  • Correct with probability ≥ 2/3

Key fact:

  • BQP ⊇ BPP
  • BQP ≠ BPP is NOT proven

Quantum Hardware (Trapped Ions / Atoms)​

Qubit Encoding​

  • Metastable electronic energy levels

Initialization​

  • Optical pumping

Measurement​

  • Cyclic transition
  • Detect photon emission

Two-Qubit Gates​

  • Require strong interaction
  • Rydberg atoms
  • Dipole–dipole interaction
  • Rydberg blockade enables entanglement

DiVincenzo Criteria​

A physical quantum computer must have:

  1. Scalable qubits
  2. State initialization
  3. Universal gate set
  4. Long coherence time
  5. Reliable measurement

Practical View​

  • Quantum computers will not replace classical computers
  • They act as accelerators for special problems
    • Factoring
    • Search
    • Quantum simulation
    • Quantum machine learning (potentially)