Algorytmy kwantowej aproksymacji

Ogólnie uważa się za mało prawdopodobne, aby komputery kwantowe były w stanie skutecznie rozwiązywać problemy związane z NP. W klasycznym przypadku jednym podejściem do rozwiązania takich problemów jest zastosowanie algorytmów aproksymacyjnych. Czy były jakieś badania algorytmów aproksymacyjnych wykorzystujących obliczenia kwantowe, w których kwantowość znacznie przyspiesza w porównaniu z klasycznymi metodami aproksymacji?

Przez „znaczący” rozumiem niekoniecznie wykładniczy, ale większy niż dla odpowiednich dokładnych algorytmów. Innymi słowy, jestem zainteresowany tym, czy złagodzenie wymogu, że nasz algorytm daje dokładne rozwiązanie, daje znaczącą przewagę algorytmom kwantowym.

Komentarz zaktualizowany do częściowej odpowiedzi:

Obecnie istnieje sporo pracy nad domniemaną (lub nie) kwantową wersją twierdzenia PCP: patrz na przykład ten post na blogu Scotta Aaronsona http://www.scottaaronson.com/blog/?p=139 lub ta odpowiedź autorstwa Peter Shor o MathOverflow /mathpro/45106/quantum-pcp-theorem/45167#45167

Odnośnie do algorytmów przybliżania kwantowego można zapoznać się z odnośnikiem „Algorytmy aproksymacyjne dla problemów z kompletnym QMA” http://arxiv.org/abs/1101.3884

Osobiście nie jestem świadomy żadnej pracy w kierunku algorytmów kwantowej aproksymacji w sensie aproksymacji względnych (vs aproksymacji addytywnych) (choć niekoniecznie oznacza to, że nie istnieją).

Zauważ, że jeśli intencją jest zaprojektowanie poli-time quantum ok ALG dla, powiedzmy, NP-trudne problemy, wiele problemów, takich jak MAX-CUT już obcisłe klasyczne ALG ok (zakładając unikalnych gier przypuszczeń lub przez PCP). Najprawdopodobniej więc warto zacząć od zbadania problemu, który ma lukę w znanym stosunku aproksymacji w stosunku do wyników twardości.

Drugim kierunkiem jest twardość aproksymacji - patrz np. Http://arxiv.org/abs/0811.3412 i http://arxiv.org/abs/1012.3319 dla częściowego pozytywnego i negatywnego postępu w odniesieniu do możliwego kwantowego twierdzenia PCP.

Niby trywialna odpowiedź, ale istnieje oszacowanie prawdopodobieństwa akceptacji obwodu kwantowego lub dowolnego z równoważnych problemów, takich jak aproksymacja wielomianu Jonesa lub rozwiązanie liniowego układu równań lub ślad mocy duża rzadka matryca.

Ponadto przybliżone zliczanie przyspiesza wiele algorytmów aproksymacyjnych opartych na próbkowaniu.

Algorytm przybliżenie optymalizacji algorytmów przedstawiony jest tutaj - papierowe prezenty algorytm kwantowy przybliżenie dla obiektywnej funkcji, które ma jednolitą bramy, która ma swoją lokalizację jako optimum funkcji celu. W przypadku stałego , który zmienia się w zależności od wielkości danych wejściowych, algorytm kwantowy znajduje przybliżenie do optymalnego rozwiązania. Przebadali aplikację pod kątem problemów z optymalizacją MaxSat i MAX-CUT (w niektórych przypadkach zwykłych wykresów). Funkcja celu dla problemu optymalizacji jest postrzegana jako specjalny operator jednostkowy, który koncentruje rozwiązanie, a tym samym osiąga przybliżenie.$i$