Quantum Computing: The Walsh-Hadamard Matrix — Backbone of Grover's Diffusion Operator

Originally published on malcolmlow.net

In the Grover's Algorithm — Inversion About the Mean walkthrough, the diffusion operator applies H⊗³ twice per iteration. Every single step is governed by a sign table called the Hadamard Reference. That table is not a lookup shortcut — it is the 8×8 Walsh-Hadamard Transform matrix written out in full. This post derives it from scratch: one qubit, then two, then all three, arriving at the complete matrix and the rule behind every sign in it.

1 · The Circuit: Three Qubits, Three Hadamard Gates

We initialise all three qubits in the ground state |0⟩ and route each through its own independent Hadamard gate. There are no two-qubit (entangling) gates — the circuit is entirely parallel.

All three outputs are identical because all three inputs are identical. The structure emerges when we take their tensor product.

2 · Single-Qubit Hadamard Action

In matrix form:

H = (1/√2) [ +1  +1 ]

            [ +1  -1 ]

Key property: H is its own inverse — H² = I. Every element has magnitude 1/√2, so tensoring three copies multiplies the magnitudes to 1/√8 while the signs follow a precise bitwise pattern.

3 · Two-Qubit Tensor Product: q₀ ⊗ q₁

|+⟩ ⊗ |+⟩

= (1/√2)(|0⟩ + |1⟩) ⊗ (1/√2)(|0⟩ + |1⟩)

= (1/2)( |00⟩ + |01⟩ + |10⟩ + |11⟩ )

All four two-qubit basis states appear with equal amplitude 1/2. Measurement probability per state: (1/2)² = 25%.

4 · Three-Qubit Tensor Product: q₀ ⊗ q₁ ⊗ q₂

|+⟩ ⊗ |+⟩ ⊗ |+⟩

= (1/√8)( |000⟩ + |001⟩ + |010⟩ + |011⟩

        + |100⟩ + |101⟩ + |110⟩ + |111⟩ )

This is |ψinit⟩ — the uniform superposition over all 8 basis states that opens Grover's algorithm. Each state carries amplitude +1/√8 ≈ 0.3535 and measurement probability 1/8 = 12.5%.

5 · The 8×8 Walsh-Hadamard Sign Matrix

When H⊗³ is applied to an arbitrary basis state |j⟩:

H⊗³ |j⟩ = (1/√8) Σᵢ (−1)^popcount(i AND j) |i⟩

The entry at row i, column j carries sign (−1)^popcount(i AND j) divided by √8.

+ = amplitude +1/√8 ≈ +0.3535 / − = amplitude −1/√8 ≈ −0.3535

          |000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩

          ─────────────────────────────────────────────────

H|000⟩ →    +     +     +     +     +     +     +     +

H|001⟩ →    +     −     +     −     +     −     +     −

H|010⟩ →    +     +     −     −     +     +     −     −

H|011⟩ →    +     −     −     +     +     −     −     +

H|100⟩ →    +     +     +     +     −     −     −     −

H|101⟩ →    +     −     +     −     −     +     −     +

H|110⟩ →    +     +     −     −     −     −     +     +

H|111⟩ →    +     −     −     +     −     +     +     −

Each row shows how an input basis state |j⟩ distributes its amplitude across all 8 output states after H⊗³ is applied.

6 · Why the Sign is (−1)^popcount(i AND j)

Because H acts independently on each qubit, H⊗³ is the tensor product of three 2×2 matrices. The entry at row i, column j is the product of the three corresponding single-qubit entries:

H⊗³[i, j] = H[i₀, j₀] × H[i₁, j₁] × H[i₂, j₂]

Each single-qubit factor equals +1 unless both the k-th bit of i and the k-th bit of j are 1, in which case it equals −1. Multiplying all three:

sign(i, j) = (−1)^(i₀j₀ + i₁j₁ + i₂j₂) = (−1)^popcount(i AND j)

The rule in plain terms: bitwise AND the row index and the column index, count the 1-bits, check parity. Even count → positive. Odd count → negative.

Quick verification: row H|101⟩, column |011⟩

Matches the matrix in Section 5: row H|101⟩, column |011⟩ is indeed −.

7 · Connection to Grover's Diffusion Operator

This matrix is the Hadamard Reference used throughout the Grover's Algorithm walkthrough. The diffusion operator D = H⊗³ (2|0⟩⟨0| − I) H⊗³ works in three sub-steps, each directly using this matrix:

Without the sign structure of the Walsh-Hadamard matrix, neither the uniform superposition nor the diffusion step would work. The matrix is the silent engine behind Grover's quadratic speedup.

Quantum Series 2026 · Built with Qiskit 1.x