AFTD Auto-Formalizing Theoretical Domains

xz_matrix_a_is_hermitian

theoremverified

For every natural number L, the matrix xz_matrix_a L is Hermitian: (xz_matrix_a L).IsHermitian.

Statement

theorem xz_matrix_a_is_hermitian (L : ℕ) : (xz_matrix_a L).IsHermitian
Source
arXiv:2610.20846, Appendix C
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
  • xz_matrix_aThe matrix xz_matrix_a (L : ℕ) : Matrix (Fin L → Fin 2) (Fin L → Fin 2) ℂ defined as…
  • xz_pauli_stringThe function xz_pauli_string (L : ℕ) : (Fin L → Fin 2) → PauliString L mapping a configuration a : Fin L → Fin 2 to the Pauli string…
  • PauliStringA Pauli string of length $n$ is a function $p : \mathrm{Fin}\,n \to \mathrm{PauliBasis}$.
  • PauliBasisThe four Pauli basis elements $\{I,X,Y,Z\}$, represented as an inductive type.
  • pauliMatrixFor a Pauli string $p$ on $n$ qubits, the $2^n\times 2^n$ matrix obtained as the tensor product of the single-qubit Pauli matrices…
  • PauliBasis.toMatrixMaps each Pauli basis element $\{I,X,Y,Z\}$ to its corresponding $2\times 2$ matrix $\{\sigma_I,\sigma_X,\sigma_Y,\sigma_Z\}$.
  • sigmaIThe $2\times 2$ identity matrix over $\mathbb{C}$, i.e.\ the Pauli operator $I$.
  • sigmaXThe bit-flip Pauli matrix $X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ over $\mathbb{C}$.
  • sigmaYThe bit-phase-flip Pauli matrix $Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}$ over $\mathbb{C}$.
  • sigmaZThe phase-flip Pauli matrix $Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$ over $\mathbb{C}$.

Read back from the Lean

For every natural number $L$, the complex matrix xz_matrix_a L (indexed by functions Fin L → Fin 2) is Hermitian (i.e., equal to its conjugate transpose).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The matrix $A_L$ is defined as the real scalar multiple $1/2^L$ of a sum of $L$-qubit Pauli string matrices. The proof establishes that $A_L$ is Hermitian in three stages: first, it checks by exhaustive entry calculation that each single-qubit Pauli basis matrix ($I, X, Y, Z$) is Hermitian; second, it shows that any tensor product of Pauli matrices (a Pauli string) is Hermitian because the conjugate transpose distributes over the product of entries; finally, it distributes the conjugate transpose across the scalar multiple and sum defining $A_L$, observes that the real scalar $1/2^L$ is fixed by complex conjugation, and concludes using the Hermiticity of each Pauli string summand.

  1. Each of the four single-qubit Pauli basis matrices is Hermitian.

    We perform a case analysis on the Pauli basis element $b \in \{I, X, Y, Z\}$. In each case, matrix extensionality (`ext i j`) reduces proving $(b.\text{toMatrix})^\dagger = b.\text{toMatrix}$ to checking equality at each coordinate pair $i, j \in \{0, 1\}$. Exhausting all four coordinate pairs with `fin_cases`, the equality of each entry with its conjugate transpose is verified by unfolding the definitions of the Pauli matrices and conjugate transpose.

    lines 2–6

      cases b <;> {
        ext i j
        fin_cases i <;> fin_cases j <;>
          simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ, Matrix.conjTranspose]
      }
  2. Every $n$-qubit Pauli string matrix is Hermitian.

    By matrix extensionality (`ext i j`), it suffices to show that the $(i, j)$-entry of the conjugate transpose of $\text{pauliMatrix } p$ equals its $(i, j)$-entry. Using `Matrix.conjTranspose_apply`, the $(i, j)$-entry of the conjugate transpose is the complex conjugate of the $(j, i)$-entry. By definition of `pauliMatrix`, this entry is the product $\prod_k (p(k))_{j_k, i_k}$. The complex conjugate operation distributes across the product using `star_prod`. Congruence of products (`Finset.prod_congr`) reduces the claim to each index $k$. For each single-qubit factor, $p(k)$ is Hermitian by `xz_matrix_a_is_hermitian_pauli_basis`, so applying matrix equality to coordinates $(i_k, j_k)$ via `congr_fun` and rewriting with `Matrix.conjTranspose_apply` shows that $\text{star}((p(k))_{j_k, i_k}) = (p(k))_{i_k, j_k}$, completing the proof.

    lines 9–19

    uses Matrix.conjTranspose_apply, star_prod, Finset.prod_congr, xz_matrix_a_is_hermitian_pauli_basis, congr_fun

      ext i j
      rw [Matrix.conjTranspose_apply]
      dsimp [pauliMatrix]
      change star (∏ k, (p k).toMatrix (j k) (i k)) = ∏ k, (p k).toMatrix (i k) (j k)
      rw [star_prod]
      apply Finset.prod_congr rfl
      intro k _
      have h := xz_matrix_a_is_hermitian_pauli_basis (p k)
      have h_app := congr_fun (congr_fun h (i k)) (j k)
      rw [Matrix.conjTranspose_apply] at h_app
      exact h_app
  3. The conjugate transpose of $A_L$ distributes across the scalar multiple $1/2^L$ and the sum over Pauli strings.

    We unfold the definitions of $A_L$ and `Matrix.IsHermitian`. The matrix $A_L$ is defined as $(1/2^L) \sum_a \text{pauliMatrix}(\text{xz\_pauli\_string } L\ a)$. Using `Matrix.conjTranspose_smul` and `Matrix.conjTranspose_sum`, the conjugate transpose of $A_L$ rewrites to $\text{star}(1/2^L) \sum_a (\text{pauliMatrix}(\text{xz\_pauli\_string } L\ a))^\dagger$.

    lines 23–24

    uses Matrix.conjTranspose_smul, Matrix.conjTranspose_sum

      unfold xz_matrix_a Matrix.IsHermitian
      rw [Matrix.conjTranspose_smul, Matrix.conjTranspose_sum]
  4. The scalar coefficient $1/2^L$ is real and thus invariant under complex conjugation.

    Because $2^L$ is a real number, the scalar $1/2^L$ is real, so its complex conjugate `star (1 / (2^L : ℂ))` equals $1/2^L$. Rewriting with this equality restores the scalar factor $(1/2^L)$ on the conjugate transpose side.

    lines 25–26

      have hstar : star (1 / (2 ^ L : ℂ)) = 1 / (2 ^ L : ℂ) := by simp
      rw [hstar]
  5. Each term in the sum is Hermitian, establishing that $A_L$ is Hermitian.

    Cancelling the scalar factor $1/2^L$ on both sides using `congr 1`, it remains to show that the sum of the conjugate transposed matrices equals the original sum. By `Finset.sum_congr`, it suffices to show that each summand is equal to its conjugate transpose. For any binary string $a$, the summand is the Pauli string matrix for `xz_pauli_string L a`, which is Hermitian by `xz_matrix_a_is_hermitian_pauli_matrix`.

    lines 27–30

    uses Finset.sum_congr, xz_matrix_a_is_hermitian_pauli_matrix

      congr 1
      apply Finset.sum_congr rfl
      intro a _
      exact xz_matrix_a_is_hermitian_pauli_matrix (xz_pauli_string L a)
