Skocz do zawartości


Zdjęcie

Loop computing dla trudnych problemów obliczeniowych?


  • Zaloguj się, aby dodać odpowiedź
4 odpowiedzi w tym temacie

#1 Jarek Duda

Jarek Duda

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 670 postów

Napisano 04 listopad 2017 - 11:05

Ogólnie chciałoby się użyć fizyki dla rozwiązywania trudnych problemów obliczeniowych - podłożyć jej problem tak żeby rozwiązała go swoim naturalnym zachowaniem ... szybciej niż klasyczny komputer.

Nie jest to łatwe, komputery kwantowe (nie te adiabatyczne) dają nadzieję m.in. na faktoryzację w czasie wielomianowym algorytmem Shora, ale ogólnie nie znamy wiele takich podejść, najważniejsze pytanie to czy fizyka pozwala rozwiązywać problemy NP-zupełne w czasie wielomianowym (?).

 

Wydaje się naturalnym sposobem konwersji problemu NP na system fizyczny jest szukanie punktu stałego pętli - wrzuciłem to ostatnio na stackexchange, odpisał sam Peter Shor, na razie konkluzja jest że to podejście nie jest znane w literaturze i nie wiadomo czy ma szansę działać (?):

https://physics.stac...for-np-problems

 

W problemie NP łatwo (czas wielomianowy) przetestować czy dany input (ciąg bitów) jest satysfakcjonujący, trudnością jest to że istnieje wykładniczo wiele takich ciągów, ale np. tylko jeden z nich jest satysfakcjonujący - pytanie jak efektywnie sprawdzać istnienie takiego satysfakcjonującego ciągu?

Wyobraźmy sobie że tester (czy input jest satysfakcjonujący) jest zaimplementowany jako kilka warstw bramek logicznych (np. w postaci 3-SAT), teraz połączmy kabelkami w pętlę w ten sposób:

WQFXL.jpg

 

Zwykle elektronika ma zegar synchronizujący działanie - powyższy układ testowałby jedno wejście na cykl, aż do do osiągnięcia satysfakcjonującego, będącego punktem stałym takiej pętli.

Czyli z zegarem rozwiązalibyśmy problem w czasie wykładniczym ... ale co jeśli taki układ byłby bez zegara/synchronizacji?

Chyba nie ma powodu żeby przechodził przez wykładniczą ilość możliwości (?) - powinien się stabilizować dużo szybciej (?)

Pytanie czy taki ustabilizowany przepływ elektronów będzie się (wystarczająco często?) stabilizował na rozwiązaniu naszego problemu?

 

ps. slajdy o nietypowych podejściach do trudnych problemów obliczeniowych: https://www.dropbox....8/pnpslides.pdf

Jakieś inne obiecujące nietypowe podejścia?


  • 0

Reklamy Google

#2 lost

lost

    Górnik

  • Nowi użytkownicy
  • Pip
  • 3 postów

Napisano 14 listopad 2017 - 11:48

Prezentuje się to niezwykle ciekawie. Zobaczymy jak ta technologia wyewoluuje w przyszłości.


  • 0

#3 Jarek Duda

Jarek Duda

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 670 postów

Napisano 14 listopad 2017 - 12:50

Ogólnie jest kilka opcji/pytań:

1) czy taki układ bez zegara będzie zawsze sam się synchronizował? (ostatecznie zachowując jak układ z zegarem)
2) jeśli nie to czy będzie "szumiał" w nieskończoność, czy może jednak powinien zbiec do stabilnego przepływu? - wyobrażając sobie że tam są amperomierze, wskazywałyby one niekończące się fluktuacje, czy ostatecznie stabilizowałyby się na stałych wartościach?
3) Jeśli będą się stabilizowały, to jak szybko i czy taki finalny stan będzie odpowiadał rozwiązaniu naszego problemu?

Osobiście myślę że wszystkie trzy opcje mogą występować w zależności od szczegółów/parametrów, ale obawiam się że w 3) przypadku zwykle nie będzie rozwiązywał naszego problemu, "kłamiąc" na kilku bramkach: ustawiając je pomiędzy dyskretnymi wartościami.

 

Jest ogólny problem w konwertowaniu trudnych problemów na ciągłą optymalizację (też np. w adiabatycznych komputerach kwantowych) - zwykle pojawia się wykładnicza ilość lokalnych minimów (w przeciwnym razie też klasycznie moglibyśmy rozwiązać w czasie wielomianowym).

