qpm-marimo.py

import marimo

__generated_with = "0.11.5"
app = marimo.App(width="medium")

@app.cell(hide_code=True)
def _(mo):
    mo.md(
        r"""
        # Generate random flat quantum permutation matrices
        #
        """
    )
    return


@app.cell(hide_code=True)
def _(mo):
    mo.md(
        r"""
        Let $A$ be a unital $C^*$-algebra. An $n \times n$ matrix $u = (u_{ij})_{1\le i,j\le n} \in \mathcal M_n(A)$
        is called a **quantum permtuation matrix** if it satisfies the conditions below:

        1. *Projection Entries:* Each entry is a projection:
           $$u_{ij}^2 = u_{ij} \quad \text{and} \quad u_{ij}^* = u_{ij} \quad \text{for all } i,j.$$

        2. *Row and Column Sums:* The entries in each row and each column sum to the unit of $A$:
        $$\sum_{j=1}^n u_{ij} = 1_A \quad \text{for all } i=1,\dots,n,$$
        $$\sum_{i=1}^n u_{ij} = 1_A \quad \text{for all } j=1,\dots,n.$$
        """
    )
    return


@app.cell(hide_code=True)
def _(mo):
    mo.md(
        """
        We are interested here in the special case where: 

        1. the algebra $A$ is finite dimensional: $A = \mathcal M_d(\mathbb C)$
        2. the projections $u_{ij}$ have *unit rank* (we call $u$ *flat*); in particular $d=n$.
        """
    )
    return


@app.cell
def _(mo):
    mo.md(
        """
        ## An alogrithm for generating random flat quantum permutation matrices
        ##
        """
    )
    return


@app.cell
def _(mo):
    mo.md(
        r"""
        We propose the following very simple algorithm for generating quantum permutation matrices, based on normalizing the rows and the columns of a matrix of unit rank projections. The alternating normalization of rows and columns is inspired by the **Sinkhorn algorithm** for producing random bistochastic matrices. 

        1. Start from a random matrix: $u_{ij}$ is the orthogonal projection on a random gaussian vector
        2. While the error is larger than some predefined constant and the maximal number of steps has not been attained:
        3. Normalize each row of $u$
        4. Normalize each column of $u$
        5. End-while
        6. Output the matrix $u$
        """
    )
    return


@app.cell
def _(mo):
    mo.md(
        r"""
        The row (respectively the column) normalization procedures are performed as follows. Collect all the vectors appearing on the $i$-th row of $u$ in a matrix $R_i$. Replace $R_i$ by $\tilde R_i$, the *closest unitary matrix* to $R_i$. This matrix can be obtained from the *singular value decomposition* of $R_i$: 
        $$\text{ if } R_i = V_i \Delta_i W_i^*, \, \text{ then }\, \tilde R_i = V_i W_i^*.$$
        """
    )
    return


@app.cell
def _(mo):
    mo.md(
        """
        ## Implementation
        ##
        """
    )
    return


@app.cell
def _(mo):
    eps_slider =  mo.ui.slider(0, 10, value=6)
    max_iter_slider =  mo.ui.slider(1, 10000, value=2000)
    n_slider =  mo.ui.slider(2, 20, step=1, value=4)
    return eps_slider, max_iter_slider, n_slider


@app.cell
def _(eps_slider, mo):
    mo.md(f"-lg(Error tolerance): {eps_slider} \t error_tolerance = 1e-{eps_slider.value}")
    return


@app.cell
def _(max_iter_slider, mo):
    mo.md(f"Max iterations: {max_iter_slider} \t max_iter = {max_iter_slider.value}")
    return


@app.cell
def _(mo, n_slider):
    mo.md(f"Matrix dimension: {n_slider} \t n = {n_slider.value}")
    return


@app.cell
def _(mo):
    button = mo.ui.run_button(label="Randomize!")
    button
    return (button,)


@app.cell
def _(errors, plt, scalar_products):
    # Create a figure with two subplots side by side
    fig, axs = plt.subplots(1, 2, figsize=(12, 5))

    # Plot the errors on a log scale in the first subplot
    axs[0].semilogy(errors)
    axs[0].set_xlabel('Iteration')
    axs[0].set_ylabel('Error (log scale)')
    axs[0].set_title('Error Convergence')
    axs[0].grid(True)

    # Plot the histogram in the second subplot
    axs[1].hist(scalar_products, bins=30, edgecolor='black')
    axs[1].set_xlabel('Absolute Values Squared of Scalar Products')
    axs[1].set_ylabel('Frequency')
    axs[1].set_title('Histogram of Absolute Values Squared of Scalar Products')
    axs[1].grid(True)

    # Adjust layout to prevent overlap
    plt.tight_layout()
    plt.gca()
    return axs, fig


