Algorytm Grovera i jego związek z klasami złożoności?

Mylę się co do algorytmu Grovera i jego związku z klasami złożoności.

Algorytm Grovera znajduje element w bazie danych (tak, że ) elementów z wywołaniami do wyroczni.$k$$N=2^n$$f(k)=1$

Mamy więc następujący problem:

Problem: Znajdź w bazie danych, tak aby$k$$f(k)=1$

Teraz jestem świadomy, że nie jest to problem desision, dlatego nasze normalne definicje klasy złożoności , itp. Tak naprawdę nie mają zastosowania. Ale jestem ciekawy, jak zdefiniowalibyśmy klasę złożoności w takim przypadku - i czy pogoda jest wykonywana w odniesieniu do czy ?$\text{P}$$\text{NP}$$N$$n$

Ponadto algorytm Grovera może być użyty jako podprogram. Czytałem w kilku miejscach, że algorytm Grovera nie zmienia klasy złożoności problemu - czy istnieje heurystyczny sposób, aby to zobaczyć.

Podsumowanie

• Istnieje teoria złożoności problemów wyszukiwania (znana również jako problemy relacji). Teoria ta obejmuje klasy o nazwie FP , FNP i FBQP, które skutecznie rozwiązują problemy wyszukiwania przy użyciu różnego rodzaju zasobów.
• Na podstawie problemów wyszukiwania możesz także zdefiniować problemy decyzyjne, co pozwala powiązać problemy wyszukiwania ze zwykłymi klasami P , NP i BQP .
• Niezależnie od tego, czy rozważasz wersję wyszukiwania wersji decyzji problemu, sposób, w jaki weźmiesz pod uwagę wkład do problemu wyszukiwania nieustrukturyzowanego, określi, jakie górne granice możesz nałożyć na jego złożoność.

Złożoność problemów w relacjach

Jak zauważasz, problem Grovera rozwiązuje problem wyszukiwania , który w literaturze o złożoności jest czasem znany również jako problem relacji . Oznacza to, że jest to następujący problem:

Struktura ogólnego problemu wyszukiwania.
Biorąc pod uwagę wejściowy i relację binarną R , znajdź y takie, które utrzymuje R ( x , y ) .$x$$R$$y$$R(x,y)$

Klasy złożoności FP i FNP są zdefiniowane w kategoriach takich problemów, gdzie szczególnie interesuje się przypadek, w którym ma długość co najwyżej funkcję wielomianową długości x , i gdzie relacja R ( x , y ) może sama w sobie być obliczana w czasie ograniczonym przez wielomian o długości ( x , y ) .$y$$x$$R(x,y)$$(x,y)$

W szczególności: przykład problemu „wyszukiwania w bazie danych”, do którego zwykle stosuje się wyszukiwanie Grovera, można opisać w następujący sposób.

Wyszukiwanie nieustrukturyzowane.
Biorąc pod uwagę wyrocznię wejściową takie, że O | ⟩ | b ⟩ = | ⟩ | b ⊕ f ( a ) ⟩ dla funkcji f : { 0 , 1 } m → { 0 , 1 } , znajdź y takie, że O | y ⟩ | 0 ⟩ = | y ⟩ | $\mathcal O: \mathcal H_2^{\otimes m+1} \!\to \mathcal H_2^{\otimes m+1}$$\mathcal O \lvert a \rangle \lvert b \rangle = \lvert a \rangle \lvert b \oplus f(a) \rangle$$f: \{0,1\}^m \to \{0,1\}$$y$ .$\mathcal O \lvert y \rangle \lvert 0 \rangle = \lvert y \rangle \lvert 1 \rangle$

