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.

cc.complexity-theory quantum-computing query-complexity

— blk
źródło

Przypadkowo głosowałem za zamknięciem jako „nie na temat”, ponieważ myślałem, że głosuję na inne pytanie i kliknąłem złą kartę. Myślę, że to świetne pytanie i doskonale na ten temat , ale system nie pozwala mi wycofać mojego przypadkowego głosowania.

— Artem Kaznatcheev

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

— Robin Kothari
źródło

Chcę tu tylko coś podkreślić. Jeśli celem jest wyznaczenie dolnej granicy algorytmu Simona za pomocą metody wielomianowej, zamień go w przeciwnika, a następnie ponownie przekształć w algorytm wykresu uczenia się, prawdopodobnie nie zadziałałoby. (Gdybym to był ja, znalazłbym to bezpośrednio w ramce wykresu uczenia się). Nasza redukcja dotyczy metody wielomianowej do multiplikatywnej metody przeciwnika (która jest silniejsza niż dodatek ogólny). Nie znam związku z programami span, ponieważ multiplikatywna metoda przeciwnika nie jest SDP.

— Loïck,

@ Loïck: Racja. Nawet jeśli zostanie znaleziona optymalna addytywna matryca przeciwnika dla problemu Simona, nie jest jasne, jak skonstruować w tym celu program zakresu (lub wykres uczenia się).

— Robin Kothari,