Loop computing dla trudnych problemów obliczeniowych?

[Jarek Duda 139]

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.stackexchange.com/questions/365542/continuous-time-loop-computer-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:

 

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.com/s/nwyxf44u38i42d8/pnpslides.pdf

Jakieś inne obiecujące nietypowe podejścia?

[lost 2]

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

[Jarek Duda 139]

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

[thikim 119]

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.

Edytowane 15 listopada 2017 przez thikim

[Jarek Duda 139]

Analogiczny problem dotyczy głośnych obecnie adiabatycznych komputerów kwantowych ( https://en.wikipedia.org/wiki/Adiabatic_quantum_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.physicsforums.com/threads/shors-algorithm-and-similar-exploitation-of-qm.922555/ ):

 

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.stackexchange.com/questions/308106/causality-in-cpt-symmetry-ananlogue-of-free-electron-laser-stimulated-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) ?

[Jarek Duda 139]

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 ...

Wrzuciłem tą swoją obiekcję na stackexchange ... i właśnie potwierdził mi ją sam Peter Shor:

https://physics.stackexchange.com/questions/369590/shors-algorithm-why-doesnt-the-final-collapse-of-the-auxiliary-qubits-crippl/

 

W skrócie odpowiedział że konieczne jest ich "uncompute" do jakichś ustalonych wartości ...

Tyle że tego "drobnego wymogu" wydaje się że nikt nie rozważał w literaturze ... i jest niemożliwy do realizacji: ostatecznie mamy mieć permutację, czyli nie wolno nam zafiksować większości bitów!

Czyli chyba RSA jest bezpieczne - Shor z niemożliwego do realizacji stał się jeszcze bardziej niemożliwy

 

Ps. tutaj jest obiekcja do adiabatycznych komputerów kwantowych - podczas gdy wymagają rozsądnie dużej "spectral gap", w trudnych problemach ona chyba zawsze maleje wykładniczo: https://physics.stackexchange.com/questions/370633/adiabatic-qc-are-there-known-difficult-problems-with-spectral-gap-not-exponenti

Czyli chyba bańka komputerów kwantowych zbliża się do pęknięcia ... chyba ostatnia nadzieja to kontrowersyjne time-loop computing ...

[thikim 119]

wrzuciłem to ostatnio na stackexchange, odpisał sam Peter Shor,

To już drugi raz

Miło że tu piszesz o tych swoich przemyśleniach. Dla przytłaczającej większości z nas są to zbyt trudne sprawy do ogarnięcia ale zawsze parę zdań daje się w tym wyłowić takich które są w stanie zrozumieć i inni. I pcha ich to do przodu.

I to jest bardzo pozytywne w Twoich wpisach.

Edytowane 26 listopada 2017 przez thikim

[Jarek Duda 139]

Tym razem odpisał odnośnie własnego algorytmu, dodając "niewinny" wymóg (uncomputing auxiliary qubits to fixed values) który chyba jest zupełnie  ignorowany w literaturze ... i niemożliwy do spełnienia.

Obawiam się że komputery kwantowe mają podobny status jak np. zimna fuzja ... tyle że dzięki lepszemu PR magii QM udało im się zbudować potężną niszę ekologiczną ...

[Jajcenty 314]

 

 

Obawiam się że komputery kwantowe mają podobny status jak np. zimna fuzja ... tyle że dzięki lepszemu PR magii QM udało im się zbudować potężną niszę ekologiczną ...

 

Na zimną fuzję nie ma takich nakładów. Mam nadzieję, że biznes jest racjonalny i nie sponsoruje badań prowadzących w krzaki. 

[Jarek Duda 139]

Niestety nauka działa innymi mechanizmami - opartymi na "ciekawości".

 

Np. wyobraźmy sobie że jest problem fizyczny, na który ktoś znalazł prostą odpowiedź - pewnie parę osób zacytuje, ale już np. doktoratu/grantu z tego nie będzie ...

A co jeśli obok pojawi się "ciekawe rozwiązanie" - egzotyczne, niewiele wiadomo, można na tym napisać tysiące publikacji/doktoratów/grantów - ich autorzy budują niszę wmawiającą że to jest jedyny słuszny sposób myślenia ... i po kilku dekadach nikt już nawet nie pamięta o prostym rozwiązaniu ...

 

Powyższy przykład odnosi się do grawitomagnetyzmu zaproponowanego w 1893 przez Heavisidea ( https://en.wikipedia.org/wiki/Gravitoelectromagnetism ) ... którego to tak naprawdę potwierdziło np. Gravity Probe B w 2005 jako przybliżenie ogólnej teorii względności Einsteina - wymagającej niezwykle kontrowersyjnych dodatkowych wymiarów: że nasza czasoprzestrzeń jest nieskończenie płaska w czymś wyżej wymiarowym - co powinno być widać np. w wymianie ciepła, a jednak absolutnie nic nie widać.

Owszem czysty grawitomagnetyzm to za mało, ale można na nim budować ... zamiast tego, pokolenia fizyków piszących publikacje o OTW spowodowały że stał się jedynym słusznym sposobem myślenia ...

 

Podobne mechanizmy widać w magii mechaniki kwantowej - np. budowa zachwytu komputerami kwantowymi, co przyciąga więcej ludzi i kasy, którzy jeszcze mocniej zachwalają wspaniałości komputerów kwantowych i ściągają więcej kasy ...

 

Dalej mamy np. tokamaki - od ~1950 naukowcy obiecują że za 20 lat to już na pewno będzie działać ... budując sobie niszę żyjącą z kontynuacji tej obietnicy ...

Są inne obiecujące metody, ale nie mają szans przebić się przez zaistniały mainstream tokamaków - ich finansowanie jest rzędy wielkości niższe ...