Klasyfikacja bram dwustronnych

Krata Posta , opisana przez Emila Posta w 1941 r., Jest w zasadzie kompletnym diagramem włączenia zestawów funkcji boolowskich, które są zamknięte w składzie: na przykład funkcje monotoniczne, funkcje liniowe nad GF (2) i wszystkie funkcje. (Post nie zakładał, że stałe 0 i 1 są dostępne za darmo, co znacznie skomplikowało jego sieć).

Moje pytanie brzmi: czy kiedykolwiek opublikowano coś analogicznego dla klasycznych bram dwustronnych , takich jak bramy Toffoli i Fredkin. To znaczy, które klasy odwracalnych przekształceń na {0,1} ⁿ mogą być generowane przez pewną kolekcję odwracalnych bramek? Oto zasady: masz prawo nieograniczoną liczbę ancilla bitów, niektóre ustawioną na 0 i inni ustawiony na 1, tak długo jak powrócił wszystkie bity ancilla są do swoich pierwotnych ustawień po swojej transformacji {0,1} ⁿ jest skończone. Również SWAP 2 bitów (tj. Ponowne oznaczenie ich indeksów) jest zawsze dostępny za darmo. Zgodnie z tymi zasadami mój uczeń Luke Schaeffer i ja byliśmy w stanie zidentyfikować następujące dziesięć zestawów transformacji:

Pusty zestaw
Zestaw wygenerowany przez bramkę NOT
Zestaw wygenerowany przez NOTNOT (tj. Bramki NOT zastosowane do dowolnych 2 bitów)
Zestaw wygenerowany przez CNOT (tj. Bramka Controlled-NOT)
Zestaw wygenerowany przez CNOTNOT (tj. Przerzuć 2-ty i 3-bitowy bit, jeśli pierwszy bit to 1)
Zestaw wygenerowany przez CNOTNOT i NOT
Zestaw wygenerowany przez bramę Fredkin (tj. Controlled-SWAP)
Zestaw wygenerowany przez Fredkina i CNOTNOT
Zestaw wygenerowany przez Fredkina, CNOTNOT i NOT
Zbiór wszystkich przekształceń

Chcemy zidentyfikować pozostałe rodziny, a następnie udowodnić, że klasyfikacja jest kompletna --- ale zanim spędzimy nad tym dużo czasu, chcielibyśmy wiedzieć, czy ktoś już to zrobił.

circuit-families

— Scott Aaronson
źródło

Brakuje NOTCSWAP i (CSWAP, NOTCSWAP), gdzie NOTCSWAP jest jak kontrolowana zamiana, ale zamienia argumenty x, y, gdy argument c wynosi 0 (zamiast zamiany, gdy c wynosi 1 jak w CSWAP)? Oba te elementy są potrzebne, aby uzyskać wszystkie permutacje zachowujące ciężar Hamminga: CSWAP dopuszcza tylko wektory o wadze Hamminga ≥2, natomiast NOTCSWAP dopuszcza tylko wektory o wadze Hamminga ≤n-2.

— David Eppstein,

Również (zabrakło miejsca w poprzednim komentarzu), wymagając, aby większa liczba bitów kontrolnych była równa zero lub zero, możesz uzyskać jeszcze bardziej ograniczone podzbiory permutacji zachowujących ciężar Hamminga, dopuszczając jedynie wektory o wadze Hamminga co najmniej lub co najwyżej arbitralne granica. To daje niezliczoną ilość klas transformacji.

— David Eppstein,

Dzięki, David - ale założyłem, że 0 i 1 ancillas były dostępne za darmo, właśnie w celu wykluczenia takich „przewrotności”. Czy to nie robi?

— Scott Aaronson,

Niech będzie klasą wszystkich permutacji zachowujących Hamminga . Wtedy spełnia twoje wymagania, a iff : nieuwzględnienia gdzie indziej są obserwowane przez funkcję ary st , i dla . W szczególności wszystkie te nieskończenie wiele klas są odrębne.

