Pojęcie monotonicznych obwodów kwantowych

W złożoności obliczeniowej istnieje istotne rozróżnienie między obliczeniami monotonicznymi i ogólnymi, a słynne twierdzenie Razborova stwierdza, że ​​3-SAT, a nawet DOPASOWANIE nie są wielomianowe w monotonicznym modelu obwodów boolowskich.

Moje pytanie jest proste: czy istnieje analog kwantowy dla obwodów monotonicznych (lub więcej niż jednego)? Czy istnieje kwantowe twierdzenie Razborowa?

Naprawdę zadajesz dwa różne pytania i masz nadzieję, że istnieje jedna odpowiedź, która odpowiada na oba: (1) Jakie są naturalne pojęcia obwodów monotonicznych kwantów? (2) Jak wyglądałby wynik kwantowy w stylu Razborova oparty na sieci?

Nie jest oczywiste, jak osiągnąć oba jednocześnie, więc opiszę, co wydaje mi się rozsądnym pojęciem kwantowych obwodów monotonicznych (bez wskazania, czy istnieje odpowiedni wynik Razborowa), i zupełnie innym pojęciem jak wyglądałaby „naturalna” kwantowa hipoteza Razborowa (bez wskazania, czy to prawda).

Czego chcemy od kwantowego

Jak zauważam w komentarzach, myślę, że nie trzeba próbować wyciskać pojęcia obwodów monotonicznych do formy jednolitości. Bez względu na to, czy ewolucja z czasem nie musi zachowywać standardowej podstawy, czy fakt, że istnieje wiele podstaw pomiaru, w których wyniki mogą być uwikłane, uważam, że warunkiem sine qua non obliczeń kwantowych jest fakt, że podstawa standardowa nie jest jedyną podstawą. Nawet wśród stanów produktu jest on w niektórych implementacjach definiowany jedynie przez wybór układu odniesienia.

Musimy rozważyć rzeczy w taki sposób, aby usunąć standardową podstawę z jej tradycyjnego uprzywilejowanego miejsca - lub, w tym przypadku, w miarę możliwości, zachowując sensowną koncepcję monotoniczności.

Prosty model kwantowych obwodów monotonicznych

Rozważmy model obwodu, który jest ukryty w komentarzu Tsuyoshi Ito o „monotonicznych kanałach kwantowych” (i który jest właściwie tym, co należy zrobić, jeśli chce się pojęcia „obwodu”, który nie ogranicza się do ewolucji jednostkowej).

$\mathbf H$$\mathbb C^2$$\mathsf G: \mathbf H_a \otimes \mathbf H_b \to \mathbf H_c$$a,b$$c$$|0\rangle\!\langle 0|$$|1\rangle\!\langle 1|$$\langle 1 | \,\mathop{\mathrm{Tr}_a}\bigl(\rho_{ab}\bigr) |1\rangle$$\langle 1 | \,\mathop{\mathrm{Tr}_b}\bigl(\rho_{ab}\bigr) |1\rangle$$\langle 1 | \mathsf G(\rho_{ab}) | 1 \rangle$$\mathsf G$

1. $\{ |00\rangle, |\mu\rangle, |\nu\rangle, |11\rangle \}$$|\mu\rangle,|\nu\rangle$

2. $\rho \in \{ \rho_{00}, \rho_\mu, \rho_\nu, \rho_{11} \}$$\langle 1 | \rho_{00} | 1 \rangle \leqslant \langle 1 | \rho_\lambda | 1 \rangle \leqslant \langle 1 | \rho_{11} | 1 \rangle$$\lambda \in \{ \mu, \nu \}$

Obwody są po prostu ich kompozycjami w rozsądny sposób. Możemy także zezwolić na rozdysponowanie, w postaci obwodów, które jednostkowo osadzają i ; powinniśmy przynajmniej zezwolić na te mapy na wejściu, aby umożliwić skopiowanie każdego (nominalnie klasycznego) bitu wejściowego.$|0\rangle \mapsto |00\cdots 0\rangle$$|1\rangle \mapsto |11\cdots 1\rangle$

