Generalize LOE-Magic bounds from Clifford+T to {CX,CCX,S}+H

[ChanceSiyuan]

Summary

Extend Theorem 2 of [Dowling et al.] (the LOE ≤ Magic hierarchy: $E^{(\alpha)}_A(O_U) \leq M^{(\alpha)}(O_U) \leq \nu(U) \leq \tau(U)$) from the Pauli basis / Clifford+T framework to the computational basis / {CX,CCX,S}+H framework. This produces a dual "coherence-based" version of the entanglement–magic connection, replacing magic (non-Cliffordness) with coherence (non-classicality in the computational basis).

Motivation

In the original work, the hierarchy of monotones is built on the Clifford group structure:

• Free gates: Clifford group $\mathcal{C}(\mathcal{B}_{\text{Pauli}})$ generated by ${H, S, CX}$
• Non-free (magic) gate: $T$-gate
• Key property: Clifford group is a 3-design but not a 4-design

In operator_magic.qmd, the group $\mathcal{C}(\mathcal{B}_{\text{comp}})$ generated by ${CX, CCX, S}$ plays an analogous role for the computational basis. The Hadamard gate $H$ is the "non-free" gate — it creates coherence (superposition) just as $T$ creates magic. Establishing the parallel theorem bridges entanglement and coherence resources.

Target Theorem

Theorem (Generalized). For any $N$-qubit unitary $U$, any initial computational-basis operator $O \in \mathcal{B}_{\text{comp}} \setminus {\mathbb{I}}$, for any $\alpha \geq 0$ and any bipartition $\mathcal{H} = \mathcal{H}A \otimes \mathcal{H}{\bar{A}}$:

$$\mathcal{F} \leq_{(U \sim \mu, \alpha \leq 2)} E^{(\alpha)}_A(O_U) \leq M^{(\alpha)}_{\text{comp}}(O_U) \leq \nu_{\text{comp}}(U) \leq \eta(U)$$

Progress

Step 1: Prove {CX, CCX, S} is a 3-design but not a 4-design — ✅ DONE (in operator_magic.qmd)

Sub-issues

• Characterize the 4-fold commutant of C(B_comp) #1 — Characterize the 4-fold commutant of C(B_comp)
• Define H-count, computational nullity, OCE, and new ensembles #2 — Define H-count, computational nullity, OCE, and new ensembles
• Compute average operator purity for H-doped and nu_comp-compressible ensembles #3 — Compute average operator purity for H-doped and nu_comp-compressible ensembles
• Prove upper bound chain E_A <= M_comp <= nu_comp <= eta #4 — Prove upper bound chain E_A <= M_comp <= nu_comp <= eta
• State generalized theorem and integrate into paper #5 — State generalized theorem and integrate into paper

Potential Issues / Gaps

1. Bit-permutation symmetry in the commutant: The $\mathcal{C}(\mathcal{B}_{\text{comp}})$ commutant has $S_n$ bit-permutation averaging in addition to $S_k$ replica permutations, which may complicate the Weingarten-like calculus.
2. Choice of initial operator $O$: Need to verify the 4-fold average simplifies for computational-basis elements $|j\rangle\langle k|$ as it does for Pauli strings.
3. Explicit form of extra commutant elements: May be more complex than the clean $\Lambda^{\pm}$ projectors of the Clifford case.
4. Relation between $\eta(U)$ and $\tau(U)$: Discuss whether the two theorems give complementary or redundant information.
5. Physical interpretation — coherence vs. magic: Clarify the regime where each bound is tighter.
6. Diagonalization of $\Xi_{\text{comp}}$: May be a larger matrix than the Clifford $24 \times 24$ case.
7. Connection to BKE framework: Position the new theorem within the bra-ket entanglement framework.

Acceptance Criteria

• Explicit characterization of the 4-fold commutant with closed-form projectors
• Formal definitions of H-count, computational nullity, OCE, and the two new ensembles
• Average operator purity computed for both ensembles, with leading-order expressions in large $D$
• All three upper-bound inequalities proven
• Formal theorem written and integrated into the paper as a new section
• Discussion of the relation to the existing Clifford+T theorem and the BKE framework