Algorytmy kwantowe oparte na transformatach innych niż transformaty Fouriera

19

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?

Sam Burville
źródło
10
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
5
@ScottAaronson skomentuj -> odpowiedz
Alessandro Cosentino
@ScottAaronson Świetnie, przyjrzę się im. Dzięki!
Sam Burville,
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:

16

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.Zp2)Zp

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.Zp2)Zp

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
Dzięki za zwrócenie na to uwagi. Wyjaśniłem akronim w ostatniej edycji.
Juan Bermejo Vega
4

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