Rozsądne wydaje się albo rozważenie całego kontinuum takich bram, albo ograniczenie ich do pewnego skończonego zbioru. Każdy wybór powoduje powstanie innej „bazy bramek monotonicznych” dla obwodów; można rozważyć, jakie właściwości mają różne monotoniczne zasady. Stany można wybierać całkowicie niezależnie, z zastrzeżeniem ograniczenia monotoniczności; niewątpliwie byłoby interesujące (i prawdopodobnie praktyczne wiązać błąd) ustawieniei, chociaż nie widzę powodu, aby wymagać tego w teorii. Oczywiście AND i OR są bramami tego typu, gdziei$\rho_{00}, \rho_\mu, \rho_\nu, \rho_{11}$$\rho_{00} = |0\rangle\!\langle 0|$$\rho_{11} = |1\rangle\!\langle 1|$$\rho_\mu = \rho_\nu = |0\rangle\!\langle 0|$$\rho_\mu = \rho_\nu = |1\rangle\!\langle 1|$odpowiednio, cokolwiek wybierze lub .$|\mu\rangle$$|\nu\rangle$

Dla każdego stałego k można również rozważyć podstawy bramek, w tym bramki k -wejściowe-jedno-wyjściowe. Najprostszym podejściem w tym przypadku byłoby prawdopodobnie dopuszczenie gates które można zaimplementować jak wyżej, umożliwiając dowolny rozkład podprzestrzeni każdej wagi Hamminga , i wymaganie, aby dla każdego$\mathsf G: \mathbf H^{\otimes k} \to \mathbf H$$\mathcal V_w \leqslant \mathcal H_2^{\otimes k}$$0 \leqslant w \leqslant k$

$$\max_{|\psi\rangle \in \mathcal V_w}\;\langle 1 | \,\mathsf G\Bigl( |\psi\rangle\!\langle\psi| \Bigr)\, |1\rangle \;\;\leqslant\;\; \min_{|\psi\rangle \in \mathcal V_{w+1}}\;\langle 1 | \,\mathsf G\Bigl( |\psi\rangle\!\langle\psi| \Bigr)\, |1\rangle$$ $0 \leqslant w < k$ . Nie jest jasne, ile dodatkowej mocy obliczeniowej to by ci dało (nawet w przypadku klasycznym).

Nie wiem, czy jest coś ciekawego do powiedzenia na temat takich obwodów poza klasycznym przypadkiem, ale wydaje mi się, że jest to najbardziej obiecująca kandydacka definicja „kwantowego obwodu monotonicznego”.

Wariant kwantowy wyniku Razborova

Rozważmy ekspozycję Tima Gowersa dotyczącą wyników Alona i Boppany (1987), Combinatorica 7 s. 1–22, które wzmacniają wyniki Razborova (i wyraźnie wyjaśniają niektóre z jego technik) dotyczące monotonicznej złożoności CLIQUE. Gowers przedstawia to jako rekurencyjną konstrukcję rodziny zestawów, patrząc od „ ” kostki boolowskiej dla każdego . Jeśli usuniemy uprzywilejowaną pozycję standardowej bazy w zestawach podstawowych, analogicznie do lokalnej lematy Quantum Lovász , możemy rozważyć podprzestrzeń

$$E_j = \Bigl\{ \mathbf x \in \{0,1\}^n \;:\; x_j = 1 \Bigr\}$$ $1 \leqslant j \leqslant n$$\mathcal H_2^{\otimes n}$odpowiadać twierdzeniu binarnemu (czy stan należy do podprzestrzeni, czy jest do niej ortogonalny), co może wynikać z pomiaru. Na przykład, możemy rozważyć podprzestrzeni podane przez Dopuszczamy kwantowo-logiczne analogi koniunkcji i dysjunkcji podprzestrzeni: $n$$\mathcal A_j \leqslant \mathcal H_2^{\otimes n}$ $$\begin{align*} \mathcal A_j = U_j \mathcal E_j \;, & \text{ for each $1 \leqslant j \leqslant n$} \\ \text{where } &\mathcal E_j := \Bigl\{ | \mathbf x \rangle \;:\; \mathbf x \in E_j \Bigr\} ; \\ &U_j : \mathcal H_2^{\otimes n} \to \mathcal H_2^{\otimes n} \text{ a unitary of bounded complexity}. \end{align*}$$ $$\begin{gather*} \mathcal A \wedge \mathcal B = \mathcal A \cap \mathcal B ; \\ \mathcal A \vee \mathcal B = \mathcal A + \mathcal B = \Bigl\{ \mathbf a + \mathbf b \,:\, \mathbf a \in \mathcal A\;,\; \mathbf b \in \mathcal B \Bigr\} . \end{gather*}$$ Następnie pytamy, jak długo wymagana jest rekurencyjna konstrukcja spójników i rozłączeń przestrzeni, aby uzyskać przestrzeń , tak że projektor na różni się tylko nieznacznie od projektora na przestrzeń rozpiętą przez funkcje wskaźnikowe wykresów mających kliki o rozmiarze ; na przykład, aby$C$$\Pi_C$$C$$\Pi_{K(r)}$$r$$\| \Pi_C - \Pi_{K(r)} \|_\infty <\; 1/\mathrm{poly}(n)$. Część monotoniczna bierze udział w kwantowych operacjach logicznych, a prymitywne twierdzenia o danych wejściowych są również kwantowe.

