Co wiadomo na temat skuteczności niezawodnego przetwarzania?

Jak dobrze zbadano następujący problem w TCS? (Przepraszam, jeśli opis problemu brzmi niejasno!)

Biorąc pod uwagę model obliczeń MC (maszyna Turinga, automaty komórkowe, maszynę Kolmogorov-Uspenskii ... itd.) Oraz model hałasu, który mógłby wpływać na obliczenia MC, istnieje sposób na odzyskanie po błędach spowodowanych przez ten hałas w skuteczny sposób? Na przykład, powiedzmy, że jakiś rodzaj hałasu wpływa na maszynę Turinga M, czy można opracować maszynę Turinga M ', która symuluje M bez większych kosztów i jest niezawodna (co oznacza, że ​​M' jest tolerancyjny na ten hałas)?

Wydaje się, że niektóre modele obliczeń są lepsze od innych: na przykład Automaty komórkowe. Jakieś wyniki, jeśli hałas zostanie zastąpiony modelem przeciwnika?

Przepraszamy za tag! Nie mam wystarczającej reputacji, aby umieścić odpowiedni tag (niezawodne, odporne na błędy obliczenia ... itd.)

Chociaż istnieją pewne techniki, które można zastosować do odporności na uszkodzenia dla wszystkich modeli, to jak odporny jest model obliczeniowy na odporność na uszkodzenia, zależy od modelu. Na przykład Peter Gacs przeprowadził sporo badań dotyczących odporności na uszkodzenia automatów komórkowych i pokazuje, że (przy dużym nakładzie pracy) można zbudować odporne na uszkodzenia automaty komórkowe.

Von Neumann udowodnił, że dzięki redundancji można zbudować niezawodny komputer z niewiarygodnych komponentów przy użyciu jedynie logarytmicznego obciążenia.

Do obliczeń kwantowych, układy kwantowe mogą być odporny na błędy z polylogarithmic napowietrznych ( górze, gdzie znaleźć właściwą wartość C jest wciąż otwarta). Kolejnym otwartym pytaniem dotyczącym obliczeń kwantowych jest to, czy adiabatyczne obliczenia kwantowe można uczynić odpornymi na uszkodzenia w fizycznie uzasadniony sposób (fizycznie uzasadniony oznacza, że ​​możliwe jest, że metoda prowadzi do skalowalnego adiabatycznego komputera kwantowego; na przykład nie można wziąć temperatura do 0 w miarę powiększania się obliczeń).$\log^c n$$c$

Myślę, że praca związana z samostabilizacją jest zbliżona do ducha twojego pytania.

System samostabilizujący się odzyskuje po uszkodzeniu pamięci RAM.

Zadane pytanie brzmi: „Czy istnieje sposób na skuteczne usunięcie błędów spowodowanych hałasem [kwantowym] w skuteczny sposób?” a odpowiedź Petera Shora w sposób godny podziwu obejmuje jeden skuteczny sposób odpowiedzi na to pytanie, a mianowicie zaprojektowanie odpornych na uszkodzenia komputerów kwantowych.

Alternatywny skuteczny sposób jest bardzo często spotykany w praktyce inżynierskiej. Rozumujemy „Jeśli szum jest wystarczająco duży, aby żadne obliczenia kwantowe nie były możliwe, być może dynamikę systemu można zasymulować za pomocą klasycznych zasobów w P.”

Innymi słowy, często możemy „skutecznie odzyskać” hałas, uznając, że hałas stanowi dla nas ważną usługę, poprzez wykładnicze zmniejszenie złożoności obliczeniowej symulacji zarówno układów klasycznych, jak i kwantowych.

Literatura na temat podejść skoncentrowanych na hałasie do symulacji dynamicznej jest obszerna i rośnie; najnowszym odniesieniem, którego twierdzenia są zarówno fizycznie umotywowane, jak i przyjemnie rygorystyczne, i które zawiera wiele odniesień do szerszej literatury, są górne granice Plenio i Virmani dotyczące progów tolerancji uszkodzeń w głośnych komputerach kwantowych na bazie Clifforda (arXiv: 0810.4340v1).

