Category: hadamard gate

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

QUANTUM SERIES 2026
The mathematical foundation behind Grover’s diffusion operator — derived from first principles.

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 here — the circuit is entirely parallel.

Qubit Input Gate Output ket
q₀ |0⟩ H (1/√2)( |0⟩ + |1⟩ )
q₁ |0⟩ H (1/√2)( |0⟩ + |1⟩ )
q₂ |0⟩ H (1/√2)( |0⟩ + |1⟩ )

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

2  ·  Single-Qubit Hadamard Action

The Hadamard gate H maps the two computational basis states as follows:

Input H |input⟩ Short notation
|0⟩ (1/√2)( |0⟩ + |1⟩ ) |+⟩
|1⟩ (1/√2)( |0⟩ − |1⟩ ) |−⟩

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₁

Expanding the tensor product of the first two post-H qubits:

|+⟩ ⊗ |+⟩
  = (1/√2)(|0⟩ + |1⟩) ⊗ (1/√2)(|0⟩ + |1⟩)
  = (1/2)( |0⟩⊗|0⟩ + |0⟩⊗|1⟩ + |1⟩⊗|0⟩ + |1⟩⊗|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₂

Adding the third qubit expands the superposition to all 8 three-bit strings:

|+⟩ ⊗ |+⟩ ⊗ |+⟩
  = (1/√2)³ (|0⟩+|1⟩) ⊗ (|0⟩+|1⟩) ⊗ (|0⟩+|1⟩)
  = (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 (Phase 0 in the walkthrough). Each state carries amplitude +1/√8 ≈ 0.3535 and measurement probability 1/8 = 12.5%. All signs are positive because we only applied H to |0⟩ inputs — the sign variation appears when H⊗³ acts on states other than |000⟩.
5  ·  The 8×8 Walsh-Hadamard Sign Matrix

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

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. The table below shows all 64 signs — green (+) for +1/√8 and red (−) for −1/√8:

H⊗³ |j⟩ →
output |i⟩ ↓		 |000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
H|000⟩ + + + + + + + +
H|001⟩ + − + − + − + −
H|010⟩ + + − − + + − −
H|011⟩ + − − + + − − +
H|100⟩ + + + + − − − −
H|101⟩ + − + − − + − +
H|110⟩ + + − − − − + +
H|111⟩ + − − + − + + −
+  =  amplitude +1/√8 ≈ +0.3535     −  =  amplitude −1/√8 ≈ −0.3535
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 simply 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. So the k-th factor contributes a sign of (−1)iₖ·jₖ. 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⟩

i (row) j (col) i AND j popcount Sign
101 (= 5) 011 (= 3) 001 1 (odd) − ✓

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 table used throughout the Grover’s Algorithm — Inversion About the Mean post. The diffusion operator D = H⊗³ (2|0⟩⟨0| − I) H⊗³ works in three sub-steps, each directly using this matrix:

Sub-step Operation Grover walkthrough steps
First H⊗³ Maps computational basis → Hadamard basis. Each amplitude spreads across all 8 columns via the sign table. 4.1  ·  6.1  ·  8.1
Phase flip 2|0⟩⟨0|−I: keeps |000⟩ unchanged, negates all other states. This is the inversion-about-the-mean mechanism. 4.2  ·  6.2  ·  8.2
Second H⊗³ Maps back to computational basis using the same sign table (H is self-inverse). Routes constructive interference into the target state. 4.3  ·  6.3  ·  8.3
The bottom line: without the sign structure of the Walsh-Hadamard matrix, neither the uniform superposition (Phase 0) nor the diffusion step (every iteration) would work. The matrix is the silent engine behind Grover’s quadratic speedup.

Quantum Series 2026  ·  Built with Qiskit 1.x

✦ This article was generated with the assistance of Claude by Anthropic ✦

Introduction to Quantum Computing: Qubits, Hadamard Gates, and Superposition

QUANTUM SERIES 2026
Qubits, the Hadamard gate, superposition, tensor products, and quantum interference from first principles.

Classical computers store information in bits that are always exactly 0 or 1. Quantum computers exploit the principles of quantum mechanics to do something fundamentally different: they operate on qubits, which can exist in a superposition of both states simultaneously. The Hadamard gate is the simplest gate that creates this superposition, and understanding it from first principles is the entry point to every quantum algorithm that follows.

1  ·  The Qubit

A qubit is the fundamental unit of quantum information. Unlike a classical bit, a qubit can exist in a superposition of |0⟩ and |1⟩ simultaneously. We write its general state using Dirac (bra-ket) notation:

|ψ⟩ = α|0⟩ + β|1⟩

Here α and β are complex numbers called probability amplitudes. They must satisfy the normalisation condition:

|α|² + |β|² = 1

The two computational basis states are represented as column vectors:

|0⟩ = 1
0
|1⟩ = 0
1

When we measure the qubit in state |ψ⟩ = α|0⟩ + β|1⟩, we get |0⟩ with probability |α|² and |1⟩ with probability |β|². The act of measurement destroys the superposition and collapses the qubit to a definite classical state.

Key distinction: The superposition is not just ignorance about a hidden value. The qubit genuinely occupies both states until measured, and this physical reality is what quantum algorithms exploit.

2  ·  The Hadamard Gate

The Hadamard gate H is a 2×2 unitary matrix that maps each computational basis state to an equal superposition:

H  =  (1/√2)    +1   +1 
 +1   −1 

Applying H to each basis state:

InputH |input⟩Short name
|0⟩(1/√2)( |0⟩ + |1⟩ )|+⟩
|1⟩(1/√2)( |0⟩ − |1⟩ )|−⟩

Both outputs have equal amplitudes of 1/√2, giving a 50% measurement probability for each outcome. The sign difference between |+⟩ and |−⟩ is what drives interference later.

Unitarity check: H†H = I. Since H is real and symmetric, H† = H, so H² = I. The Hadamard gate is its own inverse.

3  ·  H² = I: Quantum Interference

Applying H twice to |0⟩ returns the qubit to |0⟩. The algebra shows exactly why the |1⟩ amplitudes cancel through destructive interference:

H(H|0⟩)
  = H( (1/√2)(|0⟩ + |1⟩) )
  = (1/√2)( H|0⟩ + H|1⟩ )
  = (1/√2)( (1/√2)(|0⟩+|1⟩) + (1/√2)(|0⟩−|1⟩) )
  = (1/2)( |0⟩ + |1⟩ + |0⟩ − |1⟩ )
  = (1/2)( 2|0⟩ )
  = |0⟩ ✓
The +|1⟩ and −|1⟩ terms cancel completely (destructive interference) while the |0⟩ terms add (constructive interference). This is the fundamental mechanism behind quantum algorithms: arranging amplitudes so wrong answers cancel and the correct answer survives.

4  ·  Single-Qubit Circuit: H–H–Measure

A single qubit routed through two Hadamard gates and then measured always returns 0 with 100% probability:

q_0: H H M
StepStateNotes
1. Initialise|ψ₀⟩ = |0⟩Ground state
2. First H|ψ₁⟩ = (1/√2)(|0⟩+|1⟩)Superposition: 50/50
3. Second H|ψ₂⟩ = |0⟩Interference collapses back
4. MeasureResult = 0100% probability
This is a concrete demonstration that superposition is not just probabilistic noise. The deterministic outcome of 0 is only possible because the two Hadamard gates interact through interference, a purely quantum effect with no classical analogue.

5  ·  Tensor Products and Multi-Qubit States

Multi-qubit systems are described using the tensor product (⊗). For two qubits, the four computational basis states are:

KetTensor formColumn vector
|00⟩|0⟩ ⊗ |0⟩[1, 0, 0, 0]ᵀ
|01⟩|0⟩ ⊗ |1⟩[0, 1, 0, 0]ᵀ
|10⟩|1⟩ ⊗ |0⟩[0, 0, 1, 0]ᵀ
|11⟩|1⟩ ⊗ |1⟩[0, 0, 0, 1]ᵀ

The tensor product of two vectors is computed by multiplying each element of the first vector by the entire second vector and stacking the results. For |0⟩ ⊗ |1⟩:

|0⟩ ⊗ |1⟩
  = [1, 0]ᵀ ⊗ [0, 1]ᵀ
  = [ 1×[0,1]ᵀ ]  =  [0, 1, 0, 0]ᵀ  = |01⟩
    [ 0×[0,1]ᵀ ]
Dimension growth: n qubits span a 2ⁿ-dimensional Hilbert space. A 3-qubit system already has 8 basis states; a 50-qubit system has 2⁵⁰ ≈ 10¹⁵, impossible to store classically.

6  ·  Two-Qubit Superposition: H⊗H on |00⟩

Applying independent Hadamard gates to both qubits starting from |00⟩:

q_0: H
q_1: H
(H⊗H)|00⟩
  = (H|0⟩) ⊗ (H|0⟩)
  = (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. Each has measurement probability (1/2)² = 25%. This is the two-qubit analogue of the uniform superposition that opens algorithms like Grover’s.

7  ·  Interference in a Two-Qubit H–H Circuit

Applying H⊗H twice to |00⟩ returns it to |00⟩. The interference analysis on each basis state shows the mechanism:

Input to 2nd H⊗HAfter (H⊗H)
|00⟩(1/2)( |00⟩ + |01⟩ + |10⟩ + |11⟩ )
|01⟩(1/2)( |00⟩ − |01⟩ + |10⟩ − |11⟩ )
|10⟩(1/2)( |00⟩ + |01⟩ − |10⟩ − |11⟩ )
|11⟩(1/2)( |00⟩ − |01⟩ − |10⟩ + |11⟩ )

The initial superposition has equal weight 1/2 on each of the four states. Summing contributions to each output:

Output stateAmplitude sum (× 1/4)Result
|00⟩+1 +1 +1 +14/4 = 1 ✓ constructive
|01⟩+1 −1 +1 −10 destructive
|10⟩+1 +1 −1 −10 destructive
|11⟩+1 −1 −1 +10 destructive
Only |00⟩ survives. This is the same interference structure that the Grover diffusion operator exploits at scale: constructive interference on the target state, destructive on all others.

8  ·  The H⊗H Matrix and Why It Matters

The combined H⊗H operator is a 4×4 Walsh-Hadamard matrix (scaled by 1/2). Its sign pattern is exactly the two-qubit case of the popcount rule derived in the Walsh-Hadamard post:

H⊗H  =  (1/2)    +1   +1   +1   +1 
 +1   −1   +1   −1 
 +1   +1   −1   −1 
 +1   −1   −1   +1 

Every quantum algorithm that achieves a speedup over classical computation does so through the same three-phase structure:

PhaseOperationPurpose
1. OpenHadamard on all qubitsCreate uniform superposition over all 2ⁿ states
2. OperateOracle / phase manipulationMark or bias the amplitude of the target answer
3. CloseHadamard again (+ measurement)Interference concentrates probability on the answer
The bottom line: the qubit and the Hadamard gate are the entry point to everything. Grover’s O(√N) search, Shor’s O((log N)³) factoring, and every other quantum speedup ultimately trace back to this interference mechanism operating at scale.
About the author

Malcolm Low is an Associate Professor at the Singapore Institute of Technology, writing on quantum computing, programming, and applied computing from Singapore.

Website: malcolmlow.com  ·  Singapore

Quantum Series 2026  ·  Built with Qiskit 1.x

✦ This article was generated with the assistance of Claude by Anthropic ✦