Zastosowania obliczeń kwantowych w świecie rzeczywistym (z wyjątkiem bezpieczeństwa)

Załóżmy, że zbudowaliśmy uniwersalny komputer kwantowy.

Z wyjątkiem problemów związanych z bezpieczeństwem (kryptografia, prywatność, ...), które z obecnych problemów w świecie rzeczywistym mogą skorzystać z korzystania z niego?

Interesują mnie zarówno:

• problemy obecnie nierozwiązywalne dla praktycznego wejścia,
• problemy, które są obecnie rozwiązywane, ale znaczne przyspieszenie znacznie poprawiłoby ich użyteczność.

Skutecznie symulująca mechanikę kwantową.

Brassard, Hoyer, Mosca i Tapp wykazali, że uogólnione poszukiwanie Grovera, zwane amplifikacją amplitudy, można wykorzystać do uzyskania kwadratowego przyspieszenia w dużej klasie klasycznej heurystyki. Intuicja stojąca za ich pomysłem polega na tym, że klasyczna heurystyka używa losowości do szukania rozwiązania danego problemu, więc możemy użyć wzmocnienia amplitudy do wyszukiwania zestawu losowych ciągów dla takiego, który sprawi, że heurystyka znajdzie dobre rozwiązanie. Daje to kwadratowe przyspieszenie w czasie działania algorytmu. Aby uzyskać więcej informacji, zobacz sekcję 3 dokumentu, do którego link znajduje się powyżej.

Symulowanie układów kwantowych!

Zauważyłem, że w innej odpowiedzi, która o tym wspominała, było kilka komentarzy na temat tego, czy to prawda, ponieważ jest to nieoczywiste twierdzenie. I ludzie prosili o referencje. Oto kilka referencji.

Oryginalna propozycja Feynmana:

Feynman, R .: Symulacja fizyki za pomocą komputerów. Int. J. Theor. Phys. 21 (6) (1982) 467–488

Wydajne algorytmy dla wszystkich układów kwantowych określonych przez „lokalnych” hamiltonianów. (Lloyd wyjaśnia również, że każdy system zgodny ze szczególną i ogólną teorią względności ewoluuje zgodnie z lokalnymi interakcjami).

Lloyd, S .: Uniwersalne symulatory kwantowe. Science 273 (5278) (1996) 1073–1078

Dalsze uogólnienie na rzadkie hamiltoniany, które są bardziej ogólne niż lokalne hamiltoniany:

Aharonov, D., Ta-Shma, A .: Adiabatyczne generowanie stanu kwantowego i wiedza o zerowym poziomie statystycznym. W: Proc. 35. STOC, ACM (2003) 20–29

Dalsza lektura:

Berry, D., Ahokas, G., Cleve, R., Sanders, B .: Efektywne algorytmy kwantowe do symulacji rzadkich hamiltonianów. Commun Matematyka Phys. 270 (2) (2007) 359–371

Childs, AM: Kwantowe przetwarzanie informacji w ciągłym czasie. Praca doktorska, Massachusetts Institute of Technology (2004)

Wizjonowanie jest zarówno niebezpieczne, jak i polemiczne w tej dziedzinie, dlatego powinniśmy być ostrożni w tym temacie. Jednak niektóre algorytmy Q z wielomianowymi przyspieszeniami mają interesujące potencjalne zastosowania.

Wiadomo, że wyszukiwania Grovera można użyć do wielomianowego przesądzenia rozwiązania problemów NP-zupełnych [1] . Jest to udowodnione dla 3-SAT w [2] . Niektóre zastosowania SAT, zapożyczone z [3] , to: sprawdzanie równoważności obwodu , automatyczne generowanie wzorca testowego , sprawdzanie modelu za pomocą liniowej logiki czasowej , planowanie w sztucznej inteligencji i haplotyping w bioinformatyce . Chociaż niewiele wiem na te tematy, ta linia badań wydaje mi się raczej praktyczna.

Istnieje również algorytm kwantowy do oceny drzew NAND z przyspieszeniem wielomianowym w porównaniu z klasycznym obliczeniem [ 8 , 10 , 11 ]. Drzewo NAND jest przykładem drzewa gry, bardziej ogólnej struktury danych wykorzystywanej do badania meczów gier planszowych, takich jak Chess and Go. Wydaje się prawdopodobne, że tego rodzaju przyspieszenia można wykorzystać do zaprojektowania potężniejszych graczy. Czy może to zainteresować niektórych twórców gier kwantowych?

Niestety, granie w gry w rzeczywistości nie jest dokładnie tym samym, co ocenianie drzew: istnieją komplikacje, np. Jeśli Twoi gracze nie stosują optymalnych strategii [ 12 ]. Nie widziałem żadnego badania uwzględniającego scenariusz z życia, więc trudno jest powiedzieć, jak korzystne jest przyspieszenie z [ 8 ] w praktyce. To może być dobry temat do dyskusji.

myślę, że podniosłeś doskonałe pytanie na granicy badań QM (częściowo wskazywane dotychczas przez brak odpowiedzi), ale nie zostało to całkowicie formalnie zdefiniowane ani uchwycone jako problem. pytanie brzmi „co dokładnie algorytmy QM mogą obliczyć wydajnie i tak?” pełna odpowiedź nie jest znana i jest aktywnie ścigana. niektóre z nich związane są z (otwartymi pytaniami) złożonością klas związanych z QM.

tak by się stało, że zdefiniowano nieco formalne pytanie. jeśli można wykazać, że klasy QM są równoważne „znacznie potężnym” klasom innym niż QM, to jest Twoja odpowiedź. ogólnym tematem tego typu wyników będzie klasa „niezbyt trudna w QM”, równoważna klasie „trudna w QM”. istnieją różne tego typu separacje klas otwartej złożoności (być może ktoś inny może zaproponować je bardziej szczegółowo).

Coś dziwnego w obecnej wiedzy o QM na temat algorytmów kwantowych polega na tym, że istnieje pewien dziwny zestaw algorytmów, o których wiadomo, że działają w QM, ale wydaje się, że nie ma w nich zbyt dużej spójności / spójności. wydają się dziwne i pod pewnymi względami odłączone. nie ma widocznej „ogólnej zasady” dla „problemów, które można wyliczyć w QM, są na ogół w tej formie”, pomimo uzasadnionych oczekiwań, że ktoś może tam być.

np. kontrastuje to z teorią kompletności NP, która jest znacznie bardziej spójna w porównaniu. wydaje się, że być może lepiej rozwinięta teoria QM uzyskałaby większe poczucie spójności przypominające teorię kompletności NP.

silniejszym pomysłem może być to, że ostatecznie, gdy teoria złożoności QM zostanie lepiej rozwinięta, kompletność NP w jakiś sposób do niej „pasuje”.

dla mnie najbardziej ogólne przyspieszenie QM lub szeroko stosowana strategia, jaką widziałem, wydaje się być algorytmem Groversa, ponieważ tyle praktycznego oprogramowania jest związane z zapytaniami db. i pod pewnymi względami coraz bardziej „nieustrukturyzowane”:

$O(\sqrt{N})$$Ω(N)$