184 lines
8.2 KiB
Python
184 lines
8.2 KiB
Python
|
# symmetry_oracle.sage
|
||
|
|
#
|
||
|
|
# Zwei unabhaengige, computergestuetzte "Symmetrie-Orakel" fuer den vollen
|
||
|
|
# Bloch-Tensor C(rho) eines Graphzustands, angewandt auf einen Schnitt S | S^c.
|
||
|
|
# Verallgemeinert das von Hand gerechnete Ring-Graphzustand-Reflexions-Beispiel
|
||
|
|
# (Section 6 des Papers) zu einem Werkzeug, das man auf beliebige Graphen mit
|
||
|
|
# n <~ 6-8 Knoten anwenden kann.
|
||
|
|
#
|
||
|
|
# (A) Stabilisator-Mechanismus (Lemma "stabilizer-degeneracy"):
|
||
|
|
# exakte GF(2)-symplektische Rechnung an den Stabilisatorerzeugern
|
||
|
|
# K_v = X_v * prod_{u ~ v} Z_u. Liefert -- wenn die Injektivitaetshypothese
|
||
|
|
# fuer psi erfuellt ist -- Singulaerwert und Vielfachheit von M_tilde_S(rho_H)
|
||
|
|
# in geschlossener Form, ohne jede Numerik.
|
||
|
|
#
|
||
|
|
# (B) Schwache (cut-faktorisierende) Symmetrie-Hypothese (Prop. "block-diagonal"):
|
||
|
|
# H = Stab_{Aut(G)}(S) (setwise), gefunden durch direkte Enumeration von
|
||
|
|
# Aut(G) (fuer n<=6-8 unproblematisch). Die induzierte Permutationsdarstellung
|
||
|
|
# von H auf S wird ueber die Charaktertafel in Aut-Irreduzible zerlegt --
|
||
|
|
# das sagt voraus, in welche Isotypen-Bloecke M_S zerfaellt (nicht die
|
||
|
|
# Singulaerwerte selbst, die bleiben zustandsabhaengig).
|
||
|
|
#
|
||
|
|
# Die beiden Mechanismen sind gemaess Remark "two-mechanisms" im Paper
|
||
|
|
# unabhaengig und werden hier bewusst getrennt und gegeneinander gegengeprueft,
|
||
|
|
# nicht kombiniert.
|
||
|
|
#
|
||
|
|
# Ausfuehren mit: sage symmetry_oracle.sage
|
||
|
|
#
|
||
|
|
# HINWEIS: Dieses Skript wurde ohne Zugriff auf eine laufende Sage-Instanz
|
||
|
|
# geschrieben (reines Nachrechnen von Hand als Validierung, siehe unten). Die
|
||
|
|
# Mathematik ist geprueft; falls eine einzelne Sage-Methode in eurer Version
|
||
|
|
# anders heisst, sollte der eingebaute Konsistenz-Check (assert) das sofort
|
||
|
|
# anzeigen statt still falsche Zahlen zu liefern.
|
||
|
|
|
||
|
|
from sage.all import *
|
||
|
|
|
||
|
|
|
||
|
|
def graph_state_generator_matrix(G):
|
||
|
|
"""
|
||
|
|
n x 2n GF(2)-Matrix [I | A], deren Zeilen die symplektischen Vektoren der
|
||
|
|
Stabilisatorerzeuger K_v = X_v * prod_{u ~ v} Z_u sind.
|
||
|
|
Konvention: Spalten 0..n-1 = X-Anteile, n..2n-1 = Z-Anteile (wie im Paper,
|
||
|
|
Lemma "code-support").
|
||
|
|
"""
|
||
|
|
n = G.num_verts()
|
||
|
|
A = G.adjacency_matrix().change_ring(GF(2))
|
||
|
|
I = identity_matrix(GF(2), n)
|
||
|
|
return I.augment(A), n
|
||
|
|
|
||
|
|
|
||
|
|
def restrict_columns(Gen, S, n):
|
||
|
|
cols = sorted(S) + [n + v for v in sorted(S)]
|
||
|
|
return Gen.matrix_from_columns(cols)
|
||
|
|
|
||
|
|
|
||
|
|
def stabilizer_mechanism(G, S):
|
||
|
|
"""Mechanismus (A), siehe Kopfkommentar."""
|
||
|
|
Gen, n = graph_state_generator_matrix(G)
|
||
|
|
S = list(S)
|
||
|
|
Sc = [v for v in G.vertices() if v not in S]
|
||
|
|
Gen_S = restrict_columns(Gen, S, n) # phi: Restriktion auf S (Quelle)
|
||
|
|
Gen_Sc = restrict_columns(Gen, Sc, n) # psi: Restriktion auf S^c (Ziel)
|
||
|
|
rank_phi, rank_psi = Gen_S.rank(), Gen_Sc.rank()
|
||
|
|
ker_phi_dim, ker_psi_dim = n - rank_phi, n - rank_psi
|
||
|
|
|
||
|
|
result = {
|
||
|
|
"S": S, "Sc": Sc, "n": n,
|
||
|
|
"dim_ker_phi": ker_phi_dim, "dim_im_phi": rank_phi,
|
||
|
|
"dim_ker_psi": ker_psi_dim, "dim_im_psi": rank_psi,
|
||
|
|
"psi_injective": (ker_psi_dim == 0),
|
||
|
|
}
|
||
|
|
if result["psi_injective"]:
|
||
|
|
dS, dSc = 2 ** len(S), 2 ** len(Sc) # Qubit-Fall, d=2 pro Partei
|
||
|
|
ker_phi_size = 2 ** ker_phi_dim
|
||
|
|
im_phi_size = 2 ** rank_phi
|
||
|
|
mult = im_phi_size - 1
|
||
|
|
sv = sqrt(QQ(ker_phi_size) / QQ((dS - 1) * (dSc - 1)))
|
||
|
|
result["singular_value"] = sv
|
||
|
|
result["multiplicity"] = mult
|
||
|
|
result["nuclear_norm_contribution"] = mult * sv
|
||
|
|
return result
|
||
|
|
|
||
|
|
|
||
|
|
def weak_hypothesis_prediction(G, S):
|
||
|
|
"""Mechanismus (B), siehe Kopfkommentar."""
|
||
|
|
Aut = G.automorphism_group()
|
||
|
|
S = list(S)
|
||
|
|
S_frozen = frozenset(S)
|
||
|
|
# H = Stab_{Aut(G)}(S) setwise, durch direkte Enumeration (robust, |Aut(G)|
|
||
|
|
# ist fuer n<=6-8 klein genug, dass das kein Performanceproblem ist).
|
||
|
|
stab_elements = [g for g in Aut if frozenset(g(v) for v in S) == S_frozen]
|
||
|
|
H = PermutationGroup(stab_elements)
|
||
|
|
|
||
|
|
reps = H.conjugacy_classes_representatives()
|
||
|
|
sizes = [len({h * g * h ** (-1) for h in H}) for g in reps]
|
||
|
|
order = H.order()
|
||
|
|
CT = H.character_table()
|
||
|
|
|
||
|
|
id_idx = [i for i, g in enumerate(reps) if g == H.one()][0]
|
||
|
|
degrees = [CT[i, id_idx] for i in range(CT.nrows())]
|
||
|
|
assert sum(d ** 2 for d in degrees) == order, \
|
||
|
|
"Konsistenz-Check fehlgeschlagen: Summe der Quadrate der Irrep-Dimensionen != |H|."
|
||
|
|
|
||
|
|
perm_char = [sum(1 for v in S if g(v) == v) for g in reps]
|
||
|
|
|
||
|
|
decomposition = []
|
||
|
|
for i in range(CT.nrows()):
|
||
|
|
chi = [CT[i, j] for j in range(len(reps))]
|
||
|
|
mult = sum(sizes[j] * perm_char[j] * chi[j].conjugate()
|
||
|
|
for j in range(len(reps))) / order
|
||
|
|
if mult != 0:
|
||
|
|
decomposition.append((mult, degrees[i]))
|
||
|
|
|
||
|
|
# Zweiter, von der Spaltenreihenfolge unabhaengiger Konsistenz-Check:
|
||
|
|
# sum_lambda m_lambda * dim(V_lambda) muss = dim(Perm(S)) = |S| sein.
|
||
|
|
# Schlaegt dieser Check fehl, stimmt die Zuordnung reps <-> CT-Spalten
|
||
|
|
# nicht ueberein (dann bitte melden statt der Ausgabe zu trauen).
|
||
|
|
total_dim = sum(m * d for m, d in decomposition)
|
||
|
|
assert total_dim == len(S), (
|
||
|
|
f"Konsistenz-Check fehlgeschlagen: sum(m*dim) = {total_dim} != |S| = {len(S)}. "
|
||
|
|
"Vermutlich Reihenfolge-Mismatch zwischen conjugacy_classes_representatives() "
|
||
|
|
"und character_table()-Spalten -- bitte melden, dann fixen wir das gemeinsam."
|
||
|
|
)
|
||
|
|
|
||
|
|
return {"H": H, "order": order, "decomposition": decomposition}
|
||
|
|
|
||
|
|
|
||
|
|
def report(G, S, label):
|
||
|
|
print("=" * 70)
|
||
|
|
print(f"{label}: Schnitt S={sorted(S)} | S^c={[v for v in G.vertices() if v not in S]}")
|
||
|
|
print("=" * 70)
|
||
|
|
|
||
|
|
stab = stabilizer_mechanism(G, S)
|
||
|
|
print("\n-- (A) Stabilisator-Mechanismus --")
|
||
|
|
print(f" dim ker(phi) = {stab['dim_ker_phi']}, dim im(phi) = {stab['dim_im_phi']}")
|
||
|
|
print(f" dim ker(psi) = {stab['dim_ker_psi']}, dim im(psi) = {stab['dim_im_psi']}")
|
||
|
|
if stab["psi_injective"]:
|
||
|
|
sv, mult, contrib = stab["singular_value"], stab["multiplicity"], stab["nuclear_norm_contribution"]
|
||
|
|
print(" psi injektiv -> Lemma greift exakt.")
|
||
|
|
print(f" Singulaerwert = {sv} (numerisch {float(sv):.6f})")
|
||
|
|
print(f" Vielfachheit = {mult}")
|
||
|
|
print(f" Beitrag zur Nuklearnorm = {contrib} (numerisch {float(contrib):.6f})")
|
||
|
|
else:
|
||
|
|
print(" psi NICHT injektiv -> Lemma greift nicht direkt auf den vollen M_S-Block;")
|
||
|
|
print(" der Ueberschuss sitzt in tieferen Sektoren (vgl. Diskussion des")
|
||
|
|
print(" diagonalen Schnitts in Section 6 des Papers).")
|
||
|
|
|
||
|
|
weak = weak_hypothesis_prediction(G, S)
|
||
|
|
print("\n-- (B) Schwache Symmetrie-Hypothese (Aut(G)-Stabilisator) --")
|
||
|
|
print(f" H = Stab_Aut(G)(S), |H| = {weak['order']}")
|
||
|
|
print(" Isotypenzerlegung von Perm(S) unter H (Multiplizitaet, Dimension):")
|
||
|
|
for mult, deg in weak["decomposition"]:
|
||
|
|
print(f" m={mult}, dim={deg} -> {mult} Kopie(n) eines {deg}-dim. Blocks,")
|
||
|
|
print(" je x3 fuer die interne Pauli-Richtung (x,y,z)")
|
||
|
|
print()
|
||
|
|
|
||
|
|
|
||
|
|
# --- Validierung an einem bekannten Fall: der Ring-Graphzustand aus dem Paper ---
|
||
|
|
|
||
|
|
ring = Graph({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}) # 4-Zyklus 0-1-2-3-0
|
||
|
|
|
||
|
|
report(ring, [0, 1], "Ring-Graphzustand, 'benachbarter' Schnitt")
|
||
|
|
report(ring, [0, 2], "Ring-Graphzustand, 'diagonaler' Schnitt")
|
||
|
|
|
||
|
|
# Erwartung (Tabelle zum Ring-Graphzustand im Paper, dort 1-indiziert als
|
||
|
|
# {1,2}|{3,4} bzw. {1,3}|{2,4}, hier 0-indiziert):
|
||
|
|
#
|
||
|
|
# benachbarter Schnitt {0,1}|{2,3}:
|
||
|
|
# (A) psi injektiv, Nuklearnorm-Beitrag = 5 <-- sollte exakt 5 ausgeben
|
||
|
|
# (B) H = <(0 1)(2 3)> ~= Z_2, Perm(S) = trivial + sign, je Multiplizitaet 1
|
||
|
|
# (das ist exakt die im Paper von Hand hergeleitete Zerlegung in die
|
||
|
|
# symmetrische/antisymmetrische Kombination (e_x^(1) +- e_x^(2))/sqrt(2))
|
||
|
|
#
|
||
|
|
# diagonaler Schnitt {0,2}|{1,3}:
|
||
|
|
# (A) psi NICHT injektiv, weil X_0 X_2 in H vollstaendig auf S getragen ist
|
||
|
|
# -- passend zur Bemerkung im Paper, dass hier der volle Sektor nur
|
||
|
|
# saettigt und der Ueberschuss aus tieferen Sektoren kommt.
|
||
|
|
|
||
|
|
# --- Eigenes Beispiel: hier einen n=5/6-Graphen eintragen ---
|
||
|
|
eigener_graph = Graph({0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 4], 3: [1, 4], 4: [2, 3]})
|
||
|
|
report(eigener_graph, [0, 1], "eigenes Beispiel")
|
||
|
|
|
||
|
|
star = Graph({0: [1,2,3]}) # Stern: Zentrum 0, Blätter 1,2,3
|
||
|
|
report(star, [1,2,3], "Stern, S = Blätter")
|