C_{n}

$C_n$

n

$n$

C_{n}

$C_n$

C_{n} \subseteq C_{m}

$C_n\subseteq C_m$

m | n

$m|n$

C_{n}

$C_n$

n

$n$

f_{n}

$f_n$

f_{n} (0^{n}) = 1^{n}

$f_n(0^n)=1^n$

f_{n} (1^{n}) = 0^{n}

$f_n(1^n)=0^n$

f (x) = x

$f(x)=x$

x \neq 0^{n}, 1^{n}

$x\ne0^n,1^n$

— Emil Jeřábek wspiera Monikę

Zobacz artykuł eccc.hpi-web.de/report/2015/066, w którym te pomysły zostały dopracowane i który również odwołuje się do odpowiedzi Emila poniżej.

— András Salamon

$\def\N{\mathbb N}\DeclareMathOperator\sym{Sym}\def\cC{\mathcal C}\def\cD{\mathcal D}\def\cP{\mathcal P}\def\cI{\mathcal W}\def\cMI{\mathcal{MW}}\DeclareMathOperator\pol{Pol}\DeclareMathOperator\inv{Inv}\DeclareMathOperator\minv{MInv}\let\pres\parallel$ To jest prezentacja połowy dualności dla odwracalnych transformacji, analogicznie do standardowej dualności klon-koklon (jak tutaj ). Nie odpowiada na pytanie, ale pokazuje, że wszystkie zamknięte klasy takich funkcji są określone przez zachowanie właściwości określonej formy.

W przeciwieństwie do standardowego przypadku, główną komplikacją jest to, że permutacje mogą się liczyć (zachowują liczność), dlatego ich niezmienniki muszą wymagać nieco arytmetyki, aby to uwzględnić.

Zacznę od pewnej niepewnej terminologii. Fix skończonego zbioru baza . (W klasycznym przypadku Scott pyta o . Części dyskusji działają również dla nieskończonego , ale nie dla głównej charakterystyki.) $A$ $A=\{0,1\}$ $A$

Zestaw permutacji (lub: odwracalne przemiany) jest podzbiorem , w którym oznacza grupę o permutacje . Klon permutacji jest zbiorem permutacji takie, że $\cC\subseteq\cP:=\bigcup_{n\in\N}\sym(A^n)$ $\sym(X)$ $X$ $\cC$

Każdy jest zamknięty w trakcie tworzenia. $\cC\cap\sym(A^n)$

Dla każdego permutacja zdefiniowana przez jest w . $\pi\in\sym(\{1,\dots,n\})$ $\tilde\pi\in\sym(A^n)$ $\tilde\pi(x_1,\dots,x_n)=(x_{\pi(1)},\dots,x_{\pi(n)})$ $\cC$

Jeśli i , permutacja definicją jest . $f\in\cC\cap\sym(A^n)$ $g\in\cC\cap\sym(A^m)$ $f\times g\in\sym(A^{n+m})$ $(f\times g)(x,y)=(f(x),g(y))$ $\mathcal C$

Ponieważ jest skończone, 1 oznacza, że jest podgrupą . OP wymaga tylko 2 dla transpozycji , ale wersja tutaj jest wyraźnie równoważna. Warunek 3 jest równoważny temu, co nazwałem wprowadzeniem zmiennych zastępczych w powyższych komentarzach. $A$ $\cC\cap\sym(A^n)$ $\sym(A^n)$ $\pi$

Klon mistrz jest klonem permutacji z naddatkiem ancillas:

Niech , i będą takie, że dla wszystkich . Zatem oznacza . $f\in\sym(A^{n+m})$ $g\in\sym(A^n)$ $a\in A^m$ $f(x,a)=(g(x),a)$ $x\in A^n$ $f\in\cC$ $g\in\cC$

Naszym celem jest scharakteryzowanie klonów permutacji i klonów głównych przez niektóre niezmienniki. Pozwól mi najpierw zmotywować to drugie przez kilka przykładów na : $A=\{0,1\}$

