ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-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.

Two-state reversible walk and its endpoint phases

Example

For $a \in [0, 1]$ , take

$P_{a} = (\begin{array}{cc} 1 - a & a \\ a & 1 - a \end{array}), π = (1 / 2, 1 / 2) .$

Compute the discriminant and the complete eigenvalue multisets of the one-reflection walk $U$ and its square $W = U^{2}$ , including both endpoint parameters.

Facts & Assumptions

Given: The finite row-stochastic kernel $(X, P_{a})$ with the supplied law $π$ and the definitions of $T, S, D, U, W$ from Szegedy row-preparation map and discriminant and Szegedy reflection walk and its two-reflection square.

[F1]

Finite reversible Markov chain with positive stationary law: a finite reversible chain has a positive stationary probability law and satisfies detailed balance.

[F2]

The Szegedy discriminant is self-adjoint and contractive: $T^{*} T = I$ and $D_{x y} = \sqrt{(P_{a})_{x y} (P_{a})_{y x}}$ .

[F3]

Szegedy row-preparation map and discriminant: the label/product bases are orthonormal; $T ∣ x ⟩ = ∣ x ⟩ \sum_{y} \sqrt{(P_{a})_{x y}} ∣ y ⟩$ , $S ∣ x, y ⟩ = ∣ y, x ⟩$ , and $D = T^{*} S T$ .

[F4]

Szegedy reflection walk and its two-reflection square: $U = S (2 T T^{*} - I)$ and $W = U^{2}$ .

[F5]

Szegedy walk invariant subspaces from discriminant eigenvectors: for $D v = μ v$ , the span of $T v, S T v$ is an invariant line when $μ = \pm 1$ and an invariant plane when $- 1 < μ < 1$ .

[F6]

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

[F7]

Szegedy spectral mapping for one and two reflections: an interior discriminant eigenvalue $μ$ contributes $e^{\pm i \arccos μ}$ to $U$ and $e^{\pm 2 i \arccos μ}$ to $W$ ; a $+ 1$ or $- 1$ endpoint eigendirection contributes that same sign to $U$ and $+ 1$ to $W$ .

[F8]

Write $σ_{m u l t} (T)$ for the multiset of eigenvalues counted with algebraic multiplicity. The ordinary spectrum $σ (T)$ is a set. Eigenvalues, eigenvectors, eigenspaces $E_{λ} (T) = \ker (T - λ I)$ , and the spectrum $σ_{F} (T)$ of an endomorphism: the spectrum of an endomorphism is the set of scalars with a nonzero eigenvector; the zero-space endomorphism has empty spectrum.

[F9]

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

[F10]

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.

[F11]

The orthogonal complement $W^{⊥} = {v : ⟨ v, w ⟩ = 0 for all w \in W}$ : $H^{⊥}$ consists of vectors whose inner product with every vector of $H$ is zero.

[F12]

For a subspace $W$ of a finite-dimensional inner product space, $V = W \oplus W^{⊥}$ : in a finite-dimensional inner-product space, $V = H \oplus H^{⊥}$ .

Verification

1.1F1givenalgebra

Both rows of $P_{a}$ sum to one, $π P_{a} = π$ , and $P_{a}$ is symmetric, so $π_{x} (P_{a})_{x y} = π_{y} (P_{a})_{y x}$ for all $x, y$ . Thus $π$ is a positive stationary reversible law.

1.2F2algebra

Since $P_{a}$ is symmetric and has nonnegative entries, [F2] gives $D = P_{a}$ . The vectors $u_{+} = (1, 1)$ and $u_{-} = (1, - 1)$ form a basis with $D u_{+} = u_{+}$ and $D u_{-} = (1 - 2 a) u_{-}$ .

1.3F3F4F6F8algebra

At $a = 0$ , $T ∣ 0 ⟩ = ∣ 00 ⟩$ and $T ∣ 1 ⟩ = ∣ 11 ⟩$ , so $A = B = span {∣ 00 ⟩, ∣ 11 ⟩}$ . On $A$ , $R_{A} = 2 T T^{*} - I$ is $+ I$ and $S = I$ , so $U = + I$ . On $K = span {∣ 01 ⟩, ∣ 10 ⟩}$ , [F6] gives $U = - S$ , whose eigenvectors $∣ 01 ⟩ + ∣ 10 ⟩$ and $∣ 01 ⟩ - ∣ 10 ⟩$ have eigenvalues $- 1$ and $+ 1$ . Hence $σ_{m u l t} (U) = {1, 1, 1, - 1}$ and $W = I$ has four eigenvalues $+ 1$ .

