Algorithm Reference — 19 Algorithms

1. Grover's Search Algorithm

Problem: Find a specific item in an unsorted database of N items. Classical: O(N) queries. Quantum: O(√N) queries — quadratic speedup. Qubits needed: log₂(N).

Grover's algorithm works by repeatedly applying two operations: (1) an oracle that flips the phase of the target state, and (2) a diffusion operator that amplifies the marked state's amplitude. After approximately π/4·√N iterations, measuring the register yields the target with high probability (>96% for single target). Sansqrit implements both single-target and multi-target variants. The oracle is implemented by directly negating the amplitude of the target basis state in the sparse vector — an O(1) operation. The diffusion operator applies H⊗n, negates all states except |0⟩, then applies H⊗n again.

simulate {
    -- Find item 42 in a database of 128 items (7 qubits)
    let r = grover_search(n_qubits=7, target=42, shots=1000)
    print(f"Found: {r.solution}")         -- 42
    print(f"Probability: {r.probability:.4f}")  -- ~0.96
    print(f"Queries: {r.n_queries}")       -- ~9 (vs 128 classical)
}

2. Shor's Factoring Algorithm

Problem: Factor an integer N into prime factors. Classical: O(exp(n^1/3)) (sub-exponential). Quantum: O(n³) — exponential speedup. This is the algorithm that threatens RSA encryption.

Shor's algorithm uses quantum period-finding to discover the order r of a random base a modulo N. If r is even, then gcd(a^r/2 ± 1, N) yields a non-trivial factor. The quantum part uses the Quantum Fourier Transform (QFT) to extract the period from the modular exponentiation function. Sansqrit implements the full algorithm including classical pre-processing (GCD checks for small factors), quantum order-finding simulation, and classical post-processing (extracting factors from the period).

simulate {
    let f15 = shor_factor(15)
    print(f"15 = {f15.factors[0]} × {f15.factors[1]}")  -- 3 × 5
    let f21 = shor_factor(21)
    print(f"21 = {f21.factors[0]} × {f21.factors[1]}")  -- 3 × 7
}

3. Variational Quantum Eigensolver (VQE)

Problem: Find the ground state energy of a molecular Hamiltonian. Application: Quantum chemistry — drug discovery, materials science, catalysis. Type: Hybrid quantum-classical algorithm.

VQE prepares a parameterized quantum state (ansatz), measures the expectation value of the Hamiltonian, and uses a classical optimizer to minimize the energy. Sansqrit implements VQE with: hardware-efficient ansatz (Ry/Rz layers + CNOT entanglement), parameter-shift rule gradient computation, gradient descent optimizer, and a pre-built H₂ Hamiltonian in the STO-3G basis set (Jordan-Wigner mapping). The parameter-shift rule computes gradients by evaluating the circuit at θ ± π/2: ∂E/∂θ = (E(θ+π/2) - E(θ-π/2)) / 2.

import chemistry
molecule H2 { atoms: [H, H], bond_length: 0.74, basis_set: "STO-3G" }
simulate {
    let r = vqe(H2, ansatz="EfficientSU2", layers=2, max_iter=200)
    print(f"Ground state energy: {r.energy:.6f} Hartree")
    print(f"Converged: {r.converged} in {r.n_iterations} iterations")
}

4. QAOA — Quantum Approximate Optimization

Problem: Solve combinatorial optimization problems (MaxCut, graph coloring, traveling salesman). Type: Hybrid quantum-classical. Qubits: One per graph node.

QAOA alternates between a cost layer (RZZ gates encoding graph edges with angles γ) and a mixer layer (Rx gates with angles β). The parameters γ and β are optimized classically. Sansqrit implements QAOA for MaxCut with grid-search optimization over γ and β.

simulate {
    let edges = [(0,1), (1,2), (2,3), (3,0), (0,2)]
    let r = qaoa_maxcut(edges=edges, n_nodes=4, layers=3, shots=1000)
    print(f"Best cut: {r.best_cost}/{len(edges)} edges")
    print(f"Partition: {r.best_bitstring}")
}

5. Quantum Phase Estimation (QPE)

Problem: Estimate the eigenphase φ where U|ψ⟩ = e^2πiφ|ψ⟩. Precision: n counting bits give 2^-n accuracy. Used by: Shor's algorithm, HHL, quantum chemistry.

simulate {
    let phase = estimate_phase(
        unitary = fn(q) { Rz(q, PI/4) },
        n_bits = 8
    )
    print(f"Estimated: {phase.phase:.6f}, Expected: {PI/4:.6f}")
}

