Czy istnieje jakieś ogólne stwierdzenie dotyczące tego, jakie problemy można rozwiązać bardziej efektywnie za pomocą komputera kwantowego?

Czy istnieje ogólne stwierdzenie o tym, jakie problemy można rozwiązać bardziej efektywnie za pomocą komputerów kwantowych (tylko model bramki kwantowej)? Czy problemy, dla których znany jest dzisiaj algorytm, mają wspólną właściwość?

O ile rozumiem obliczenia kwantowe pomagają rozwiązać problem ukrytej podgrupy (Shor); Algorytm Grovera pomaga przyspieszyć problemy z wyszukiwaniem. Czytałem, że algorytmy kwantowe mogą przyspieszyć, jeśli szukasz „globalnej własności” funkcji (Grover / Deutsch).

1. Czy istnieje bardziej zwięzłe i poprawne stwierdzenie na temat tego, gdzie obliczenia kwantowe mogą pomóc?
2. Czy można wyjaśnić, dlaczego fizyka kwantowa może w tym pomóc (najlepiej coś głębszego niż „interferencja” może być wykorzystana)? I dlaczego prawdopodobnie nie pomoże to w przypadku innych problemów (np. Problemów NP-zupełnych)?

Czy istnieją odpowiednie dokumenty, które tylko to omawiają?

Zadałem to pytanie wcześniej na cstheory.stackexchange.com, ale może być bardziej odpowiednie tutaj.

O ogólnej pomocy obliczeniowej

Nie zdając sobie z tego sprawy, zadajesz wersję jednego z najtrudniejszych pytań, jakie możesz zadać na temat informatyki teoretycznej. Możesz zadać to samo pytanie na temat klasycznych komputerów, ale zamiast pytania, czy dodanie „kwantowości” jest pomocne, możesz zadać:

• Czy istnieje zwięzłe stwierdzenie na temat tego, gdzie mogą pomóc losowe algorytmy?

  Można tu powiedzieć coś bardzo niejasnego - jeśli uważasz, że rozwiązania są obfite (lub że liczba rozwiązań jakiegoś podproblemu jest obfita), ale że ich systematyczne skonstruowanie może być trudne, wtedy warto mieć możliwość wybory losowe, aby ominąć problem systematycznej budowy. Ale uwaga, czasem powodem, dla którego wiesz, że istnieje wiele rozwiązań podproblemu, jest to, że istnieje dowód z zastosowaniem metody probabilistycznej . W takim przypadku wiesz, że liczba rozwiązań jest duża, redukując do tak naprawdę pomocnego algorytmu losowego!

  O ile nie masz innego sposobu uzasadnienia faktu, że liczba rozwiązań jest wystarczająca dla tych przypadków, nie ma prostego opisu, kiedy może pomóc losowy algorytm. A jeśli masz wystarczająco wysokie wymagania „pomocności” (przewaga wielomianowa), pytasz, czy , co jest nierozwiązanym problemem w teorii złożoności. $\mathsf P \ne \mathsf{BPP}$
  
  

• Czy istnieje zwięzłe stwierdzenie na temat tego, gdzie sparaliżowane algorytmy mogą pomóc?

  Tutaj może być nieco lepiej. Jeśli problem wygląda na to, że można go podzielić na wiele niezależnych podproblemów, można go sparaliżować - chociaż jest to niejasne kryterium, które można rozpoznać po „zobaczeniu”. Główne pytanie brzmi: czy będziesz wiedział, kiedy to zobaczysz? Czy zgadlibyście, że testowanie wykonalności układów równań liniowych na racjonalnościach jest nie tylko możliwe do zrównoleglenia, ale można je rozwiązać za pomocą obwodów o głębokości [por  . Comput. Złożony. 8 (str. 99-126), 1999 ]?$O(\log^2 n)$

  Jednym ze sposobów, w jaki ludzie próbują przedstawić intuicję na dużą skalę, jest zbliżenie się do pytania z przeciwnego kierunku i stwierdzenie, kiedy wiadomo, że sparaliżowany algorytm nie pomoże. W szczególności nie pomoże, jeśli problem ma z natury sekwencyjny aspekt. Ale ma to charakter kołowy, ponieważ „sekwencyjny” oznacza po prostu, że struktura, którą można zobaczyć w przypadku problemu, nie jest sparaliżowana.

  Ponownie nie ma prostego, kompleksowego opisu tego, kiedy sparaliżowany algorytm może pomóc. A jeśli masz wystarczająco wysokie wymagania „pomocności” (górna granica logarytmiczna limitu czasu, przy założeniu równoległości wielomianowej), to pytasz, czy $\mathsf P \ne \mathsf{NC}$ , która ponownie jest nierozwiązanym problemem w teorii złożoności .
  
  