1.4F3F4F6F8algebra

At $a = 1$ , $T ∣ 0 ⟩ = ∣ 01 ⟩$ and $T ∣ 1 ⟩ = ∣ 10 ⟩$ , so $A = B = span {∣ 01 ⟩, ∣ 10 ⟩}$ . On $A$ , $R_{A} = + I$ and $U = S$ , with eigenvalues $+ 1, - 1$ . On $K = span {∣ 00 ⟩, ∣ 11 ⟩}$ , $S = I$ , so [F6] gives $U = - I$ . Thus $σ_{m u l t} (U) = {1, - 1, - 1, - 1}$ and $W = I$ has four eigenvalues $+ 1$ .

2.1F5F7F8step 1.2algebra

Suppose $0 < a < 1$ and set $λ = 1 - 2 a \in (- 1, 1)$ and $θ = \arccos λ \in (0, π)$ . By [F7], the $u_{+}$ endpoint line contributes $+ 1$ to $U$ and $W$ , and the $u_{-}$ invariant plane contributes $e^{i θ}, e^{- i θ}$ to $U$ and $e^{2 i θ}, e^{- 2 i θ}$ to $W$ .

3.1F2F3F4F5F6F9F10F11F12step 1.2step 2.1algebra∎

Under the hypothesis of step 2.1, put $r = \sqrt{1 - a}$ and $s = \sqrt{a}$ . Let $A = im T$ and $B = im (S T)$ ; these are subspaces by [F9]–[F10]. By [F3], their spanning vectors are $T ∣ 0 ⟩ = r ∣ 00 ⟩ + s ∣ 01 ⟩$ , $T ∣ 1 ⟩ = s ∣ 10 ⟩ + r ∣ 11 ⟩$ , $S T ∣ 0 ⟩ = r ∣ 00 ⟩ + s ∣ 10 ⟩$ , and $S T ∣ 1 ⟩ = s ∣ 01 ⟩ + r ∣ 11 ⟩$ . The vector $k = (s ∣ 00 ⟩ - r ∣ 01 ⟩ - r ∣ 10 ⟩ + s ∣ 11 ⟩) / \sqrt{2}$ has norm one because $r^{2} + s^{2} = 1$ and is orthogonal to each spanning vector by cancellation of the two $r s$ terms. Hence [F11] gives $0 \neq k \in K : = (A + B)^{⊥}$ ; since the product register has dimension four, [F12] implies $\dim (A + B) \leq 3$ . By [F5], $S T u_{+} = T u_{+}$ gives a common nonzero vector in $A \cap B$ , while $T u_{-}$ and $S T u_{-}$ are linearly independent because $- 1 < λ < 1$ . These two vectors are orthogonal to the common vector: $⟨ T u_{+}, T u_{-} ⟩ = ⟨ S T u_{+}, S T u_{-} ⟩ = 0$ by isometry of $T$ and unitarity of $S$ , and $⟨ T u_{+}, S T u_{-} ⟩ = ⟨ u_{+}, D u_{-} ⟩ = 0$ by the distinct eigenvalues in step 1.2; the reverse cross-pairing vanishes by conjugate symmetry. Thus $\dim (A + B) \geq 3$ , so it is exactly $3$ and $K$ is one-dimensional, hence $K = span {k}$ . The coefficients of $∣ 01 ⟩$ and $∣ 10 ⟩$ in $k$ are equal, so [F3] gives $S k = k$ . By [F6], $U = - S = - I$ on $K$ . Combining this complement eigenvalue with the line and plane eigenvalues from step 2.1 yields $σ_{m u l t} (U) = {1, - 1, e^{i θ}, e^{- i θ}}$ and $σ_{m u l t} (W) = {1, 1, e^{2 i θ}, e^{- 2 i θ}}$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

48 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)