ExampleConstruction: Literature-sourcedVerification: 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.

Complete-graph search matrix and gap

Example

For the complete graph search instance with any finite $N \geq 2$ , let $∣ w ⟩$ be the marked vertex and let $∣ r ⟩$ be the uniform vector on the $N - 1$ unmarked vertices. Compute the invariant $2 \times 2$ generator matrix in the ordered basis $(∣ w ⟩, ∣ r ⟩)$ and its eigenvalue gap. Include the boundary case $N = 2$ . Also verify the supplied uniform preparation for $N = 2$ and $N = 4$ against the one- and two-qubit Hadamard circuits.

Facts & Assumptions

Given: $N \geq 2$ , the encoded complete-graph adjacency, marked projector, and Hamiltonian $H = - A / N - P_{w}$ of the algorithm.

[F1]

Complete-graph continuous-time search: on the active label basis, $A ∣ x ⟩ = \sum_{y \neq x} ∣ y ⟩$ , $P_{w} = ∣ w ⟩ ⟨ w ∣$ , and $H = - A / N - P_{w}$ .

[F2]

Graph adjacency and Laplacian generator conventions: symmetric graph adjacency is Hermitian and the ordered vertex basis is fixed.

[F3]

Dirac Notation Conversion: $∣ x ⟩ ⟨ y ∣$ acts by $z \mapsto ⟨ z, y ⟩ x$ .

[F4]

Finite registers and their ordered computational bases and The computational basis is orthonormal: distinct encoded labels are orthonormal basis vectors.

[F5]

Exact and approximate success of complete-graph continuous-time search: with the supplied uniform preparation, exact evolution under $H = - A / N - P_{w}$ at $t = π \sqrt{N} / 2$ gives marked-label probability exactly $1$ .

[F6]

Hadamard preparation of a uniform binary state: for $N = 2^{n}$ , the standard-binary uniform state is $H^{\otimes n} ∣ 0^{n} ⟩$ , with $n$ Hadamard gates when primitive.

Verification

technique · direct

1.1givenF4choosealgebra

The $N - 1$ unmarked encoded basis vectors are pairwise orthonormal by [F4], so $∣ r ⟩ = (N - 1)^{- 1 / 2} \sum_{x \neq w} ∣ x ⟩$ is unit and orthogonal to the unit vector $∣ w ⟩$ . The uniform vector is $∣ s ⟩ = N^{- 1 / 2} ∣ w ⟩ + \sqrt{(N - 1) / N} ∣ r ⟩$ , whose squared coefficient norms sum to $1$ .

2.1givenF1step 1.1algebra

By [F1], $A ∣ w ⟩ = \sum_{x \neq w} ∣ x ⟩ = \sqrt{N - 1} ∣ r ⟩$ . For $∣ r ⟩$ , each summand $A ∣ x ⟩$ contains $∣ w ⟩$ once, so its $∣ w ⟩$ coefficient is $\sqrt{N - 1}$ ; for each unmarked $y$ , the sum contains $∣ y ⟩$ once for each $x \neq y, w$ , hence $N - 2$ times. Thus $A ∣ r ⟩ = \sqrt{N - 1} ∣ w ⟩ + (N - 2) ∣ r ⟩$ .

3.1F1F2F3step 2.1algebra

The two vectors span an invariant subspace for $A$ by step 2.1. By [F3], $P_{w} ∣ w ⟩ = ∣ w ⟩$ and $P_{w} ∣ r ⟩ = 0$ , so $P_{w}$ also preserves this span. The symmetric adjacency is Hermitian by [F2], and the generator matrix is $H = (\begin{array}{cc} - 1 & - \sqrt{N - 1} / N \\ - \sqrt{N - 1} / N & - (N - 2) / N \end{array}) .$

4.1step 3.1algebra

Put $K = H + (N - 1) I / N$ . Direct multiplication gives $K^{2} = I / N$ , and $tr K = 0$ . Equivalently, its characteristic polynomial is $λ^{2} - 1 / N$ , so its eigenvalues are $\pm 1 / \sqrt{N}$ . Therefore the eigenvalues of $H$ are $- (N - 1) / N \pm 1 / \sqrt{N}$ , and their gap is $2 / \sqrt{N}$ .

5.1step 1.1step 3.1step 4.1algebra

At $N = 2$ , $∣ r ⟩$ is the single unmarked basis vector and the formula in step 3.1 becomes $H = (\begin{array}{cc} - 1 & - 1 / 2 \\ - 1 / 2 & 0 \end{array})$ . The shifted matrix has eigenvalues $\pm 1 / \sqrt{2}$ , so the gap is $\sqrt{2}$ ; all normalizations and denominators used above remain valid.

5.2F5step 1.1step 3.1step 4.1

For the uniform input $∣ s ⟩$ in step 1.1, [F5] gives marked-label probability $1$ after exact evolution at $t = π \sqrt{N} / 2$ . The invariant matrix and its gap were derived locally in steps 3.1–4.1.

6.1F1F2F6algebra∎

Specialize to the standard binary encoding for $N = 2$ and $N = 4$ . For $N = 2$ , the preparation is $H ∣ 0 ⟩ = (∣ 0 ⟩ + ∣ 1 ⟩) / \sqrt{2}$ , which is the required uniform state with one Hadamard gate. For $N = 4$ , applying the second factor gives $H^{\otimes 2} ∣ 00 ⟩ = (∣ 00 ⟩ + ∣ 01 ⟩ + ∣ 10 ⟩ + ∣ 11 ⟩) / 2$ , the required uniform state with two Hadamard gates. These are the $n = 1, 2$ cases of [F6]; no preparation or gate cost is inferred from the search matrix.

Depends on

Used by

Nothing in the library uses this result yet.

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, Chapter 17 §17.1 (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes, Chapter 9 §9.1 (standard reference, not scraped)