Quantum Computing:
Structured Interference at Scale

from qiskit import QuantumCircuit, Aer, execute
from qiskit.visualization import plot_histogram

# Hadamard creates superposition: |0⟩ → (|0⟩ + |1⟩)/√2
qc = QuantumCircuit(1, 1)
qc.h(0)  # Equator of Bloch sphere
qc.measure(0, 0)

simulator = Aer.get_backend('qasm_simulator')
result = execute(qc, simulator, shots=1024).result()
counts = result.get_counts()

# Interference example: H-Z-H = Identity
# H puts in superposition, Z flips phase of |1⟩, 
# second H makes amplitudes interfere back to |0⟩
qc2 = QuantumCircuit(1, 1)
qc2.h(0)
qc2.z(0)  # Adds -1 phase to |1⟩ component
qc2.h(0)  # Interference: |0⟩ and -|0⟩ cancel for |1⟩ output
qc2.measure(0, 0)

from qiskit import QuantumCircuit

# Create Bell state: H on control, then CNOT
qc = QuantumCircuit(2, 2)
qc.h(0)        # Superposition
qc.cx(0, 1)    # Entangle: |00⟩ + |11⟩
qc.measure_all()

# This 2-qubit state requires 4 complex amplitudes classically.
# 50 qubits require 2^50 ≈ 1.1e15 amplitudes = 9 petabytes at 8 bytes each.
# That's why you can't simulate 50 qubits on your laptop.

Periodicity in amplitudes → spikes in frequency domain

QFT is the lens that makes period visible. If your quantum state has amplitudes that repeat every $r$ indices, the QFT transforms it into peaks at multiples of $N/r$.

from qiskit.circuit.library import QFT
import numpy as np

# QFT on 3 qubits
qft = QFT(3)

# Inverse QFT is used in phase estimation
iqft = QFT(3, inverse=True)

# Period finding: if f(x) = f(x+r), QFT peaks at multiples of 2^n/r
# Shor exploits this: factoring → order finding → period finding

Link to QFT intuition

Order finding: given $a, N$, find smallest $r > 0$ such that $a^r \bmod N = 1$. Create superposition $\frac{1}{\sqrt{Q}} \sum_x |x\rangle|a^x \bmod N\rangle$. The second register entangles with periodic $x$. Measure it, collapsing the first to a superposition of $x$ values spaced by $r$. QFT on the first register gives peaks at $j \cdot 2^n / r$. Measure, run continued fractions, extract $r$.

from math import gcd
from fractions import Fraction

def shor_classical_post(N, a, r):
    """After quantum step gives period r"""
    if r % 2 != 0:
        return None  # Try again
    x = pow(a, r//2, N)
    if x == N - 1:
        return None  # Try again
    p = gcd(x + 1, N)
    q = gcd(x - 1, N)
    return p, q

# Quantum part: find r such that a^r ≡ 1 (mod N)
# 1. Create |x⟩|a^x mod N⟩ in superposition
# 2. Measure second register → first becomes periodic
# 3. QFT first register → peaks at multiples of 2^n/r
# 4. Measure → get j, compute r from continued fractions of j/2^n
# Shor's algorithm is interference: amplitudes for non-periods cancel

from qiskit import QuantumCircuit
import numpy as np

def grover_oracle(n, marked):
    """Marks target state by flipping its phase"""
    qc = QuantumCircuit(n)
    # Example: mark |11...1⟩
    qc.x(range(n))  # Flip to |00...0⟩
    qc.h(n-1)
    qc.mcx(list(range(n-1)), n-1)  # Multi-controlled Z
    qc.h(n-1)
    qc.x(range(n))
    return qc

def diffusion(n):
    """Reflection about mean: H-X-MCX-X-H"""
    qc = QuantumCircuit(n)
    qc.h(range(n))
    qc.x(range(n))
    qc.h(n-1)
    qc.mcx(list(range(n-1)), n-1)
    qc.h(n-1)
    qc.x(range(n))
    qc.h(range(n))
    return qc

# Grover = (Oracle + Diffusion)^k where k ≈ π/4 * √N
# Interference: marked state amplitude grows, others shrink

from qiskit import QuantumCircuit, transpile
from qiskit.providers.fake_provider import FakeBrooklyn
from qiskit.providers.aer.noise import NoiseModel

# Brooklyn: 65-qubit 2D grid, limited connectivity
backend = FakeBrooklyn()
coupling_map = backend.configuration().coupling_map

# Algorithmic circuit: all-to-all
qc = QuantumCircuit(65)
for i in range(64):
    qc.cx(i, 64)  # CNOT from each qubit to qubit 64

# Transpile to hardware: adds SWAPs to route
qc_mapped = transpile(qc, backend, optimization_level=3)
print(f"Algorithmic: {qc.size()} gates")
print(f"Physical: {qc_mapped.size()} gates")  # Expect 10-20x overhead

# Noise model: T1=100µs, T2=100µs, gate_time=50ns
# Coherence limits you to ~2000 gates before fidelity < 1/e
noise_model = NoiseModel.from_backend(backend)
# SWAP = 3 CNOTs, each CNOT adds errors
# Fidelity drops exponentially: F = (1-p)^G

# Surface code resource estimate
import math

def logical_error_rate(p, d):
    """Approx logical error for distance-d surface code"""
    # P_L ≈ 0.1 * (p/p_th)^((d+1)/2), p_th ≈ 0.01
    p_th = 0.01
    if p >= p_th:
        return 1.0  # Above threshold, no protection
    return 0.1 * (p / p_th) ** ((d + 1) / 2)

p_physical = 1e-3
d = 25
p_logical = logical_error_rate(p_physical, d)  # ~1e-12
physical_per_logical = 2 * d**2  # ~1250

# Shor-2048 needs ~4000 logical qubits × 1250 = 5M physical
# At 1µs cycle time, 1e8 T-gates × 25 cycles = 2500s runtime