Walsh-Hadamard Transform

Hadamard matrix

Definition: a square matrix whose entries are either +1 or -1, and whose rows are mutually orthogonal.

Properties: HHT=nInH H^T = n I_n

Sylvester’s construction for the 2^n * 2^n case:

H20=[1]H21=[1111]H2n+1=[H2nH2nH2nH2n]orH2n+1=H21H2nH_{2^0} = [1] \quad H_{2^1} = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \quad H_{2^{n+1}} = \begin{bmatrix} H_{2^n} & H_{2^n} \\ H_{2^n} & -H_{2^n} \end{bmatrix} \quad or \quad H_{2^{n+1}} = H_{2^1} \otimes H_{2^n}

Hadamard conjecture for the n = 4*k case:

Hadamard gate for qutrits

From several places (1 2 3) I found the Hadamard gate for qutrits:

H3=[1111ωω21ω2ω]ω=e2iπ3 H_3 = \begin{bmatrix} 1 & 1 & 1 \\ 1 & \omega & \omega^2 \\ 1 & \omega^2 & \omega \end{bmatrix} \qquad \omega = e^{\frac{2i\pi}{3}}

It is not a Hadamard matrix, since H3H3T=3[100001010]3I3H_3 H_3^T = 3 \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} \neq 3 I_3

Question: Why is this matrix chosen to be the THadamard gate?

fWHT examples

Boolean function AND

I borrowed from these slides.

x1 x2 f(x1, x2) = x1 AND x2
1 1 1
1 -1 1
-1 1 1
-1 -1 -1

The column vector can be used to represent the boolean functions. 4 basis functions are:

1 x2 x1 x1⋅x2
1 1 1 1 1
x2 1 -1 1 -1
x1 1 1 -1 -1
x1⋅x2 1 -1 -1 1

The fWHT for AND is:

H4f=[1111111111111111][1111]=[31313113] H_4 ⋅ f_{\land} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix} ⋅ \begin{bmatrix} 1 \\ 1 \\ 1 \\ -1 \end{bmatrix} = \begin{bmatrix} 3-1 \\ 3-1 \\ 3-1 \\ 1-3 \end{bmatrix}

The AND function is thus “analyzed” into the following one:

f(x1,x2)=14[(31)1+(31)x2+(31)x1+(13)x1x2]f(x_1, x_2) = \frac{1}{4} [(3-1)⋅1 + (3-1)⋅x_2 + (3-1)⋅x_1 + (1-3)⋅x_1 x_2]

Boolean function NOT

x f(x) = NOT(x)
1 -1
-1 1

The column vector can be used to represent the boolean functions.

H2not=[1111][11]=[+1111]=[02]H_2 ⋅ not = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} ⋅ \begin{bmatrix} -1 \\ 1 \end{bmatrix} = \begin{bmatrix} +1-1 \\ -1-1 \end{bmatrix} = \begin{bmatrix} 0 \\ -2 \end{bmatrix}

So NOT can be analyzed into:

not(x)=12[(11)1+(11)x]=xnot(x) = \frac{1}{2} [(1-1)⋅1 + (-1-1)⋅x] = -x

Similarly, for ID(x) = xconstF(x) = F, and constT(x) = T, we have:

H2id=[02]id(x)=12[01+2x]=xH_2 ⋅ id = \begin{bmatrix} 0 \\ 2 \end{bmatrix} \qquad id(x) = \frac{1}{2} [0⋅1 + 2⋅x] = x \newline H2constF=[20]constF(x)=12[21+0x]=1H_2 ⋅ constF = \begin{bmatrix} 2 \\ 0 \end{bmatrix} \qquad constF(x) = \frac{1}{2} [2⋅1 + 0⋅x] = 1 \newline H2constT=[20]constT(x)=12[(2)1+0x]=1H_2 ⋅ constT = \begin{bmatrix} -2 \\ 0 \end{bmatrix} \qquad constT(x) = \frac{1}{2} [(-2)⋅1 + 0⋅x] = -1

The composition of not and id under the other basis is (?):

[02][02]=[proj2(0,0)2×2]=[04]\begin{bmatrix} 0 \\ -2 \end{bmatrix} \odot \begin{bmatrix} 0 \\ 2 \end{bmatrix} = \begin{bmatrix} proj_2(0,0) \\ -2 × 2 \end{bmatrix} = \begin{bmatrix} 0 \\ -4 \end{bmatrix}

The composition of not and constF under the other basis is (?):

