Snapkitty/quantum-kernel

1# markov_moves.jl — Braid Simplification + Canonical Form2 3module MarkovMoves4 5using LinearAlgebra6 7export canonical_form, markov_stabilization, markov_destabilization8export braid_conjugacy_class, is_trivial_braid, burau_matrix9 10# ═══════════════════════════════════════════════════════════════════════11# Types12# ═══════════════════════════════════════════════════════════════════════13 14struct BraidWord15    generators::Vector{Int}16    edge_indices::Vector{Int}17    n_strands::Int18end19 20BraidWord(n_strands::Int) = BraidWord(Int[], Int[], n_strands)21 22const HERON_EDGES_0 = [23    (0, 1), (1, 2),24    (0, 3), (1, 3), (1, 4), (2, 4), (2, 5),25    (3, 4), (4, 5), (5, 6),26    (3, 7), (4, 7), (4, 8), (5, 8), (5, 9), (6, 9),27    (7, 8), (8, 9)28]29 30# ═══════════════════════════════════════════════════════════════════════31# Canonical Form via Handle Reduction32# ═══════════════════════════════════════════════════════════════════════33 34"""35    canonical_form(bw::BraidWord)36 37Compute canonical form using:381. Free reduction (cancel σ σ⁻¹ pairs)392. Artin relations403. Garside normal form (left-greedy)41"""42function canonical_form(bw::BraidWord)::BraidWord43    bw_reduced = free_reduce(bw)44    bw_garside = garside_normal_form(bw_reduced)45    return bw_garside46end47 48function free_reduce(bw::BraidWord)::BraidWord49    stack = Tuple{Int,Int}[]50    for (gen, edge) in zip(bw.generators, bw.edge_indices)51        if !isempty(stack) && stack[end] == (-gen, edge)52            pop!(stack)53        else54            push!(stack, (gen, edge))55        end56    end57    gens = [s[1] for s in stack]58    edges = [s[2] for s in stack]59    BraidWord(gens, edges, bw.n_strands)60end61 62function garside_normal_form(bw::BraidWord)::BraidWord63    gens = copy(bw.generators)64    edges = copy(bw.edge_indices)65 66    for _ in 1:367        for i in 1:length(gens)-168            if gens[i] < 0 && gens[i+1] > 0 && edges[i] == edges[i+1]69                gens[i], gens[i+1] = gens[i+1], gens[i]70            end71        end72    end73 74    BraidWord(gens, edges, bw.n_strands)75end76 77# ═══════════════════════════════════════════════════════════════════════78# Markov Moves79# ═══════════════════════════════════════════════════════════════════════80 81function markov_stabilization(bw::BraidWord, strand_pos::Int)::BraidWord82    @assert 1 <= strand_pos <= bw.n_strands83    new_n = bw.n_strands + 184    new_gen = strand_pos85    edge_idx = (strand_pos - 1) % length(HERON_EDGES_0) + 186    BraidWord(vcat(bw.generators, new_gen),87              vcat(bw.edge_indices, edge_idx),88              new_n)89end90 91function markov_destabilization(bw::BraidWord)::BraidWord92    if bw.n_strands <= 293        return bw94    end95    last_gen = bw.n_strands - 196    if length(bw.generators) > 0 && abs(bw.generators[end]) == last_gen97        if count(g -> abs(g) == last_gen, bw.generators) == 198            return BraidWord(bw.generators[1:end-1],99                           bw.edge_indices[1:end-1],100                           bw.n_strands - 1)101        end102    end103    return bw104end105 106# ═══════════════════════════════════════════════════════════════════════107# Conjugacy & Triviality108# ═══════════════════════════════════════════════════════════════════════109 110function braid_conjugacy_class(bw::BraidWord)::BraidWord111    gens = bw.generators112    edges = bw.edge_indices113    n = length(gens)114 115    if n == 0116        return bw117    end118 119    best = (gens, edges)120    for shift in 1:n-1121        shifted_gens = vcat(gens[shift+1:end], gens[1:shift])122        shifted_edges = vcat(edges[shift+1:end], edges[1:shift])123        if shifted_gens < best[1]124            best = (shifted_gens, shifted_edges)125        end126    end127 128    BraidWord(best[1], best[2], bw.n_strands)129end130 131function is_trivial_braid(bw::BraidWord)::Bool132    reduced = canonical_form(bw)133    return isempty(reduced.generators)134end135 136# ═══════════════════════════════════════════════════════════════════════137# Burau Representation (for Jones polynomial verification)138# ═══════════════════════════════════════════════════════════════════════139 140"""141    burau_matrix(bw::BraidWord, t=im)142 143Reduced Burau representation (n-1 × n-1).144Used for Jones polynomial evaluation.145"""146function burau_matrix(bw::BraidWord, t::ComplexF64=ComplexF64(0,1))::Matrix{ComplexF64}147    n = bw.n_strands148    if n <= 1149        return Matrix{ComplexF64}(I, 1, 1)150    end151    M = Matrix{ComplexF64}(I, n-1, n-1)152 153    for gen in bw.generators154        i = abs(gen)155        if i >= n156            continue157        end158        B = Matrix{ComplexF64}(I, n-1, n-1)159        if gen > 0160            if i < n-1161                B[i,i] = 1 - t162                if i+1 <= n-1163                    B[i,i+1] = t164                    B[i+1,i] = 1165                    B[i+1,i+1] = 0166                end167            else168                B[i,i] = 1 - t169            end170        else171            if i < n-1172                B[i,i] = 0173                if i+1 <= n-1174                    B[i,i+1] = 1175                    B[i+1,i] = t176                    B[i+1,i+1] = 1 - t177                end178            end179        end180        M = B * M181    end182    return M183end184 185end # module MarkovMoves186