TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The Szegedy discriminant is self-adjoint and contractive

Statement

For every finite row-stochastic kernel, the map $T$ of Szegedy row-preparation map and discriminant satisfies $T^{*} T = I$ and is an isometry, and the matrix entries of $D = T^{*} S T$ are

$D_{x y} = \sqrt{P_{x y} P_{y x}} .$

Hence $D$ is real symmetric, self-adjoint, and $∥ D ∥ \leq 1$ . If $(X, P, π)$ is also finite reversible, then

$D = diag (\sqrt{π}) P diag (1 / \sqrt{π}) .$

Every eigenvalue of $D$ is real and belongs to $[- 1, 1]$ . The empty state set has the zero endomorphism and empty spectrum; the similarity assertion is only made when a positive stationary probability vector is supplied.

Facts & Assumptions

Given: A finite set $X$ , a row-stochastic $P$ , the product-basis inner product, and the maps $T, S, D$ defined in Szegedy row-preparation map and discriminant. A reversible specialization additionally supplies $π_{x} > 0$ , $π P = π$ , and detailed balance.

[F1]

Szegedy row-preparation map and discriminant: $T ∣ x ⟩ = ∣ x ⟩ \otimes \sum_{y} \sqrt{P_{x y}} ∣ y ⟩$ , $S ∣ x, y ⟩ = ∣ y, x ⟩$ , and $D = T^{*} S T$ .

[F2]

Finite row-stochastic kernel: $P_{x y} \geq 0$ and $\sum_{y} P_{x y} = 1$ for every row.

[F3]

Every linear map between finite-dimensional inner product spaces has a unique adjoint: $T^{*}$ is the unique linear map satisfying $⟨ T v, w ⟩ = ⟨ v, T^{*} w ⟩$ .

[F4]

Self-adjoint and normal endomorphisms of a finite-dimensional real or complex inner product space: an endomorphism is self-adjoint when it equals its adjoint.

[F5]

Bessel's inequality for a finite orthonormal list and Parseval's identity for an orthonormal basis: an orthonormal basis satisfies $∥ u ∥^{2} = \sum_{i} ∣ ⟨ u, e_{i} ⟩ ∣^{2}$ , and every finite orthonormal list satisfies Bessel's inequality.

[F6]

Square roots exist: a unique $\sqrt{a} \geq 0$ with $(\sqrt{a})^{2} = a$ ; the positives are ${x^{2} : x \neq 0}$ : every nonnegative real has a unique nonnegative square root.

[F7]

Finite reversible Markov chain with positive stationary law: detailed balance is $π_{x} P_{x y} = π_{y} P_{y x}$ and every $π_{x} > 0$ .

[F8]

The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv|| and The operator norm is 0 on the zero domain and otherwise equals the largest singular value, attained at a right-singular vector: the operator norm is the maximum over unit vectors, and that maximum exists in finite dimension.

[F9]

Real and complex inner product spaces, with the inner product linear in the first argument and Inner products separate vectors, and the induced norm is homogeneous: $∥ λ v ∥ = ∣ λ ∣ ∥ v ∥$ : sesquilinearity extends equality of basis pairings to all vectors, and a vector pairing to zero with every vector is zero.

[F10]

Real and complex inner product spaces, with the inner product linear in the first argument: for the root inner product, scalar multiplication is linear in the first argument and conjugate-linear in the second.

Proof

1.1F1F2F3F9algebra

If $X = \emptyset$ , the domain and codomain are zero spaces, so $T^{*} T = I_{0}$ and $D$ is the zero endomorphism. Assume now $X \neq \emptyset$ . For basis labels $x, x^{'}$ , the first register gives $⟨ T ∣ x ⟩, T ∣ x^{'} ⟩ ⟩ = 0$ when $x \neq x^{'}$ , while for $x = x^{'}$ the value is $\sum_{y} P_{x y} = 1$ by [F2]. Hence the images of the orthonormal basis are orthonormal, which by expansion of arbitrary vectors proves $T$ is an isometry. Moreover, for all $x, x^{'}$ , [F3] gives $⟨ ∣ x ⟩, T^{*} T ∣ x^{'} ⟩ = ⟨ T ∣ x ⟩, T ∣ x^{'} ⟩ = ⟨ ∣ x ⟩, ∣ x^{'} ⟩$ . Sesquilinearity extends this equality to pairings against every vector; conjugate symmetry and nondegeneracy [F9] then give $T^{*} T ∣ x^{'} ⟩ = ∣ x^{'} ⟩$ . Therefore $T^{*} T = I$ .

