Metadata-Version: 2.4
Name: ultraqse
Version: 1.0.0
Summary: Von Neumann Entropy of CNOT circuits via Walsh-Hadamard transforms over GF(2)
Author-email: Ozgurooozer <ozigoca@gmail.com>
License-Expression: MIT
Project-URL: Repository, https://github.com/Ozgurooozer/ultraqse
Keywords: quantum,entropy,von neumann,walsh hadamard,gf2,cnot,entanglement,quantum circuits
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering :: Physics
Classifier: Intended Audience :: Science/Research
Classifier: Operating System :: OS Independent
Requires-Python: >=3.9
Description-Content-Type: text/markdown
Requires-Dist: numpy>=1.21

# QSE Theorem Reference

**Convention:** `Rx(θ)|0⟩ = cos(θ/2)|0⟩ − i·sin(θ/2)|1⟩`  
**Ry convention:** `Ry(θ)|0⟩ = cos(θ/2)|0⟩ − sin(θ/2)|1⟩`  
**Φ_M(s)** = ∏_{i: (M^T s)_i = 1} cos(θᵢ)  
**M** ∈ F₂^{NB×NA}: M[b][a] = 1 iff CNOT(ctrl=a, tgt=b) is present  
**Qubit layout:** A-qubits = bits 0..NA−1, B-qubits = bits NA..NA+NB−1  

---

## Core Theorems

| ID | Name | Formula | max_err |
|----|------|---------|---------|
| **T14** | Walsh-Hadamard Master | `P_b = (1/2^NB) Σ_s (−1)^{b·s} Φ_M(s)`, `VNE = H({P_b})` | < 7e-16 |
| **T-UNIVERSAL** | Diagonal Mixed Input | `P_b = Σ_{x: Mx=b} ρ_A[x,x]` (works for any diagonal ρ_A) | < 5e-16 |
| **T-UNIVERSAL-GEN** | Nonlinear Gates | `P_b = Σ_{x: f(x)=b} |ψ[x]|²` | < 3e-16 |
| **T16** | Phase Invariance | VNE depends only on {|cos(θᵢ/2)|²}, not on U(1) phases | < 7e-16 |

---

## Structural Theorems

| ID | Name | Key Result | max_err |
|----|------|-----------|---------|
| **T17** | Blindness | VNE = 0 ↔ rank_F₂(M) = 0 | exact |
| **T-RANK** | Rank Upper Bound | `VNE(B) ≤ rank_F₂(M)` | exact |
| **T-OPT** | Rank Saturation | θ = π/2 ⟹ `VNE = rank_F₂(M)` exactly | exact |
| **T-SUB** | Monotone Substructure | Adding CNOT → rank nondecreasing → VNE nondecreasing | exact |

---

## Gate Extensions

| ID | Name | Key Result | max_err |
|----|------|-----------|---------|
| **T-BINIT** | B-Init Independence | T14 formula unchanged for any product-state B init (full-rank M) | < 7e-16 |
| **CZ-T14** | CZ Equivalence | CZ + \|+⟩_A = CNOT + \|0⟩_A (same VNE) | < 6e-16 |
| **T-fSim** | fSim Gate (NA=1) | λ± = (1 ± √D)/2, D = 1 − sin²(2α)sin⁴(θ/2); φ-invariant | < 2e-15 |
| **T-FSIM-PRODUCT** | fSim Product Gates | NA independent fSim gates (qubit i ↔ B-qubit i): `VNE = Σᵢ H(λ±ᵢ)` | < 4e-14 |
| **iSWAP** | Full iSWAP | iSWAP + Rx(θ)\|0⟩_B → product state → VNE = 0 | < 4e-16 |
| **T-SWAP** | SWAP via 3 CNOTs | SWAP(A_a, B_b) via CNOT→CNOT→CNOT → VNE(B) = 0 | < 7e-16 |

---

## Symmetry & Invariance Theorems

| ID | Name | Key Result | max_err |
|----|------|-----------|---------|
| **T-RY-EQ** | Ry = Rx Symmetry | VNE(Ry(θ) circuit) = VNE(Rx(θ) circuit) for same θ and M | < 8e-16 |
| **T-MIRROR** | Schmidt Symmetry | VNE(A) = VNE(B) for any pure bipartite state \|Ψ⟩_AB | < 8e-16 |
| **T-COHERENCE-DIAG** | Off-diagonal ρ_A Blindness | Off-diagonal ρ_A elements do not affect VNE(B); ρ_B always diagonal; VNE depends only on diag(ρ_A) | 0 |

**T-COHERENCE-DIAG note:** This is a non-trivial result. Even if A is in a coherent superposition
(off-diagonal ρ_A ≠ 0), the partial trace over A produces a strictly diagonal ρ_B, so
the CNOT circuit acts as a classical channel at the level of B's entropy.

---

## Gradient Theorems

