# Problem Statement

The problem is to calculate the coefficients $A_{j_1\cdots j_n}$, of a square matrix A with size $N$ by $N$ of complex double elements, whose weighted sum with $N^2$ irreducible matrices $[j_1]\otimes \cdots \otimes [j_n]$ is equal to $A$. $N=2^n$, where $n$ is a natural number. $[j]$ are the Pauli matrices for $j=(1,2,3)$ or identity for $j=0$. $\otimes$ is the Kronecker product.

# Input

Square matrix $A$ with size (2^n,2^n), where $n$ is a natural number.

# Output

Weighted coefficients $A_{j_1\cdots j_n}$, where $j=(0,1,2,3)$.

# Details that might be relevant in identifying Missing Application

I wrote a program that computes the full decomposition of a $N \times N$ matrix into the sum of weighted gamma matrices and their multi-linears in $\mathcal{O}(N^2\log{}N)$ steps. $$A = \sum_{k=0}^{n}\sum_{j=1}^{\begin{pmatrix}2n+1 \\ k\end{pmatrix}} A_{k\{j\}}\sigma^{k\{j\}}$$ $A$ is the matrix to decompose. $N=2^n$, where $n$ is a natural number. $A_{k\{j\}}$ are the weighted elements to be computed. $\sigma^{k\{j\}}=\gamma^{j_{1}}\gamma^{j_{2}}\gamma^{j_{3}}\cdots$ are the multi-linears equal to the product of $k$ unique gamma matrices. $k\{j\}$ is the $j$th set of uniquely chosen $k$ indices. For example in $N=4$ and $k = 2$: $k\{j\}$ is pick the $j$th element from the list $(01,02,03,04,12,13,14,23,24,34)$, where none of elements share the same indices. Another representation of $$A = \sum_{j_1=0}^{3}\cdots \sum_{j_n=0}^{3} \ [j_1]\otimes \cdots \otimes[j_n] \ A_{j_1 \cdots j_n}$$ where $\otimes$ is the Kronecker product, $[1]$, $[2]$, $[3]$, are the Pauli matrices, $[0]$ is identity, $A_{j_1 \cdots j_n}$ are the weighted elements to be computed in a different basis, and $(j_1 \cdots j_n)$ can be treated as a number in base 4. One can show that multipliting two matrices $[j_1]\otimes \cdots \otimes[j_n]$ and $[l_1]\otimes \cdots \otimes[l_n]$ to get $[g_1]\otimes \cdots \otimes[g_n]$ is equivalent to $(j_1 \cdots j_n)$ xor $(l_1 \cdots l_n)$ = $(g_1 \cdots g_n)$ but missing the sign.

There exists a simple map between $A_{k\{j\}} \longleftrightarrow A_{j_1\cdots j_n}$.

# Questions

(1) Does this algorithm already exist?

(2) Does it have an application?

• Is this algorithm better than the current gold-standard for solving this problem? (What is the standard algorithm?) – Raphael Jan 4 '16 at 16:25
• @Raphael I am asking for the current gold-standard algorithm as well. I do not know what the gold-standard algorithm is if it exists. – linuxfreebird Jan 4 '16 at 16:59
• I'm struggling to understand what algorithmic task/problem your algorithm solves. Can you give a self-contained description of what the problem is? What are the inputs and the outputs? What's a weighted gamma matrix? What's a multi-linear? What's a non-permutation? What does $k\{j\}$ mean? (I see what you wrote but I can't understand it; what $k$ indices are you referring to?) What's the definition of $\gamma^{j_i}$? What field are you working over? Is this for real numbers, rationals, or something else? – D.W. Jan 4 '16 at 21:00
• @D.W. I implemented your suggestions. Please let me know if more clarification is needed. Thanks. – linuxfreebird Jan 5 '16 at 3:47
• Looks like something related to multipartite quantum states. Your last displayed equation is how to construct the density matrix of a multi-qubit state from its correlation tensor. – celtschk Jan 14 '16 at 22:36