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

12

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.kN=2nf(k)=1

N=2n/2

Mamy więc następujący problem:

Problem: Znajdź w bazie danych, tak abykf(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 ?PNPNn

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ć.

Spaghetti kwantowe
źródło
Rozważ użycie \text{}do pisania nazw klas złożoności. Na przykład \text{NP}lub\text{BQP}
Sanchayan Dutta
1
Nie jestem pewien, o co tu pytasz. Algorytmy nie mogą należeć do klas złożoności, ponieważ klasy złożoności zawierają problemy obliczeniowe. Zastanawiasz się, czy problem określony w pytaniu jest zawarty w „znanej” klasie złożoności, czy jest dla niej kompletny? Zastanawiasz się, czy „odkrycie” algorytmu Grovera prowadzi do twierdzenia o związku między znanymi klasami złożoności? Proszę o wyjaśnienie.
Dyskretna jaszczurka

Odpowiedzi:

6

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 ) .xRyR(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 ) .yxR(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 | 1O:H.2)m+1H.2)m+1O|za|b=|za|bfa(za)fa:{0,1}m{0,1}y .O|y|0=|y|1

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

R(O,y)[O|y|0=|y|1][f(y)=1].

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.xfpyramids

  • 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 (nxN=n/N.yfa(y)=1 , ta procedura zatrzymuje się w czasie O ( N log N ) O ( n log n ) , więc problem występuje wFP.O(logN.)O(logn)O(N.logN.)O(nlogn)

    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 2x{0,1}ny{0,1}mO:H2m+1H2m+1w 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 |y|bmΩ(logn)xf:{0,1}m{0,1}mO(n)f(y) tym samym wydajnie oceni O na standardowych stanach bazowych. To stawia problem wFNP.y{0,1}mO

    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=|x|OO(p(n)O(p(n)2m) . 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.O(p(n)2n)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 OnxOxN=n/NnxONO(2n/2)zapytania zasłaniają drobiazgową wiadomość, że ten algorytm wciąż ma czas wykładniczy dla komputera kwantowego.O(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.xRy: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 istniejexx 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?OxO

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.OnOnx

Niestrukturalnych Szukaj względem Oracle . O
Przy danych wejściowych długości n ,x=111n

  • znajdź (problem z relacją) luby{0,1}n

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

takie, że .O|y|0=|y|1

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.NPOFNPOBQPOFBQPO

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).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.OONPOBQPO

Niel de Beaudrap
źródło
2

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.nmn

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.m2n/2m2n1

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.

piramidy
źródło
fizycy lubią odwoływać się do poglądu, że wciąż jest to wykładnicze przyspieszenie bez znanego ”… czy miałeś na myśli napisać „ wciąż przyspieszenie wielomianowe ”?
glS
Nie, jest to rzeczywiście przyspieszenie wykładnicze (po prostu za mało, aby zmienić wykładniczy środowisko uruchomieniowe w niewykładniczy).
piramidy
2

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ć):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 )fa(x)x{0,1}nxfa(x)=1pxmpoli(n) tylko wtedy, gdy f ( x ) = 1 , a funkcja g ( x , p x ) jest wydajnie obliczalna (tzn. Ma czas działania poli ( n ) .sol(x,px)=1fa(x)=1sol(x,px)poli(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)xxf(x)g(x,px)=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)xx=72px=(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 1G1G2xf(x)pxG1G2g(x,px)pxG1przy użyciu określonej permutacji sprawdza, czy macierz przylegania jest taka sama jak w .G2

  • 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.xf(x)pxg(x,px)

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 .NPPP

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.PNPNPPPNP

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 ) )NPxpxm=poly(n)g(x,px)=1O(2mpoly(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,px)=1pxO(2m/2poly(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.

DaftWullie
źródło
Klasy P i NP są zwykle definiowane jako klasy języków lub problemów decyzyjnych, na przykład w odpowiedzi na to pytanie . Chociaż można je „zakodować” jako funkcje z wyjściem binarnym, tak jak tutaj, jest to nieco niestandardowe w teorii złożoności.
Dyskretna jaszczurka
@Discretelizard Prawda, ale ja dążyłem do celów pedagogicznych, aby uniknąć konieczności wprowadzania dodatkowej terminologii / techniki. Jestem pewien, że istnieją pewne subtelności, których brakuje w moim opisie (np. Podałem funkcję zamiast rodziny funkcji), ponownie z zamiarem nie zagniecenia się i próby przejścia do sedna. f(x)
DaftWullie
Możesz definiować rzeczy w dowolny sposób, ale myślę, że warto wspomnieć, że nie jest to standard, gdy np. Czytelnicy sprawdzają inne źródła. Stąd komentarz.
Dyskretna jaszczurka
-1

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

n10

Problem jest znany jako NP-zupełny.

kludg
źródło
3
W tym, co mówisz, jest element prawdy - że prawie zawsze należy myśleć o wyroczni jako o ocenie funkcji, a nie o wyszukiwaniu w bazie danych; i jeśli ta funkcja może być oceniona w czasie wielomianowym, to faktycznie jest to instancja SAT, która faktycznie jest NP-kompletna. Ale biorąc pod uwagę, że przyspieszenie Grovera jest co najwyżej kwadratowe, nie jest jasne, czy kompletność NP SAT jest istotna dla tego, co faktycznie robi algorytm Grovera.
Niel de Beaudrap
2
Ze względu na ignorancję lub trolling downvoting nie będę już wnosił tego forum.
kludg
@kludg Przyznaję, że jeden z niższych głosów jest mój, więc pozwól mi wyjaśnić; Twoja odpowiedź bez dalszego kontekstu lub wyjaśnień nie odpowiada na żadne z pytań, które zadałem w PO. Jest to interesujący punkt, ale jak do tej pory powiedziałem, że nie dotyczy to moich konkretnych pytań. Teraz mogę się mylić w tej kwestii, a odpowiedź na to pytanie jest odpowiedzią na niektóre z moich pytań - jeśli tak, to nie sądzę, aby udzielono na nie odpowiedzi w sposób jednoznaczny.
Kwalifikacja kwantowa