Algorytmy kwantowe oparte na transformatach innych niż transformaty Fouriera

W obliczeniach kwantowych i informacjach kwantowych Nielsena i Chuanga twierdzą, że wiele algorytmów opartych na kwantowych transformacjach Fouriera opiera się na właściwości niezmienniczości Coseta transformatów Fouriera i sugeruje, że właściwości niezmienniczości innych transformacji mogą dać nowe algorytmy.

Czy przeprowadzono jakieś owocne badania nad innymi transformacjami?

quantum-computing quantum-information

— Sam Burville
źródło

Tak. Yi-Kai Liu, Shelby Kimmel i inni opracowali algorytmy kwantowe oparte na transformacjach falkowych, a Stephen Jordan opracował algorytmy kwantowe oparte na transformacji Clebscha-Gordana. Możesz wyszukiwać referencje w Google, w przeciwnym razie inni mogą je dostarczyć. Oczywiście problemy rozwiązane przez te algorytmy nie są tak głośne jak faktoring i dyskretny log (w przeciwnym razie już o tym słyszeliście).

— Scott Aaronson

@ScottAaronson skomentuj -> odpowiedz

— Alessandro Cosentino

@ScottAaronson Świetnie, przyjrzę się im. Dzięki!

— Sam Burville,

Wyrocznie hamiltonowskie?

— vzn

Yi-Kai Liu opracował algorytmy kwantowe wykorzystujące transformację krzywoliniową (patrz pełna wersja na arXiv lub krótka wersja z FOCS).

— Māris Ozols,

Odpowiedzi:

Chciałbym dodać więcej odniesień do komentarza Scotta:

Rzeczywiście, transformacje Clebscha-Gordana (które można traktować jako wielorejestrowe kwantowe transformaty Fouriera) są użytecznym narzędziem w projektowaniu algorytmów kwantowych dla problemów niehabelistycznych ukrytych podgrup (HSP).

Transformaty Clebscha-Gordana zostały wykorzystane przez Grega Kuperberga i Odeda Regeva do rozwiązania dwuściennego HSP w czasie podwykładniczym (jeszcze superpolinomialnym). Te algorytmy kwantowe nie są wydajne, ale mają większą złożoność zapytań niż algorytmy klasyczne.
Dave Bacon użył także transformacji Clebscha-Gordana do rozwiązania problemu ukrytej podgrupy (HSP) w grupie Heisenberga w czasie wielomianowym. Mogę polecić ten papier, ponieważ jest dość jasny. $\mathbb{Z}_p^2\rtimes \mathbb{Z}_p$

Piszę również, aby dodać, że nie powinniśmy zapominać, że zarówno kwantowe transformaty Fouriera, jak i transformacje Clebscha-Gordana nie zawsze są niezbędne, nawet jeśli mogą być bardzo przydatne.

W algorytmie Shora (lub nawet w estymacji fazy kwantowej) transformaty Fouriera można zastąpić testami Hadamarda , dlatego stosowanie bram Hadamarda zamiast transformacji Fouriera: ta sztuczka jest spowodowana przez Kitaeva i możesz przeczytać o tym tutaj .
Istnieje jeszcze inny wydajny algorytm dla HSP w stosunku do , autorstwa Bacon, Childs, Van Dam, który nie używa transformacji Clebsch-Gordana. Zamiast tego algorytm wykorzystuje pewien rodzaj potężnego POVM, znany jako Pretty Good Measurement. $\mathbb{Z}_p^2\rtimes \mathbb{Z}_p$

Oczywiście ta lista jest prawdopodobnie niekompletna. Mam nadzieję, że ktoś wskaże inne wyniki, o których jeszcze nie wspomniano.

— Juan Bermejo Vega
źródło

HSP = problem ukrytej podgrupy

— vzn

Dzięki za zwrócenie na to uwagi. Wyjaśniłem akronim w ostatniej edycji.

— Juan Bermejo Vega

Nie jestem pewien, czy jest to bezpośrednio związane z twoim pytaniem, ale przeczytanie go skłoniło mnie do zastanowienia się nad artykułem Petera Høyera, który przeczytałem kilka lat temu. Pokazuje w nim, w jaki sposób najpopularniejsze algorytmy kwantowe, takie jak Grovera lub Shora, stosują ten sam wzorzec stosowania czegoś, co nazywa „sprzężonymi operatorami”, i buduje nowe algorytmy również w oparciu o ten sam wzorzec.

Jak powiedziałem, minęło kilka lat, odkąd go przeczytałem, więc mój opis jest nieco niechlujny, ale oto link na wypadek, gdybyś chciał to sprawdzić.

http://journals.aps.org/pra/abstract/10.1103/PhysRevA.59.3280

— Philippe Lamontagne
źródło