W ogólnym przypadku istnieje problem z potraktowaniem tego jako problemu obliczeniowego: rozbieżność nie odpowiada żadnej wiedzy, którą można by uzyskać z pewnością poprzez pomiary na skończonej liczbie kopii za pomocą pomiarów czarnej skrzynki dla i , chyba że są to obrazy projektorów dojeżdżających do pracy. Ten ogólny problem można nadal traktować jako interesujący wynik dotyczący złożoności geometryczno-kombinatorycznej i może on prowadzić do rezultatów związanych ze sfrustrowanymi lokalnymi Hamiltionianami. Jednak bardziej naturalne może być po prostu wymaganie, aby podprzestrzenie$\mathcal A$$\mathcal B$$\mathcal A_j$powstają z projektorów dojeżdżających do pracy, w którym to przypadku rozbieżność jest tylko klasyczną OR wyników pomiarów tych projektorów. Wtedy możemy wymagać, aby jednostki były takie same, a to staje się problemem dotyczącym obwodu jednostkowego (który powoduje powstanie „prymitywnych zdarzeń”) z monotonicznym klasycznym przetwarzaniem końcowym (który wykonuje operacje logiczne na tych zdarzeniach).$U_j$

Zauważ też, że jeśli nie narzucimy żadnych dalszych ograniczeń na spacje , może to być podprzestrzeń z bardzo dużym nakładaniem się z pewną spacją rozpiętą według standardowych stanów bazowych , które są ciągami binarnymi, w których .$\mathcal A_j$$\mathcal E_k^\bot$$\mathbf x \in \bar E_k$$x_k = 0$

• Jeśli ta możliwość sprawia, że ​​piszczysz, zawsze możesz wymagać, aby miał kąt oddzielenia od dowolnego co najmniej (tak, aby nasze prymitywne podprzestrzenie były w najgorszym przypadku w przybliżeniu niezależne od podprzestrzeni, w których jeden z bitów jest ustawiony na 1).$\mathcal A_j$$\mathcal E_k^\bot$$\frac{\pi}{2} - 1/\mathrm{poly}(n)$

• Jeśli nie narzucimy takiego ograniczenia, wydaje mi się, że dopuszczenie podprzestrzeni o dużym nakładaniu się z stanowiłoby przeszkodę w przybliżeniu CLIQUE (r); albo bylibyśmy mniej lub bardziej ograniczeni do rozważania nieobecności określonej krawędzi (zamiast jej obecności), albo bylibyśmy zmuszeni zignorować jedną z krawędzi całkowicie. Nie uważam więc za niezwykle ważne nakładanie jakichkolwiek ograniczeń na , z wyjątkiem tego, że wszystkie są obrazami zestawu dojeżdżających do pracy projektorów, jeśli naszym celem jest rozważenie, jak „monotonicznie ocenić KLIKNIĘCIE z prostych propozycji kwantowych „. W najgorszym przypadku klasycznie sprowadzałoby się to do dopuszczenia bramek NIE na wejściu (i do tego, że wszystkie wygaszanie następuje po zanegowaniu).$\mathcal E_k^\bot$$\mathcal A_j$

Ponownie nie jest dla mnie jasne, czy podstawienie zestawów podstawowych dowolnymi podprzestrzeniami powoduje bardziej interesujący problem niż zwykłe użycie podprzestrzeni ; choć ograniczając się do formuł CNF (w przypadku dojazdów do pracy lub w przypadku dojazdów do pracy), uzyskane wyniki odpowiadałyby pewnej koncepcji złożoności pozbawionego frustracji hamiltonianu, którego różnorodność stanu podstawowego składała się ze standardowych podstaw stany reprezentujące kliki.$\mathcal H_2^{\otimes n}$$\mathcal E_j$

Jak dowodzą komentarze Robina i Tsuyoshi, pojęcie obwodów monotonicznych wydaje się łatwe do rozszerzenia na obwody kwantowe.

