Pomnóż macierze Pauliego

12

Do Pauli matryce są zbiorem macierzy 2x2, które występują bardzo powszechnie w fizyce kwantowej (nie, nie trzeba znać żadnych fizyki kwantowej do tego wyzwania). Jeśli uwzględnimy tożsamość w zestawie, cztery macierze to:

 σ0 =      σ1 =      σ2 =      σ3 = 
[1  0]    [0  1]    [0 -i]    [1  0]
[0  1]    [1  0]    [i  0]    [0 -1]

Mnożąc dwa z nich zawsze daje inną Pauli matrycy, choć może zostać pomnożona przez jedną ze złożonych etapów 1, i, -1, -i. Na przykład .σ1σ3 = -iσ2

Twoim zadaniem jest pomnożenie wielu macierzy Pauliego i zwrócenie wynikowej macierzy i fazy. Wejście zostanie podany jako niepusty ciąg cyfr 0do 3reprezentującą matryce do . Wyjście powinno być łańcuch zawierający pojedynczy cyfrę macierzy wynikowej, ewentualnie przed , lub w celu wskazania fazy ( jest ).σ0σ3i--i--1

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Nie wolno używać żadnych wbudowanych (lub zewnętrznych) funkcji związanych z matrycami Pauli.

To jest kod golfowy, wygrywa najkrótsza odpowiedź (w bajtach).

Przypadki testowe

1 => 1
13 => -i2
000 => 0
123 => i0
03022 => 3
02132230 => -i3
1320130100032 => i2
311220321030322113103 => -2
0223202330203313021301011023230323 => -i0
1323130203022111323321112122313213130330103202032222223 => -1
Martin Ender
źródło
3
Dodałem znacznik abstract-algebra, ponieważ w zasadzie wymaga uproszczenia słów w uogólnionej grupie czwartorzędowej .
Peter Taylor

Odpowiedzi:

3

Pyth, 47 bajtów

Wydaje mi się, że nadal można grać w golfa. Ale to znacznie przewyższa CJam.

p.U&-=T*q3l{[0bZ)^_1%-Zb3xbZmvdz@+c"i - -i")khT

Wypróbuj online: pakiet demonstracyjny lub testowy

Wyjaśnienie

Ustalenie wynikowego typu macierzy polega po prostu na umieszczeniu wszystkich liczb.

Podczas mnożenia 2 macierzy A*B, faza zmienia się, jeśli nie macierzą jest σ0i A != B.

                                                 implicit: T=10, z=input string
                            mvdz                 evaluate each char of the input 
 .U                                              reduce: b=first value, for Y in mvdz[1:]
    -=T                                            T -= ...
        q3l{[0bZ)                                     (3 == len(set([0,b,Z])))
       *         ^_1%-Zb3                             * (-1)^((Z-b)%3)
   &                                               and
                         xbY                       update b by (b xor Y)
                                 +c"i - -i")k    the list ["i", "-", "-i", ""]
                                @            hT  take the element at index T+1 (modulo wrapping)
p                                                print phase and matrix
Jakube
źródło
oczywiście mam 44, jeśli używam tego samego algorytmu, którym jest zasadniczo Sp300.
Optymalizator
9

Python 2, 108 89 87 86 bajtów

x=y=0
for m in map(int,raw_input()):x+=m*y and(m-y)%3*3/2;y^=m
print"--i"[~x%4::2]+`y`

(Podziękowania dla @grc i @xnor za pomoc)

Wyjaśnienie

Podzielmy współczynnik i macierz podstawową. Jeśli skupimy się tylko na macierzy podstawowej, otrzymamy tę tabliczkę mnożenia (np. 13Jest -i2, więc wstawiamy 2):

  0123

0 0123
1 1032
2 2301
3 3210

co po prostu dzieje się tak samo jak bitowe xor.

Teraz skupmy się na współczynnikach. Jeśli pozwolimy odpowiednio 0123oznaczać 1,i,-1,-i, otrzymamy:

  0123

