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

What Makes Quantum Computing Different?

Classical computers process information using bits that exist in one of two states: 0 or 1. Quantum computers, however, leverage the strange and powerful principles of quantum mechanics to process information in fundamentally different ways. At the heart of this difference lies the qubit (quantum bit) and quantum gates like the Hadamard gate that manipulate these qubits.

Understanding the Qubit

A qubit is the basic unit of quantum information. Unlike classical bits, qubits can exist in a superposition of states, meaning they can be in state |0⟩, state |1⟩, or any quantum combination of both simultaneously.

Mathematical Representation

We represent qubit states using Dirac notation (bra-ket notation):

|0⟩ state:

1
0

|1⟩ state:

0
1

A general qubit state can be written as:

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

where α and β are complex numbers called probability amplitudes, and they must satisfy the normalization condition:

|α|² + |β|² = 1

When we measure a qubit in this state, we get:

  • |0⟩ with probability |α|²
  • |1⟩ with probability |β|²

The Hadamard Gate: Creating Superposition

The Hadamard gate (H) is one of the most important quantum gates. It creates an equal superposition from a classical state, which is the key to quantum algorithms’ power.

Hadamard Gate Matrix

The Hadamard gate is represented by the following 2×2 matrix:

H = (1/√2) ×

1 1
1 −1

Opening Superposition

Let’s see what happens when we apply the Hadamard gate to the |0⟩ state:

Step 1: Matrix Multiplication

H|0⟩ = (1/√2) ×
1 1
1 −1
×
1
0

Step 2: Result

= (1/√2) ×
1
1

Step 3: Final State

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

🎯 Key Insight: This creates an equal superposition! The qubit now has a 50% probability of being measured as 0 and 50% as 1.

Similarly, applying H to |1⟩:

H|1⟩ = (1/√2)(|0⟩ − |1⟩)

Closing Superposition

Here’s the remarkable property: the Hadamard gate is its own inverse. Applying it twice returns the qubit to its original state.

H(H|0⟩) calculation:

= 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⟩ ✓

💡 Quantum Interference: The amplitude for |1⟩ cancels out completely, and we return to the definite state |0⟩. This is the magic of quantum interference!

Example Circuit: Creating and Collapsing Superposition

Let’s look at a simple quantum circuit:

     ┌───┐┌───┐┌─┐
q_0: ┤ H ├┤ H ├┤M├
     └───┘└───┘└─┘

Legend: H = Hadamard gate, M = Measurement

Step-by-step Execution:

Step State Description
1. Initial |ψ₀⟩ = |0⟩ Qubit starts in state 0
2. After H |ψ₁⟩ = (1/√2)(|0⟩+|1⟩) Superposition! 50% chance of 0 or 1
3. After H |ψ₂⟩ = |0⟩ Back to |0⟩! Superposition collapsed
4. Measure Result = 0 We measure 0 with 100% probability

Multi-Qubit Systems and Tensor Products

When working with multiple qubits, we use the tensor product (⊗) to describe the combined state space.

Two-Qubit System

For two qubits, we have four possible basis states:

|00⟩ = |0⟩ ⊗ |0⟩
|01⟩ = |0⟩ ⊗ |1⟩
|10⟩ = |1⟩ ⊗ |0⟩
|11⟩ = |1⟩ ⊗ |1⟩

Tensor Product Example

Let’s calculate |0⟩ ⊗ |1⟩ step by step:

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

The tensor product stacks the results:

  • First element (1) × [0, 1] = [0, 1]
  • Second element (0) × [0, 1] = [0, 0]
  • Stack them: [0, 1, 0, 0]
Result:
0
1
0
0
= |01⟩

Creating Multi-Qubit Superposition

Consider applying Hadamard gates to both qubits starting from |00⟩:

     ┌───┐
q_0: ┤ H ├
     ├───┤
q_1: ┤ H ├
     └───┘

Initial: |ψ₀⟩ = |00⟩

After H gates on both qubits:

(H ⊗ H)|00⟩ = (H|0⟩) ⊗ (H|0⟩)

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

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

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

🌟 Amazing Result: Both qubits are now in superposition! The system has an equal 25% probability of being measured in ANY of the four possible states: |00⟩, |01⟩, |10⟩, or |11⟩.

Opening and Closing Multi-Qubit Superposition

Here’s the complete example showing interference:

     ┌───┐┌───┐
q_0: ┤ H ├┤ H ├
     ├───┤├───┤
q_1: ┤ H ├┤ H ├
     └───┘└───┘

Step 1: Initial State

|ψ₀⟩ = |00⟩

Step 2: After First H Gates (Opening Superposition)

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

Equal superposition of all 4 states!

Step 3: After Second H Gates (Closing Superposition)

We need to apply H⊗H to each of the four states:

Input State After (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⟩)

⚡ Quantum Interference Analysis:

For |00⟩: (1/4) × (+1 +1 +1 +1) = 4/4 = 1 ✓

Constructive interference!

For |01⟩: (1/4) × (+1 −1 +1 −1) = 0 ✗

Destructive interference – cancels out!

For |10⟩: (1/4) × (+1 +1 −1 −1) = 0 ✗

Destructive interference – cancels out!

For |11⟩: (1/4) × (+1 −1 −1 +1) = 0 ✗

Destructive interference – cancels out!

Final Result:

|ψ₂⟩ = |00⟩

🎉 We’re back to the original state through quantum interference!

Tensor Product of Hadamard Gates

The combined Hadamard operator H⊗H creates a 4×4 matrix:

H ⊗ H = (1/2) ×

1 1 1 1
1 −1 1 −1
1 1 −1 −1
1 −1 −1 1

This 4×4 matrix operates on the four-dimensional space of two-qubit states.

Why This Matters

The ability to create and manipulate superposition is what gives quantum computers their potential power. While a classical computer must check each possibility one at a time, a quantum computer in superposition can process multiple possibilities simultaneously.

The Art of Quantum Algorithm Design

  1. Opening Superposition: Using Hadamard gates to explore multiple states simultaneously
  2. Quantum Operations: Manipulating the superposition in clever ways
  3. Closing Superposition: Using interference to amplify the correct answer and cancel wrong ones

This is the foundation upon which all quantum algorithms are built, from Grover’s search algorithm to Shor’s factoring algorithm.

Conclusion

The qubit and Hadamard gate are the building blocks of quantum computation. By understanding how the Hadamard gate creates and collapses superposition through the mathematics of state vectors and tensor products, we gain insight into the fundamental principles that make quantum computing possible.

The next time you hear about quantum speedup or quantum advantage, remember that it all starts with these simple mathematical operations on qubits in superposition.

🚀 Ready to experiment yourself?

Popular quantum computing frameworks like Qiskit, Cirq, and Q# allow you to create and simulate these circuits on your own computer, and even run them on real quantum hardware through cloud platforms!