Interaktywne dowody za pomocą Postselection?

Zdefiniuj model obliczeniowy MPostBQP, aby był identyczny z PostBQP, z wyjątkiem tego, że dopuszczamy wielomianowo wiele pomiarów kubitowych przed pomiarem selekcyjnym i pomiarem końcowym.

Czy możemy podać jakiekolwiek dowody wskazujące, że MPostBQP ma większą moc niż PostBQP?

Zdefiniuj MPostBQP [k], aby umożliwić wiele rund pomiaru i wyboru po dokonaniu ostatecznego pomiaru. Wybierz indeksowanie, więc MPostBQP [1] = PostBQP i MPostBQP [2] = MPostBQP i tak dalej. (Aktualizacja: formalna definicja jest podana poniżej).

Rozważ gry Arthur-Merlin. Być może możemy je zasymulować w tym modelu obliczeniowym: Postselekcja może przyjąć rolę Merlina w tworzeniu przekonujących wiadomości, a pomiary pośrednie mogą przyjąć rolę rzutów monetą Arthura. Ta możliwość sprawia, że ​​pytam:

Czy mamy AM [k] $\subset$ MPostBQP [k]?

Jest to faktycznie znane dla , co mówi MA PP. Pokazanie go dla oznaczałoby MPostBQP = PP tylko wtedy, gdy AM PP. Ponieważ istnieje wyrocznia, w stosunku do której AM nie jest zawarte w PP , może to dać odpowiedź twierdzącą na moje pierwsze pytanie.$k=1$$\subset$$k=2$$\subset$

Wreszcie, w przypadku wielomianowo wielu rund,

Czy mamy PSPACE MPostBQP [poli]? Jeśli tak, czy to równość?$\subset$

Byłoby to filozoficznie interesujące (przynajmniej dla mnie), ponieważ powiedziałoby nam, że „możliwa do rozwiązania” klasa problemów dla „wybierającego czarownika” obejmuje (lub jest ) całą PSPACE.

EDYCJA: Poproszono mnie o formalną definicję MPostBQP. (Zaktualizowałem poniższe).

MPostBQP [k] to klasa języków dla której istnieje jednolita rodzina obwodów kwantowych taka że dla wszystkich wejścia procedura poniżej wydajnością ważne z prawdopodobieństwem co najmniej , jeżeli oraz z prawdopodobieństwem najwyżej Jeżeli . Procedura, która pozwala na pewne wybory, które mogą zależeć od (ale nie ), jest zdefiniowana następująco:$L \subset \{0,1\}^*$$\{C_n\}_{n \geq 1}$$x$$2/3$$x \in L$$1/3$$x \notin L$$L$$x$

Procedura: Krok 1. Zastosuj operator unitarny odpowiadający do stanu wejściowego . Zauważ, że długość pierwszego jest najwyżej wielomianowa o długości . Krok 2. Dla : Jeśli jest parzyste, zmierz dowolną liczbę kubitów z pierwszego rejestru (najwyżej wielomianowo, biorąc pod uwagę rozmiar rejestru). Jeśli jest nieparzyste, to zaznacz tak, że wybrany pojedynczy kubit w pierwszym rejestrze mierzy jako$C_n$$\left\vert 0\cdots 0\right> \otimes \left\vert x \right>$$\left\vert0\cdots 0\right>$$x$$i = 1 \cdots k$$i$$i$$\left\vert 0 \right>$(i mają gwarancję, że prawdopodobieństwo jest niezerowe, więc postselekcja jest oczywiście ważna). Krok 3. Na koniec zmierz ostatni kubit w pierwszym rejestrze i zwróć true, jeśli zmierzymy a false w przeciwnym razie.$\left \vert 1 \right>$

Mamy MPostBQP [0] = BQP, MPostBQP [1] = PostBQP, a MPostBQP: = MPostBQP [2]. Próbuję odzwierciedlić klasy Arthura-Merlina, gdzie AM [0] = BPP, AM [1] = MA i AM [2] = AM.

