Czy algorytmy kwantowe z przyspieszeniem wykładniczym można ponownie odczytać za pomocą programów zakresu?

Wiadomo, że dolna granica ogólnego przeciwnika charakteryzuje złożoność kwantowych zapytań z powodu przełomowej pracy Reichardta i in. Ta sama linia pracy ustanawia również połączenia ze strukturą programu zakresu do projektowania algorytmów kwantowych.

Wiele interesujących algorytmów kwantowych, w tym z przyspieszeniem wykładniczym, takich jak algorytm Simona i algorytm Shora do wyszukiwania okresów, można wyrazić w kwantowym modelu zapytań.

Czy jest jakaś praca pokazująca dolne granice dla tych algorytmów w ogólnym modelu przeciwnika? Czy jest jakaś praca w celu uzyskania algorytmów Simona lub Shora w ramach programu span?

Najwyraźniej tylko algorytmy kwantowe z przyspieszeniem wielomianowym, takie jak algorytmy Grovera, zostały ponownie wyprowadzone przy użyciu frameworku programów (lub wykresu uczenia Belowa).

Istnieje praca Koriana i in. pokazując dolne granice Simona za pomocą metody wielomianowej, ale najwyraźniej nie ma znanego sposobu na przeniesienie dolnych granic wielomianowej metody na ogólne dolne granice przeciwnika.

Myślę, że w twoim pytaniu są co najmniej 3 pytania. Nie mam zadowalającej odpowiedzi na wszystkie z nich, więc nie jest to pełna odpowiedź. Mamy nadzieję, że będzie więcej odpowiedzi, które odpowiedzą na wszystkie pytania.

Pytanie w tytule: Czy algorytmy kwantowe z przyspieszeniem wykładniczym mogą być ponownie odczytane za pomocą programów zakresu?

Jak zauważyłeś, ogólna granica przeciwnika charakteryzuje złożoność kwantowych zapytań wszystkich problemów decyzyjnych, w tym problemów obietnic, dla których mamy wykładnicze przyspieszenia. Zasadniczo istnieje program rozpinający, który rozwiązuje problem ukrytej podgrupy Abelian, który jest pytaniem stosowanym w algorytmach Simona i Shora. Ale czy istnieje wyraźny program zakresu dla tego, jest twoje następne pytanie.

Czy jest jakaś praca w celu uzyskania algorytmów Simona lub Shora w ramach programu span?

Nie słyszałem o takich wynikach. Nie znam programu zakresu dla problemu Simona ani żadnego innego AHSP.

Czy istnieje sposób na przełożenie dolnych granic metody wielomianowej na ogólne dolne granice przeciwnika?

Tak, wierzę, że jest. Wydaje mi się, że nie mogę znaleźć gazety, która ma taki wynik, ale mogę podać link do wykładu wygłoszonego przez Jérémie Roland . W streszczeniu przemawia:

... Dokładniej, pokażemy, że multiplikatywna metoda przeciwnika, odmiana oryginalnej metody przeciwnika, uogólnia nie tylko uogólnioną metodę przeciwnika, ale także metodę wielomianową, tak że zasadniczo obejmuje wszystkie znane metody dolnej granicy. Dlatego zapewnia to konstruktywne podejście do rzucania wielomianowych dolnych granic w ramy metody przeciwnika.

Aktualizacja : Artykuł jest teraz dostępny online: Wyraźna relacja między wszystkimi dolnymi granicami złożoności kwantowej złożoności zapytań Loïcka Magnina i Jérémie Rolanda