0 0000
1 0031
2 0103
3 0310

W tym celu najpierw sprawdzamy, czy któraś z tych liczb wynosi 0 m*y, dbając o lewą kolumnę i górny wiersz. Dodanie (m-y)%3następnie daje:

  0123

0 0000
1 0021
2 0102
3 0210

co jest bliskie, tyle że 2zamiast tego mamy 3. Rozliczamy to poprzez wykonanie *3/2.

Do indeksowania zauważamy, że jeśli weźmiemy ciąg "--i"i wybieramy co drugi znak, zaczynając od indeksów 0123, otrzymujemy "-i","-","i","".

Sp3000
źródło
Ładne krojenie sznurka, zapomniałem o tym . Wierzę, że można zrobić 3-n%4tak ~n%4. Podejrzewam, że możesz wyrazić m*y and(m-y)%3*3/2krócej za pomocą magicznego sznurka, ale moja pierwsza próba była 877449216>>2*m+8*ytylko powiązana. Istnieje również dość algebraiczna formuła, która Y=m^ybrzmi (m-y)*(y-Y)*(Y-m)/2, ale jeśli tak, to długo.
xnor
@ xnor Och ~, fajnie - denerwujące mnie było denerwujące: / Jestem pewien, że m*y and(m-y)%3*3/2można je również skrócić, ale spędziłem całą noc i nigdzie nie dotarłem ... wrócę do tego, jeśli Mieć czas. Może fakt, że mam mod wolności 4, może pomóc.
Sp3000,
6

Siatkówka , 77 bajtów

Pomyślałem, że wykorzystam tę okazję, aby pochwalić się nową funkcją Retina: pętle wieloetapowe. Powinno to znacznie skrócić wiele zadań (zwłaszcza zastępowanie warunkowe).

ii
-
+`(.)\1|0

(.)-|(\d)(\d)
-$1$3$2
12
i3
23
i1
31
i2
)`(\d)i
i$1
^\D*$
$&0

Retina jest moim własnym językiem programowania opartym na wyrażeniach regularnych. Kod źródłowy można pogrupować w etapy: każdy etap składa się z dwóch wierszy, w których pierwszy zawiera wyrażenie regularne (i potencjalnie pewną konfigurację), a drugi wiersz to ciąg zastępujący. Etapy są następnie nakładane na STDIN w kolejności, a wynik końcowy jest drukowany na STDOUT.

Możesz użyć powyższego bezpośrednio jako pliku źródłowego za pomocą -sprzełącznika wiersza poleceń. Jednak nie liczę przełącznika, ponieważ możesz również po prostu umieścić każdą linię w osobnym pliku (wtedy tracisz 15 bajtów dla nowych linii, ale dodajesz +15 dla dodatkowych plików).

Wyjaśnienie