Główny klon permutacji chroniący Hamminga (generowany przez bramę Fredkina). Jeśli oznacza włączenie do , permutacje te charakteryzują się właściwością gdzie , a ja piszę . $w$ $\{0,1\}$ $\N$
$y = f (x) ⟹ \sum_{i = 1}^{n} w (x_{i}) = \sum_{i = 1}^{n} w (y_{i}),$ $y=f(x)\implies\sum_{i=1}^nw(x_i)=\sum_{i=1}^nw(y_i),$ $f\in\sym(A^n)$ $x=(x_1,\dots,x_n)$
Główny klon permutacji zachowujący moduł Hamminga naprawił moduł , wspomniany w komentarzach. Charakteryzuje się tym samym wzorem jak powyżej, jeśli interpretujemy jako funkcję od do cyklicznej grupy i obliczamy tam sumę. $m$ $w$ $\{0,1\}$ $C(m)$
Główny klon permutacji afinicznych , , (wygenerowany przez CNOT). Łatwo sprawdza się (lub z przypadku Post), że funkcja pojedynczego wyjścia jest afiniczna iff zachowuje relację . Zatem jeśli zdefiniujemy przez w klonie wtw więc mamy do czynienia z sumami w monoidzie $f(x)=Mx\oplus b$ $M\in\mathrm{GL}(n,\mathbb F_2)$ $b\in\mathbb F_2^n$ $\mathbb F_2^n\to\mathbb F_2$ $x^1\oplus x^2\oplus x^3\oplus x^4=0$ $w\colon\{0,1\}\to\{0,1\}$
$w (x^{1}, x^{2}, x^{3}, x^{4}) = x^{1} \oplus x^{2} \oplus x^{3} \oplus x^{4},$ $w(x^1,x^2,x^3,x^4)=x^1\oplus x^2\oplus x^3\oplus x^4,$ $f\in\sym(A^n)$ $y^{1} = f (x^{1}) \land \dots \land y^{4} = f (x^{4}) ⟹ {max}_{i = 1}^{n} w (x_{i}^{1}, \dots, x_{i}^{4}) = {max}_{i = 1}^{n} w (y_{i}^{1}, \dots, y_{i}^{4}),$ $y^1=f(x^1)\land\dots\land y^4=f(x^4)\implies\max_{i=1}^nw(x^1_i,\dots,x^4_i)=\max_{i=1}^nw(y^1_i,\dots,y^4_i),$ $(\{0,1\},0,\max)$ .

Ogólnie rzecz biorąc, funkcja wagi jest mapowaniem , gdzie , a jest monoidą przemienną. Funkcja wagi Master jest, że odwzorowuje wszystkie ukośne -tuples , do odwracalnych elementów . Niech oznacza klasę wszystkich funkcji wagi, a główne funkcje wagi. $w\colon A^k\to M$ $k\in\N$ $M$ $k$ $(a,\dots,a)$ $a\in A$ $M$ $\cI$ $\cMI$

Jeśli , a jest funkcją wagi, mówimy, że jest niezmiennikiem lub (bezmyślnie zapożyczając terminologię), że jest polimorfizmem i napisz , jeśli następujący warunek obowiązuje dla wszystkich : $f\in\sym(A^n)$ $w\colon A^k\to M$ $w$ $f$ $f$ $w$ $f\pres w$ $(x_i^j)_{i=1..n}^{j=1..k},(y_i^j)_{i=1..n}^{j=1..k}\in A^{n\times k}$

Jeśli , to $y^1=f(x^1),\dots,y^k=f(x^k)$
$\sum_{i = 1}^{n} w (x_{i}) = \sum_{i = 1}^{n} w (y_{i}) .$ $\sum_{i=1}^nw(x_i)=\sum_{i=1}^nw(y_i).$

