TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)

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.

Exact and approximate success of complete-graph continuous-time search

Statement

For every integer $N \geq 2$ , every marked label $w \in [N]$ , and every encoded complete-graph search instance of Complete-graph continuous-time search whose supplied preparation produces $e_{s} = N^{- 1 / 2} \sum_{x} e_{e n c (x)}$ , exact evolution under $H = - A / N - ∣ e_{e n c (w)} ⟩ ⟨ e_{e n c (w)} ∣$ at $t = π \sqrt{N} / 2$ places the search register in the marked basis ray with probability exactly $1$ . If that evolution is replaced by a unitary $V$ with $∥ V - U_{H} (t) ∥_{o p} \leq ρ$ for $ρ \geq 0$ , the measured probability of the marked label is at least $1 - 2 ρ$ .

Facts & Assumptions

Given: The finite encoded register, $N \geq 2$ , marked label $w$ , complete-graph generator and uniform state from the algorithm, real time $t = π \sqrt{N} / 2$ , and, for the approximation clause, a unitary simulator $V$ with the stated operator-norm error bound.

[F1]

Complete-graph continuous-time search: on the active label subspace, $A e_{e n c (x)} = \sum_{y \neq x} e_{e n c (y)}$ , the marked projector is $P_{w} = ∣ e_{e n c (w)} ⟩ ⟨ e_{e n c (w)} ∣$ , $H = - A / N - P_{w}$ , and $e_{s} = N^{- 1 / 2} \sum_{x} e_{e n c (x)}$ .

[F2]

Finite Hermitian matrix dynamics: for a finite self-adjoint matrix, $U_{H} (t)$ is the spectral sum with coefficient $e^{- i t λ}$ on the $λ$ -eigenspace.

[F3]

Unitary and differential identities for finite matrix dynamics: $U_{H} (t)$ is unitary.

[F4]

The computational basis is orthonormal: for every $d \geq 1$ , the ordered computational basis of $Q_{d}$ is orthonormal; in particular, each qubit factor basis $(e_{0}, e_{1})$ is orthonormal.

[F5]

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

[F6]

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

[F7]

$\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ : $e^{i x} = \cos x + i \sin x$ for real $x$ .

[F8]

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

[F9]

The measurement law for a finite continuous-time walk: for a unit register state, the probability of basis outcome $y$ is the squared modulus of its $y$ -coordinate.

[F10]

Operator-norm error bounds a basis-outcome probability change: for unitary outputs with operator-norm separation at most $ρ$ , any one basis-outcome probability changes by at most $2 ρ$ .

[F11]

The adjoint $T^{*} : W \to V$ is characterised by $⟨ T v, w ⟩_{W} = ⟨ v, T^{*} w ⟩_{V}$ : the adjoint is characterized by $⟨ T x, y ⟩ = ⟨ x, T^{*} y ⟩$ .

[F12]

Ordered tensor registers, their inner product, and wire permutations: an ordered tensor register uses the lexicographic product basis and product inner product; with the orthonormal qubit bases from [F4], the full computational basis is orthonormal.

Proof

technique · direct

1.1givenF1F4F5F11F12algebra