6. HHL — Quantum Linear Systems

Problem: Solve Ax = b for x. Classical: O(N·κ²). Quantum: O(log(N)·κ²) — exponential speedup in system size. Requirement: A must be Hermitian and sparse.

simulate {
    let r = hhl_solve([[2,1],[1,2]], [1,0])
    print(f"Solution: x = {r.solution}")
    print(f"Condition number: {r.condition_number:.2f}")
}

7. Bernstein-Vazirani Algorithm

Problem: Find hidden bitstring s where f(x) = s·x mod 2. Classical: n queries. Quantum: 1 query. Speedup: Linear → constant.

simulate {
    let secret = [1, 0, 1, 1, 0]
    let found = bernstein_vazirani(n_bits=5, oracle_secret=secret)
    print(f"Secret: {found}")  -- [1, 0, 1, 1, 0]
}

8. Simon's Algorithm

Problem: Find hidden period s where f(x) = f(x⊕s). Classical: O(2^n/2). Quantum: O(n). Speedup: Exponential.

simulate {
    let period = simon_algorithm(n_bits=4, secret=[1,0,1,0])
    print(f"Hidden period: {period}")
}

9. Deutsch-Jozsa Algorithm

Problem: Determine if f is constant (same output for all inputs) or balanced (equal 0s and 1s). Classical: 2^n-1+1 queries (worst case). Quantum: 1 query. Speedup: Exponential.

simulate {
    let result = deutsch_jozsa(n_bits=4, oracle_type="balanced")
    print(result)  -- "balanced"
}

10. Quantum Walk

Application: Quantum random walks on graphs — used for search algorithms, spatial search, and transport simulation. Quantum walks spread quadratically faster than classical random walks.

simulate { let r = quantum_walk_line(n_positions=8, n_steps=20, shots=1000)
print(r) }

11. Quantum Counting

Problem: Estimate the number of solutions M to a search problem without finding them. Combines QPE with Grover's operator.

simulate { let r = quantum_counting(n_search_bits=5, n_counting_bits=4, n_solutions=3)
print(f"Estimated solutions: {r.count_estimate:.1f}") }

12. SWAP Test

Problem: Estimate |⟨ψ|φ⟩|² — the overlap between two quantum states — using one ancilla qubit and Fredkin gates.

simulate { let overlap = swap_test(engine1, engine2, shots=1000)
print(f"State overlap: {overlap:.4f}") }

13. Quantum Teleportation

Problem: Transfer a quantum state from one qubit to another using shared entanglement and classical communication. Requires 1 Bell pair + 2 classical bits.

simulate {
    let q = quantum_register(3)
    Ry(q[0], PI/3)  -- state to teleport
    let (b0, b1) = teleport(engine)
    print("State teleported to qubit 2!")
}

14. Superdense Coding

Achievement: Send 2 classical bits using 1 qubit transmission + shared entanglement. The inverse of teleportation.

simulate {
    let (r0, r1) = superdense_coding(bit0=1, bit1=1)
    print(f"Received: {r0}{r1}")  -- "11"
}

15. BB84 Quantum Key Distribution

Application: Generate a shared cryptographic key between two parties (Alice and Bob) that is provably secure against eavesdropping. Any interception is detectable via quantum mechanics (no-cloning theorem). This is the foundation of quantum cryptography.

simulate {
    let (alice_key, bob_key, error_rate) = bb84_qkd(key_length=256)
    print(f"Key length: {len(alice_key)}")
    print(f"Error rate: {error_rate:.4f}")  -- 0.0 without eavesdropper
}

16. Quantum Amplitude Estimation

Problem: Estimate the probability of a specific outcome with quadratic speedup over classical sampling. Used in quantum finance (option pricing) and Monte Carlo simulation.

simulate { let r = amplitude_estimation(n_qubits=5, n_eval_bits=4, target=7)
print(f"Estimate: {r.count_estimate:.2f}, Confidence: {r.confidence:.2%}") }

17. Variational Quantum Classifier

Application: Quantum machine learning — train a parameterized quantum circuit to classify data. Features are encoded as rotation angles (Ry), followed by variational layers optimized via gradient descent.

simulate {
    let x = [[0,0],[0,1],[1,0],[1,1]]
    let y = [0, 1, 1, 0]  -- XOR problem
    let (params, accuracy) = variational_classifier(
        n_features=2, training_data=zip(x,y), n_layers=4, epochs=100, lr=0.01)
    print(f"Accuracy: {accuracy:.0%}")
}