Tutaj , i podobnie dla . Innymi słowy, jeśli (a raczej jego równoległe rozszerzenie do ) zachowuje sumę w swoich argumentów. $x^j=(x^j_1,\dots,x^j_n)$ $x_i=(x_i^1,\dots,x_i^k)$ $y$ $f\pres w$ $f$ $(A^k)^n$ $w$

Relacja między a (lub ) indukuje połączenie Galois między zestawami permutacji , a klasami funkcji wagowych , w zwykły sposób: a zatem podwójny izomorfizm odpowiednio między kompletnymi sieciami zamkniętych zbiorów permutacji i zamkniętymi klasami (wzorcowych) funkcji wagowych. Aby zobaczyć, że jesteśmy na dobrej drodze, obserwujemy, że zamknięte zestawy permutacji są rzeczywiście klonami: $\pres$ $\cP$ $\cI$ $\cMI$ $\cC\subseteq\cP$ $\cD\subseteq\cI$

\begin{aligned} Pol (D) & = {f \in P : \forall w \in D (f ∥ w)}, \\ {Inv}^{*} (C) & = {w \in W : \forall f \in C (f ∥ w)}, \\ {MInv}^{*} (C) & = M W \cap {Inv}^{*} (C), \end{aligned}

$\begin{align*} \pol(\cD)&=\{f\in\cP:\forall w\in\cD\,(f\pres w)\},\\ \inv^*(\cC)&=\{w\in\cI:\forall f\in\cC\,(f\pres w)\},\\ \minv^*(\cC)&=\cMI\cap\inv^*(\cC), \end{align*}$

Lemma: Jeśli , to jest klonem permutacji. Jeśli , to jest klonem głównym. $\cD\subseteq\cI$ $\pol(\cD)$ $\cD\subseteq\cMI$ $\pol(\cD)$

Dowód: pierwsze stwierdzenie jest mniej lub bardziej oczywiste. Po drugie, niech , będzie jak w warunku 4, tak aby , i niech będą jak w definicji . Wstaw , , a . Zatem implikuje Jednak są odwracalne w ponieważ jest funkcją wagi wzorcowej, stąd $w\in\cD$ $f,g,a$ $f\pres w$ $(x_i^j),(y_i^j)$ $g\pres w$ $\bar x^j=(x^j,a)$ $\bar y^j=(y^j,a)=f(\bar x^j)$ $u_i=w(a_i,\dots,a_i)$ $f\pres w$

\sum_{i = 1}^{n} w (x_{i}) + \sum_{i = 1}^{m} u_{i} = \sum_{i = 1}^{n + m} w ({\bar{x}}_{i}) = \sum_{i = 1}^{n + m} w ({\bar{y}}_{i}) = \sum_{i = 1}^{n} w (y_{i}) + \sum_{i = 1}^{m} u_{i} .

$\sum_{i=1}^nw(x_i)+\sum_{i=1}^mu_i=\sum_{i=1}^{n+m}w(\bar x_i)=\sum_{i=1}^{n+m}w(\bar y_i)=\sum_{i=1}^nw(y_i)+\sum_{i=1}^mu_i.$

u_{i}

$u_i$

M

$M$

w

$w$

\begin{matrix} QED & \sum_{i = 1}^{n} w (x_{i}) = \sum_{i = 1}^{n} w (y_{i}) . \end{matrix}

$\sum_{i=1}^nw(x_i)=\sum_{i=1}^nw(y_i).\tag*{QED}$

Zanim przejdziemy dalej, musimy rozwiązać jeden problem: monoidy mogą być ogromne , dlatego niezmienniki tej formy można słusznie podejrzewać, że są bezużytecznymi abstrakcyjnymi bzdurami.

Po pierwsze, biorąc pod uwagę funkcję wagi , możemy założyć, że jest generowane przez (i przez odwrotne dodawanie obrazów elementów ukośnych w przypadku głównym), podobnie jak inne elementy nie wprowadzić obraz. W szczególności jest generowane w sposób ostateczny . Po drugie, na podstawie ogólnych wyników z algebry uniwersalnej możemy napisać jako iloczyn pośredni gdzie każdy jest pośrednio nieredukowalny, a jest ilorazem poprzez tą projekcję produktu $w\colon A^k\to M$ $M$ $w(A^k)$ $M$ $M$ $M$