Perspektywy „zwięzłych i poprawnych opisów, kiedy [X] jest pomocny” nie wydają się w tym momencie zbyt duże. Chociaż możesz zaprotestować, że jesteśmy tu zbyt surowi: z powodu domagania się więcej niż wielomianowej przewagi, nie moglibyśmy nawet twierdzić, że niedeterministyczne maszyny Turinga były „pomocne” (co jest oczywiście absurdalne). Nie powinniśmy domagać się tak wysokiego paska - przy braku technik skutecznego rozwiązywania problemu satysfakcji powinniśmy przynajmniej zaakceptować, że jeśli moglibyśmy w jakiś sposób uzyskać niedeterministyczną maszynę Turinga, rzeczywiście bylibyśmy bardzo pomocni . Różni się to jednak od dokładnego scharakteryzowania , dla których problemów uznalibyśmy to za pomocne.

O przydatności komputerów kwantowych

Cofając się o krok, czy jest coś , co możemy powiedzieć o tym, gdzie przydatne są komputery kwantowe?

Możemy powiedzieć: komputer kwantowy może zrobić coś interesującego tylko wtedy, gdy wykorzystuje strukturę problemu, niedostępną dla klasycznego komputera. (Wskazują na to uwagi o „globalnej własności” problemu, jak wspomniałeś). Ale możemy powiedzieć więcej: problemy rozwiązywane przez komputery kwantowe w modelu obwodu jednostkowego będą przedstawiać niektóre cechy tego problemu jako operatorów unitarnych . Cechy problemu niedostępne dla klasycznych komputerów będą wszystkie te, które nie mają (możliwego do udowodnienia) statystycznie istotnego związku ze standardową podstawą.

• W przypadku algorytmu Shora ta właściwość jest wartościami własnymi operatora permutacji, który jest zdefiniowany w kategoriach mnożenia przez pierścień.
• $\pm 1$

Nie jest szczególnie zaskakujące, że w obu przypadkach informacje dotyczą wartości własnych i wektorów własnych. Jest to doskonały przykład właściwości operatora, który nie musi mieć żadnego znaczącego związku ze standardową podstawą. Ale nie ma konkretnego powodu, dla którego informacja musi być wartością własną. Wszystko, co jest potrzebne, to umieć opisać jednolitego operatora, kodując pewną istotną cechę problemu, która nie jest oczywista z kontroli standardowej podstawy, ale jest dostępna w inny łatwo opisany sposób.

Ostatecznie wszystko to mówi, że komputer kwantowy jest przydatny, gdy można znaleźć algorytm kwantowy do rozwiązania problemu. Ale przynajmniej jest to ogólny zarys strategii znajdowania algorytmów kwantowych, co nie jest gorsze niż ogólne zarysy strategii, które opisałem powyżej dla algorytmów losowych lub sparaliżowanych.

Uwagi o tym, kiedy komputer kwantowy jest „pomocny”

Jak zauważyli inni ludzie, „gdzie kwantowe może pomóc” zależy od tego, co rozumiesz przez „pomoc”.

• Algorytm Shora jest często wyłapywany w takich dyskusjach i raz na jakiś czas ludzie podkreślają, że nie wiemy, że rozkład na czynniki nie jest możliwy do rozwiązania w czasie wielomianowym. Czy więc faktycznie wiemy, że „obliczenia kwantowe byłyby pomocne w obliczaniu liczb”?

  Pomijając trudności w realizacji komputerów kwantowych, myślę, że rozsądną odpowiedzią jest „tak”; nie dlatego, że wiemy, że nie można efektywnie rozkładać na czynniki przy użyciu konwencjonalnych komputerów, ale dlatego , że nie wiemy, jak to zrobić przy użyciu konwencjonalnych komputerów. Jeśli komputery kwantowe pomagają ci zrobić coś, do czego nie masz lepszego podejścia, wydaje mi się, że to „pomaga”.

