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.

Szegedy spectral mapping for one and two reflections

Statement

Let $D = T^{*} S T$ be the discriminant of a finite row-stochastic kernel and let $U = S (2 T T^{*} - I)$ and $W = U^{2}$ . For every eigenvalue $λ \in (- 1, 1)$ of $D$ , counted with multiplicity, its invariant planes contribute eigenvalues

$\exp (i \arccos λ), \exp (- i \arccos λ) for U, \exp (2 i \arccos λ), \exp (- 2 i \arccos λ) for W .$

For each eigendirection with $λ = 1$ (respectively $λ = - 1$ ), the plane collapses to a line on which $U$ acts as $+ I$ (respectively $- I$ ), so $W$ acts as $+ I$ . On the remaining subspace $K = (ran T + ran (S T))^{⊥}$ , $U = - S$ and its eigenvalues lie in ${+ 1, - 1}$ ; therefore all eigenvalues of $W$ there are $+ 1$ . If $X = \emptyset$ , both spaces are zero and the statements about eigenvalues are vacuous.

Facts & Assumptions

Given: A finite row-stochastic kernel $(X, P)$ , the maps $T, S, D, U, W$ from Szegedy row-preparation map and discriminant and Szegedy reflection walk and its two-reflection square, and the root inner product linear in its first argument.

[F1]

The Szegedy discriminant is self-adjoint and contractive: $D$ is self-adjoint, $∥ D ∥ \leq 1$ , and $T^{*} T = I$ .

[F2]

Szegedy walk invariant subspaces from discriminant eigenvectors: if $D v = λ v$ , then $span {T v, S T v}$ is invariant with $U (T v) = S T v$ and $U (S T v) = - T v + 2 λ S T v$ ; the span is one-dimensional at $λ = \pm 1$ and two-dimensional for $∣ λ ∣ < 1$ .

[F3]

Szegedy reflections and walk operators are unitary: $U$ is unitary and equals $- S$ on $A^{⊥}$ , where $A = ran T$ .

[F4]

Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely: a finite-dimensional complex normal endomorphism has an orthonormal eigenbasis.

[F5]

Eigenvalues, eigenvectors, eigenspaces $E_{λ} (T) = \ker (T - λ I)$ , and the spectrum $σ_{F} (T)$ of an endomorphism: an eigenvalue has a nonzero eigenvector, and the spectrum is the set of eigenvalues.

[F6]

The orthogonal complement $W^{⊥} = {v : ⟨ v, w ⟩ = 0 for all w \in W}$ and For a subspace $W$ of a finite-dimensional inner product space, $V = W \oplus W^{⊥}$ : for a subspace $V_{0}$ of a finite-dimensional inner-product space, $V = V_{0} \oplus V_{0}^{⊥}$ .

[F7]

Principal inverse sine and inverse cosine: $\arccos : [- 1, 1] \to [0, π]$ satisfies $\cos (\arccos r) = r$ .

[F8]

Parity and the Pythagorean identity for sine and cosine: $\sin^{2} θ + \cos^{2} θ = 1$ for real $θ$ .

[F9]

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.

[F10]

Euler's formula: $\exp (i θ) = \cos θ + i \sin θ$ for every real $θ$ : $\exp (i θ) = \cos θ + i \sin θ$ for real $θ$ .

[F11]

$\exp (z + w) = \exp z \exp w$ , and the complex exponential extends the real exponential: $\exp (z + w) = \exp z \exp w$ .

[F12]

Signs, monotonicity intervals, and ranges of sine and cosine: sine is strictly increasing on $[- π / 2, π / 2]$ and strictly decreasing on $[π / 2, 3 π / 2]$ .

[F13]

The kernel and image are linear subspaces, and a linear map is injective if and only if its kernel is trivial: the image of a linear map is a linear subspace.

[F14]

Quarter-turn values and shifts by pi/2 and pi: $\sin 0 = 0$ , $\sin (π / 2) = 1$ , and $\sin π = 0$ .

[F15]

Kernel and image of a linear map: $im T = {T (v) : v \in V}$ .

Proof

1.1F1F4F5choose

If $X = \emptyset$ , then $C^{X} = C^{X \times X} = {0}$ , so there are no eigenvalues and the claims are vacuous. Assume now $X \neq \emptyset$ . By [F1] and [F4], choose an orthonormal eigenbasis $(v_{j})$ of the self-adjoint $D$ , with real eigenvalues $λ_{j} \in [- 1, 1]$ ; the bound follows from $∥ D ∥ \leq 1$ .