Write $∣ w ⟩ : = e_{e n c (w)}$ and $∣ r ⟩ : = (N - 1)^{- 1 / 2} \sum_{x \neq w} e_{e n c (x)}$ . By [F4], [F12] these are orthonormal; the sum defining $∣ r ⟩$ has $N - 1 \geq 1$ terms. In their ordered basis, [F1] gives $A ∣ w ⟩ = \sqrt{N - 1} ∣ r ⟩$ and $A ∣ r ⟩ = \sqrt{N - 1} ∣ w ⟩ + (N - 2) ∣ r ⟩$ . By [F5], $P_{w} ∣ w ⟩ = ∣ w ⟩$ and $P_{w} ∣ r ⟩ = 0$ , so its restricted matrix is $diag (1, 0)$ . Thus their span $S$ is invariant under $H$ , and the restricted matrices are $A = (\begin{array}{cc} 0 & \sqrt{N - 1} \\ \sqrt{N - 1} & N - 2 \end{array}), H = (\begin{array}{cc} - 1 & - \sqrt{N - 1} / N \\ - \sqrt{N - 1} / N & - (N - 2) / N \end{array}) .$ In the full orthonormal computational basis [F12], $A$ has real symmetric entries between distinct encoded labels and zero entries elsewhere; [F5] makes $P_{w}$ diagonal with a single $1$ . Hence the matrix of $H = - A / N - P_{w}$ is real symmetric, so $⟨ H x, y ⟩ = ⟨ x, H y ⟩$ for all $x, y$ and [F11] gives $H = H^{*}$ . For $z \in S^{⊥}$ and $v \in S$ , self-adjointness and invariance of $S$ give $⟨ H z, v ⟩ = ⟨ z, H v ⟩ = 0$ , so $S^{⊥}$ is invariant too. Thus $H$ splits into self-adjoint blocks on $S$ and $S^{⊥}$ . The input state is $∣ s ⟩ = N^{- 1 / 2} ∣ w ⟩ + \sqrt{(N - 1) / N} ∣ r ⟩$ , which is unit because $∣ w ⟩, ∣ r ⟩$ are orthonormal and the squared coefficients sum to $1$ .

2.1step 1.1algebra

On this two-dimensional invariant span put $K : = H + (N - 1) I / N$ . Then $K = \frac{1}{N} (\begin{array}{cc} - 1 & - \sqrt{N - 1} \\ - \sqrt{N - 1} & 1 \end{array}), K^{2} = I / N, \sqrt{N} K ∣ s ⟩ = - ∣ w ⟩ .$ The first two equalities follow by direct multiplication; for the last, the first coordinate of $K ∣ s ⟩$ is $- 1 / \sqrt{N}$ and the second is $0$ .

3.1step 1.1step 2.1F2F6F7algebra

Let $P_{\pm} = (I \pm \sqrt{N} K) / 2$ . Step 2.1 and self-adjointness of $K$ give $P_{\pm}^{2} = P_{\pm} = P_{\pm}^{*}$ , $P_{+} P_{-} = 0$ , $P_{+} + P_{-} = I$ , and $K P_{\pm} = \pm P_{\pm} / \sqrt{N}$ . By step 1.1, each eigenspace of $H$ is the orthogonal sum of the corresponding eigenspaces of its two blocks: projecting $H z = λ z$ onto either invariant summand preserves that equation. Therefore the spectral sum [F2] restricts on $S$ to the sum determined by $P_{\pm}$ . On $S$ , $H = K - (N - 1) I / N$ , so [F2] and [F6] give, for $a = t / \sqrt{N}$ , $U_{H} (t) ∣_{S} = e^{i t (N - 1) / N} (e^{- i a} P_{+} + e^{i a} P_{-})$ . By [F7], this is $e^{i t (N - 1) / N} (\cos a I - i \sqrt{N} \sin a K)$ .

4.1step 2.1step 3.1F7F8F9algebra

At $t = π \sqrt{N} / 2$ , [F8] gives $a = π / 2$ , so step 3.1 and $\sqrt{N} K ∣ s ⟩ = - ∣ w ⟩$ give $U_{H} (t) ∣ s ⟩ = i e^{i t (N - 1) / N} ∣ w ⟩$ . The coefficient has modulus one by [F7], hence [F9] assigns probability exactly $1$ to the marked label.

5.1givenF3F10step 4.1algebra∎

In the approximate branch, both $V$ and $U_{H} (t)$ are unitary and the prepared input $∣ s ⟩$ is unit. Applying [F10] to the marked basis outcome shows its probability differs from the exact probability in step 4.1 by at most $2 ρ$ . Since that exact probability is $1$ , the simulated success probability is at least $1 - 2 ρ$ .

Depends on

Used by

Complete-graph search matrix and gap Example

Dependency tree · two levels

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