Matrix.conjTranspose_apply
The $(j, i)$-entry of the conjugate transpose of a matrix $M$ is the complex conjugate of its $(i, j)$-entry: $M^\dagger_{j, i} = (M_{i, j})^*$.
star_prod
The complex conjugate of a finite product of elements is the product of their complex conjugates: $(\prod_{x \in s} f(x))^* = \prod_{x \in s} f(x)^*$.
Finset.prod_congr
Two products over identical index sets are equal if their terms agree at every index.
xz_matrix_a_is_hermitian_pauli_basis
Each of the four single-qubit Pauli basis matrices ($I, X, Y, Z$) is Hermitian: $b.\text{toMatrix}^\dagger = b.\text{toMatrix}$.
congr_fun
If two functions (or matrices) are equal, their values at any given input (or index) are equal.
Matrix.conjTranspose_smul
The conjugate transpose of a scalar multiple of a matrix equals the conjugate of the scalar times the conjugate transpose of the matrix: $(c \cdot M)^\dagger = c^* \cdot M^\dagger$.
Matrix.conjTranspose_sum
The conjugate transpose of a finite sum of matrices is the sum of their conjugate transposes: $(\sum_{i \in s} M_i)^\dagger = \sum_{i \in s} M_i^\dagger$.
Finset.sum_congr
Two sums over identical index sets are equal if their terms agree at every index.
xz_matrix_a_is_hermitian_pauli_matrix
For any $n$-qubit Pauli string $p$, the corresponding tensor-product matrix is Hermitian: $(\text{pauliMatrix } p)^\dagger = \text{pauliMatrix } p$.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

lemma xz_matrix_a_is_hermitian_pauli_basis (b : PauliBasis) : (b.toMatrix).IsHermitian := by  cases b <;> {    ext i j    fin_cases i <;> fin_cases j <;>      simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ, Matrix.conjTranspose]  }lemma xz_matrix_a_is_hermitian_pauli_matrix {n : ℕ} (p : PauliString n) : (pauliMatrix p).IsHermitian := by  ext i j  rw [Matrix.conjTranspose_apply]  dsimp [pauliMatrix]  change star (∏ k, (p k).toMatrix (j k) (i k)) = ∏ k, (p k).toMatrix (i k) (j k)  rw [star_prod]  apply Finset.prod_congr rfl  intro k _  have h := xz_matrix_a_is_hermitian_pauli_basis (p k)  have h_app := congr_fun (congr_fun h (i k)) (j k)  rw [Matrix.conjTranspose_apply] at h_app  exact h_app/-- The matrix A_L is Hermitian for any length L. -/theorem xz_matrix_a_is_hermitian (L : ℕ) : (xz_matrix_a L).IsHermitian := by  unfold xz_matrix_a Matrix.IsHermitian  rw [Matrix.conjTranspose_smul, Matrix.conjTranspose_sum]  have hstar : star (1 / (2 ^ L : ℂ)) = 1 / (2 ^ L : ℂ) := by simp  rw [hstar]  congr 1  apply Finset.sum_congr rfl  intro a _  exact xz_matrix_a_is_hermitian_pauli_matrix (xz_pauli_string L a)
See it in the graphDiscuss this resultChallenge it