2.1F1F2F3F6step 1.1algebra

With the linear-first root inner product, the matrix entry is $D_{x y} = ⟨ D e_{y}, e_{x} ⟩_{r o o t} = \overline{⟨ e_{x}, D e_{y} ⟩_{r o o t}} = \overline{⟨ T e_{x}, S T e_{y} ⟩_{r o o t}}$ by [F3]. Expanding the two row states, only $∣ x, y ⟩$ overlaps, with real coefficient $\sqrt{P_{x y} P_{y x}}$ ; hence $D_{x y} = \sqrt{P_{x y} P_{y x}}$ .

2.2F1F3F5step 1.1

For any $w$ in the product space, Parseval in the domain basis and [F3] give $∥ T^{*} w ∥^{2} = \sum_{x} ∣ ⟨ T^{*} w, ∣ x ⟩ ⟩ ∣^{2} = \sum_{x} ∣ ⟨ w, T ∣ x ⟩ ⟩ ∣^{2}$ . The vectors $T ∣ x ⟩$ are orthonormal by step 1.1, so Bessel's inequality [F5] makes this sum at most $∥ w ∥^{2}$ .

3.1F4step 2.1algebra

The formula in step 2.1 is unchanged by exchanging $x, y$ and is real, so $D$ is represented by a real symmetric matrix in the orthonormal label basis. Therefore $D^{*} = D$ and $D$ is self-adjoint by [F4].

3.2F1F8step 1.1step 2.2algebra

If $X = \emptyset$ , then the domain is zero and [F8] gives $∥ D ∥ = 0$ . Otherwise, for every unit vector $v$ , $∥ D v ∥ = ∥ T^{*} S T v ∥ \leq ∥ S T v ∥ = ∥ T v ∥ = 1$ , using step 2.2, the swap's basis-permutation norm preservation, and step 1.1. Taking the maximum over the nonempty unit sphere proves $∥ D ∥ \leq 1$ ; [F8] ensures the finite-dimensional maximum exists.

4.1F4F10step 3.1step 3.2algebra

If $v \neq 0$ and $D v = λ v$ , self-adjointness gives $λ ∥ v ∥^{2} = ⟨ D v, v ⟩ = ⟨ v, D v ⟩ = \overline{λ} ∥ v ∥^{2}$ , so $λ$ is real by [F10]. Step 3.2, applied after scaling $v$ to a unit vector, gives $∣ λ ∣ ∥ v ∥ = ∥ D v ∥ \leq ∥ v ∥$ ; hence $∣ λ ∣ \leq 1$ .

5.1F2F6F7step 2.1algebra∎

In the reversible case, detailed balance and $π_{y} > 0$ give $P_{y x} = π_{x} P_{x y} / π_{y}$ . Since $P_{x y} \geq 0$ , step 2.1 becomes $D_{x y} = P_{x y} \sqrt{π_{x} / π_{y}}$ , exactly the $(x, y)$ entry of $diag (\sqrt{π}) P diag (1 / \sqrt{π})$ .

Depends on

Used by

A stationary directed cycle is not similar to its discriminant Counterexample
Two-state reversible walk and its endpoint phases Example
Discriminant of the marked-state absorbing walk Lemma
Szegedy reflections and walk operators are unitary Lemma
Szegedy walk invariant subspaces from discriminant eigenvectors Lemma
Exact row-preparation access count for one and two walk steps Theorem
Finite reversible-walk finding cost Theorem
Szegedy spectral mapping for one and two reflections Theorem
Walk detection correctness and cost Theorem

Cited to discharge well-definedness by Szegedy row-preparation map and discriminant.

Dependency tree · two levels

36 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Andrew M. Childs, Lecture Notes on Quantum Algorithms, §§18.2–18.3 (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes, §8.2 (standard reference, not scraped)