• $O(2^{0.386\,n})$

  Być może algorytm Grovera jako taki nie jest szczególnie pomocny. Może być jednak pomocne, jeśli wykorzystasz go do opracowania bardziej sprytnych klasycznych strategii wykraczających poza poszukiwania brutalnej siły: stosując wzmocnienie amplitudy , naturalne uogólnienie algorytmu Grovera na bardziej ogólne ustawienia, możemy poprawić wydajność wielu nietrywialnych algorytmów dla SAT (patrz np. [ACM SIGACT News  36 (str. 103--108), 2005 - bezpłatny link PDF ]; czapka dla Martina Schwarza, który wskazał mi to odniesienie w komentarzach).

  Podobnie jak w przypadku algorytmu Grovera, amplifikacja amplitudy powoduje jedynie przyspieszenie wielomianowe: ale mówiąc praktycznie, nawet przyspieszenie wielomianowe może być interesujące, jeśli nie zostanie wymyte przez narzut związany z ochroną informacji kwantowej przed hałasem.

TL; DR: Nie, nie mamy dokładnego „ogólnego” stwierdzenia na temat tego, jakiego rodzaju problemy komputery kwantowe mogą rozwiązać , w kategoriach teorii złożoności. Mamy jednak przybliżony pomysł.

Zgodnie z podtytułem Wikipedii dotyczącym związku z teorią złożoności obliczeniowej

Klasa problemów, które mogą być skutecznie rozwiązane przez komputery kwantowe, nazywa się BQP , dla „ograniczonego błędu, kwantowego, czasu wielomianowego”. Komputery kwantowe uruchamiają tylko algorytmy probabilistyczne , więc BQP na komputerach kwantowych jest odpowiednikiem BPP („błąd ograniczony, probabilistyczny, czas wielomianowy”) na komputerach klasycznych. Definiuje się go jako zbiór problemów możliwych do rozwiązania za pomocą algorytmu wielomianowego, którego prawdopodobieństwo błędu jest ograniczone do połowy . Mówi się, że komputer kwantowy „rozwiązuje” problem, jeśli w każdym przypadku jego odpowiedź będzie prawidłowa z dużym prawdopodobieństwem. Jeśli to rozwiązanie działa w czasie wielomianowym, problem ten występuje w BQP.

BQP jest zawarty w klasie złożoności #P (a ściślej w powiązanej klasie problemów decyzyjnych P ^#P ), która jest podklasą PSPACE .

Podejrzewa się, że BQP jest rozłączny z NP-zupełnym i ścisłym nadzorem P, ale nie jest to znane. Zarówno rozkład na czynniki całkowite, jak i dyskretny log są w BQP. Oba te problemy są problemami NP podejrzewanymi o występowanie poza BPP, a zatem poza P. Oba podejrzewa się, że nie są NP-kompletne. Istnieje powszechne błędne przekonanie, że komputery kwantowe mogą rozwiązać problemy z NP-zupełnym czasem wielomianowym. Nie wiadomo, że to prawda, i ogólnie uważa się, że jest to nieprawda.

Zdolność komputera kwantowego do przyspieszania klasycznych algorytmów ma sztywne granice - górne granice złożoności obliczeń kwantowych. Przytłaczającej części klasycznych obliczeń nie można przyspieszyć na komputerze kwantowym. Podobny fakt dotyczy konkretnych zadań obliczeniowych, takich jak problem wyszukiwania, dla którego algorytm Grovera jest optymalny.

${\displaystyle O({\sqrt[{3}]{N}})}$$\displaystyle O({\sqrt {N}})$

