Czy od czasu Grovera i Shora nastąpił naprawdę przełomowy postęp w dziedzinie algorytmów kwantowych?

(Przepraszam za nieco amatorskie pytanie)

Studiowałem informatykę kwantową w latach 2004-2007, ale od tego czasu straciłem orientację w tej dziedzinie. W tamtym czasie było dużo szumu i dyskusji na temat QC potencjalnie rozwiązującej wszelkiego rodzaju problemy, przewyższającej klasyczne komputery, ale w praktyce były tylko dwa teoretyczne przełomy:

• Algorytm Shora, który wykazywał znaczne przyspieszenie, ale który miał ograniczone zastosowanie i nie był tak naprawdę przydatny poza rozkładem liczb całkowitych.
• Algorytm Grovera, który miał zastosowanie do szerszej kategorii problemów (ponieważ można go zastosować do rozwiązania problemów NP-Complete), ale który wykazywał jedynie przyspieszenie wielomianowe w porównaniu do klasycznych komputerów.

Omówiono także wyżarzanie kwantowe, ale nie było jasne, czy było to naprawdę lepsze niż klasyczne wyżarzanie symulowane, czy nie. QC oparte na pomiarach i reprezentacja stanu wykresu QC były również gorącymi tematami, ale nie udowodniono też niczego ostatecznego w tym zakresie.

Czy od tego czasu poczyniono postępy w dziedzinie algorytmów kwantowych? W szczególności:

• Czy istnieją jakieś naprawdę przełomowe algorytmy oprócz Grovera i Shora?
• Czy nastąpił postęp w określaniu relacji BQP do P, BPP i NP?
• Czy osiągnęliśmy jakiś postęp w zrozumieniu natury przyspieszenia kwantowego poza stwierdzeniem, że „musi to wynikać z uwikłania”?

Czy istnieją jakieś naprawdę przełomowe algorytmy oprócz Grovera i Shora?

To zależy od tego, co rozumiesz przez „naprawdę przełomowy”. Grover i Shor są szczególnie wyjątkowe, ponieważ były tak naprawdę pierwszymi przykładami, które wykazały szczególnie cenne typy przyspieszenia z komputerem kwantowym (np. Przypuszczalna wykładnicza poprawa Shora) i miały zabójcze aplikacje dla określonych społeczności.

Od tego czasu zaprojektowano kilka algorytmów kwantowych i myślę, że trzy są szczególnie godne uwagi:

• Algorytm BQP-complete do oceny wielomianu Jonesa w poszczególnych punktach. Wspominam o tym, ponieważ poza bardziej oczywistymi rzeczami, takimi jak symulacja Hamiltona, uważam, że był to pierwszy algorytm kompletny w BQP, więc naprawdę pokazuje pełną moc komputera kwantowego.

• Algorytm HHL do rozwiązywania równań liniowych. Jest to nieco zabawne, ponieważ bardziej przypomina podprogram kwantowy z kwantowymi wejściami i wyjściami. Jest jednak również kompletny pod względem BQP i w tej chwili cieszy się dużym zainteresowaniem ze względu na potencjalne zastosowania w uczeniu maszynowym i tym podobne. Wydaje mi się, że jest to najlepszy kandydat na naprawdę przełomowe osiągnięcie, ale to kwestia opinii.

• Chemia kwantowa . Wiem o nich bardzo niewiele, ale algorytmy znacznie się rozwinęły od czasu, kiedy wspomniałeś, i zawsze były cytowane jako jedna z przydatnych aplikacji komputera kwantowego.

Czy nastąpił postęp w określaniu relacji BQP do P, BPP i NP?

Zasadniczo nie. Wiemy, że BQP zawiera BPP i nie znamy związku między BQP a NP.

Czy osiągnęliśmy jakiś postęp w zrozumieniu natury przyspieszenia kwantowego poza stwierdzeniem, że „musi to wynikać z uwikłania”?

Nawet wtedy, gdy studiowałeś go pierwotnie, powiedziałbym, że był on bardziej precyzyjnie zdefiniowany. Istnieją (i były) dobre porównania między uniwersalnymi zestawami bramek (potencjalnie zdolnymi do przyspieszenia wykładniczego) i klasycznie symulowanymi zestawami bramek. Przypomnijmy na przykład, że bramy Clifford powodują splątanie, ale klasycznie można je symulować. Nie chodzi o to, że proste jest precyzyjne określenie tego, co jest wymagane w bardziej pedagogiczny sposób.

Być może poczyniono pewne postępy w zakresie innych modeli obliczeń. Na przykład model DQC1 jest lepiej zrozumiany - jest to model, który wydaje się mieć pewne przyspieszenie w stosunku do klasycznych algorytmów, ale jest mało prawdopodobne, aby był w stanie wykonać pełne obliczenia BQP (ale zanim wciągniesz się w szum, który możesz znaleźć w Internecie nie jest splot obecny w obliczeniach).

Z drugiej strony, stwierdzenie „to z powodu uwikłania” nadal nie jest całkowicie rozwiązane. Tak, dla kwantowego obliczania stanu czystego musi istnieć pewien splątanie, ponieważ w przeciwnym razie system jest łatwy do symulacji, ale dla mieszanych stanów separacyjnych nie wiemy, czy można je wykorzystać do obliczeń, czy też można je skutecznie symulować.

Można również zadać bardziej wnikliwe pytanie: czy osiągnęliśmy postęp w zrozumieniu, które problemy będą podatne na przyspieszenie kwantowe? Jest to nieco inne, ponieważ jeśli uważasz, że komputer kwantowy daje ci nowe bramki logiczne, których nie ma klasyczny komputer, to oczywiste jest, że aby uzyskać przyspieszenie, musisz użyć tych nowych bram. Nie jest jednak jasne, czy każdy problem podlega takim korzyściom. Które są? Istnieją klasy problemów, w których można spodziewać się przyspieszenia, ale myślę, że nadal zależy to od indywidualnej intuicji. To prawdopodobnie nadal można powiedzieć o klasycznych algorytmach. Napisałeś algorytm x. Czy jest lepsza klasyczna wersja? Może nie, a może po prostu tego nie zauważasz. Dlatego nie wiemy, czy P = NP.

Algorytm Kerenidis-Prakash był przełomowy, dopóki Ewin Tang nie naprawił ziemi:

Quanta Magazine: Major Quantum Computing Advance przestarzały przez nastolatka .