[02][20]=[proj2(0,2)2×0]=[20]\begin{bmatrix} 0 \\ -2 \end{bmatrix} \odot \begin{bmatrix} 2 \\ 0 \end{bmatrix} = \begin{bmatrix} proj_2(0,2) \\ -2 × 0 \end{bmatrix} = \begin{bmatrix} 2 \\ 0 \end{bmatrix}

The composition of constT and constF under the other basis is (?):

[20][20]=[proj2(2,2)0×0]=[20]\begin{bmatrix} -2 \\ 0 \end{bmatrix} \odot \begin{bmatrix} 2 \\ 0 \end{bmatrix} = \begin{bmatrix} proj_2(-2,2) \\ 0 × 0 \end{bmatrix} = \begin{bmatrix} 2 \\ 0 \end{bmatrix}

Typed function swap (+ type)

swap :: 1 + 1 -> 1 + 1
| inl () = inr ()
| inr () = inl ()
x f(x) = swap x
inl () inr ()
inr () inl ()

Two basis functions are:

constL :: 1 + 1 -> 1 + 1
| inl () = inl ()
| inr () = inl ()

id :: 1 + 1 -> 1 + 1
| inl () = inl ()
| inr () = inr ()

The corresponding fWHT is (l for inl & r for inr):

H2swap=[lllr][rl]=[lr+lllr+rl]H_2 ⋅ swap = \begin{bmatrix} l & l \\ l & r \end{bmatrix} ⋅ \begin{bmatrix} r \\ l \end{bmatrix} = \begin{bmatrix} l⋅r+l⋅l \\ l⋅r+r⋅l \end{bmatrix}

Question: What does this mean?

Analogous to vectors:

Analyzed into:

swap(x)=12lr[(lr+ll)l+(lr+rl)x]swap(x) = \frac{1}{2|l||r|} [(l⋅r+l⋅l)⋅l + (l⋅r+r⋅l)⋅x]

if we generalize the type for swap a little:

swap :: A + A -> A + A
| inl a = inr a
| inr a = inl a

There is no significant difference except the pattern-matched value a : A:

Fully generalized swap

swap :: A + B -> B + A
| inl a = inr a
| inr b = inl b
x f(x) = swap x
inl a inr a
inr b inl b

Two basis functions would be:

b0(f) :: A + B -> B + A
| inl a = inl (f a)
| inr b = inl b
    where 
        f :: A -> B

b1(f,g) :: A + B -> B + A
| inl a = inl (f a)
| inr b = inr (g b)
    where 
        f :: A -> B
        g :: B -> A

This is a bit strange since they are parameterized.

The corresponding fWHT is:

H2swap=[l(f(a))l(f(a))l(b)r(g(a))][r(a)l(b)]H_2 ⋅ swap = \begin{bmatrix} l(f(a)) & l(f(a)) \\ l(b) & r(g(a)) \end{bmatrix} ⋅ \begin{bmatrix} r(a) \\ l(b) \end{bmatrix}

It breaks the symmetricity. Impose b = f(a)?

THadamard example

Come up with a function whose type is 3 -> 3 (similar to NOT whose type is 2 -> 2):

x f(x)
11 ω\omega
ω\omega ω2\omega^2
ω2\omega^2 11

It’s a one-cycle permutation. The 3 basis functions are:

x x^0 x^1 x^2
11 11 11 11
ω\omega 11 ω\omega ω2\omega^2
ω2\omega^2 11 ω2\omega^2 ω\omega

The fWHT for this function f is:

H3f=[1111ωω21ω2ω][ωω21]=[ω+ω2+1ω+1+ω2ω+ω+ω]H_3 ⋅ f = \begin{bmatrix} 1 & 1 & 1 \\ 1 & \omega & \omega^2 \\ 1 & \omega^2 & \omega \end{bmatrix} ⋅ \begin{bmatrix} \omega \\ \omega^2 \\ 1 \end{bmatrix} = \begin{bmatrix} \omega + \omega^2 + 1 \\ \omega + 1 + \omega^2 \\ \omega + \omega + \omega \end{bmatrix}

This function f is analyzed into:

f(x)=13[(ωω21)1+(ω1ω2)x+(ωωω)x2]f(x) = \frac{1}{3} [(\omega \oplus \omega^2 \oplus 1)⋅1 + (\omega \oplus 1 \oplus \omega^2)⋅x + (\omega \oplus \omega \oplus \omega) ⋅ x^2]

What does this mean?