Find the Givens embedding ${}^{i}G_{j,k}(A)$

Converts a gray mapped decimal number to simple binary mapped decimal number. This routine follows the inverse mapping of the function gray_ordering()

Parameters

• $n$ The number of digits in the equivalent binary mapping
• $g$ The gray mapped decimal number
• $d$ The simple binary mapped decimal number

julia> G2D.(0:7,3)
[0,1,3,2,7,6,4,5]

For a given unitary matrix $U$, it finds the cascaded rotation matrix $C$ such that $C\times U =I$, except for the diagonal element of the $n$th element which is $\det(U)$. The matrix $C$ is obtained by the cascade of several (i.e., $2^{n-1}(2^{n}-1)$) two level Givens rotation matrices, namely,

\[C = \prod_{i=1}^{n-1} \prod_{j=0}^{n-1-i}{ {}^{i}G_{n-j,n-j-1}}\]

\[\prod_{i=1}^{n-1} \prod_{j=0}^{n-1-i}{ {}^{i}G_{n-j,n-j-1} U(n)} = \begin{pmatrix} 1 & \ldots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \ldots & \det(U)\end{pmatrix}.\]

Parameters

• U – Input. Unitary matrix of size $n$
• Ic – Identity matix with the exception that the last diagonal entry ($n$th diagonal element) which is $\det(U)$.
• C – The cascaded rotation matrix ${}^{n-1}G_{n} \times {}^{n-2}G_{n-1} \times {}^{n-2}G_{n} \times \ldots \times {}^{2}G_{3} \times \ldots \times {}^{2}G_{n-1} \times {}^{2}G_{n} \times {}^{1}G_{2} \times \ldots \times {}^{1}G_{n-1} \times {}^{1}G_{n}$

Examples

julia> using LinearAlgebra
julia> N=4;A=rand(N,N)+im*rand(N,N);S=svd(A);U=S.U
4×4 Matrix{ComplexF64}:
  -0.4-0.06im   0.23-0.73im  -0.03-0.14im   0.39-0.27im
 -0.61-0.32im   0.07+0.06im   0.32+0.02im  -0.64-0.08im
 -0.38-0.33im  -0.48+0.38im  -0.07-0.4im    0.46+0.07im
  -0.2-0.26im  -0.09-0.14im   -0.7+0.47im  -0.09+0.38im
julia> Gc,Ic=Gcascaded(U)
4×4 Matrix{ComplexF64}:
 1.0+0.0im   0.0+0.0im  -0.0+0.0im   0.0-0.0im
 0.0+0.0im   1.0-0.0im   0.0+0.0im  -0.0-0.0im
 0.0-0.0im  -0.0+0.0im   1.0+0.0im   0.0+0.0im
 0.0-0.0im  -0.0+0.0im   0.0-0.0im   0.4-0.9im
julia> det(A)
0.4166084175706718 - 0.9090860390575042im

Find the matrix which has a Givens matrix embedding ${}^{i}G_{j,k}(A)$.

For a given matrix $A$, a generic rotation matrix ${}^{i}G_{j,k}(A)$ is generated. The matrix ${}^{i}G_{j,k}(A)$ is such that it helps to selectively nullifies an element of matrix $V={}^{i}G_{j,k}(A) A$. That is, $V_{j,i}=0$ where $V={}^{i}G_{j,k}(A) A$. The fllowing Givens rotation matrix ${}^{i}\Gamma_{j,k}$

\[\begin{aligned} {}^{i}\Gamma_{j,k} &= \begin{pmatrix} {}^{i}g_{k,k} & {}^{i}g_{k,j} \\ {}^{i}g_{j,k} & {}^{i}g_{j,j}\end{pmatrix} \\ &=\frac{1}{\sqrt{\lvert a_{j,i} \rvert^{2}+ \lvert a_{k,i} \rvert^{2}}}\begin{pmatrix} a_{k,i}^{*} & a_{j,i}^{*} \\ -a_{j,i} & {}^{i}a_{k,i}\end{pmatrix}. \end{aligned}\]

