Quantum Computing: Qubits, Gates & Algorithms

Classical computing uses bits (0 or 1). Quantum computing uses QBs — quantum mechanical systems that exist in SUP of |0⟩ and |1⟩ simultaneously. A single QB state: |ψ⟩ = α|0⟩ + β|1⟩ where α,β are complex amplitudes satisfying |α|² + |β|² = 1. Measurement collapses SUP to definite state w/ probability |α|² for |0⟩ and |β|² for |1⟩. This probabilistic nature is fundamental, not a limitation — it's the source of quantum computational advantage.

Bloch sphere representation: any single QB pure state maps to a point on the unit sphere. North pole = |0⟩, south pole = |1⟩, equator = equal SUP states w/ varying phase. Polar angle θ determines measurement probabilities, azimuthal angle φ determines relative phase between amplitudes. Phase has no classical analogue but is critical for interference effects that power QAs.

Multi-QB systems: n QBs span a 2ⁿ-dimensional Hilbert space. Two QBs: |ψ⟩ = α|00⟩ + β|01⟩ + γ|10⟩ + δ|11⟩. This exponential state space is why QCs potentially outperform CCs for certain problems. 50 QBs encode 2⁵⁰ ≈ 10¹⁵ amplitudes — more than petabyte of classical storage to fully describe.

ENT is the quintessential quantum resource. Bell state (|00⟩ + |11⟩)/√2 means measuring one QB instantly determines the other, regardless of distance. ENT is not faster-than-light communication (no-communication theorem) but enables quantum teleportation, superdense coding, & is essential for QA speedups. Creating ENT: apply Hadamard to first QB, then CNOT w/ second as target.

Quantum gates are unitary operations (preserve probability, reversible). Single-QB gates:
- Pauli-X (NOT gate): |0⟩↔|1⟩, bit flip
- Pauli-Y: rotation around Y-axis, combines bit flip + phase flip
- Pauli-Z: |0⟩→|0⟩, |1⟩→-|1⟩, phase flip only
- Hadamard (H): |0⟩→(|0⟩+|1⟩)/√2, creates equal SUP, most important single gate
- S gate: π/2 phase, T gate: π/4 phase (essential for fault-tolerant gate sets)
- Rx(θ), Ry(θ), Rz(θ): arbitrary rotations around respective axes

Two-QB gates:
- CNOT (Controlled-NOT): flips target QB iff control is |1⟩. Universal for generating ENT. Matrix is 4×4 identity w/ bottom-right 2×2 block being Pauli-X.
- CZ (Controlled-Z): applies Z to target iff control is |1⟩. Symmetric — either QB can be considered control.
- SWAP: exchanges two QB states. Decomposable into 3 CNOTs.
- Toffoli (CCNOT): three-QB gate, flips target iff both controls are |1⟩. Universal for classical reversible computing.

Universal gate sets: {H, T, CNOT} can approximate any unitary to arbitrary precision (Solovay-Kitaev theorem guarantees efficient decomposition). Hardware-native gate sets vary: superconducting QCs typically use {Rx, Ry, CNOT} or {√X, Rz, CZ}; trapped ion systems use {Rφ, XX} or similar. COMP transpiles abstract circuits to hardware-native gates.

Quantum circuit model: computation = prepare initial state |0⟩⊗n → apply sequence of gates → measure. Circuit depth (longest gate path) determines execution time & DECOherence impact. Circuit width = number of QBs. COMP optimization reduces depth & gate count while preserving functionality. Key optimizations: gate cancellation (consecutive inverse gates cancel), gate commutation (reorder independent gates to reduce depth), template matching (replace subcircuits w/ shorter equivalents).

Key QAs:

Deutsch-Jozsa: determines if function is constant or balanced w/ single query (exponential speedup over deterministic classical). Demonstrates quantum parallelism concept but limited practical use.

Grover's search: unstructured search in O(√N) vs O(N) classical. Quadratic speedup. Uses amplitude amplification — oracle marks target state, diffusion operator amplifies marked amplitude. Optimal iterations: π√N/4. Over-iterating reduces success probability. Applications: database search, SAT solving, optimization.