Nowością w tym rozwiązaniu jest )etap przedostatni. To zamyka wieloetapową pętlę. Brak dopasowania (, co oznacza, że ​​pętla domyślnie rozpoczyna się na pierwszym etapie. Dlatego pierwsze 7 etapów powtarza się, aż pełne przejście przez wszystkie 7 z nich przestanie zmieniać wynik. Te 7 etapów po prostu wykonuje różne transformacje, które stopniowo zmniejszają liczbę matryc w łańcuchu i łączą fazy. Po osiągnięciu ostatecznego wyniku żaden z siedmiu wzorów już się nie zgadza i pętla się kończy. Następnie dodajemy 0, jeśli w wyniku nie ma jeszcze cyfry (ponieważ powyższe etapy po prostu usuwają wszystkie tożsamości, w tym wynik).

Oto, co robią poszczególne etapy:

ii
-

Łączy wszystkie pary iw, -aby zmniejszyć znaki fazy.

+`(.)\1|0
<empty>

Teraz, jeśli pozostały dwa kolejne identyczne znaki, jest to jedna --lub dwie identyczne macierze. W obu przypadkach pomnożenie ich daje tożsamość. Ale nie potrzebujemy tożsamości, więc po prostu usuwamy je wszystkie, a także tożsamości jawne 0. Ten etap powtarza się sam z, +aż wynik przestanie się zmieniać. Zapewnia to 123321całkowite rozwiązanie takich problemów , że w następnym kroku można założyć, że wszystkie pary cyfr są różne.

(.)-|(\d)(\d)
-$1$3$2

To właściwie dwie osobne transformacje w jednym (dla golfitude). Zauważ, że jeśli pierwsza alternatywa pasuje $2i $3są puste, a jeśli druga pasuje, $1jest pusta. Można to rozłożyć na następujące dwa kroki:

(\d)(\d)
-$2$1

To po prostu zamienia wszystkie pary cyfr i dodaje znak minus. Ponieważ usunęliśmy wszystkie 0s i wszystkie identyczne pary, to będzie tylko dopasować 12, 23, 31, 21, 32, 13. Ten krok może wydawać się dziwny, ale pozwala mi później sprawdzić tylko połowę tych przypadków, ponieważ te, których nie mogę przetworzyć, zostaną zamienione tutaj w następnej iteracji.

Drugą częścią powyższego etapu było:

(.)-
-$1

Powoduje to stopniowe przesuwanie -znaków do końca w lewo (jedna pozycja na iterację). Robię to tak, aby ostatecznie wszyscy byli obok siebie i zostali rozwiązani na wcześniejszym etapie.

12
i3
23
i1
31
i2

Te trzy etapy rozwiązują teraz po prostu trzy pary produktów. Jak powiedziałem powyżej, będzie to obejmować tylko połowę odpowiednich przypadków, ale druga połowa zostanie załatwiona w następnej iteracji, po tym, jak poprzedni krok zamienił wszystkie pary.

)`(\d)i
i$1

To ostatni etap pętli. Jest podobny do tego, który przesuwa -się w lewo, z wyjątkiem i. Główną różnicą jest to, że zamienia się itylko cyframi. Gdybym używał, (.)ito w przypadkach, w których dostaję jeden -ilub i-dwa, zostałyby zamienione na czas nieokreślony, a program nie zakończyłby się. To zamienia je tylko na prawo od -znaków. Jest to wystarczające - tak długo, jak wszyscy -i ipojawiają się razem w pewnym momencie, mogą zostać rozwiązane poprawnie.

^\D*$
$&0

Ostatni krok (poza pętlą). Pamiętaj, że zawsze usuwaliśmy wszystkie tożsamości, więc jeśli wynikiem jest tożsamość (razy faza), to nie będziemy już mieć wymaganej cyfry na wyjściu, więc dodajemy ją z powrotem.

Na przykład tutaj są wszystkie pośrednie formy 0223202330203313021301011023230323(pomijanie etapów, które nie powodują żadnych zmian):

0223202330203313021301011023230323

321321312        # Remove identities
-23-31-12-132    # Swap all pairs
-23-31-i3-132    # Resolve 12
-i1-31-i3-132    # Resolve 23
-i1-i2-i3-132    # Resolve 31
-i-1i-2i-3-312   # Move - to the left and swap pairs
-i-1i-2i-3-3i3   # Resolve 12
-i-i1-i2-3-i33   # Move i to the left
-i-i1-i2-3-i     # Remove identities
--ii-1i-2-3i     # Move - to the left
--ii-i1-2-i3     # Move i to the left
----i1-2-i3      # Resolve ii
i1-2-i3          # Remove identities
i-1-2i3          # Move - to the left
i-1-i23          # Move i to the left
-i-1i-32         # Move - to the left and swap pairs
-i-i1-32         # Move i to the left
--ii-1-23        # Move - to the left and swap pairs
--ii-1-i1        # Resolve 23
----1-i1         # Resolve ii
1-i1             # Remove identities
-1i1             # Move - to the left
-i11             # Move i to the left
-i               # Remove identities. Now the loop can't change this any longer.
-i0              # Fix the result by adding in the 0.
Martin Ender
źródło