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.
Generator convention matters
Statement refuted
For every finite undirected graph, every initial unit pure state, and every time, replacing by leaves the computational-basis measurement law unchanged. For every finite graph with positive degrees, replacing by also leaves the minimum nonnegative time needed to reach any specified walk output ray unchanged.
Facts & Assumptions
Given: The graph-generator conventions and finite matrix evolution in the preceding definitions. Produce finite counterexamples to both claims.
Graph adjacency and Laplacian generator conventions: , , and when every degree is positive, .
Finite Hermitian matrix dynamics: for self-adjoint , .
, and the complex exponential extends the real exponential: for complex .
, , and : and for real .
Sine and cosine defined by their real power series: sine and cosine are given by their real power series.
The alternating series test: if is nonincreasing with then converges, the sum lies between any two consecutive partial sums, and the error after terms is at most : for decreasing nonnegative terms tending to zero, the alternating sum lies between consecutive partial sums.
Quarter-turn values and shifts by pi/2 and pi: , , and shifts by negate sine and cosine.
The zero sets of sine and cosine and the least positive common period 2 pi: exactly when for an integer .
Finite registers and their ordered computational bases and The computational basis is orthonormal: the ordered basis of is the standard orthonormal basis.
The measurement law for a finite continuous-time walk: for self-adjoint and unit , measuring in an orthonormal basis assigns each basis line its squared-coordinate probability.
Counterexample
For the two-vertex graph with one edge, in basis the adjacency swaps the basis vectors, and , and . Thus , , and . Put , , and . Direct inner-product calculations using [F9] give and ; direct application of gives and . Thus is an orthonormal eigenbasis.
For the three-vertex path with ordered vertices , the degrees are and , , . Thus All degrees are positive, so [F1] defines . Put , , and . By direct coordinate inner products in the standard orthonormal basis [F9], is an orthonormal basis; direct multiplication gives , , and . The vectors , , and also have unit norm and pairwise zero inner products. Direct multiplication gives , , and . Hence the four generator spectra are , , , and . This directly compares adjacency, normalized adjacency, and both Laplacian signs on the irregular graph.
The spectral definition [F2] gives eigenphases for on and for . By [F3]–[F4], these are equivalently and : on and , respectively, the coefficients are and . The coordinate after is ; after it is . Thus [F10] gives and .
Put , which is unit by step 1.2, and fix the target ray , since by [F4], [F7]. For any real , and by [F1]–[F2]. Since the coefficient is the same nonzero number in both target and output, equality of rays forces the scalar multiple to be and is equivalent to equality of the displayed relative phases.
At , the cosine-series magnitudes and sine-series magnitudes decrease to zero: each next factorial multiplies the denominator by a factor at least , so both sequences tend to zero. By [F5]–[F6], the cosine sum lies above its two-term partial sum , and the sine sum lies above . Therefore . The two Laplacian signs give different same-time measurement laws.
If , then . By [F3]–[F4], this forces and ; [F8] puts the angle at , and [F7] shows must be even. Thus . For this is at least ; for it is at most . Hence its least nonnegative value is . The same argument for gives , whose least nonnegative value is . For the second family, gives , every gives a larger time, and every gives a negative time. Thus the least nonnegative time is . These runtimes differ because .
Depends on
- Graph adjacency and Laplacian generator conventions
- Finite Hermitian matrix dynamics
- Unitary and differential identities for finite matrix dynamics
- Finite registers and their ordered computational bases
- The computational basis is orthonormal
- The measurement law for a finite continuous-time walk
- $\exp(z+w)=\exp z\,\exp w$, and the complex exponential extends the real exponential
- $\exp(x+iy)=e^x(\cos y+i\sin y)$, $|\exp(x+iy)|=e^x$, and $e^{i\pi}+1=0$
- Quarter-turn values and shifts by pi/2 and pi
- The zero sets of sine and cosine and the least positive common period 2 pi
- Sine and cosine defined by their real power series
- The alternating series test: if $(b_k)$ is nonincreasing with $b_k \to 0$ then $\sum_{k} (-1)^{k} b_k$ converges, the sum lies between any two consecutive partial sums, and the error after $n$ terms is at most $b_n$
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
67 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)