Chociaż komputery kwantowe mogą być szybsze od klasycznych komputerów w przypadku niektórych typów problemów, te opisane powyżej nie mogą rozwiązać żadnego problemu, którego klasyczne komputery nie są w stanie rozwiązać. Maszyna Turinga może symulować te komputery kwantowe, więc taki komputer kwantowy nigdy nie rozwiąże nierozstrzygalnego problemu, takiego jak problem zatrzymania. Istnienie „standardowych” komputerów kwantowych nie obala tezy Kościoła-Turinga. Spekulowano, że teorie grawitacji kwantowej, takie jak teoria M lub grawitacja kwantowa w pętli, mogą pozwolić na budowę jeszcze szybszych komputerów. Obecnie definiowanie obliczeń w takich teoriach jest otwartym problemem ze względu na problem czasu, tzn. Obecnie nie istnieje oczywisty sposób opisania, co oznacza dla obserwatora przesłanie danych wejściowych do komputera, a następnie otrzymanie danych wyjściowych.

Jeśli chodzi o to, dlaczego komputery kwantowe mogą skutecznie rozwiązywać problemy BQP:

1. $n$$2n$

2. Zwykle obliczenia na komputerze kwantowym kończą się pomiarem. Prowadzi to do załamania stanu kwantowego do jednego ze stanów podstawowych. Można powiedzieć, że stan kwantowy jest mierzony we właściwym stanie z dużym prawdopodobieństwem.

Co ciekawe, jeśli teoretycznie zezwalamy na selekcję końcową (która nie ma żadnej praktycznej implementacji), otrzymujemy klasę złożoności po BQP :

W teorii złożoności obliczeniowej PostBQP jest klasą złożoności składającą się ze wszystkich problemów obliczeniowych możliwych do rozwiązania w czasie wielomianowym na kwantowej maszynie Turinga z ponownym wyborem i ograniczonym błędem (w tym sensie, że algorytm jest poprawny w co najmniej 2/3 czasu wejścia). Jednak Postselection nie jest uważany za cechę, którą posiadałby komputer realistyczny (nawet kwantowy), ale mimo to maszyny po selekcji są interesujące z teoretycznego punktu widzenia.

Chciałbym dodać to, co jaszczurka @Discrete wspomniała w sekcji komentarzy. Nie zdefiniowałeś wprost, co rozumiesz przez „może pomóc”, jednak ogólną zasadą w teorii złożoności jest to, że jeśli komputer kwantowy „może pomóc” w zakresie rozwiązywania w czasie wielomianowym (z błędem) w klasie problem może rozwiązać leży w BQP, ale nie w P ani BPP. Podejrzewa się, że ogólny związek między klasami złożoności, o których mówiliśmy powyżej :

$\text{P $\subseteq$ BPP $\subseteq$ BQP $\subseteq$ PSPACE}$

Jednak P = PSPACE, jest otwartym problemem w informatyce . Również związek między P i NP nie jest jeszcze znany.

Nie ma takiego ogólnego oświadczenia i jest mało prawdopodobne, że będzie ono wkrótce. Wyjaśnię, dlaczego tak jest. Aby uzyskać częściową odpowiedź na twoje pytanie, pomocne może być przeanalizowanie problemów w dwóch klasach złożoności: BQP i PostBQP.

Klasy złożoności najbliższe problemom, które można skutecznie rozwiązać za pomocą komputerów kwantowych modelu bramki kwantowej, to:

1. BQP ; i
2. PostBQP

BQP składa się z problemów, które można rozwiązać w czasie wielomianowym w obwodzie kwantowym. Najważniejsze algorytmy kwantowe, takie jak algorytm Shora, rozwiązują problemy w BQP.

$=$

Jednak obecnie nie ma metod praktycznego wdrożenia postselekcji, więc PostBQP jest bardziej teoretyczny.

Związek między P, NP i BQP jest obecnie nieznany; i otwarty problem rzędu P vs. NP. Jako ogólne stwierdzenie, jakie rodzaje problemów można rozwiązać bardziej efektywnie za pomocą komputerów kwantowych, należy odpowiedzieć na pytanie BQP vs. P (jeśli BQP = P, to najwyraźniej komputery kwantowe nie są bardziej wydajne (przynajmniej dla teoretyków złożoności))

Podobnie jak zdjęcie Blue, bardziej podoba mi się ten z magazynu Quanta , ponieważ wydaje się, że wizualnie podsumowuje to, o czym mówimy.