| ID | Name | Formula | max_err |
|----|------|---------|---------|
| **T-GRAD** | Rx VNE Gradient | `d(VNE)/dθᵢ = −Σ_b (dP_b/dθᵢ)·log₂(P_b)` where `dP_b/dθᵢ = (1/2^NB) Σ_{s: (M^T s)_i=1} (−1)^{b·s}·(−tan θᵢ)·Φ_M(s)` | < 2e-10 (FD limit) |

**T-GRAD note:** The 2e-10 error is the finite-difference floor, not an analytic error.
The closed-form formula is exact; verification uses 4th-order central differences (h=1e-5).

---

## Information-Theoretic Theorems

| ID | Name | Formula | max_err |
|----|------|---------|---------|
| **T-MUTUAL** | Mutual Information | `I(A;B) = 2·VNE(B)` for pure state | exact |
| **T-MI** | MI Non-Negativity | `I(B₁;B₂) ≥ 0` | analytical |
| **T-PAULI** | Pauli Representation | `Φ_M(s) = ⟨Z^{M^T s}⟩_A` (Pauli expectation value form) | exact |

---

## Dynamics

| ID | Name | Key Result | max_err |
|----|------|-----------|---------|
| **T15A** | k-Layer Circuits | `M_eff = M₁ ⊕ M₂ ⊕ ... ⊕ Mₖ (mod 2)` | < 8e-16 |
| **T18** | Period-2 | Even number of identical CNOT layers → M_eff = 0 → VNE = 0 | < 4e-16 |
| **T-BIDIR** | Bidirectional Circuits | Alternating A→B and B→A CNOT layers reduce to T14(M_eff) | < 2e-15 |

**T-BIDIR details:**

For circuits with interleaved A→B layers (CNOTs ctrl=a, tgt=B_b) and B→A layers
(CNOTs ctrl=B_b, tgt=a), the effective M matrix is:

```
M_eff[b, :] = M_raw[b, :] @ T_cum  (mod 2)
```

where T_cum ∈ F₂^{NA×NA} is the cumulative A-space shear transformation accumulated
from all B→A CNOTs seen so far. Update rule after CNOT(ctrl=B_b, tgt=A_a):

```
T_cum[a, :] ^= M_eff[b_abs, :]   (row XOR, not matrix multiply)
```

**Invertibility condition:** T_cum must have full GF(2) rank (= NA). When T_cum is
singular, multiple x-values map to the same A-state with different B-states, creating
off-diagonal ρ_B elements (quantum coherences) that break the T14 assumption. The
theorem applies only to circuits where T_cum remains invertible throughout.

---

## Noise Theorems

| ID | Name | Formula | max_err |
|----|------|---------|---------|
| **T-NOISE** | Amplitude Damping | After AD_γ on B: `P₀ → P₀+γP₁`, `P₁ → (1−γ)P₁`; `VNE_noisy = H(P₀+γP₁, (1−γ)P₁)` | < 3e-16 |
| **S2** | k-Round Transfer Matrix | `T = S_AD_A · S_CNOT · S_AD_B · S_CNOT` (16×16 superoperator); `vec(ρₖ) = Tᵏ·vec(ρ₀)` | < 7e-16 |

---

## Moment & Rényi Theory

| ID | Name | Formula | max_err |
|----|------|---------|---------|
| **T22** | Rényi Moments | `Tr(ρᵅ) = (1/2^{(α−1)NB}) Σ_{s₁..s_{α−1}} ∏Φ_M(sᵢ)·Φ_M(⊕sᵢ)` | < 2e-15 |
| **T29** | Newton-Girard Spectrum | Power-sum moments (T22) → Newton-Girard identities → all eigenvalues of ρ_B | < 7e-7 |
| **T-RENYI-DERIV** | Rényi Derivative | `dS_α/dα\|_{α=1} = −(ln2/2)·Var_P[log₂ P_b]` where `Var_P = Σ_b P_b(log₂ P_b)² − VNE²` | < 4e-10 (4th-order FD) |
| **T-RENYI-CONV** | Rényi→VNE Convergence | `S_α → VNE` as `α → 1` | 0 |

**T-RENYI-DERIV note:** Derived by Taylor-expanding `log Tr(ρᵅ)` around α=1 using T22
moments. The `(ln2/2)·Var` coefficient follows from the second cumulant of the log-probability
distribution. Verified with 4th-order central differences (h=1e-3) to avoid FD floor.

---

## Random Circuit Statistics

| ID | Name | Key Result | max_err |
|----|------|-----------|---------|
| **T-RANDOM-VNE** | Expected VNE = Expected GF(2) Rank | `E[VNE(θ=π/2)] = E[rank_GF₂(M)]` over uniform random M ∈ F₂^{NB×NA} | 0 |

**Gaussian binomial formula:**

```
E[rank_GF₂(M)] = (1/2^{NA·NB}) · Σ_{r=1}^{min(NA,NB)} r · [NB choose r]₂ · ∏_{j<r}(2^NA − 2^j)

[n choose k]₂ = ∏_{j=0}^{k-1}(2^n − 2^j) / ∏_{j=0}^{k-1}(2^k − 2^j)   (Gaussian binomial)
```

