Walsh-Hadamard Transform

Hadamard matrix

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

Properties: $H H^T = n I_n$

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

$H_{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:

• its existence is still an open question.
• the smallest n for which no Hadamard matrix is presently known is 668.

Hadamard gate for qutrits

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

$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 $H_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:

$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(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.

$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) = \frac{1}{2} [(1-1)⋅1 + (-1-1)⋅x] = -x$

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

$H_2 ⋅ id = \begin{bmatrix} 0 \\ 2 \end{bmatrix} \qquad id(x) = \frac{1}{2} [0⋅1 + 2⋅x] = x \newline$ $H_2 ⋅ constF = \begin{bmatrix} 2 \\ 0 \end{bmatrix} \qquad constF(x) = \frac{1}{2} [2⋅1 + 0⋅x] = 1 \newline$ $H_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 (?):

$\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 (?):

$\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 (?):

$\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):

$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:

• l and r are two vectors whose angle are π.
• |l| = |r| should hold.
• ⋅ is dot product.
• + is scalar sum.

Analyzed into:

$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:

• inl and inr are like unit vectors with angle π.
• what does a : A mean here? a scalar?

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:

$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)
$1$	$\omega$
$\omega$	$\omega^2$
$\omega^2$	$1$

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

x	x^0	x^1	x^2
$1$	$1$	$1$	$1$
$\omega$	$1$	$\omega$	$\omega^2$
$\omega^2$	$1$	$\omega^2$	$\omega$

The fWHT for this function f is:

$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) = \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?