M \subseteq \prod_{i \in I} M_{i},

$M\subseteq\prod_{i\in I}M_i,$

M_{i}

$M_i$

M_{i}

$M_i$

M

$M$

i

$i$

π_{i}

$\pi_i$ ; w szczególności wciąż jest skończoną generacją przemiennej monoidu. W wyniku Mal'ceva, fg pośrednio nieredukowalne komutatywne monoidy (lub półgrupy) są w rzeczywistości skończone . Mapowanie jest znowu funkcją wagi, master jeśli było i łatwo jest zauważyć, że Zatem możemy bez utraty ogólności ograniczyć uwagę na funkcjach wagi , gdzie jest skończone i pośrednio nieredukowalne. Niech będzie klasą takich funkcji wagowych, i

w_{i} = π_{i} \circ w : A^{k} \to M_{i}

$w_i=\pi_i\circ w\colon A^k\to M_i$

w

$w$

Pol (w) = ⋂_{i \in I} Pol (w_{i}) .

$\pol(w)=\bigcap_{i\in I}\pol(w_i).$

w : A^{k} \to M

$w\colon A^k\to M$

M

$M$

F W

$\mathcal{FW}$

\begin{aligned} Inv (C) & = F W \cap {Inv}^{*} (C), \\ MInv (C) & = F W \cap {MInv}^{*} (C) . \end{aligned}

$\begin{align*} \inv(\cC)&=\mathcal{FW}\cap\inv^*(\cC),\\ \minv(\cC)&=\mathcal{FW}\cap\minv^*(\cC). \end{align*}$ Przykładami skończonych pośrednio nieredukowalnych komutatywnych monoidów są grupy cykliczne i skrócone monoidy addycyjne . Ogólny przypadek jest bardziej skomplikowany, niemniej jednak wiele można powiedzieć o ich strukturze: każdy można napisać w pewien sposób jako rozłączny związek i skończoną grupę zerową o pewnych właściwościach. Zobacz Grillet po szczegóły.

C (p^{d})

$C(p^d)$

({0, \dots, d}, 0, min {d, x + y})

$(\{0,\dots,d\},0,\min\{d,x+y\})$

C (p^{d})

$C(p^d)$

Teraz jesteśmy gotowi na główny punkt tego postu:

Twierdzenie: Zamknięte zestawy permutacji w połączeniu Galois ze skończonymi, pośrednio nieredukowalnymi (wzorcowymi) funkcjami wagowymi są dokładnie klonami permutacyjnymi (klony wzorcowe, odpowiednio).

Oznacza to, że jeśli , klon permutacji wygenerowany przez to , a klon główny wygenerowany przez to . $\cC\subseteq\cP$ $\cC$ $\pol(\inv(\cC))$ $\cC$ $\pol(\minv(\cC))$

Dowód: W świetle powyższej dyskusji wystarczy wykazać, że jeśli jest klonem permutacji, a , to istnieje niezmienny o , tak że i można przyjąć celu być funkcją masy Master gdyby jest klonem głównego. $\cC$ $f\in\sym(A^n)\smallsetminus\cC$ $w\colon A^k\to M$ $\cC$ $f\nparallel w$ $w$ $\cC$

