gf8_oracle_syndrome
def
The syndrome s_A of the GF(8) multiplication phase oracle U_3 |x, y, z> = (-1)^{z . (x * y)} |x, y, z> on nine qubits: s_A = 1 iff A = {x_q, y_r, z_l} (qubit q, qubit 3 + r, qubit 6 + l) and bit l of alpha^q * alpha^r in GF(8) = F_2[alpha]/(alpha^3 + alpha + 1) is 1; s_A = 0 for every other subset A (the oracle is pure-cubic). By the moment form of the Amy-Mosca correspondence, the T-count of U_3 is the least size of a set of nonzero parities whose order-1, 2, 3 moments equal this syndrome.
Statement
def gf8_oracle_syndrome (A : Finset (Fin 9)) : ZMod 2- Defined in
- Exact T-counts of Toffoli Layers from an Isotropy Bound, arXiv:2610.01024, Proposition 55 and Fact 21 (the GF(8) multiplication phase oracle and its syndrome)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- gf8_mult_coeffThe structure constants for multiplication in GF(8) with respect to the basis {1, alpha, alpha^2} with irreducible polynomial alpha^3 +…
- Used by 10
- gf8_oracle_parity_repr_nonemptyEvery parity representation S of the GF(8) multiplication oracle syndrome is nonempty because the syndrome at {0, 3, 6} is 1 mod 2,…
- gf8_oracle_min_t_count_le_29The minimal T-count of the GF(8) multiplication oracle is at most 29, certified by an explicit 29-parity representation.
- gf8_oracle_syndrome_zero_zero_zeroSanity check: the syndrome of the GF(8) oracle is 1 on {x_0, y_0, z_0}, since 1 * 1 = 1 has bit 0 set.
- gf8_oracle_t_count_le_29The GF(8) multiplication oracle has a parity representation with 29 parities, so its T-count delta(U_3) in Hadamard-free {CNOT, T}…
- gf8_oracle_syndrome_eq_zero_of_card_ne_threeThe syndrome of the GF(8) multiplication oracle vanishes on any subset A ⊆ Fin 9 whose cardinality is not 3, because non-zero syndrome…
- gf8_oracle_min_t_countThe minimal T-count of the GF(8) multiplication phase oracle on nine qubits in the Hadamard-free {CNOT, T} model, defined via the…
- gf8_oracle_syndrome_singletonSanity check: the GF(8) oracle has no order-one syndrome.
- gf8_oracle_syndrome_same_registerSanity check: the syndrome of the GF(8) oracle vanishes on a triple inside one register.
- gf8_oracle_min_t_count_ge_20The slice-rank lower bound: the minimal T-count of the GF(8) multiplication oracle is at least 20.
- gf8_oracle_t_count_ge_20The slice-rank floor of arXiv:2610.01024 Proposition 59 at k = 3: every parity representation of the GF(8) multiplication oracle's…
Lean source view module on GitHub
/-- The order-at-most-three syndrome of the GF(8) multiplication phase oracle on nine qubits (qubits 0-2 hold x, 3-5 hold y, 6-8 hold z, polynomial basis with alpha^3 = alpha + 1): 1 exactly on the triples {x_q, y_r, z_l} for which bit l of alpha^q * alpha^r is 1, and 0 on every other set. -/ def gf8_oracle_syndrome (A : Finset (Fin 9)) : ZMod 2 := if ∃ q r l : Fin 3, gf8_mult_coeff q r l = 1 ∧ A = {⟨q.val, by omega⟩, ⟨3 + r.val, by omega⟩, ⟨6 + l.val, by omega⟩} then 1 else 0