LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-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.

Controlled-Z edge gates commute

Statement

For any two edges $e, f$ of a finite simple graph on an ordered qubit register, the embedded operators $C Z_{e}$ and $C Z_{f}$ commute. Consequently the finite graph-state edge product is independent of the ordering of its edges.

Facts & Assumptions

Given: A finite ordered vertex set and the diagonal gate $C Z ∣ x_{u} x_{v} ⟩ = (- 1)^{x_{u} x_{v}} ∣ x_{u} x_{v} ⟩$ on each edge pair.

[F1]

The controlled-phase definition gives the angle- $π$ diagonal gate $C Z ∣ x_{u} x_{v} ⟩ = (- 1)^{x_{u} x_{v}} ∣ x_{u} x_{v} ⟩$ , and the graph-state definition embeds one such gate per finite edge (Controlled Phase Rotation, Graph state of an ordered finite simple graph).

Proof

1.1F1given

Fix any computational-basis string $x \in F_{2}^{V}$ . By [F1], $C Z_{{u, v}}$ multiplies $∣ x ⟩$ by the scalar $(- 1)^{x_{u} x_{v}}$ and does not change $x$ .

2.1step 1.1givenalgebra

For edges $e = {u, v}$ and $f = {r, s}$ , the two compositions $C Z_{e} C Z_{f}$ and $C Z_{f} C Z_{e}$ therefore both multiply each $∣ x ⟩$ by $(- 1)^{x_{u} x_{v} + x_{r} x_{s}}$ . The computational-basis vectors span the finite register, so the operators are equal. This covers disjoint edges and edges sharing one endpoint.

3.1step 2.1F1algebra∎

Any two orderings of a finite edge set differ by finitely many adjacent transpositions. Each adjacent transposition preserves the product by step 2.1, so all edge orders give the same graph-state vector; the empty edge set is the identity product.

Depends on

Used by

Dependency tree · two levels

13 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

M. Hein et al., Entanglement in graph states and its applications, arXiv:quant-ph/0602096, §2.1 and Definition Graph States I, pp. 10–14 (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415, §20.6, pp. 178–180 (standard reference, not scraped)