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 H H^T = n I_n H H T = n I n
Sylvester’s construction for the 2^n * 2^n
case:
H 2 0 = [ 1 ] H 2 1 = [ 1 1 1 − 1 ] H 2 n + 1 = [ H 2 n H 2 n H 2 n − H 2 n ] o r H 2 n + 1 = H 2 1 ⊗ H 2 n 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} H 2 0 = [ 1 ] H 2 1 = [ 1 1 1 − 1 ] H 2 n + 1 = [ H 2 n H 2 n H 2 n − H 2 n ] or H 2 n + 1 = H 2 1 ⊗ 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 = [ 1 1 1 1 ω ω 2 1 ω 2 ω ] ω = e 2 i π 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}} H 3 = 1 1 1 1 ω ω 2 1 ω 2 ω ω = e 3 2 iπ
It is not a Hadamard matrix, since H 3 H 3 T = 3 [ 1 0 0 0 0 1 0 1 0 ] ≠ 3 I 3 H_3 H_3^T = 3 \begin{bmatrix}
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0
\end{bmatrix}
\neq
3 I_3 H 3 H 3 T = 3 1 0 0 0 0 1 0 1 0 = 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 ∧ = [ 1 1 1 1 1 − 1 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 ] ⋅ [ 1 1 1 − 1 ] = [ 3 − 1 3 − 1 3 − 1 1 − 3 ]
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}
H 4 ⋅ f ∧ = 1 1 1 1 1 − 1 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 ⋅ 1 1 1 − 1 = 3 − 1 3 − 1 3 − 1 1 − 3
The AND
function is thus “analyzed” into the following one:
f ( x 1 , x 2 ) = 1 4 [ ( 3 − 1 ) ⋅ 1 + ( 3 − 1 ) ⋅ x 2 + ( 3 − 1 ) ⋅ x 1 + ( 1 − 3 ) ⋅ x 1 x 2 ] 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] f ( x 1 , x 2 ) = 4 1 [( 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 ⋅ n o t = [ 1 1 1 − 1 ] ⋅ [ − 1 1 ] = [ + 1 − 1 − 1 − 1 ] = [ 0 − 2 ] 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} H 2 ⋅ n o t = [ 1 1 1 − 1 ] ⋅ [ − 1 1 ] = [ + 1 − 1 − 1 − 1 ] = [ 0 − 2 ]
So NOT
can be analyzed into:
n o t ( x ) = 1 2 [ ( 1 − 1 ) ⋅ 1 + ( − 1 − 1 ) ⋅ x ] = − x not(x) = \frac{1}{2} [(1-1)⋅1 + (-1-1)⋅x] = -x n o t ( x ) = 2 1 [( 1 − 1 ) ⋅ 1 + ( − 1 − 1 ) ⋅ x ] = − x
Similarly, for ID(x) = x
, constF(x) = F
, and constT(x) = T
, we have:
H 2 ⋅ i d = [ 0 2 ] i d ( x ) = 1 2 [ 0 ⋅ 1 + 2 ⋅ x ] = x H_2 ⋅ id =
\begin{bmatrix}
0 \\ 2
\end{bmatrix}
\qquad
id(x) = \frac{1}{2} [0⋅1 + 2⋅x] = x
\newline H 2 ⋅ i d = [ 0 2 ] i d ( x ) = 2 1 [ 0 ⋅ 1 + 2 ⋅ x ] = x
H 2 ⋅ c o n s t F = [ 2 0 ] c o n s t F ( x ) = 1 2 [ 2 ⋅ 1 + 0 ⋅ x ] = 1 H_2 ⋅ constF =
\begin{bmatrix}
2 \\ 0
\end{bmatrix}
\qquad
constF(x) = \frac{1}{2} [2⋅1 + 0⋅x] = 1
\newline H 2 ⋅ co n s tF = [ 2 0 ] co n s tF ( x ) = 2 1 [ 2 ⋅ 1 + 0 ⋅ x ] = 1
H 2 ⋅ c o n s t T = [ − 2 0 ] c o n s t T ( x ) = 1 2 [ ( − 2 ) ⋅ 1 + 0 ⋅ x ] = − 1 H_2 ⋅ constT =
\begin{bmatrix}
-2 \\ 0
\end{bmatrix}
\qquad
constT(x) = \frac{1}{2} [(-2)⋅1 + 0⋅x] = -1 H 2 ⋅ co n s tT = [ − 2 0 ] co n s tT ( x ) = 2 1 [( − 2 ) ⋅ 1 + 0 ⋅ x ] = − 1
The composition of not
and id
under the other basis is (?):
[ 0 − 2 ] ⊙ [ 0 2 ] = [ p r o j 2 ( 0 , 0 ) − 2 × 2 ] = [ 0 − 4 ] \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} [ 0 − 2 ] ⊙ [ 0 2 ] = [ p ro j 2 ( 0 , 0 ) − 2 × 2 ] = [ 0 − 4 ]
The composition of not
and constF
under the other basis is (?):
[ 0 − 2 ] ⊙ [ 2 0 ] = [ p r o j 2 ( 0 , 2 ) − 2 × 0 ] = [ 2 0 ] \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} [ 0 − 2 ] ⊙ [ 2 0 ] = [ p ro j 2 ( 0 , 2 ) − 2 × 0 ] = [ 2 0 ]
The composition of constT
and constF
under the other basis is (?):
[ − 2 0 ] ⊙ [ 2 0 ] = [ p r o j 2 ( − 2 , 2 ) 0 × 0 ] = [ 2 0 ] \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} [ − 2 0 ] ⊙ [ 2 0 ] = [ p ro j 2 ( − 2 , 2 ) 0 × 0 ] = [ 2 0 ]
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 ⋅ s w a p = [ l l l r ] ⋅ [ r l ] = [ l ⋅ r + l ⋅ l l ⋅ r + r ⋅ l ] 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} H 2 ⋅ s w a p = [ l l l r ] ⋅ [ r l ] = [ l ⋅ r + l ⋅ l l ⋅ r + r ⋅ l ]
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:
s w a p ( x ) = 1 2 ∣ l ∣ ∣ r ∣ [ ( l ⋅ r + l ⋅ l ) ⋅ l + ( l ⋅ r + r ⋅ l ) ⋅ x ] swap(x) = \frac{1}{2|l||r|} [(l⋅r+l⋅l)⋅l + (l⋅r+r⋅l)⋅x] s w a p ( x ) = 2∣ l ∣∣ r ∣ 1 [( 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 ⋅ s w a p = [ 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} H 2 ⋅ s w a p = [ l ( f ( a )) l ( b ) l ( f ( a )) r ( g ( a )) ] ⋅ [ r ( a ) l ( b ) ]
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 1 1
ω \omega ω
ω \omega ω
ω 2 \omega^2 ω 2
ω 2 \omega^2 ω 2
1 1 1
It’s a one-cycle permutation. The 3 basis functions are:
x
x^0
x^1
x^2
1 1 1
1 1 1
1 1 1
1 1 1
ω \omega ω
1 1 1
ω \omega ω
ω 2 \omega^2 ω 2
ω 2 \omega^2 ω 2
1 1 1
ω 2 \omega^2 ω 2
ω \omega ω
The fWHT for this function f
is:
H 3 ⋅ f = [ 1 1 1 1 ω ω 2 1 ω 2 ω ] ⋅ [ ω ω 2 1 ] = [ ω + ω 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} H 3 ⋅ f = 1 1 1 1 ω ω 2 1 ω 2 ω ⋅ ω ω 2 1 = ω + ω 2 + 1 ω + 1 + ω 2 ω + ω + ω
This function f
is analyzed into:
f ( x ) = 1 3 [ ( ω ⊕ ω 2 ⊕ 1 ) ⋅ 1 + ( ω ⊕ 1 ⊕ ω 2 ) ⋅ x + ( ω ⊕ ω ⊕ ω ) ⋅ x 2 ] 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] f ( x ) = 3 1 [( ω ⊕ ω 2 ⊕ 1 ) ⋅ 1 + ( ω ⊕ 1 ⊕ ω 2 ) ⋅ x + ( ω ⊕ ω ⊕ ω ) ⋅ x 2 ]
What does this mean?