2.1F1F2step 1.1algebra

For distinct basis vectors $v_{j}, v_{k}$ , the spans $span {T v_{j}, S T v_{j}}$ and $span {T v_{k}, S T v_{k}}$ are orthogonal: the $T$ -images and their swapped images pair to $⟨ v_{j}, v_{k} ⟩ = 0$ , while the cross pairings equal $⟨ v_{j}, D v_{k} ⟩ = λ_{k} ⟨ v_{j}, v_{k} ⟩ = 0$ . These spans together generate $A + B$ , where $A = ran T$ and $B = ran (S T)$ .

2.2F2F7F8F9F10F11F12F14step 1.1algebra

Fix an eigenvalue $λ_{j} \in (- 1, 1)$ and its plane basis $a = T v_{j}, b = S T v_{j}$ . By [F2], the matrix of $U$ in the ordered basis $(a, b)$ is $(\begin{array}{cc} 0 & - 1 \\ 1 & 2 λ_{j} \end{array})$ , so its characteristic equation is $z^{2} - 2 λ_{j} z + 1 = 0$ . Its roots are $z = λ_{j} \pm i \sqrt{1 - λ_{j}^{2}}$ ; each root has eigenvector $(1, - z)$ in these coordinates, and the roots are distinct because $∣ λ_{j} ∣ < 1$ . Put $θ_{j} = \arccos λ_{j} \in (0, π)$ . By [F7], $\cos θ_{j} = λ_{j}$ . If $0 < θ_{j} \leq π / 2$ , strict increase from $\sin 0 = 0$ on $[0, π / 2]$ gives $\sin θ_{j} > 0$ ; if $π / 2 < θ_{j} < π$ , strict decrease to $\sin π = 0$ on $[π / 2, π]$ gives the same. These monotonicity and endpoint facts are [F12] and [F14]. Then [F8] and uniqueness in [F9] yield $\sin θ_{j} = \sqrt{1 - λ_{j}^{2}}$ . [F10] identifies the roots as $\exp (\pm i θ_{j})$ , and [F11] squares them to $\exp (\pm 2 i θ_{j})$ for $W = U^{2}$ .

2.3F2step 1.1algebra

If $λ_{j} = \pm 1$ , [F2] gives $S T v_{j} = λ_{j} T v_{j}$ , so the corresponding line contributes the single eigenvalue $λ_{j}$ to $U$ and $+ 1$ to $W$ . This counts one endpoint eigenvalue per eigendirection, not two coincident plane eigenvalues.

3.1F3F6F13F15step 2.1algebra

Let $H = A + B$ , the sum of the images of $T$ and $S T$ as identified by [F15]; both are subspaces by [F13], so their sum is a subspace. By [F6], $C^{X \times X} = H \oplus K$ with $K = H^{⊥}$ . Since $K \subseteq A^{⊥}$ , [F3] gives $U ∣_{K} = - S ∣_{K}$ . The swap preserves $K$ : for $a \in A$ and $w \in K$ , $⟨ a, S w ⟩ = ⟨ S a, w ⟩ = 0$ because $S a \in B$ , and for $b \in B$ and $w \in K$ , $⟨ b, S w ⟩ = ⟨ S b, w ⟩ = 0$ because $S b \in A$ .

4.1F3step 2.2step 2.3step 3.1algebra∎

On $K$ , $S^{2} = I$ , so each $w \in K$ decomposes as $(w + S w) / 2 + (w - S w) / 2$ ; these summands lie in $K$ by step 3.1 and satisfy $S (w + S w) = w + S w$ and $S (w - S w) = - (w - S w)$ . Thus $U = - S$ has eigenvalues only $\pm 1$ on $K$ , and $W = U^{2}$ is identity there. Combining this with steps 2.2–2.3 gives the complete eigenvalue multiset, including repeated eigenvalues and any overlap of endpoint values with the complement. No irreducibility, aperiodicity, or choice principle is used.

Depends on

Used by

Two-state reversible walk and its endpoint phases Example
Finite reversible-walk finding cost Theorem
Walk detection correctness and cost Theorem

Dependency tree · two levels

81 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.3 (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes, §8.2 (standard reference, not scraped)