@app.cell
def _(mo):
    mo.md(r"""Note that for $n=2,3$ the histogram of scalar product shows only 0's and 1's: the vectors are either colinear or orthogonal. In other words, the elements $u_{ij}$ **commute**. For $n \geq 4$ this is no longer the case: the scalar product between vectors can take arbitrary values.""")
    return


@app.cell
def _(mo):
    mo.md(
        r"""
        ## Open questions
        ##

        1. Prove the convergence of the algorithm for generic initializations.
        2. Find the speed of convergence for arbitrary $n$
        3. What is the distribution of the scalar products for (large / given) $n$? How about the maximal norm of a commutator $[u_{ij}, u_{kl}]$?
        """
    )
    return


@app.cell
def _(mo):
    mo.md(
        r"""
        ## References
        ## 

        1. S. Wang, “Quantum symmetry groups of finite spaces,” _Communications in mathematical physics_, vol. 195, no. 1, pp. 195–211, 1998.
        2. T. Banica, J. Bichon, and B. Collins, “Quantum permutation groups: a survey,” _Banach Center Publications_, vol. 78, no. 1, pp. 13–34, 2007.
        3. T. Banica, I. Nechita, "Flat matrix models for quantum permutation groups," _Adv. Appl. Math._ 83, 24-46 (2017).
        """
    )
    return


@app.cell
def _(np):
    def generate_random_complex_gaussian_matrix(n):
        matrix = np.empty((n, n, n), dtype=np.complex128)
        for i in range(n):
            for j in range(n):
                real_part = np.random.normal(size=n)
                imag_part = np.random.normal(size=n)
                matrix[i, j] = (real_part + 1j * imag_part) / np.sqrt(2)
        return matrix

    def orthonormalize_vectors_svd(vectors):
        u, _, v = np.linalg.svd(vectors)
        return u @ v

    def error_QPM(u):
        err = -1;

        for i in range(u.shape[0]):
            slice = u[i, :, :]
            err = max(err, np.linalg.norm(slice @ slice.conj().T - np.eye(slice.shape[0])))
            slice = u[:, i, :]
            err = max(err, np.linalg.norm(slice @ slice.conj().T - np.eye(slice.shape[0])))

        return err

    def scalar_products_QPM(u):
        # Calculate the absolute values squared of the scalar products of the vectors in the matrix u
        scalar_products = []
        for i in range(u.shape[0]):
            for j in range(1, u.shape[0]):
                for k in range(1, u.shape[0]):
                    for l in range(1, u.shape[0]):
                        scalar_product = np.abs(np.dot(u[i,j,:], u[k,l,:].conj()))**2
                        scalar_products.append(scalar_product)

        return scalar_products
    return (
        error_QPM,
        generate_random_complex_gaussian_matrix,
        orthonormalize_vectors_svd,
        scalar_products_QPM,
    )


@app.cell
def _():
    import marimo as mo
    import numpy as np
    import matplotlib.pyplot as plt
    return mo, np, plt


@app.cell
def _(
    button,
    eps_slider,
    error_QPM,
    generate_random_complex_gaussian_matrix,
    max_iter_slider,
    n_slider,
    orthonormalize_vectors_svd,
    scalar_products_QPM,
):
    button

    u = generate_random_complex_gaussian_matrix(n_slider.value)

    error_tolerance = 10**(-eps_slider.value)
    max_iter = max_iter_slider.value

    iter = 0
    error = error_QPM(u)
    errors = [error]  # Initialize a list to store errors
    scalar_products = scalar_products_QPM(u) # Initialize the scalar product list

    while error > error_tolerance and iter < max_iter:

        # orthonormalize rows
        for i in range(n_slider.value):
            u[i, :, :] = orthonormalize_vectors_svd(u[i, :, :]) 

        # orthonormalize columns
        for j in range(n_slider.value):
            u[:, j, :] = orthonormalize_vectors_svd(u[:, j, :]) 

        error = error_QPM(u)
        errors.append(error)  # Append the current error to the list    

        if iter % 10 == 0:
            scalar_products = scalar_products_QPM(u) # Update scalar prodcuts
        iter += 1
    return (
        error,
        error_tolerance,
        errors,
        i,
        iter,
        j,
        max_iter,
        scalar_products,
        u,
    )


@app.cell
def _():
    return


if __name__ == "__main__":
    app.run()