is embedded in an identity matrix $I(n)$ to produce,

\[{}^{i}G_{j,k}(A) = \begin{pmatrix} 1 & 0 & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & 0 \\ 0 & 1 & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \ddots & {\color{red} {}^{i}g_{k,k}} & \ddots & {\color{red} {}^{i}g_{k,j}} & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \ddots \ddots & & \ddots & \ddots & \vdots \\ 0 & 0 & \ddots & {\color{red} {}^{i}g_{j,k}} & \ddots & {\color{red} {}^{i}g_{j,j}} & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \ldots & \ldots & \ldots & \ldots & \ldots & 1 & 0 \\ 0 & 0 & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & 1 \end{pmatrix}.\]

Essentially, ${}^{i}G_{j,k}(A)$ is a modified identity matrix such that four non trivial elements are taken from the givens rotation matrix ${}^{i}\Gamma_{j,k}$.

Decomposition of aribtrary unitary matrix $U(n) \in S(2^n)$, as a cascade of two level Givens matrices.

Using the following property,

\[\prod_{j=0}^{n-1}{ {}^{1}G_{n-j,n-j-1} U(n)} = \begin{pmatrix} 1 & 0 \\ 0 & U(n-1)\end{pmatrix}\]

\[\prod_{i=1}^{n-1} \prod_{j=0}^{n-1-i}{ {}^{i}G_{n-j,n-j-1} U(n)} = \begin{pmatrix} 1 & \ldots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \ldots & \det(U)\end{pmatrix}.\]

There are $2^{n-1}(2^{n}-1)$ number of unitary two-level matrices (each of them formed by embedding a Givens rotaton matrix into indentity matrix). Note that $\sum_{i=1}^{2^{n}}{N-i}=2^{n-1}(2^{n}-1)$.

Parameters