Aby mieć sensowną definicję kwantowego obwodu monotonicznego, musimy wybrać porządek stanów kwantowych, w odniesieniu do których monotoniczność jest zdefiniowana. Klasycznie rozsądną opcją (i taką, która prowadzi do normalnego pojęcia obwodów monotonicznych), jest ciężar Hamminga, ale rozważmy kolejność podaną przez dowolną funkcję .$f$

Ponieważ ewolucja zamkniętego układu kwantowego jest jednolita (co możemy założyć, że podaje ją ), to dla każdego stanu tak, że istnieje stan alternatywny taki że ale dla którego , a zatem ewolucja nie jest monotoniczna.$U$$|\psi\rangle$$f(U|\psi\rangle)>f(|\psi\rangle)$$|\phi\rangle$$f(|\phi\rangle) > f(|\psi\rangle)$$f(U|\psi\rangle)>f(U|\phi\rangle)$$U$

Zatem jedynymi obwodami, które są monotoniczne w stosunku do są te, które dla wszystkich . Zatem dowolny zestaw bram, który jest monotoniczny w stosunku do składa się z bram, które dojeżdżają z .$f$$f(U|\psi\rangle)=f(|\psi\rangle)$$|\psi\rangle$$f$$f$

Oczywiście zestawy bramek, które mogą to spełnić, zależą od definicji . Jeśli jest stałe, wówczas wszystkie zestawy bramek są monotoniczne w stosunku do niego. Jeśli jednak wybieramy jako wagę stanów Hamminga w podstawie obliczeniowej (nieco naturalne przedłużenie stosowane w klasycznym przypadku), otrzymujemy ciekawą strukturę. Nałożone ograniczenie wymaga, aby waga Hamminga pozostała niezmieniona. Operacje, które zachowują tę kwotę do operacji po przekątnej lub częściowych SWAP lub ich kombinacji. Struktura ta pojawia się dość często w fizyce (w modelach ścisłego wiązania itp.) I jest podobna do problemu rozpraszania Bosona badanego przez Aaronsona i Arkhipova$f$$f$$f$$f$, choć nie identyczne (to nieco inny problem rozpraszania). Ponadto zawiera obwody dla IQP , a zatem nie powinien być efektywnie klasycznie symulowany.

zadajesz w zasadzie dwa pytania o bardzo zróżnicowanym poziomie trudności, na granicy dwóch dużych pól, tj. obwodów boolowskich i obliczeń QM, dotyczące możliwości czegoś, co w matematyce nazywane jest czasem „twierdzeniem mostkowym”:

• analog kwantowy obwodów monotonicznych

• analog kwantowy Razborova thm

krótka odpowiedź szczery to nie lub nie tak daleko .

dla (1), nie tak trudne pytanie, ale wciąż najwyraźniej rzadko rozważane, pojawiło się następujące odniesienie, które można uznać za pokrewny przypadek w literaturze.

Twardość aproksymacji problemów kwantowych według Gharibiana i Kempe

rozważają niektóre problemy „monotoniczne” w kontekście kwantowym, np. QMSA, „minimalne przypisanie monotonicznego zadawania kwantowego, QMSA”, tj. analog SAT QM; (także inny problem Quantum Monotone Minimalna waga słowa, QMW) i pokazują pewne wyniki twardości aproksymacji, tj. dolne granice. Oni nie uważają obwodów kwantowych monotonia per se , ale pomysł, że mógłby być układ kwantowy lub algorytm, który rozwiązuje monotonia funkcja QMSA może być traktowany jako analogu QM.

co do (2), byłby to bardzo zaawansowany wynik, gdyby istniał, czego nie wydaje się „jak dotąd”. Thm Razborova jest zasadniczo dolnym ograniczonym wynikiem typu „wąskiego gardła”, uważanym za wyraźny przełom i prawie niezrównany wynik w teorii obwodów (monotonicznych).

z grubsza tak, oczywiście, że w obliczeniach QM występują pewne wąskie gardła, np. związane z bezpośrednimi twierdzeniami o produktach, ankieta patrz np.

Algorytmy kwantowe, dolne granice i kompromisy czasoprzestrzenne Spalek

jednak prawdopodobnie lepsza analogiczna QM obliczająca dolną granicę nakładałaby dolną granicę na liczbę operacji kubitowych lub ewentualnie oparta na „pełnych” bramkach, takich jak bramki Toffoli, dla funkcji monotonicznej. nie znam dowodów tego typu.

inne podejście może ograniczyć analizę do specjalnych kwantowych bramek AND i OR z dodatkowymi bitami „pomocniczymi”, aby uczynić bramy odwracalnymi.