EDYCJA (27.03.11 17.00): Wydaje się, że debata na temat tego, jak należy zdefiniować postselekcję w tym kontekście. Oczywiście mam na myśli definicję, która nie trywializuje mojego pytania! :) Przyjęłam następującą definicję : Po zaznaczeniu k-tego bitu oznacza to, że rzutujemy stan na podprzestrzeń, w której k-bit ma wartość$0$i normalizować. Okazuje się, że w schemacie, w którym dokonujemy selekcji przed wykonaniem pomiarów, możemy uzyskać ostateczne statystyki, patrząc na prawdopodobieństwa warunkowe w schemacie, w którym selekcje po zastępowane są pomiarami. Twierdzę jednak, że ta charakterystyka załamuje się, gdy pomiary i selekcje są przeplatane. Myślę, że zamieszanie wynika z tego, że ludzie używają tej „definicji prawdopodobieństwa warunkowego” (która działa w szczególnym przypadku, z której uogólniam) jako definicji postselekcji, a nie podanej właśnie definicji „pomiaru wymuszonego”, która wyraźnie zależy od porządek z powodu braku przemienności. Mam nadzieję, że to pomoże!

EDYCJA (27.03.11 9 wieczorem): Postselekcję zdefiniowałem już w formalizmie czysto państwowym. Niel podał analizę formalizmu macierzy gęstości, który nie zgadza się z moim dla przykładu 3-kubitowego. Winowajcą jest ponownie definicja postselekcji. Zdefiniuj ponowny wybór w ustawieniu macierzy gęstości w następujący sposób. Biorąc pod uwagę macierz gęstości , przepisz ją jako mieszaninę stanów rozdzielnych . Niech będzie wynikiem postselekcji (na niektórych kubitach) przy użyciu czystego stanu formalizmu, który zdefiniowałem powyżej. Zdefiniuj wynik postselekcji na jako .$M$$M = \sum p_i \left\vert a_i \right> \left< a_i \right\vert$$\left\vert A_i \right>$$M$$\sum p_i \left\vert A_i \right> \left< A_i \right\vert$

Jest to bardziej sensowna definicja, ponieważ nie daje nam wyników, które mówią, że po dokonaniu selekcji zmieniamy statystyki zdarzeń (pomiarów), które już oglądaliśmy. Oznacza to, że to prawdopodobieństwo monet, które „już przerzuciliśmy”. Nie ma dla mnie sensu stwierdzenie, że cofniemy się w czasie i uprzedzimy monetę, która już się wydarzyła, ponieważ zwiększyłoby to prawdopodobieństwo obecnej selekcji.$p_i$

EDYCJA (28.03.11 13.00): Niel przyznaje, że z moimi definicjami problem ma sens i nie trywializuje - ale z zastrzeżeniem, że nie powinienem nazywać go postselekcją . Biorąc pod uwagę zamieszanie, muszę się z nim zgodzić. Nazwijmy więc to, co zdefiniowałem jako selekcję , która wykonuje „wymuszony pomiar”. Prawdopodobnie powinienem zmienić nazwę zdefiniowanych przeze mnie klas złożoności (aby nie mieć w nich „Post”), więc nazwijmy je QMS [k] (wybór kwantowy).

Z komentarzy wynika, że ​​Shaun ma na myśli coś innego niż to, co zwykle rozumie się po selekcji. Rozumiem teraz, że oznacza to, że statystyki dla wszelkich pomiarów wykonanych przed określonym ponownym wyborem nie powinny być zmieniane przez późniejszy dodatkowy wybór. Jest to podobne do posiadania operatora projekcji, w którym normalizacja przeprowadzana jest nad każdą gałęzią funkcji falowej odpowiadającej konkretnemu zakresowi pomiarowemu, a nie nad funkcją falową jako całością.