Dobrze to widać w problemie subset-sum (chyba trudniej o coś prostszego): mamy (duże) liczby naturalne k_i, pytanie czy hiperpłaszczyzna prostopadła do wektora k przecina {-1,1}^n ?
Jako problem globalnej optymizacji: na hiperpłaszczyźnie minimalizujemy odległość do najbliższego wierzchołka.
Schodząc po gradiencie, mamy mamy zwykle wykładniczo wiele atraktorów odpowiadających różnym wierzchołkom.
Interesujący nas atraktor: do minimalnej odległości zero, zwykle nie wyróżnia się wystarczająco żeby ułatwić szukanie.

ps. także sceptyczna praca Scotta Aaronsona odnośnie różnych fizycznych podejść: arxiv.org/pdf/quant-ph/0502072.pdf


  • 0

#4 thikim

thikim

    Kierownik robót

  • Użytkownicy
  • PipPipPipPipPipPip
  • 3938 postów

Napisano 15 listopad 2017 - 18:24

Osobiście myślę że wszystkie trzy opcje mogą występować w zależności od szczegółów/parametrów, ale obawiam się że w 3) przypadku zwykle nie będzie rozwiązywał naszego problemu

Też bym na to stawiał. Trzeba więc dobrze dobierać parametry.


Użytkownik thikim edytował ten post 15 listopad 2017 - 18:24

  • 0

#5 Jarek Duda

Jarek Duda

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 670 postów

Napisano 18 listopad 2017 - 11:35

Analogiczny problem dotyczy głośnych obecnie adiabatycznych komputerów kwantowych ( https://en.wikipedia...tum_computation ): podczas gdy w publikacjach rozważają sytuacje z dosłownie kilkoma lokalnymi minimami energetycznymi, trudne problemy zawierałyby ich wykładniczo wiele, np. 2^1000 ...

Pewnie też dlatego ostatnio już raczej mówią tylko o innych motywacjach - symulacje fizyczne ... zobaczymy.

 

Trochę inaczej wygląda sytuacja "tradycyjnych komputerów kwantowych", jak algorytm Shora - przynajmniej w teorii pozwalający na faktoryzację w czasie wielomianowym, podczas gdy klasycznie znamy na razie tylko wykładnicze - dodatkowo problem jest istotny ponieważ na jego trudności opiera się sporo używanej obecnie kryptografii (RSA).

Tutaj jest diagram co tam się dzieje od strony kwantowej ( https://www.physicsf...n-of-qm.922555/ ): EW7qP.png

 

Robimy superpozycję wszystkich możliwych wartości, liczymy funkcję klasyczną na tych wartościach, potem mierzymy wartość tej funkcji klasycznej.

Ten pomiar ograniczył oryginalną superpozycję 2^n możliwości, do superpozycji tylko tych które dają stałą zmierzoną wartość - taka ograniczona superpozycja jest zwykle okresowa i ten okres (mierzony QFT) pozwala powiedzieć coś o dzielnikach N - rozwiązując problem faktoryzacji.

Ciekawe jest to z perspektywy kauzalnej - rozgałęziamy obliczenia, na jednej gałęzi coś robimy (pomiar ograniczający zespół), co istotnie wpływa na drugą gałąź obliczeń ...

 

Jednak oczywiście jest kilka problemów, jak dekoherencja, konieczność korekcji błędów ... która wymaga dodatkowych bramek, które tworzą nowe miejsca dla potencjalnych błędów ...

Dalej obliczenia kwantowe (klasyczna funkcja) wymagają odwracalnych bramek, które wymagają olbrzymiej ilość auxiliary qbits (1-2 zmienne na bramkę jak OR) ... które pewnie w końcu skolapsują ("zostaną zmierzone") ... znowu ograniczająć oryginalną superpozycję - psując zamierzone obliczenia ...

 

Podsumowując, jestem dość sceptyczny odnośnie istotnego przyśpieszenia obliczeń (wykładnicza -> wielomianowa złożoność) za pomocą komputerów kwantowych ...

Jakaś iskierka nadziei tli się w możliwości zamknięcia pętli "loop computing" w czasie ... np. skoro zwykły laser pozwala przesyłać informację w przód w czasie oraz wierzymy że fizyka jest fundamentalnie CPT-symetryczna, teoretycznie wydaje się (?) możliwe zbudowanie analogu CPT lasera ( https://physics.stac...lated-absorbtio ) do przesyłania informacji wstecz ... ale nawet zakładając że udałoby się zbudować taki time-loop computer, mam mieszane uczucia czy udałoby się go uchronić przed problemem wykładniczej ilości lokalnych optimów (że kilka bramek kłamie) ?


  • 0