Klasyczni dynamicyści używają zupełnie innego języka, w którym mechanizmy hałasu noszą techniczną nazwę termostatów ; Frenkel and Smit's Understanding Molecular Simulation: od algorytmów do aplikacji (1996) zapewnia podstawowe wprowadzenie matematyczne.

Kiedy transkrybujemy klasyczne i kwantowe termostaty na język dynamiki geometrycznej, stwierdzamy (co nie dziwi), że klasyczne i kwantowe metody wykorzystania szumu w celu zwiększenia wydajności symulacji są zasadniczo identyczne; to, że ich literatura tak rzadko się nawzajem odnosi, jest w dużej mierze przypadkiem historii, który został utrudniony przez notacyjne przeszkody.

Mniej rygorystycznie, ale bardziej ogólnie, powyższe wyniki wyjaśniają genezę teorii informacji kwantowej reguły heurystycznej, która jest powszechnie stosowana przez chemików, fizyków i biologów, że każdy układ klasyczny lub kwantowy, który ma dynamiczny kontakt z kąpielą termalną, prawdopodobnie udowodnić, że można symulować z wykorzystaniem zasobów obliczeniowych w języku P do wszystkich praktycznych celów (FAPP).

Wyjątki od tej heurystyki, zarówno klasycznej, jak i kwantowej, stanowią ważne otwarte problemy. Ich liczba uderza uderzająco z roku na rok; dwuletnia Krytyczna ocena prognoz struktury (CASP) stanowi jedną obiektywną miarę tej poprawy.

Podstawowe ograniczenia tego opartego na hałasie, wieloletniego postępu w dziedzinie symulacji „Więcej niż Moore” są obecnie niedoskonale znane. Nie trzeba dodawać, że na dłuższą metę nasze coraz lepsze rozumienie tych ograniczeń zbliży nas do budowy komputerów kwantowych, natomiast w krótkim okresie wiedza ta bardzo pomaga nam w efektywnej symulacji systemów, które nie są komputerami kwantowymi. Tak czy inaczej, to dobra wiadomość.

Wygląda na to, że Gacs jest w trakcie budowy odpornej na awarie maszyny Turinga. Spójrz na to: http://arxiv.org/abs/1203.1335

Modele obliczeń kwantowych wyraźnie zajmują się hałasem i sposobami uczynienia obliczeń odpornymi na błędy wprowadzane przez ten wektor. Co ciekawe, obliczenia kwantowe można przeprowadzać do przodu i do tyłu (z natury transformacji QM Hadamarda i niezależności czasowej hamiltonianu) - „odliczanie” jest jedną z technik stosowanych do powstrzymywania fali takich błędów.

Na „prawdziwych” komputerach - serwerach Enterprise - istnieje niewielka, ale realna szansa, że ​​trochę pamięci RAM zostanie odczytanych niepoprawnie. Teorię wykrywania błędów i poprawiania kodów można zastosować na poziomie słowa maszynowego, aby wykryć i naprawić takie 1-bitowe błędy (bez bardzo dużego obciążenia). W rzeczywistości wiele serwerów Enterprise, które wykonują operacje krytyczne, zaprasza niewielki bit parzystości na każde słowo pamięci RAM.

Choć daleko mi do dowodu, wydaje mi się, że standardowe schematy kodowania z korekcją błędów mogłyby zostać przystosowane do pracy z prawie wszystkimi automatami teoretycznymi (podejrzane są automaty komórkowe) z jedynie spowolnieniem wielomianowym (w rzeczywistości liniowym?).

Trwają prace nad tak zwanymi „odpornymi” strukturami danych i algorytmem (drzewa wyszukiwania, liczniki, słownik). Modelem jest pamięć RAM z założeniem, że do$k$bity mogą być modyfikowane przez przeciwnika w dowolnym momencie. Przeciwnik ciągle nie może modyfikować wielu rejestrów. W zależności od parametru$k$, możesz uzyskać algorytmy, które nadal działają poprawnie i od których zależy czas działania $k$ jest lepszy niż bieganie $k$niezależne kopie jednego algorytmu. Niedawno zaproszone wystąpienie G. Italiano powinno dać przegląd: Odporne algorytmy i struktury danych (właśnie znalazłem ten artykuł i sam go jeszcze nie przeczytałem, ale jestem pewien, że to dobry wskaźnik).