Umieść i niech będzie wolną monoidą wygenerowaną przez (tj. Skończone słowa nad alfabetem ). Relację na definiujemy przez (Słowa o nierównej długości nigdy nie są powiązane przez .) Ponieważ każde to grupa jest stosunek równoważności (w rzeczywistości, jego ograniczenie słów o długości jest tylko stosunek równoważności orbity działającego w oczywisty sposób $k=|A|^n$ $F$ $A^k$ $A^k$ $\sim$ $F$

x_{1} \dots x_{m} \sim y_{1} \dots y_{m} ⟺ \exists g \in C \cap Sym (A^{m}) \forall j = 1, \dots, k g (x_{1}^{j}, \dots, x_{m}^{j}) = (y_{1}^{j}, \dots, y_{m}^{j}) .

$x_1\cdots x_m\sim y_1\cdots y_m\iff\hbox{$\exists g\in\cC\cap\sym(A^m)\,\forall j=1,\dots,k\,g(x^j_1,\dots,x^j_m)=(y^j_1,\dots,y^j_m).$}$

\sim

$\sim$

C \cap Sym (A^{m})

$\cC\cap\sym(A^m)$

\sim

$\sim$

m

$m$

C \cap Sym (A^{m})

$\cC\cap\sym(A^m)$

A^{m k}

$A^{mk}$ ). Co więcej, jest monoidem: jeśli i świadkami, że i odpowiednio, a następnie świadkowie .

\sim

$\sim$

g \in C \cap Sym (A^{m})

$g\in\cC\cap\sym(A^m)$

g^{'} \in Sym (A^{m^{'}})

$g'\in\sym(A^{m'})$

x_{1} \dots x_{m} \sim y_{1} \dots y_{m}

$x_1\cdots x_m\sim y_1\cdots y_m$

x_{1}^{'} \dots x_{m^{'}}^{'} \sim y_{1}^{'} \dots y_{m^{'}}^{'}

$x'_1\cdots x'_{m'}\sim y'_1\cdots y'_{m'}$

g \times g^{'} \in C \cap Sym (A^{m + m^{'}})

$g\times g'\in\cC\cap\sym(A^{m+m'})$

