A phase-encoded quantum graph embedding writes a graph on vertices into qubits through a fixed, shallow circuit and reads it out by measuring in the computational basis. Such fixed circuits are proposed as graph features for learning and for graph comparison, and parameterized versions of them (QAOA-type circuits) are studied as quantum graph neural networks whose expressive power is measured against the Weisfeiler–Leman hierarchy. A measured probability vector depends on how the vertices were labelled; sorting its entries removes the labelling and gives the sorted readout , a genuine graph invariant. The question this mission formalizes is what that invariant provably sees.
L. Miller and Y. Lee (Structural Accessibility in Phase-Encoded Quantum Graph Embeddings, manuscript submitted to STOC 2027, build of 2026-11-03) answer it at first order in the mixer angle for cubic graphs. An earlier paper of the same authors proved injectivity of the one-repetition state vector on labelled graphs under an irrational-angle condition; that result says nothing about the sorted readout, because sorting discards the labelling.
Let be a simple graph with vertices , vertex being qubit . An outcome is , with spins . The circuit is
where multiplies by , the mixer uses the axis , rotations follow the convention , and is the number of tied repetitions. The degree-aware preparation is ; on a cubic graph (every degree ) every qubit receives . The Hadamard preparation is . The members studied are PE-X1 (, ), PE-Y1 (, ), PE-X2 (, ) and PE-QX1 (, , Hadamard).
The defects of are its zero bits, . Put , , . At every outcome with defects has probability , so when the sorted readout lists the outcomes by defect count: the ranks , , form the -defect block.
For and a vertex let . The profile of is the pair of count vectors , , ; the extremal counts are , ; the odd readings are of each vector. The first-order value of is with and .
The paper organizes its theorem-level contributions as Theorems A–D: Theorem A is the template and determination goal below; Theorem B’s first-three-layers results are refTheorem 4.1 and refTheorem 4.3; Theorem C’s Weisfeiler–Leman placement is refTheorem 5.3; and Theorem D’s second-order purity closure is refTheorem 6.1. The platform allows one goal, so Theorem A is the goal while Theorems B–D are milestones of equal standing.
The milestones from Sections 4–6 and Appendix B were added on 2026-11-16 so that the mission covers every theorem of the paper.
With the mixer profiles and , for every cubic and every outcome,
and under the Hadamard preparation . If , and , then for every and all sufficiently small , equal -defect blocks of two cubic graphs force equal histograms of over all -subsets; for the Y mixer the same holds for the odd-reading histograms when and are -linearly independent. At the schedule both hypotheses hold, for every , for PE-X1, PE-X2 and PE-Y1.
The β = 0 distribution (eq. (2)); the flip ratio (Lemma B.3) and its phase-general form (Lemma B.19); the generator form of (Lemma A.1), the repetition ratios (Lemma A.2) and the Y generator (Lemma A.3); the layer template (Theorem 3.2); its extremal-count form (Corollary A.6); occupancy of the blocks by the layers (§2); X-mixer and Y-mixer layer determination (Theorems A.8, A.21) and their complementarity (Corollary A.19); the transcendence of (Lemma A.7), the schedule constants (Remark A.9) and the rational independence at the schedule (Lemma A.20).
refTheorem 4.1 gives , affine increments , and seven distinct class values iff and .
refTheorem 4.3 gives, at girth at least five, the two- and three-defect histograms; both three-defect histograms are functions of and each determines .
refTheorem B.17 gives the cubic PE-X1 second-purity closure with , , and from the pair kernels .
refTheorem B.22 shows that under the Hadamard preparation , the nonadjacent pair kernel vanishes: for every codegree and every .
The template turns a -dimensional circuit derivative into a linear functional of a combinatorial profile, which is checkable by hand on any graph. The determination statements identify explicit invariants carried by a label-free quantum readout: at the extremal-count histogram is the pair census, which fixes the triangle, four-cycle and counts. The paper develops the same analysis through the first three layers, Weisfeiler–Leman placement and second-purity closures, all milestones of this mission.
The paper's proofs are on paper only; none of the statements has a machine-checked proof. A formal development checks the sign and half-angle conventions of the template, which are easy to get wrong (a full-angle convention replaces by ; swapping bits and spins exchanges and ), and it gives a reusable finite model of product-state circuits with diagonal phase layers.
Part (1) is an exact computation, but over the full -dimensional state: the derivative of a matrix power must be expanded, each term reduced by a flip-ratio identity that depends on the half-angle conventions, and the result regrouped by the profile. Part (2) has two layers. The arithmetic step is short for the X mixer (an integer equal to times an integer) but for the Y mixer needs the four-number independence. The analytic step, from first-order values to the sorted readout at a positive , needs a quantitative perturbation argument: the -defect layer must occupy its block of ranks, and the second-order remainder must stay below the gap between distinct first-order values, uniformly in the graphs. At the schedule the number theory rests on the Hermite–Lindemann theorem and on an explicit Laurent-polynomial identity in .
Outcomes are functions with true the bit ; graphs are SimpleGraph (Fin n) with classical decidability; cubic means every vertex has exactly three neighbours. States are vectors over indexed by outcomes, the mixer is the entrywise tensor product of rotations, and the edge phase is a diagonal matrix with each edge counted once. The derivative is deriv at (the Born probability is differentiable in ), and is used only under , so no statement holds through . The sorted readout is the descending sort of the multiset of the values and blocks are cut by rank, never by defect count, so the determination statements do not presuppose that layers occupy blocks. Histograms are multisets over -subsets. "Determines" is stated as: one , then all , then all pairs of cubic graphs. The X mixer is stated for every , which contains PE-X1 and PE-X2. Transcendence and independence are over on .
Contributions welcome: proofs of the flip-ratio lemmas and of the generator form, which are reusable for any product-state circuit with diagonal phases; the perturbation argument for block occupancy; and the schedule number theory, for which the platform's proved Hermite–Lindemann theorem (DiazModulus.hermite_lindemann_holds) is available.
f113265885c9a9ab6b8d7867e881671f8f8108fe0828692fcd3f369544f97c51.namespace PhaseEncodedQGE
open Matrix
/-- Theorem A, template and determination (Theorems 3.2 and 3.3) (Miller, Lee, *Structural Accessibility in Phase-Encoded Quantum Graph Embeddings*, STOC 2027 submission (build 2026-11-03), §1.2, p.2).
Let `G` be a cubic graph on `n` vertices under a degree-prepared member, and in part (2) let
`t = tan(η/2) > 1`, so that the sorted readout at `β = 0` lists the outcomes by defect count.
1. For every outcome `x` with defect set `D`,
`λ(x) = t^{−1} ∑_{j∉D} h(k_j(D)) − t ∑_{j∈D} h(k_j(D))`, where the mixer profile `h` is
`cos(γ(2k − 3))` for the X mixer, `sin(γ(2k − 3))` for the Y mixer, and
`cos(γ(2k − 3)) + cos(2γ(2k − 3))` for two tied repetitions. Under the Hadamard preparation the
same holds with `t = 1`, the profile `sin(γ(2k − 3))`, and the two sums exchanged.
2. For the X mixer, if `h(0) ≠ h(1)` and `t²` is irrational, then for every `m` and all sufficiently
small `β > 0` the sorted readout on the ranks of the `m`-defect block determines the histogram of
`(E_in(D), E_out(D))` over all `m`-subsets `D`. For the Y mixer the same holds for the histogram of
the odd readings when `sin γ ≠ 0` and `1, sin² γ, t², t² sin² γ` are linearly independent over
`ℚ`. At the schedule `t²` is transcendental and the independence holds, so both statements hold
for every `n`.
**Formalization Note** The X mixer is stated at every number `r ≥ 1` of tied repetitions with
`h = h^{X,r}` (`r = 1, 2` are the paper's members PE-X1, PE-X2). Part (1) assumes only
`cos(η/2) ≠ 0 ≠ sin(η/2)`, which excludes the angles where `t^{±1}` or `λ = p₁/p₀` is undefined; the
Hadamard member is PE-QX1 (X mixer, one repetition). Part (2) keeps the standing assumption
`0 < η < π` of §2 (p.5). "Determines" is: one `β₀ > 0` such that for all `β ∈ (0, β₀)` and all cubic
`G, H` on `Fin n`, equal `m`-defect blocks (ranks `K_{m−1}(n)+1, …, K_m(n)` of the sorted readout)
imply equal histograms. The schedule is `(η, γ) = (23/8, 2)`; its clause covers PE-X1, PE-X2 and
PE-Y1. -/
theorem theorem_A :
(∀ (n : ℕ) (G : SimpleGraph (Fin n)), IsCubic G → ∀ (η γ : ℝ), Real.cos (η / 2) ≠ 0 →
Real.sin (η / 2) ≠ 0 → ∀ r : ℕ, 1 ≤ r → ∀ x : Outcome n,
firstOrder (degPrep G η) .X r G γ x =
(Real.tan (η / 2))⁻¹ * ∑ j ∈ Finset.univ \ defects x, hX r γ (kdef G (defects x) j) -
Real.tan (η / 2) * ∑ j ∈ defects x, hX r γ (kdef G (defects x) j)) ∧
(∀ (n : ℕ) (G : SimpleGraph (Fin n)), IsCubic G → ∀ (η γ : ℝ), Real.cos (η / 2) ≠ 0 →
Real.sin (η / 2) ≠ 0 → ∀ x : Outcome n,
firstOrder (degPrep G η) .Y 1 G γ x =
(Real.tan (η / 2))⁻¹ * ∑ j ∈ Finset.univ \ defects x, hY γ (kdef G (defects x) j) -
Real.tan (η / 2) * ∑ j ∈ defects x, hY γ (kdef G (defects x) j)) ∧
(∀ (n : ℕ) (G : SimpleGraph (Fin n)), IsCubic G → ∀ (γ : ℝ) (x : Outcome n),
firstOrder (hadPrep n) .X 1 G γ x =
∑ j ∈ defects x, Real.sin (γ * (2 * (kdef G (defects x) j : ℝ) - 3)) -
∑ j ∈ Finset.univ \ defects x, Real.sin (γ * (2 * (kdef G (defects x) j : ℝ) - 3))) ∧
(∀ (n m r : ℕ), 1 ≤ r → ∀ (η γ : ℝ), 0 < η → η < Real.pi → 1 < Real.tan (η / 2) →
hX r γ 0 ≠ hX r γ 1 → Irrational (Real.tan (η / 2) ^ 2) →
∃ β₀ > 0, ∀ β ∈ Set.Ioo 0 β₀, ∀ G H : SimpleGraph (Fin n), IsCubic G → IsCubic H →
block (degPrep G η) .X r G γ β m = block (degPrep H η) .X r H γ β m →
extremalHist G m = extremalHist H m) ∧
(∀ (n m : ℕ) (η γ : ℝ), 0 < η → η < Real.pi → 1 < Real.tan (η / 2) → Real.sin γ ≠ 0 →
LinearIndependent ℚ ![(1 : ℝ), Real.sin γ ^ 2, Real.tan (η / 2) ^ 2,
Real.tan (η / 2) ^ 2 * Real.sin γ ^ 2] →
∃ β₀ > 0, ∀ β ∈ Set.Ioo 0 β₀, ∀ G H : SimpleGraph (Fin n), IsCubic G → IsCubic H →
block (degPrep G η) .Y 1 G γ β m = block (degPrep H η) .Y 1 H γ β m →
oddHist G m = oddHist H m) ∧
(Transcendental ℚ (Real.tan ((23 / 8 : ℝ) / 2) ^ 2) ∧
LinearIndependent ℚ ![(1 : ℝ), Real.sin 2 ^ 2, Real.tan ((23 / 8 : ℝ) / 2) ^ 2,
Real.tan ((23 / 8 : ℝ) / 2) ^ 2 * Real.sin 2 ^ 2] ∧
∀ n m : ℕ, ∃ β₀ > 0, ∀ β ∈ Set.Ioo 0 β₀, ∀ G H : SimpleGraph (Fin n),
IsCubic G → IsCubic H →
(block (degPrep G (23 / 8)) .X 1 G 2 β m = block (degPrep H (23 / 8)) .X 1 H 2 β m →
extremalHist G m = extremalHist H m) ∧
(block (degPrep G (23 / 8)) .X 2 G 2 β m = block (degPrep H (23 / 8)) .X 2 H 2 β m →
extremalHist G m = extremalHist H m) ∧
(block (degPrep G (23 / 8)) .Y 1 G 2 β m = block (degPrep H (23 / 8)) .Y 1 H 2 β m →
oddHist G m = oddHist H m)) := by sorry
end PhaseEncodedQGE
Let be a cubic graph on vertices, , .
Part (1), template. For every outcome with defect set ,
where , , for the X mixer at tied repetitions ( for one, for two) and for the Y mixer. Under the Hadamard preparation (PE-QX1) the same holds with , the profile and the two sums exchanged:
Part (2), determination (with and ).
The sorted readout forgets the labelling of the vertices, so part (2) says that this label-free readout still recovers explicit graph invariants (the extremal-count and odd-reading histograms of every defect layer).
Differences from the source:
No open leaves. Every sub-goal is proved or awaiting decomposition.