Shor's factoring: factors integer N in O((log N)³) vs best classical sub-exponential. Threatens RSA/ECC cryptography. Core technique: quantum period-finding via QFT. Steps: choose random a < N, compute gcd(a,N) — if >1, done. Otherwise, find period r of f(x) = aˣ mod N using quantum phase estimation. If r even & aʳ/² ≢ -1 (mod N), then gcd(a^(r/2) ± 1, N) yields factors. Requires ~2n+3 QBs for n-bit number + significant ancilla overhead.

QFT (Quantum Fourier Transform): quantum analogue of DFT, applied to amplitude encoding. Maps computational basis to frequency basis. Requires O(n²) gates for n QBs (exponentially faster than classical FFT on equivalent-sized input). Building block for phase estimation, order finding, & HHL algorithm.

VQAs (Variational Quantum Algorithms): hybrid quantum-classical approach for NISQ era. Parameterized quantum circuit (ansatz) prepares trial state, classical optimizer adjusts parameters to minimize cost function. VQE (Variational Quantum Eigensolver) finds ground state energy of molecular Hamiltonians — applications in drug discovery, materials science, catalysis. QAOA (Quantum Approximate Optimization Algorithm) tackles combinatorial optimization (MaxCut, traveling salesman, portfolio optimization).

Noise & error in quantum systems: DECO sources — T1 (energy relaxation, QB loses energy to environment), T2 (dephasing, loss of phase coherence, T2 ≤ 2T1). Gate errors: typically 10⁻³ for single-QB, 10⁻² for two-QB on current superconducting hardware. Measurement errors: 1-5% on current devices. Crosstalk: operations on one QB affecting neighbors.

QEC (Quantum Error Correction): no-cloning theorem prevents copying QBs, so classical error correction doesn't directly apply. QEC encodes logical QB across multiple physical QBs. Surface code: leading candidate, uses 2D lattice of data & ancilla QBs, threshold error rate ~1%. Distance-d surface code: requires ~2d² physical QBs per logical QB, corrects up to ⌊(d-1)/2⌋ errors. Current goal: demonstrate break-even point where logical error rate < physical error rate. Google demonstrated this milestone in 2024.

Hardware platforms:
- Superconducting (IBM, Google): transmon QBs, microwave control, ~15μs T1, operates at 15mK in dilution refrigerator. Fast gates (~20-100ns) but limited connectivity (nearest-neighbor on grid). Current scale: 1000+ QBs (IBM) but noisy.
- Trapped ion (IonQ, Quantinuum): individual ions in electromagnetic trap, laser-controlled. Longer coherence (~seconds), all-to-all connectivity, slower gates (~10-100μs). Higher fidelity: 99.9% single-QB, 99.5% two-QB.
- Neutral atom (QuEra, Atom Computing): atoms held in optical tweezers, Rydberg interactions for entangling gates. Scalable to 1000s of QBs, reconfigurable connectivity. Emerging platform w/ rapid progress.
- Photonic (PsiQuantum, Xanadu): photons as QBs, room temperature operation, natural for quantum networking. Challenges: probabilistic gate operations, photon loss.

NISQ era strategies: current devices have 50-1000+ noisy QBs w/o full error correction. Practical approaches: error mitigation (zero-noise extrapolation, probabilistic error cancellation, symmetry verification — reduce impact of noise w/o full QEC overhead), shallow circuits (minimize depth to stay within DECO time), hybrid algorithms (VQAs offload optimization to classical processor).

Quantum advantage timeline: demonstrated for specific sampling tasks (Google Sycamore 2019, photonic boson sampling). Practical advantage for useful problems requires either fault-tolerant QCs (estimated 2030s for cryptographically relevant Shor's) or discovery of noise-resilient NISQ QAs. Near-term applications: quantum chemistry simulation, optimization heuristics, quantum machine learning, quantum sensing.

Programming frameworks: Qiskit (IBM, Python, largest ecosystem), Cirq (Google, Python, hardware-aware), PennyLane (Xanadu, ML-focused, auto-differentiation), Q# (Microsoft, integrated w/ Azure Quantum), Amazon Braket (multi-hardware access). Circuit construction: define QBs, apply gates, measure, execute on simulator or real hardware via cloud. Transpilation: abstract circuit → hardware-native gates → physical QB mapping → routing (insert SWAPs for connectivity) → scheduling.