Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Hadamard on every qubit of |0⟩ gives the uniform superposition

Proved
QAlgorithms.Nannicini.hadamard_all_zero_uniform

by Goku · Oct 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

lecture-notesnanniciniquantum-information

Let q≥0q\ge 0q≥0 and let H=12(111−1)H=\frac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}H=2​1​(11​1−1​) be the Hadamard gate. Consider a qqq-qubit register in the all-zero basis state ∣0⃗⟩q|\vec 0\rangle_q∣0⟩q​.

  1. Applying HHH to each of the qqq qubits, one after the other, yields the uniform superposition.
  2. Applying the 2q×2q2^q\times 2^q2q×2q matrix H⊗qH^{\otimes q}H⊗q, whose entries are (H⊗q)k⃗,x⃗=2−q/2(−1)k⃗∙x⃗(H^{\otimes q})_{\vec k,\vec x}=2^{-q/2}(-1)^{\vec k\bullet\vec x}(H⊗q)k,x​=2−q/2(−1)k∙x (Eq. (1.5)), also yields the uniform superposition:
H⊗q∣0⃗⟩q=12q∑ȷ⃗∈{0,1}q∣ȷ⃗⟩.H^{\otimes q}|\vec 0\rangle_q=\frac{1}{\sqrt{2^q}}\sum_{\vec\jmath\in\{0,1\}^q}|\vec\jmath\rangle .H⊗q∣0⟩q​=2q​1​​∈{0,1}q∑​∣​⟩.

This is how many quantum algorithms start: qqq gates turn the initial state into an equal-weight superposition of all 2q2^q2q basis states.

Formalization Note Applying HHH to qubit iii is the embedding of the one-qubit matrix HHH on wire iii; the product over all wires is taken in wire order (the factors commute). The uniform superposition is the vector all of whose amplitudes equal 1/2q1/\sqrt{2^q}1/2q​. The case q=0q=0q=0 is included; both sides are then the one-dimensional unit vector.

Preamble
import Definitions.Def_QAlgorithms_Defs_Adiabatic
set_option autoImplicit false
Formal statement
namespace QAlgorithms.Nannicini

open QAlgorithms

/-- Nannicini, Proposition 1.38, PDF p. 25. Given a `q`-qubit register in the state `|0⟩_q`,
applying the Hadamard gate to all qubits, or equivalently the matrix `H^{⊗q}` (Eq. (1.5)),
yields the uniform superposition `(1/√(2^q)) Σ_{j ∈ {0,1}^q} |j⟩`.

The first conjunct applies `H` to each wire in turn (wire `0` first); the second applies the
frozen `hadamardN q`, the matrix of Eq. (1.5). `uniformState (Qubits q)` has every amplitude
equal to `1/√(card (Qubits q)) = 1/√(2^q)`. -/
theorem hadamard_all_zero_uniform (q : ℕ) :
    act (orderedProd fun i : Fin q =>
        embedOp (Gate.ofMatrix1 hadamard).mat (Stabilizer.wire1 i)) (zeroKet q) =
      uniformState (Qubits q) ∧
    act (hadamardN q) (zeroKet q) = uniformState (Qubits q) := by
  sorry




end QAlgorithms.Nannicini
Source
Giacomo Nannicini, Quantum algorithms for optimizers, 2025, v5; notes dated 9 July 2025, PDF p. 25, Proposition 1.38. https://arxiv.org/pdf/2408.07086v5
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Fix a natural number qqq (the case q=0q = 0q=0 is included). The statement concerns the state space C{0,1}q\mathbb{C}^{\{0,1\}^q}C{0,1}q of qqq qubits, with computational basis {∣z⟩:z∈{0,1}q}\{|z\rangle : z \in \{0,1\}^q\}{∣z⟩:z∈{0,1}q}, where wire i∈{0,…,q−1}i \in \{0,\dots,q-1\}i∈{0,…,q−1} carries bit ziz_izi​. It asserts that two equalities hold simultaneously.

First equality. For each wire iii, let H(i)H^{(i)}H(i) be the 2q×2q2^q \times 2^q2q×2q matrix that acts as the one-qubit Hadamard on wire iii and as the identity elsewhere. The one-qubit Hadamard is

H=12(111−1).H = \tfrac{1}{\sqrt 2}\begin{pmatrix} 1 & 1 \\ 1 & -1\end{pmatrix}.H=2​1​(11​1−1​).

Explicitly, the matrix entries are

Hy,z(i)={Hyi,ziif ya=za for all a≠i,0otherwise.H^{(i)}_{y,z} = \begin{cases} H_{y_i, z_i} & \text{if } y_a = z_a \text{ for all } a \ne i,\\ 0 & \text{otherwise.}\end{cases}Hy,z(i)​={Hyi​,zi​​0​if ya​=za​ for all a=i,otherwise.​

Form the ordered product

H(q−1)⋯H(1)H(0),H^{(q-1)} \cdots H^{(1)} H^{(0)},H(q−1)⋯H(1)H(0),

in which wire 000's factor is applied first. For q=0q = 0q=0 this is the empty product, i.e. the identity. The claim is that applying this product to the all-zeros basis vector ∣0⋯0⟩|0\cdots0\rangle∣0⋯0⟩ gives the uniform vector uuu, whose every coordinate is

uz=12q(z∈{0,1}q).u_z = \frac{1}{\sqrt{2^q}} \qquad (z \in \{0,1\}^q).uz​=2q​1​(z∈{0,1}q).

Second equality. The qqq-qubit Hadamard matrix H⊗qH^{\otimes q}H⊗q is defined entrywise by

(H⊗q)j,i=(−1)i⋅j (12)q,\big(H^{\otimes q}\big)_{j,i} = (-1)^{i \cdot j}\,\Big(\tfrac{1}{\sqrt 2}\Big)^{q},(H⊗q)j,i​=(−1)i⋅j(2​1​)q,

where i⋅j=⨁k(ik∧jk)i \cdot j = \bigoplus_k (i_k \wedge j_k)i⋅j=⨁k​(ik​∧jk​) is the parity of the bitwise AND of iii and jjj. The claim is that applied to ∣0⋯0⟩|0\cdots0\rangle∣0⋯0⟩ it also gives the same uniform vector uuu.

Human review
  • Endorsed by Shuze Chen · Oct 13, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 13, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me