• U – Input. Unitary matrix of size $2^n$
• V – Output unitary matrix in two level form [1 0;0 U'] form where U' is a unitary matrix of size $2^{n-1}$.
• Gm – The $(n-2)(n-1)$ sequence of Given matrices (in augmented form) $[{}^{1}G_{n}\lvert{}^{1}G_{n-1}\lvert\ldots\lvert{}^{1}G_{2}\lvert {}^{2}G_{n}\lvert{}^{2}G_{n-1}\lvert\ldots\lvert{}^{2}G_{3}\lvert\ldots\lvert{}^{n-2}G_{n}\lvert{}^{n-2}G_{n-1}\lvert{}^{n-1}G_{n}]$
• Gs – The $(n-2)(n-1)$ sequence of Given matrices (in augmented form) left to right $[ {}^{n-1}G_{n} \lvert {}^{n-2}G_{n-1} \lvert {}^{n-2}G_{n} \lvert \ldots \lvert {}^{2}G_{3} \lvert \ldots \lvert {}^{2}G_{n-1} \lvert {}^{2}G_{n} \lvert{}^{1}G_{2} \lvert \ldots \lvert {}^{1}G_{n-1} \lvert {}^{1}G_{n} ]$

Examples

julia> using LinearAlgebra
julia> N=4;A=rand(N,N)+im*rand(N,N);S=svd(A);U=S.U
julia> Gn(U)

Generate Encoding and Decoding matrices for Gray Codes of alphabet.

julia> G,B,g,b=GrayMatrix(4, 2);
julia> G
    4×4 Matrix{Int64}:
    1  0  0  0
    1  1  0  0
    1  1  1  0
    1  1  1  1
    julia> B
    4×4 Matrix{Int64}:
    1  0  0  0
    1  1  0  0
    0  1  1  0
    0  0  1  1
    julia> g 
    4×16 Matrix{Int64}:
    0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1
    0  0  0  0  1  1  1  1  0  0  0  0  1  1  1  1
    0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1
    0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1
    julia> b 
    4×16 Matrix{Int64}:
    0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1
    0  0  0  0  1  1  1  1  1  1  1  1  0  0  0  0
    0  0  1  1  1  1  0  0  0  0  1  1  1  1  0  0
    0  1  1  0  0  1  1  0  0  1  1  0  0  1  1  0

Binary to decimal number conversion. Input can be

• binary strings,
• binary digits or
• a vector of binary string or digits

julia> bin2dec([011,"0111",0111])

Decimal to binary conversion

Plot the DNA codon matrix

julia> dnamatrix()

Generate Gray vectors

Recursive construction of binary Gray code digits.

Gray code $g[n]$ can be recursively constructed as follows. Start with $g[1] = (0,1) = (g_{1},g_{2})$

\[g[n+1] = 0g_{1},...,0g_{N−1},0g_{N},1g_{N},1g_{N−1},...,1g_{1}.\]

Examples

julia> gray(3)
3×8 Matrix{Int64}:
 0  0  0  0  1  1  1  1
 0  0  1  1  0  1  1  0
 0  1  1  0  1  1  0  0

For $n$ bits, with the corresponding decimal sequence $x=0,1,2,\ldots,2^{n-1}$, find the gray ordering sequence using the bitwise XOR logic. Namely. $gπ= x ⊻ \lfloor x/2 \rfloor = x \oplus \lfloor x/2 \rfloor$ where $⊻$ is the bitwise XOR operation.

julia> gray_ordering(3)
[0,1,3,2,6,7,5,4]

Recursive function to illustrate the reflection+shift property of Gray mapping.

Arguents

• n - The iteration number n ≥ 0
• C - The decimal sequence of the gray mapped bits
• R - The reflected sequence (without shifting)

julia> C,R = gray_recursion(4)

Given unitary matrux $U(n) \in S(2^n)$, it uses a a repeated Givens rotations to get a to level matrix as follows.

\[\prod_{j=1}^{n-2}{ {}^{1}G_{n-j,n-j-1} U(n)} = \begin{pmatrix} 1 & 0 \\ 0 & U(n-1)\end{pmatrix}\]

Parameters

• U – Input. Unitary matrix of size $2^n$
• V – Output unitary matrix in two level form [1 0;0 U'] form where U' is a unitary matrix of size $2^{n-1}$.
• GG – The $n-2$ sequence of Given matrices (in augmented form) $[{}^{1}G_{n}\lvert{}^{1}G_{n-1}\lvert\ldots\lvert{}^{1}G_{2}]$

Examples

julia> level2unitary(U)

Plots a matrix into a 2D with labels. Optional arguments including colors

julia> using Random;
julia> A= rand(0:9,10,10);
julia> matrixplot(A)

Pulse amplitude modulation (PAM) mapping. This is a type of digital modulation mapping used in Communication systems.

Given a matrix $A$ (usually a unitary matrix) and indices $(i,j,k)$, find the $\Gamma$ Givens rotation matrix and the Givens matrix embedding ${}^{i}G_{j,k}(A)$ matrix.

For a given matrix $A$, a generic rotation matrix ${}^{i}G_{j,k}(A)$ is generated. The matrix ${}^{i}G_{j,k}(A)$ is such that it helps to selectively nullifies an element of matrix $V={}^{i}G_{j,k}(A) A$. That is, $V_{j,i}=0$ where $V={}^{i}G_{j,k}(A) A$. The fllowing Givens rotation matrix ${}^{i}\Gamma_{j,k}$

\[\begin{aligned} {}^{i}\Gamma_{j,k} &= \begin{pmatrix} {}^{i}g_{k,k} & {}^{i}g_{k,j} \\ {}^{i}g_{j,k} & {}^{i}g_{j,j}\end{pmatrix} \\ &=\frac{1}{\sqrt{\lvert a_{j,i} \rvert^{2}+ \lvert a_{k,i} \rvert^{2}}}\begin{pmatrix} a_{k,i}^{*} & a_{j,i}^{*} \\ -a_{j,i} & {}^{i}a_{k,i}\end{pmatrix}. \end{aligned}\]

is embedded in an identity matrix $I(n)$ to produce,

\[{}^{i}G_{j,k}(A) = \begin{pmatrix} 1 & 0 & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & 0 \\ 0 & 1 & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \ddots & {\color{red} {}^{i}g_{k,k}} & \ddots & {\color{red} {}^{i}g_{k,j}} & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \ddots \ddots & & \ddots & \ddots & \vdots \\ 0 & 0 & \ddots & {\color{red} {}^{i}g_{j,k}} & \ddots & {\color{red} {}^{i}g_{j,j}} & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \ldots & \ldots & \ldots & \ldots & \ldots & 1 & 0 \\ 0 & 0 & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & 1 \end{pmatrix}.\]

Essentially, ${}^{i}G_{j,k}(A)$ is a modified identity matrix such that four non trivial elements are taken from the givens rotation matrix ${}^{i}\Gamma_{j,k}$.

julia> using LinearAlgebra
julia> using GrayCoding
julia>n=2;N=2^n;A=rand(N,N)+im*rand(N,N);S=svd(A);U=S.U
4×4 Matrix{ComplexF64}:
 -0.365903-0.405021im   0.442293-0.0769938im  …   0.115307-0.288609im
 -0.285173-0.35669im   -0.671764+0.0698449im     -0.384583+0.295428im
 -0.196831-0.611652im  -0.154487+0.0160399im      0.379159-0.121825im
 -0.177839-0.221435im   0.536228-0.175044im      -0.338822+0.62835im
julia> i,j,k=1,2,4
julia> Γ,G,GA=quantumΓ(U,i,j,k);
julia> round.(quantumΓ(S.U,1,2,4)[1],digits=1)
2×2 Matrix{ComplexF64}:
 -0.3+0.4im  -0.5+0.7im
  0.5+0.7im  -0.3-0.4im
julia> round.(quantumΓ(S.U,1,2,4)[2],digits=1)
4×4 Matrix{ComplexF64}:
 1.0+0.0im   0.0+0.0im  0.0+0.0im   0.0+0.0im
 0.0+0.0im  -0.3-0.4im  0.0+0.0im   0.5+0.7im
 0.0+0.0im   0.0+0.0im  1.0+0.0im   0.0+0.0im
 0.0+0.0im  -0.5+0.7im  0.0+0.0im  -0.3+0.4im
julia> round.(quantumΓ(S.U,1,2,4)[3],digits=1)
4×4 Matrix{ComplexF64}:
 -0.4-0.4im   0.4-0.1im   0.6+0.1im   0.1-0.3im
  0000000     0.7+0.5im  -0.2-0.4im  -0.3+0.2im
 -0.2-0.6im  -0.2+0.0im  -0.4-0.5im   0.4-0.1im
  0.5+0.0im   0.2-0.2im  -0.2-0.1im  -0.1-0.8im

Reflected code.

julia>reflect_code(3)
[0,1,3,2,2,3,1,0]

Quantum circuit decomposition. For nan arbitrary unitary matix for $n$ qubits. Arbitrary quantum circuit abstracted by unitary matrix $U$ decomposed by $2^{n-1}2^{n}$ unitary two-level matrices, each of which corresponds ${}^{i}\Gamma_{j,k}$. The program produce the $\Gamma$ matrix and the coefficients $i,j,k$. The quantum circuit of this decomposition can be visualized as a cascade (from left to right) of this matrix.

The unitary matrix $U$ corresponding to of the 3 quibit Tiffoli quantum gate

\[U=\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & {\color{red}0} & {\color{red}1} \\ 0 & 0 & 0 & 0 & 0 & 0 & {\color{red}1} & {\color{red}0} \\ \end{pmatrix}\]