The formula is exact over integers (no floating-point error).

---

## Inter-Theorem Connections

| ID | Connection | max_err |
|----|-----------|---------|
| **B1** | T22(α=2) = Parseval: `Σ P_b² = (1/2^NB) Σ Φ(s)²` | < 3e-16 |
| **B2** | `Φ_M(s) = E_{x~P_A}[(−1)^{(M^T s)·x}]` — Walsh-Fourier characteristic function of P_A | < 5e-16 |
| **B3** | T14 = α→1 limit of T22 Rényi hierarchy (T-RENYI-CONV) | analytical |
| **B4** | T17+T-RANK+T-OPT+T-SUB = F₂ linear matroid rank structure | analytical |
| **B5** | T22 = α-point Pauli correlation function (via T-PAULI) | analytical |
| **B6** | VNE(θ) monotone in [0, rank_F₂(M)] for uniform θ ∈ [0, π/2] | 500/500 |
| **B7** | T14 = H(f*(P_A)): VNE is Shannon entropy of the classical pushforward of P_A under M | < 4e-16 |

---

## Resolved Open Problems

| ID | Problem | Resolution | Theorem |
|----|---------|-----------|---------|
| **O1** | Closed-form for bidirectional circuits | M_eff = M_raw·T_cum (GF(2)), invertible T_cum required | T-BIDIR |
| **O2a** | T-fSim eigenvalue formula (NA=1) | D = 1 − sin²(2α)sin⁴(θ/2); φ-invariant | T-fSim |
| **O2b** | T-fSim for NA > 1 | VNE additivity for independent fSim gates | T-FSIM-PRODUCT |
| **O3** | Gradient d(VNE)/dθᵢ for Ry/Rz input | Ry gives same VNE as Rx (T-RY-EQ); Rx gradient in closed form (T-GRAD) | T-RY-EQ, T-GRAD |
| **O4** | Rényi approximation error bound | dS_α/dα\|₁ = −(ln2/2)·Var_P[log₂ P_b] | T-RENYI-DERIV |
| **O5** | Non-diagonal ρ_A extension | Off-diagonal ρ_A does not affect VNE; ρ_B always diagonal | T-COHERENCE-DIAG |
| **O6** | Random circuit VNE via F₂ matroid counting | E[VNE] = E[rank_GF₂] via Gaussian binomial | T-RANDOM-VNE |

---

## Scaling & Performance

Tested on NA=12, NB=6 (2^18 = 262,144 amplitudes):

| Operation | Complexity | Measured |
|-----------|-----------|---------|
| `t14_Pb` (WHT formula) | O(2^{2NB}) | **12 ms** |
| `vne_gradient_rx` | O(NA · 2^{2NB}) | **195 ms** |
| `exact_rho_B` (vectorized) | O(2^{NA+NB} · 2^{NB}) | **8 ms** |
| `exact_rho_B` (old O(n²) loop) | O(4^{NA+NB}) | ~hours |

**Key insight:** T14 complexity depends only on NB (the B register size), not NA.
Growing NA to 100+ costs nothing for the WHT formula — only the statevector
simulation and gradient scale with NA.

**Vectorized partial trace** (`exact_rho_B`):

```python
# Old: O(4^{NA+NB}) double loop — infeasible for NA > 6
# New: O(2^{NA+NB}) reshape + matmul
A = amps.reshape(2**NB, 2**NA)   # B-bits as rows, A-bits as cols
rho_B = A @ A.conj().T           # traces out A exactly
```

Index layout: `amps[a_bits | (b_bits << NA)]` — low NA bits are A, high NB bits are B.
Reshape naturally groups B as rows and A as columns, making the matmul correct.

---

## Package API (`qse/`)

```python
from qse import (
    # Core — T14 machinery
    build_M, phi_dict, t14_Pb, t_universal,
    vne_from_Pb, renyi_entropy, f2_rank,
    t22_moment, newton_girard,

    # States — simulation ground truth
    product_state, product_state_ry,
    exact_rho_B, exact_rho_B_mixed, vne_exact,

    # Gates — statevector operations
    apply_cnot, apply_fsim, apply_swap,

    # Gradients
    vne_gradient_rx,

    # Noise
    amplitude_damping_kraus, superop,
    noise_transfer_Pb, build_cnot_ad_transfer,

    # Random circuits
    gaussian_binom_2, expected_gf2_rank, enumerate_vne,
)
```

---

## Test Suite

Run `python qse_tests.py` — **34/34 tests** pass at machine precision (max_err < 1e-8).

| Phase | Tests | Notes |
|-------|-------|-------|
| Initial commit | 23/23 | Core + noise + moment theory |
| Katman 0 (bug fixes) | 23/23 | T-fSim formula fix, T-BINIT full-rank check, T18 generalization |
| Katman 1 (open problems) | 33/33 | O2b–O6 resolved; T-SWAP, T-MIRROR added |
| Katman 2 (new theorems) | 34/34 | T-BIDIR (O1) completed |