W tym przypadku argumenty podane w innych odpowiedziach przeze mnie i Neila już się nie utrzymują. Rzeczywiście łatwo to zauważyć$P^{PP[k]}\subseteq$ MPostBQP [k], ponieważ MPostBQP$[k]$ można postrzegać jako maszynę BQP, która potrafi $k$ zapytania do wyroczni PP i odtąd $P^{\# P}\subseteq$ MPostBQP .

Więc teraz mamy nietrywialną dolną granicę, a co z górną granicą? Najwyraźniej problem tkwi w PSPACE , ale czy możemy to zrobić lepiej? Właściwie myślę, że możemy.

Możemy zapisać dowolne obliczenia w MPostBQP jako sekwencję warstw formy: obliczenia kwantowe, po których następuje ponowny wybór, a następnie pojedynczy pomiar kubitowy. Rzeczywiście, może to być alternatywny sposób sformułowania MPostBQP [k], jako obliczenia złożonego z$k$takie warstwy (to nieco różni się od definicji Shaun, która moim zdaniem ma liczyć tylko liczbę postselekcji), a następnie ostatnia warstwa klasycznego post-processingu. Użyję tej definicji MPostBQP [k] poniżej, ponieważ prowadzi to do bardziej estetycznego wyniku.

Poniżej zaktualizowano oryginalną wersję, aby naprawić dziurę w dowodzie.

Najpierw chcemy obliczyć wynik pomiaru pierwszego mierzonego kubita (nie wybrany ponownie!). Aby to zrobić, najpierw zauważamy, że wszelkie obliczenia kwantowe można wyrazić tylko za pomocą bramek Hadamarda i bramek Toffoli oraz amplitudy$\alpha_w$ określonego obliczeniowego stanu bazowego $|w\rangle$ w danych wyjściowych można zapisać maksymalnie jako sumę $2^{H}$ warunki $a_{j,w}$, gdzie $H$jest całkowitą liczbą bramek Hadamarda, z których każda odpowiada unikalnej ścieżce obliczeniowej. Wyraźnie,$a_{j,w} = \pm 2^{-H/2}$. Prawdopodobieństwo uzyskania stanu końcowego$|w\rangle$ jest następnie podane przez $\alpha_w^2 = (\sum_j a_{j,w})^2 = \sum_{i,j} a_{j,w}a_{i,w}$. Chcemy obliczyć całkowite prawdopodobieństwo pomiaru 1. Niech$S_0$ być zbiorem obliczeniowych stanów bazowych, które spełniają kryteria po selekcji (tj. kubit po selekcji wynosi 1) i daje 0 dla mierzonego kubita, i niech $S_1$być zbiorem obliczeniowych stanów bazowych, które spełniają kryteria po selekcji i dają 1 dla mierzonego kubitu. Możemy zdefiniować

W tym przypadku prawdopodobieństwo zmierzenia 1 uwarunkowanego na 1 dla wybranego kubit jest podane przez $\frac{\pi_1^+ - \pi_1^-}{\pi_1^+ - \pi_1^- - \pi_0^- + \pi_0^+}$. Jak możemy to ustalić za pomocą 4 połączeń z wyrocznią #P. Używamy tego do generowania losowego bitu$b_1$ która wynosi 1 z prawdopodobieństwem $X_1$, to samo co pomiar kwantowy. Zatem MPostBQP [1] jest w$BPP^{\# P[4]}$.

Następnie obliczamy wynik pomiaru drugiego kubitu. Aby to zrobić, uruchamiamy te same zapytania #P jak dla pierwszej warstwy, ale w obwodzie uzyskanym przez skomponowanie pierwszych dwóch warstw i gdzie wybieramy 1 dla każdego z wybranych kubitów, ale także dla$b_1$ dla wyniku pomiaru 1. Zauważ, że chociaż jest to selekcja stanów 3 kubitów zamiast 1, jest to trywialna modyfikacja $\# P$odpytuje, po prostu dodając ancilla, która jest ustawiana tylko wtedy, gdy wszystkie 3 kubity spełniają wymagane warunki i zamiast tego wybiera po tej ancilli. To następnie generuje prawidłowe warunkowe prawdopodobieństwa wyjściowe dla wyniku drugiego zmierzonego kubitu, który oznaczamy$b_2$. Zauważ, że użyliśmy teraz 8 połączeń z wyrocznią #P .

Powtarzamy ten proces iteracyjnie, aby na warstwie $j$ wybieramy 1 dla wszystkich $j$ poprzedzające wybrane kubity i dalej $b_{i<j}$ dla wszystkich poprzednich pomiarów i oznacz wynik odpowiedniego $P^{\# P}$ maszyna $b_j$. W sumie jest to wymagane$4j$ zapytania oracle.

Mamy więc MPostBQP [k]$\subseteq P^{\# P[4k]}$, co w połączeniu z poprzednim wynikiem, że $P^{PP[k]}\subseteq$ MPostBQP$[k]$, implikuje to $P^{PP[k]} \subseteq$ MPostBQP [k]$\subseteq BPP^{\# P[4k]}$, a zatem MPostBQP $= P^{\# P}$.

[Poprawiony.] Poprawiłem swoją odpowiedź w oparciu o twoje poprawki do twojego pytania, zachowałem treść mojej pierwotnej odpowiedzi, ale skróciłem ją. Bardziej szczegółowy opis procesu „symulacji” został zastąpiony, ale przypuszczam, że można go zobaczyć, przeglądając historię edycji tego postu.

Większość ludzi zrozumie „postselekcję” w sensie warunkowego prawdopodobieństwa. Rzeczywiście, obecna wersja artykułu z Wikipedii na temat PostBQP opisuje to w ten sposób; i postrzegana jako operacja na operatorach gęstości (w której stosuje się całkowicie pozytywną mapę nie zwiększającą się trace śladu, taką, że Φ ²  = Φ, a następnie renormalizującą ślad) odzyskuje się tę definicję.

Biorąc pod uwagę tę definicję postselekcji, twoja definicja algorytmu MPostBQP [ k ] może być symulowana przez algorytm PostBQP , poprzez odroczenie selekcji końcowej i wykonanie ich jednocześnie w odpowiedni sposób. Jest to zauważone mniej lub bardziej wyraźnie na stronie 3 artykułu Aaronsona: Obliczenia kwantowe, postselekcja i probabilistyczny czas wielomianowy, który wprowadza klasę PostBQP .

Można to wyraźnie pokazać, zauważając, że aby sekwencja bitów P ₁  ,   P ₂  , ... została wybrana ( np. W 1stanie, co jest zwykle), nie ma różnicy między uwarunkowaniem, że są one 1w środku obliczenia i uwarunkowania są 1na końcu obliczeń, o ile wartości tych bitów nie zostaną zmienione w międzyczasie. Następnie, zamiast wybierania każdego z nich indywidualnie . Ponadto, obliczenie AND może być przeprowadzone w dowolnym punkcie między ostatnią transformacją bitu a jego późniejszą selekcją. Nie wpłynie to w żaden sposób na wspólne statystyki żadnej z właściwości państwa.1 , możemy obliczyć ich logiczne ORAZ przed dokonaniem wyboru, a następnie wybrać to połączenie1

Tak więc, używając wspólnej definicji postselekcji w kategoriach prawdopodobieństw warunkowych, mielibyśmy MPostBQP [ k ] =  PostBQP dla wszystkich k  > 0.

Jak zauważyłem w powyższych komentarzach, nie sądzę, że operacja, którą opisujesz na stanie wektory - w szczególności obejmujące renormalizację wektorów stanu niezależnie w każdej gałęzi rozkładu prawdopodobieństwa nad wynikami pomiaru- odpowiada postselekcji, ponieważ wiele osób w tej dziedzinie (epsecialnie eksperymentalni) opisałoby to pojęcie. Może nawet powodować pewne „niefizyczne” właściwości, jeśli zostanie rozszerzony na mapowanie operatorów gęstości. Jest to jednak możliwy sposób konstruowania czegoś w rodzaju drzew decyzyjnych, których węzły są oznaczone przez wektory stanu, a zatem jest to zasadniczo sam w sobie rozsądny proces badania. Po prostu nie nazwałbym tego procesu „postselekcją”.

[Edytuj.] Ze względu na porządek usunąłem obliczony przykład. Przypuszczam, że można to zobaczyć, przeglądając historię edycji tego postu.

Z definicji MPostBQP mogłoby się wydawać , że jest to po prostu PostBQP w fantazyjnej sukience. Zamiast próbować przekonać cię, że pomiary można zmienić, być może bardziej przekonujące byłoby udowodnienie MPostBQP = PP , ponieważ wiadomo, że PostBQP = PP (patrz quant-ph / 0412187 ). Aby to udowodnić, podzieliliśmy to na dwa zadania:

1. udowadniając, że PP$\subseteq$MPostBQP i
2. udowadniając, że MPostBQP$\subseteq$ PP

Pierwsze zadanie jest trywialne, ponieważ PP = PostBQP = MPostBQP [1]$\subseteq$MPostBQP . Drugie zadanie jest naprawdę głównym pytaniem tutaj, ale można na nie odpowiedzieć, dokonując prostej adaptacji dowodu, że PostBQP = PP , podanego w quant-ph / 0412187 ( zarys strony dowodu na Wikipedii na PostBQP ).

Poniższe elementy zostały dostosowane ze szkicu próbnego Wikipedii dla PostBQP = PP .

Możemy zapisać obwód odpowiadający dowolnemu obliczeniu MPostBQP jako szereg jednolitych bramek i selekcji końcowych . Bez utraty ogólności możemy założyć, że po wybraniu kubitu nigdy nie jest on ponownie podejmowany. Zatem stan kwantowy uzyskany na końcu obliczeń podaje: $|\psi\rangle = \prod_i (P_i^1 \prod_j A^{ij}) |x\rangle$, gdzie $P_i^1$ oznacza projektor dla qubit $i$ na $|1\rangle$ podprzestrzeń i $A^{ij}$są macierzami odpowiadającymi elementarnym bramkom. Zauważ, że bez utraty ogólności możemy założyć, że wszystkie wpisy w$A^{ij}$ są prawdziwe kosztem dodatkowego kubita.

Teraz pozwól $\{p_i\}$ być zbiorem kubitów, które są później wybrane i niech $q$być kubitem wyjściowym. My definiujemy$\pi_0 = \sum_{w \in S_0} \psi_w^2$ i $\pi_1 = \sum_{w \in S_1} \psi_w^2$, gdzie $S_0$ ($S_1$) to zbiór obliczeniowych stanów bazowych, dla których $p_i = 1 \forall i$ i $q=0$ ($q=1$). Definicja MPostBQP zapewnia, że ​​albo$\pi(1) \geq 2\pi(0)$ lub $\pi_0 \geq 2\pi_1$. Chodzi o to, aby zbudować maszynę PP do porównania$\pi_0$ i $\pi_1$. Wyrażający$\psi_w$, część końcowego działania fal $\psi$ odpowiadający konkretnemu obliczeniowemu stanowi bazowemu $w$, jako suma ścieżek i zastąpienie indeksów $i$ i $j$ na $A^{ij}$ z jednym indeksem $k$ od 1 do $G$, otrzymujemy $\psi_w = \sum_{\alpha_1 ... \alpha_G} A^{G}_{w,\alpha_G} A^{G-1}_{\alpha_G,\alpha_{G-1}} ... A^{1}_{\alpha_2,\alpha_1} x_{\alpha_1}$.

The idea, then, is to construct a PP machine which accepts with probability $\frac{1}{2}(1+C(\pi_1-\pi_0))$ for some $C>0$, since then $x \in L$ would imply that $\frac{1}{2}(1+\pi_1-\pi_0)> \frac{1}{2}$ and $\frac{1}{2}(1+\pi_1-\pi_0) < \frac{1}{2}$ if $x \notin L$.

Now let $\alpha = \{\alpha_i\}$ and $F(A,w,\alpha,X) = A^{G}_{w,\alpha_G} A^{G-1}_{\alpha_G,\alpha_{G-1}} ... A^{1}_{\alpha_2,\alpha_1} x_{\alpha_1}$. Then $\pi_1 - \pi_0 = \sum_{w \in S_1} \sum{\alpha,\alpha'} F(A,w,\alpha,X)F(A,w,\alpha',X) - \sum_{w \in S_0} \sum{\alpha,\alpha'} F(A,w,\alpha,X)F(A,w,\alpha',X)$.

Such a PP machine can then be defined as follows:

1. Pick a computational basis state $w$ uniformly at random.
2. If $w \notin S_0 \cup S_1$, then stop and accept with probability $1/2$, and reject otherwise.
3. Pick two sequences $\alpha$ and $\alpha'$ of $G$ computational basis states uniformly at random.
4. Compute $X = F(A,w,\alpha,x)F(A,w,\alpha',x)$.
5. If $w\in S_1$ then accept with probability $\frac{1+X}{2}$, and reject otherwise. Alternatively, if $w\in S_0$ then accept with probability $\frac{1-X}{2}$, and reject otherwise.

This then puts MPostBQP[k] $\subseteq$ PP, for all $k$, and hence MPostBQP is no more powerful than PostBQP.