x_{1} \dots x_{m} x_{1}^{'} \dots x_{m^{'}}^{'} \sim y_{1} \dots y_{m} y_{1}^{'} \dots y_{m^{'}}^{'}

$x_1\cdots x_mx'_1\cdots x'_{m'}\sim y_1\cdots y_my'_1\cdots y'_{m'}$

W ten sposób możemy utworzyć iloraz monoidu . Zamiana zamiany świadczy o tym, że dla każdego ; to znaczy, generatory dojeżdżają do pracy, stąd jest przemienne. Zdefiniuj funkcję wagi jako naturalne włączenie do skomponowane z mapą ilorazową. $M=F/{\sim}$ $xy\sim yx$ $x,y\in A^k$ $M$ $M$ $w\colon A^k\to M$ $A^k$ $F$

Łatwo zauważyć, że : rzeczywiście, jeśli , a , a następnie według definicji (używając zapisu jak w definicji ). Z drugiej strony załóżmy, że . Niech będą wyliczeniem , , i niech dla będzie ponownie jak w definicji . Następnie $\cC\subseteq\pol(w)$ $g\in\cC\cap\sym(A^m)$ $y^1=f(x^1),\dots,y^k=f(x^k)$

\sum_{i = 1}^{m} w (x_{i}) = x_{1} \dots x_{m} / \sim = y_{1} \dots y_{m} / \sim = \sum_{i = 1}^{m} w (y_{i})

$\sum_{i=1}^mw(x_i)=x_1\cdots x_m/{\sim}=y_1\cdots y_m/{\sim}=\sum_{i=1}^mw(y_i)$

\sim

$\sim$

∥

$\pres$

f ∥ w

$f\pres w$

{a^{j} : j = 1, \dots, k}

$\{a^j:j=1,\dots,k\}$

A^{n}

$A^n$

b^{j} = f (a^{j})

$b^j=f(a^j)$

a_{i}, b_{i} \in A^{k}

$a_i,b_i\in A^k$

i = 1, \dots, n

$i=1,\dots,n$

∥

$\pres$

a_{1} \dots a_{n} / \sim = \sum_{i = 1}^{n} w (a_{i}) = \sum_{i = 1}^{n} w (b_{i}) = b_{1} \dots b_{n} / \sim,

$a_1\cdots a_n/{\sim}=\sum_{i=1}^nw(a_i)=\sum_{i=1}^nw(b_i)=b_1\cdots b_n/{\sim},$ stąd z definicji z istnieje tak że dla każdego . Ponieważ jednak wydech , oznacza to , tj. , sprzeczność. To uzupełnia dowód na klony permutacji.

\sim

$\sim$

g \in C \cap Sym (A^{n})

$g\in\cC\cap\sym(A^n)$

g (a^{j}) = b^{j} = f (a^{j})

$g(a^j)=b^j=f(a^j)$

j

$j$

a^{j}

$a^j$

A^{n}

$A^n$

g = f

$g=f$

f \in C

$f\in\cC$

Nawet jeśli jest nadrzędnym klonem, nie musi być funkcją nadrzędnej wagi, w rzeczywistości elementy ukośne niekoniecznie mają charakter kasujący w , dlatego musimy to naprawić. Dla każdego , niech i zdefiniuj nową relację równoważności na przez Korzystając z faktu, że elementy dojeżdżają modulo , łatwo jest pokazać, że to znowu przystaje, dlatego możemy uformować monoid $\cC$ $w$ $M$ $c\in A$ $c^*=(c,\dots,c)\in A^k$ $\approx$ $F$

x_{1} \dots x_{m} \approx y_{1} \dots y_{m} ⟺ \exists c_{1}, \dots, c_{r} \in A x_{1} \dots x_{m} c_{1}^{*} \dots c_{r}^{*} \sim y_{1} \dots y_{m} c_{1}^{*} \dots c_{r}^{*} .

$x_1\cdots x_m\approx y_1\cdots y_m\iff\exists c_1,\dots,c_r\in A\,x_1\cdots x_mc_1^*\cdots c_r^*\sim y_1\cdots y_mc_1^*\cdots c_r^*.$

A^{k}

$A^k$

\sim

$\sim$

\approx

$\approx$

M^{'} = F / \approx

$M'=F/{\approx}$ i funkcja wagi . Ponieważ rozciąga , jest przemienne, a iloraz ; w szczególności . Z drugiej strony, jeśli , to ten sam argument jak powyżej wraz z definicją dałby i taki, że dla wszystkich , a więc as jest mistrzem klon, sprzeczność.

w^{'} : A^{k} \to M^{'}

$w'\colon A^k\to M'$

\approx

$\approx$

\sim

$\sim$

M^{'}

$M'$

M

$M$

C \subseteq Pol (w^{'})

$\cC\subseteq\pol(w')$

f ∥ w^{'}

$f\pres w'$

\approx

$\approx$

g \in C \cap Sym (A^{n + r})

$g\in\cC\cap\sym(A^{n+r})$

c_{1}, \dots, c_{r} \in A

$c_1,\dots,c_r\in A$

g (x, c_{1}, \dots, c_{r}) = (f (x), c_{1}, \dots, c_{r})

$g(x,c_1,\dots,c_r)=(f(x),c_1,\dots,c_r)$

x \in A^{n}

$x\in A^n$

f \in C

$f\in\cC$

C

$\cC$

Definicja zapewnia, że dla wszystkich i . Wynika z tego, że elementy mają charakter anulujący w . Łatwo jest znanym faktem, że każdy monoid komutacyjny może być osadzony w innym, w którym wszystkie elementy anulujące stają się odwracalne. Kompozycja takiego osadzenia za pomocą jest wówczas nadrzędną funkcją wagową , a , stąd . CO BYŁO DO OKAZANIA $\approx$

x c^{*} \approx y c^{*} ⟹ x \approx y

$xc^*\approx yc^*\implies x\approx y$

x, y \in F

$x,y\in F$

c \in A

$c\in A$

c^{*} / \approx = w^{'} (c^{*})

$c^*/{\approx}=w'(c^*)$

M^{'}

$M'$

w^{'}

$w'$

w^{″}

$w''$

Pol (w^{'}) = Pol (w^{″})

$\pol(w')=\pol(w'')$

w^{″} \in {MInv}^{*} (C) ∖ {MInv}^{*} (f)

$w''\in\minv^*(\cC)\setminus\minv^*(f)$

EDYCJA: Uogólnienie powyższej dualności klon-koklon jest teraz zapisane w

[1] E. Jeřábek, połączenie Galois dla operacji wielokrotnego wyjścia , preprint, 2016, arXiv: 1612.04353 [mat.LO] .

— Emil Jeřábek wspiera Monikę
źródło

Dziękuję bardzo za wysiłek, jaki musiałeś podjąć, aby to napisać! Przetrawienie zajmie mi trochę czasu, ponieważ język klonów i algebry uniwersalnej jest dla mnie dość abstrakcyjny (w rzeczy samej, to było przeszkodą, gdy próbowałem czytać tę literaturę w przeszłości). Ale kiedy konkretnie opracowujemy klony, warto wiedzieć, że wszystkie będą charakteryzować się niezmiennikami, tak jak w rzeczywistości są to wszystkie znane przykłady. (Nawiasem mówiąc, aby zobaczyć, powiedzmy, Fredkin + NOT charakteryzujący się niezmiennikiem, myślę, że patrzymy na pary danych wejściowych i mówimy, że każda transformacja zachowuje sumę ich parzystości?)

— Scott Aaronson

Tymczasem mam postępy, aby zdać relację z konkretnego pytania. Udało mi się sklasyfikować wszystkie punkty w kratce nad bramą Fredkina: jedynymi możliwościami są transformacje, które zachowują mod k Hamminga dla dowolnego k, transformacje, które zachowują lub odwracają Hamminga mod 2 (generowane przez Fredkina + NOT) i wszystkie transformacje. Mogę też scharakteryzować wszystkie punkty w siatce powyżej CNOTNOT: są to tylko te, które wymieniłem w OP (CNOTNOT + NOT, CNOT, Fredkin + NOTNOT, Fredkin + NOT, wszystko).

— Scott Aaronson

Tak, dla Fredkina + NIE możemy przyjąć , . Dzięki za aktualizację, to brzmi bardzo dobrze.

M = C (2)

$M=C(2)$

w (x, y) = x \oplus y

$w(x,y)=x\oplus y$

— Emil Jeřábek wspiera Monikę

Istnieje oczywiście nadzieja, że niezmienniki są w praktyce znacznie mniejsze niż to, co wypada z dowodów. (W przypadku Post uważam, że najgorsze, co może się zdarzyć, to ). Połączenie Galois nie pomaga bezpośrednio w konkretnej klasyfikacji, jest raczej narzędziem metodologicznym. Po pierwsze, łatwiej jest znaleźć wcześniej niezidentyfikowane klasy, jeśli wiadomo, jakiego rodzaju właściwości szukać. Po drugie, typowy krok w dowodzie klasyfikacji Posta wygląda następująco. Dotarliśmy do klasy gdzieś pośrodku sieci i chcemy opisać klasy powyżej. ...

k \leq n + 1

$k\le n+1$

C

$C$

— Emil Jeřábek wspiera Monikę

... jest określony przez jego niezmiennicze relacje . Zatem każde prawidłowe rozszerzenie musi zawierać które nie zachowuje części , i zwykle można następnie manipulować poprzez kompozycję itp. W określoną funkcję w niewielkiej liczbie zmiennych. W ten sposób otrzymujemy listę tak że każda klasa ściśle powyżej zawiera klasę wygenerowaną przez dla niektórych , i można przejść do części sieci powyżej . Nie wymaga to ogólnej korespondencji, ale znajomość niezmienników poszczególnych klas, jakie napotyka.

C

$C$

R_{1}, \dots, R_{k}

$R_1,\dots,R_k$

C

$C$

f

$f$

R_{i}

$R_i$

f

$f$

f_{1}, \dots, f_{c}

$f_1,\dots,f_c$

C

$C$

C \cup {f_{i}}

$C\cup\{f_i\}$

i

$i$

— Emil Jeřábek wspiera Monikę