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

17

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ść.
Piotr Migdal
źródło
8
Może to pomaga.
aelguindy
IIRC pojawiło się pytanie, jakie komputery kwantowe można wykorzystać do wydajnego obliczania. Możesz na to rzucić okiem.
Kaveh
Czy to jest pomocne?
Kaveh
1
@Kevah: Szczerze mówiąc, niewiele. Moje pytanie kładzie nacisk na aplikacje w świecie rzeczywistym (a więc nie tylko tam, gdzie „istnieje przyspieszenie dla konkretnego algorytmu”, ale także gdy przyspieszenie rozwiązuje konkretny problem praktyczny).
Piotr Migdal
1
Konstruowanie optymalnego drzewa filogenetycznego .
Saeed

Odpowiedzi:

17

Skutecznie symulująca mechanikę kwantową.

Tyson Williams
źródło
to jest odpowiedź na std / folklor / ironiczny / glib / near-joke i zastanawiam się, kto ją stworzył. czy ktoś ma jakieś referencje? Kwestionuję to, jak to nie jest banalnie możliwe, w następujący sposób. Obliczenia qm koncentrują się głównie na parach interakcji kubitowych (bramek). aby udowodnić, że ogólnie można skutecznie symulować QM, trzeba by pokazać, że można skutecznie symulować wszystkie możliwe interakcje n-mądre z interakcjami parami. nie widziałem tego udowodnionego w gazecie.
vzn
2
@vzn: w większości interakcji fizycznych ograniczenie do interakcji 2-cząstkowych jest dobrym przybliżeniem, wystarczającym do symulacji opartych tylko na lokalnych interakcjach 2-ciałowych, które mają sens (interakcje obejmujące więcej terminów zwykle rozpadają się bardzo szybko). Zatem istnienie ogólnych interakcji n-ciała nie unieważnia idei symulacji.
Marcin Kotowski,
@vzn Nie mam referencji, ale Scott Aaronson mówi to i wspomniał o tym w swoim ostatnim artykule w Timesie .
Tyson Williams
2
@vzn, była to oryginalna aplikacja, o której myśli kwantowej pomyślał Richard Feynman. To jest link do artykułu, w którym zaproponował ideę komputerów kwantowych ( springerlink.com/content/t2x8115127841630 ), a także możesz to sprawdzić ( wisdom.weizmann.ac.il/~naor/COURSE/feynman-simulation.pdf )
Marcos Villagra,
1
@vzn Odpowiedź jest prawidłowa, ale literatura na temat cyfrowej symulacji kwantowej w dużym stopniu wystarczy podsumować za pomocą komentarzy. Poleciłbym otwarcie nowej dyskusji, ponieważ temat jest interesujący.
Juan Bermejo Vega
8

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.

Philippe Lamontagne
źródło
8

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)

Robin Kothari
źródło
2

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.

Juan Bermejo Vega
źródło
1
Proszę przyjąć moje zaproszenie do przyłączenia się: quantumcomputing.stackexchange.com .
Rob
-6

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(N)Ω(N)

vzn
źródło
3
„Teoria złożoności QM jest lepiej rozwinięta, kompletność NP w jakiś sposób do niej„ pasuje ”. Istnieje dobrze rozwinięta teoria kwantowych interaktywnych systemów dowodowych (klasy złożoności, takie jak QMA itp.), Które uogólniają klasyczne klasy złożoności, takie jak NP, PSPACE itp. W tym sensie kompletność NP pasuje dokładnie do teorii złożoności kwantowej. (z drugiej strony zgadzam się, że w polu algorytmów kwantowych brakuje spójności, ale algorytmy kwantowe i złożoność kwantowa to różne podpola).
Marcin Kotowski,
zgodzili się, że istnieją dobrze zdefiniowane klasy i hierarchie QM, które odzwierciedlają klasy inne niż QM, ale ich relacja do („klasy względnej”) „klasycznych” klas innych niż QM i NP jest w dużej mierze kwestią otwartą, jak stwierdzono.
vzn
1
Co rozumiesz przez „coraz bardziej nieustrukturyzowane bazy danych”? Baza danych wygląda jak coś uporządkowanego z definicji.
Juan Bermejo Vega