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

Jak sama nazwa wskazuje, to pytanie jest kontynuacją tego drugiego . Byłem zachwycony jakością odpowiedzi, ale czułem, że byłoby niezwykle interesujące, gdyby dodano spostrzeżenia dotyczące technik optymalizacji i aproksymacji, ale mogą one nie pasować do tematu, stąd pytanie.

Z odpowiedzi Blue:

ogólną zasadą w teorii złożoności jest to, że jeśli komputer kwantowy „może” pomóc w rozwiązaniu wielomianu (z błędem) w klasie problemów, którą może rozwiązać, leży w BQP, ale nie w P lub BPP

Jak to się ma do klas aproksymacyjnych? Czy istnieje jakaś konkretna topologiczna, numeryczna itp. Właściwość obliczeń kwantowych, którą można wykorzystać?

Jako przykład tego, o co mógłbym prosić (ale zdecydowanie nie ograniczając się do tego!), Weźmy algorytm Christofides : wykorzystuje on specyficzne właściwości geometryczne wykresu, na którym optymalizuje (symetria, nierówność trójkąta): sprzedawca podróżuje po realnym świecie . Ale sprzedawcy mają również ogromną masę, a my możemy poznać ich pozycję i pęd jednocześnie z wielką precyzją. Może model kwantowy mógłby również działać z innymi rodzajami wskaźników z bardziej łagodnymi ograniczeniami, takimi jak dywergencja KL ? W takim przypadku rozwiązanie byłoby nadal NP zakończone, ale optymalizacja dotyczyłaby szerszej topologii. Ten przykład jest może dalekim strzałem, ale mam nadzieję, że rozumiesz. Naprawdę nie wiem, czy to w ogóle ma sens, ale odpowiedź mogłaby również rozwiązać to w takim przypadku :)

ZWIĄZANE Z:

• Poziom korzyści zapewnianych przez wyżarzanie dla podróżujących sprzedawców

Quantum Przybliżony Optymalizacja Algorytm jest dobrym miejscem do rozpoczęcia analizy względną wydajność algorytmów kwantowych na problemy aproksymacji. Jednym z dotychczasowych wyników jest to, że przy p = 1 QAOA może teoretycznie osiągnąć współczynnik aproksymacji 0,624 dla MaxCut na 3-regularnych wykresach. Ten wynik uzyskano za pomocą wyliczenia siły brutalnej różnych możliwych przypadków. Nie jest to technika, którą łatwo uogólnić, więc stosunkowo niewiele wiadomo na temat wydajności QAOA w innych problemach.

W obecnej postaci QAOA wykorzystuje bardzo mało struktury w problemie optymalizacji kombinatorycznej i działa bardziej zgodnie z metodą bezpośredniego wyszukiwania. Jedną z możliwych konsekwencji jest to, że QAOA najlepiej byłoby zastosować w przypadku problemów o minimalnej strukturze. W tym przypadku nie ma nic, czego klasyczne algorytmy mogłyby użyć do przyspieszenia procesu wyszukiwania.