Tutaj sama wyrocznia jest wkładem do problemu: odgrywa rolę , a relacją, którą obliczamy, jest R ( O , y $x$

Załóżmy, że zamiast wyroczni mamy określone wejście które opisuje sposób obliczenia funkcji f , możemy następnie rozważyć, do której klasy złożoności należy ten problem. Jak wskazano , odpowiednia klasa złożoności, którą otrzymujemy, zależy od sposobu wprowadzania danych wejściowych.$x$$f$pyramids

• Załóżmy, że funkcja wejściowa jest zapewniona jako baza danych (jak czasami opisywany jest problem), gdzie każda pozycja w bazie danych ma pewną długość . Jeśli n oznacza długość łańcucha x używane do opisania całą bazę danych , baza danych jest następnie N = n / £ -l pozycji. Następnie można wyczerpująco przeszukać całą bazę danych, sprawdzając kolejno każdy z N wpisów i zatrzymać, jeśli znajdziemy wpis y taki, że f ( y ) = 1 . Załóżmy, że każde zapytanie do bazy danych wymaga czegoś takiego jak O $\ell$$n$$x$$N = n\big/\ell$$N$$y$$f(y) = 1$ , ta procedura zatrzymuje się w czasie O ( N log N ) ⊆ O ( n log n ) , więc problem występuje wFP.$O(\log N) \subseteq O(\log n)$$O(N \log N) \subseteq O(n \log n)$

  Zakładając, że wyszukiwanie bazy danych można przeprowadzić w spójnej superpozycji, algorytm Grovera pozwala na ten problem w FBQP . Jednak, ponieważ FP  ⊆  FBQP , klasyczne wyczerpujące poszukiwanie dowodzi również, że ten problem dotyczy FBQP . Wszystko, co uzyskujemy (do współczynników logu), to kwadratowe przyspieszenie dzięki oszczędności w liczbie zapytań do bazy danych.
  
  

• Załóżmy, że funkcja wejściowa jest zwięźle opisana przez algorytm wielomianowy, który przyjmuje specyfikację oraz argument y ∈ { 0 , 1 } mi oblicza O : H m + 1$x \in \{0,1\}^n$$y \in \{0,1\}^m$$\mathcal O : \mathcal H_2^{m+1} \!\to \mathcal H_2^{m+1}\!$w standardowym stanie , w którym m może być znacznie większa niż Ohm ( log n ) . Przykładem może być gdzie x określa postać CNF jakiejś funkcji boolowskiej f : { 0 , 1 } m → { 0 , 1 } dla m ∈ O ( n ) , w którym to przypadku możemy efektywnie ocenić f ( y ) na wejściu y $\lvert y \rangle\lvert b \rangle$$m$$\Omega(\log n)$$x$$f: \{0,1\}^m \to \{0,1\}$$m \in O(n)$$f(y)$ tym samym wydajnie oceni O na standardowych stanach bazowych. To stawia problem wFNP.$y \in \{0,1\}^m$$\mathcal O$

  Biorąc pod uwagę procedurę oceny z ( x , y ) w czasie O ( p ( n ) ) dla n = | x | , Algorytm Grovera rozwiązuje problem nieustrukturyzowanego poszukiwania O w czasie O ( p ( n ) $f(y)$$(x,y)$$O(p(n))$$n = \lvert x \rvert$$\mathcal O$⊆O(p(n)$O(p(n) \sqrt{2^m})$ . To nie jest wielomianemn, a więc nie wystarczy umieścić ten problem wFBQP: Tylko uzyskania kwadratowego przyspieszenie - mimo to nadal jest potencjalnie ogromne oszczędności czasu obliczeń, przy założeniu, że korzyści, które zapewnia Algorytm Grovera nie jest stracone na narzut wymagany do obliczeń kwantowych odpornych na uszkodzenia.$\subseteq O(p(n) \sqrt{2^n})$$n$
  
  

W obu przypadkach, złożoność jest określana w kategoriach długości łańcucha x *, która określa, jak obliczyć wyroczni O . W przypadku, gdy x reprezentuje tablicę przeglądową, mamy N = n / ℓ , w którym to przypadku wydajność jako funkcja N jest podobna do wydajności jako funkcja n ; ale w przypadku, gdy x zwięźle określa O , a N ∈ O ( 2 n / 2 ) , wiadomość z dużym obrazem, że Grover rozwiązuje problem w $n$$x$$\mathcal O$$x$$N = n\big/\ell$$N$$n$$x$$\mathcal O$$N \in O(2^{n/2})$zapytania zasłaniają drobiazgową wiadomość, że ten algorytm wciąż ma czas wykładniczy dla komputera kwantowego.$O(\sqrt N)$

Złożoność decyzji wynikająca z problemów w relacjach

Istnieje prosty sposób na uzyskanie problemów decyzyjnych z problemów relacji, co jest dobrze znane z teorii problemów NP- zupełnych : przekształcenie problemu wyszukiwania na pytanie o istnienie prawidłowego rozwiązania.

Wersja decyzyjna ogólnego problemu wyszukiwania.
Biorąc pod uwagę wejście i relację binarną R , określ, czy ∃ y : R ( x , y ) jest ważne.$x$$R$$\exists y: R(x,y)$

Klasę złożoności NP można zasadniczo zdefiniować w kategoriach takich problemów, gdy relację można skutecznie obliczyć: najsłynniejsze problemy z NP -zupełnością (CNF-SAT, HAMCYCLE, 3-COLORING) dotyczą jedynie istnienia prawidłowego rozwiązania skutecznie weryfikowalny problem w relacjach. To przejście od tworzenia rozwiązań do zwykłego stwierdzania istnienia rozwiązań pozwala nam również opisywać wersje faktoryzacji liczb całkowitych, które znajdują się w BQP (pytając, czy istnieją czynniki nietrywialne, zamiast pytać o wartości czynników nietrywialnych) .$R$

W przypadku wyszukiwania nieustrukturyzowanego, która klasa złożoności najlepiej opisuje problem, zależy od struktury danych wejściowych. Ustalenie, czy istnieje rozwiązanie problemu relacji, można sprowadzić do znalezienia i zweryfikowania rozwiązania tego problemu. Zatem w przypadku, gdy dane wejściowe są ciągiem określającym wyrocznię jako tabelę przeglądową, problem nieustrukturyzowanego wyszukiwania występuje w P ; i bardziej ogólnie, jeśli x określa skuteczny sposób oceny wyroczni, problem dotyczy NP . Możliwe jest również, że istnieje sposób ustalenia, czy istnieje$x$$x$ rozwiązanie dla wyszukiwania nieustrukturyzowanego, które dokonuje tego bez faktycznego znalezienia rozwiązania, chociaż ogólnie nie jest jasne, jak to zrobić w sposób, który zapewniłby przewagę nad faktycznym znalezieniem rozwiązania.

Złożoność Oracle

Mam widoczny był przesuwając się od rozmowy o wyroczni , do sposobów, które wprowadzisz x mogą być używane do określenia (i oceny) Wyrocznia O . Ale oczywiście głównym sposobem, w jaki bierzemy pod uwagę algorytm Grovera, jest wyrocznia, w której ocena wyroczni zajmuje jeden krok czasowy i nie wymaga sprecyzowania. Jak oceniamy złożoność problemu w tym przypadku?$\mathcal O$$x$$\mathcal O$

W tym przypadku mamy do czynienia ze relatywizowanym modelem obliczeń, w którym ocena tej jednej konkretnej wyroczni (która, pamiętaj, jest wkładem do problemu) jest operacją prymitywną. Wyrocznia jest zdefiniowana dla wszystkich rozmiarów wejściowych: aby wziąć pod uwagę problem związany z wyszukiwaniem ciągów o długości n , musisz określić, że zastanawiasz się, w jaki sposób wyrocznia O działa na dane wejściowe o długości n , co ponownie byłoby możliwe, biorąc pod uwagę długość ciąg logiczny x przyjęty jako dane wejściowe. W takim przypadku sposób przedstawienia problemu może wyglądać następująco.$\mathcal O$$n$$\mathcal O$$n$$x$

Niestrukturalnych Szukaj względem Oracle . $\mathcal O$
Przy danych wejściowych długości n ,$x = 11\cdots 1$$n$

• znajdź (problem z relacją) lub$y \in \{0,1\}^n$

• ustalić, czy istnieje (problem decyzyjny)$y \in \{0,1\}^n$

takie, że .$\mathcal O \lvert y \rangle \lvert 0 \rangle = \lvert y \rangle \lvert 1 \rangle$

Ten problem występuje w (w przypadku problemu decyzyjnego) lub F N P O (w przypadku problemu relacji), w zależności od wersji problemu, którą chcesz rozważyć. Ponieważ algorytm Grover nie jest algorytmem wielomianowego czas, problem ten nie jest znany w B Q P O lub F B, Q, P O . W rzeczywistości możemy powiedzieć coś mocniejszego, co wkrótce zobaczymy.$\mathsf{NP}^{\mathcal O}$$\mathsf{FNP}^{\mathcal O}$$\mathsf{BQP}^{\mathcal O}$$\mathsf{FBQP}^{\mathcal O}$

Powodem, dla którego omówiłem rzeczywisty, oparty na wyroczni opis Nieustrukturyzowanego Wyszukiwania, było dotknięcie twojego punktu złożoności, a w szczególności kwestia rozmiaru danych wejściowych . Złożoność problemów zależy w dużej mierze od sposobu określania danych wejściowych: jako zwięzłej specyfikacji (w przypadku sposobu określania funkcji w CNF-SAT), jako wyraźnej specyfikacji (w przypadku tabeli przeglądowej dla funkcja), a nawet jako liczba całkowita określona w unarnym, tj. jako długość ciągu 1s jak powyżej (jak w „Wyszukiwanie nieustrukturyzowane względem Oracle ” powyżej).$\mathcal O$

Jak widzimy w tym drugim przypadku, jeśli traktujemy dane wejściowe tylko jako wyrocznię, sytuacja wygląda nieco nieintuicyjnie iz pewnością uniemożliwia rozmowę o sposobach realizacji „bazy danych”. Ale jedną z zalet rozważenia relatywizowanej wersji problemu z rzeczywistą wyrocznią jest to, że możemy udowodnić rzeczy, których w przeciwnym razie nie mamy pojęcia, jak to udowodnić. Gdybyśmy mogli udowodnić, że wersja decyzyjna zwięzłego problemu nieustrukturyzowanego wyszukiwania była w BQP , moglibyśmy osiągnąć ogromny przełom w praktycznych obliczeniach; i gdybyśmy mogli udowodnić, że problem decyzyjny nie był w rzeczywistości w BQP , to pokazalibyśmy, że P ≠ PSPACE, co byłoby ogromnym przełomem w złożoności obliczeniowej. Nie wiemy też, jak to zrobić. Ale dla zrelatywizować problemu, możemy pokazać, że istnieją wyrocznie , dla których wersja decyzja „niestrukturalnych Search względem O ” jest w N P O , ale nie w B Q P O . To pozwala nam pokazać, że chociaż obliczenia kwantowe są potencjalnie potężne, istnieją powody, aby oczekiwać, że BQP prawdopodobnie nie zawiera NP , i że w szczególności wersja powiązana wyszukiwania nieustrukturyzowanego prawdopodobnie nie zostanie zawarta w FBQP bez narzucania silnych ograniczeń dotyczących sposobu, w jaki wejście jest reprezentowane.$\mathcal O$$\mathcal O$$\mathsf{NP}^{\mathcal O}$$\mathsf{BQP}^{\mathcal O}$

Klasy złożoności są ogólnie definiowane w odniesieniu do wielkości danych wejściowych. Odpowiednie rozmiary tutaj to (liczba kubitów, na których pozwalasz działać algorytmowi Grovera) i liczba, o której jeszcze nie wspomniałeś, nazwij to m , bitów potrzebnych do opisania podprogramu ogólnie zwanego wyrocznią. Zazwyczaj wyrocznia zostanie skutecznie zaimplementowana w sposób, który skaluje się wielomianowo w n , co ma miejsce na przykład w przypadku zakodowania w wyroczni typowego problemu logicznego.$n$$m$$n$

W każdym razie nie uzyskuje się wzrostu klasy złożoności za pomocą algorytmu Grovera: Potrzeba wykładniczo wielu operacji kwantowych, zwykle , aby rozwiązać problem, który moglibyśmy zastosować brutalną siłą w wykładniczo wielu etapach, zwykle m ∗ 2 n - 1 , w każdym razie na klasycznym komputerze. Oznacza to, że problemy znane (np. EXPTIME) lub podejrzane (np. NP) o przyjęcie wykładniczego środowiska wykonawczego będą nadal wymagały wykładniczego środowiska wykonawczego.$m*2^{n/2}$$m*2^{n-1}$

Jednak fizycy lubią odwoływać się do poglądu, że wciąż jest to wykładnicze przyspieszenie bez znanego (lub rzeczywiście możliwego do wyobrażenia) klasycznego odpowiednika. Jest to najbardziej widoczne w przykładzie bazy danych, w którym funkcja Oracle jest wyszukiwaniem w bazie danych, a algorytm Grovera może powodować, że potrzeba dużo mniej wyszukiwań niż danych w bazie danych. W tym sensie nadal istnieje znacząca zaleta, chociaż całkowicie zaginęła w obrazie klasy złożoności.

Wszystkie zliczanie odbywa się w kategoriach , liczby bitów wymaganych do opisania danych wejściowych.$n$

Definiujemy klasę problemów w następujący sposób (lub jest to jeden ze sposobów, aby to zrobić):$\text{NP}$

Niech będzie funkcją, która akceptuje dane wejściowe x ∈ { 0 , 1 } n i zwraca wartość pojedynczego bitu 0 lub 1. Zadanie polega na tym, że musisz sprawdzić, czy dana wartość x zwraca wartość 1. Jednak, istnieje dalsza struktura problemu: jeśli f ( x ) = 1 , masz gwarancję, że istnieje dowód p x (o rozmiarze m ∼ poli ( n ) ) taki, że funkcja g ( x , p x$f(x)$$x\in\{0,1\}^n$$x$$f(x)=1$$p_x$$m\sim\text{poly}(n)$ tylko wtedy, gdy f ( x ) = 1 , a funkcja g ( x , p x ) jest wydajnie obliczalna (tzn. Ma czas działania poli ( n ) .$g(x,p_x)=1$$f(x)=1$$g(x,p_x)$$\text{poly}(n)$

Pozwól, że podam kilka przykładów (być może o to tutaj prosiłeś ?):

• Parzystość: odpowiada na pytanie „czy x jest nieparzysty?”. Jest to tak trywialne (wystarczy wziąć najmniej znaczący bit x ), że f ( x ) jest skutecznie obliczane bezpośrednio, a zatem dowód nie jest potrzebny, g ( x , p x ) = f ( x ) .$f(x)$$x$$x$$f(x)$$g(x,p_x)=f(x)$

• Liczby złożone: odpowiada na pytanie „czy dziesiętna reprezentacja x jest liczbą złożoną?”. Jednym z możliwych dowodów w kierunku „tak” (wystarczy udowodnić ten kierunek) jest podanie pary czynników. na przykład x = 72 , p x = ( 8 , 9 ) . Następnie g ( x , p ) polega po prostu na pomnożeniu razem czynników i sprawdzeniu, czy są one równe x .$f(x)$$x$$x=72$$p_x=(8,9)$$g(x,p)$$x$

• Izomorfizm wykresów: Biorąc pod uwagę dwa wykresy i G 2 (tutaj x zawiera opis obu wykresów), f ( x ) odpowiada na pytanie „czy dwa wykresy są izomorficzne?”. Dowód p x jest permutacją: stwierdzeniem, w jaki sposób wierzchołki w G 1 odwzorowują wierzchołki w G 2 . Funkcja g ( x , p x ) sprawdza, czy p x jest prawidłową permutacją, permutuje wierzchołki G $G_1$$G_2$$x$$f(x)$$p_x$$G_1$$G_2$$g(x,p_x)$$p_x$$G_1$przy użyciu określonej permutacji sprawdza, czy macierz przylegania jest taka sama jak w .$G_2$

• Saper : Stara ulubiona gra wbudowana w okna (i inne) może być wyrażona w ten sposób. Wyobraź sobie częściowo odsłoniętą deskę trałownika, więc niektóre komórki są nieznane, a niektóre odkryto, aby odkryć, ile min znajduje się w sąsiednich komórkach. Wszystko to jest wbudowane w zmienną . f ( x ) zadaje pytanie „czy istnieje ważny przydział min w nie odkrytym regionie?”. Dowód, p x jest po prostu jednym z takich przydziałów min. Można to łatwo zweryfikować za pomocą g ( x , p x ), co po prostu zapewnia zgodność z każdym znanym ograniczeniem.$x$$f(x)$$p_x$$g(x,p_x)$

Wszystkie te problemy są w ponieważ pasują do definicji skutecznego weryfikowalnego rozwiązania. Niektóre z nich znane są w P , a także: mamy już stwierdził, że badania dziwne jest w P . Liczby złożone również są, ponieważ efektywne jest sprawdzenie, czy liczba jest liczbą pierwszą, za pomocą testowania pierwotności AKS .$\text{NP}$$\text{P}$$\text{P}$

Izomorfizm grafów i trałowiec nie znane są w . Rzeczywiście, trałowiec jest znany jako NP -Complete, czyli jeżeli można skutecznie rozwiązać każdy problem NP jest w P . Wiele osób podejrzewa, że P ≠ NP , a zatem Saper ma instancje, których rozwiązanie zajmuje więcej czasu niż wielomian.$\text{P}$$\text{NP}$$\text{NP}$$\text{P}$$\text{P}\neq\text{NP}$

Jednym z możliwych sposobów rozwiązania problemu jest, dla stałego x , po prostu przetestowanie wszystkich możliwych dowodów p x aż do maksymalnej długości m = poli ( n ) i sprawdzenie, czy istnieje zadowalające rozwiązanie, tj. Poszukiwanie rozwiązania g ( x , p x ) = 1 . Oczywiście wymaga to czasu O ( 2 m poli ( m ) $\text{NP}$$x$$p_x$$m=\text{poly}(n)$$g(x,p_x)=1$$O(2^m\text{poly}(m))$, ponieważ istnieje wykładniczo wiele elementów do przeszukania, z których każdy wymaga obliczenia wielomianowego. Można to poprawić, wprowadzając wyszukiwanie Grovera: po prostu szukamy rozwiązania (tzn. Prawidłowy p x staje się zaznaczonym przedmiotem), a to zajmuje czas O ( 2 m / 2 poli ( m ) $g(x,p_x)=1$$p_x$$O(2^{m/2}\text{poly}(m))$. Jest to znacznie szybsze, ale nie zmienia oceny, czy czas działania jest wielomianowy, czy coś gorszego; nie stał się algorytmem wielomianowym. Na przykład izomorfizm grafów musiałby przeszukać wszystkie możliwe kombinacje. Saper musiałby przeszukać wszystkie możliwe zadania min na odkrytych polach.

Oczywiście czasami dodatkowa struktura problemu pozwala na różne rozwiązania, które nie wymagają przeszukiwania wszystkich możliwych dowodów. Tam wyszukiwanie Grovera jest dla nas mniej przydatne lub nawet nie, ale może być tak, że możemy wymyślić algorytm wielomianowy w inny sposób. Na przykład przypadek testowania złożonego: klasycznie znalezienie czynników liczby wydaje się trudne: nie możemy zrobić nic lepszego niż testowanie wszystkich możliwych czynników, więc korzystanie z tej formy dowodu niewiele pomaga, ale , jak już wspomniano, pytanie można rozwiązać skutecznie inną drogą, testowaniem pierwotności AKS.

Zapomnij o bazie danych. Algorytm Grovera rozwiązuje problem logicznej satysfakcji , a mianowicie:

$n$$1$$0$

Problem jest znany jako NP-zupełny.