Komputery analogowe i teza Kościoła Turinga

Chciałbym zacytować Nielsen & Chuang, Obliczenia kwantowe i informacje kwantowe, wydanie z okazji 10. rocznicy, strona 5 (moje wyróżnienie):

Jedna klasa wyzwań dla silnej tezy Kościoła i Turinga pochodzi z dziedziny obliczeń analogowych. Przez lata od Turinga wiele różnych zespołów naukowców zauważyło, że niektóre typy komputerów analogowych mogą skutecznie rozwiązywać problemy, które nie mają skutecznego rozwiązania na maszynie Turinga. Na pierwszy rzut oka wydaje się, że komputery analogowe naruszają silną formę tezy Kościoła - Turinga. Na nieszczęście dla obliczeń analogowych okazuje się, że kiedy przyjmowane są realistyczne założenia dotyczące obecności szumu w komputerach analogowych, ich moc znika we wszystkich znanych przypadkach; nie mogą skutecznie rozwiązywać problemów, których nie można skutecznie rozwiązać na maszynie Turinga.Ta lekcja - że skutki realistycznego szumu muszą być brane pod uwagę przy ocenie wydajności modelu obliczeniowego - była jednym z wielkich wczesnych wyzwań obliczeń kwantowych i informacji kwantowych, wyzwaniem, któremu udało się skutecznie opracować teorię błędu kwantowego -korekty kodów i tolerancyjne obliczenia kwantowe. Zatem, w przeciwieństwie do obliczeń analogowych, obliczenia kwantowe mogą w zasadzie tolerować skończoną ilość szumu i nadal zachowywać swoje zalety obliczeniowe.

Czy jest to stwierdzenie, że hałas skaluje się szybciej niż pewna potęga wielkości problemu, czy może ktoś skieruje mnie we właściwym kierunku, abym mógł dowiedzieć się więcej o tym, czy te granice skalowania są fundamentalne, czy tylko „zagadnieniem inżynieryjnym”?

Dla jasności pytam, czy komputery analogowe nie są w stanie pokonać maszyn Turinga ze względu na hałas.

Przede wszystkim autorzy zdają się mylić dwie różne tezy: teorię Kościoła-Turinga i tezę Cooka-Karpa. Pierwszy dotyczy tego, co można obliczać, a drugi dotyczy tego, co można obliczać skutecznie .

Zgodnie z tezą Cooka-Karpa wszystkie rozsądne „silne” modele obliczeniowe są wielomianowo równoważne w tym sensie, że wszystkie wielomianowo symulują się nawzajem. Odpowiednio, każdy rozsądny model obliczeniowy może być symulowany wielomianowo przez maszynę Turinga. Komputery kwantowe są kontrprzykładem tej tezy, ponieważ wydają się być wykładniczo bardziej wydajne niż komputery klasyczne. Nie są one jednak kontrprzykładem dla tezy Kościoła i Turinga, to znaczy przy użyciu komputerów kwantowych nie można obliczyć niczego, czego nie można jeszcze obliczyć za pomocą maszyny Turinga. Możemy również sformułować zaktualizowaną tezę Cooka-Karpa, stwierdzającą, że wszystkie fizycznie wykonalne modele obliczeniowe są symulowane wielomianowo przez komputery kwantowe.

Zaproponowano kilka fizycznych modeli obliczeń jako kwestionujących te tezy, ale pod kontrolą, wszystkie wydają się nie naruszać tezy Kościoła-Turinga, ani nie być silniejsze niż obliczenia kwantowe. Scott Aaronson proponuje uznać tę sytuację za „prawo natury”. Jednak, o ile mi wiadomo, nie ma żadnych teoretycznych argumentów na poparcie tych tez oprócz argumentu indukcyjnego, że wykazano, że wszystkie zaproponowane modele są z nimi zgodne.

ten fragment (napisany ponad dekadę temu) jest rzeczywiście kluczowy i przywołuje sporo wiedzy podstawowej oraz bardzo dobrze przewiduje pewne przyszłe kierunki badań. nawiązuje do dziedziny hiper- obliczeń, która czasami znajduje się na obrzeżach TCS, ponieważ bada modele obliczeń, które podobno są „mocniejsze” niż maszyny Turinga. ciekawym punktem na temat maszyn Turinga jest to, że mają zerowy hałas, więc w pewnym sensie informatyka opiera się na tej idealizacji, która pod pewnymi względami jest fizycznie nierealistyczna. a systemy elektroniczne naśladują tę bezszelestność jako zasadę projektowania, jest ona zawsze obecna w niskiej dynamice układów, ale bardzo skutecznie wyabstrahowana w projektach wyższych poziomów, które ograniczają wszystkie sygnały elektryczne do idealnych bitów 0/1. ponownie to:

Ta lekcja - że skutki realistycznego szumu muszą być brane pod uwagę przy ocenie wydajności modelu obliczeniowego - była jednym z wielkich wczesnych wyzwań obliczeń kwantowych i informacji kwantowych, wyzwaniem , któremu udało się skutecznie opracować teorię błędu kwantowego -korekty kodów i tolerancyjne obliczenia kwantowe.

wydaje się, że niektóre z ich twierdzeń wyglądają raczej przedwcześnie optymistycznie z perspektywy czasu. prawdą jest, że w kodach korygujących błędy QM opracowano duże ilości teorii. jednak bardzo niewiele z nich zostało przetestowanych i zweryfikowanych eksperymentalnie. niektórzy naukowcy / eksperci podejrzewają / hipotezują, że mogą istnieć prawa fizyczne, które wymagają szumu do skalowania w „zły” sposób dla większych n-bitowych układów kwantowych. jest to więc obszar aktywnych badań i kontrowersji. w rzeczywistości jest to kluczowy obszar sporny dla dwóch wiodących projektów / podejść do obliczania QM, jeden przez systemy DWave, a drugi przez grupę Martinis UCSB / Google .

Dla jasności pytam, czy komputery analogowe nie są w stanie pokonać maszyn Turinga ze względu na hałas.

to jest wielkie pytanie, prawda? aby odpowiedzieć na to pytanie, należy wziąć pod uwagę, że istnieją klasyczne systemy analogowe i ostatnio rozważane systemy kwantowe . w przypadku systemów klasycznych ogólny konsensus jest przedstawiony przez Nielsena / Chuanga, że ​​istnieją modele teoretyczne, które „wydają się” silniejsze, ale gdy prawidłowo uwzględniono hałas, ta teoretyczna „zaleta” „topnieje”. innymi słowy, proponowanie istnienia analogowych systemów obliczeniowych „zasadniczo teoretycznie szybszych” niż systemy elektroniczne już zbudowane wydają się prawie naruszać prawa fizyki / termodynamiki.

jednak pytanie dotyczące QM jest o wiele bardziej otwartym pytaniem i zależy (jak się nieco spodziewamy) od natury szumu QM i tego, czy można go faktycznie kontrolować / kontrolować, co zostało postawione w hipotezie i jest aktywnie badane.

głębsza analiza tych zagadnień znajduje się w pracy Aaronsonsa NP-complete Problemy i rzeczywistość fizyczna . sceptyczny przegląd można znaleźć w „Dyakonov Prospects” dla obliczeń kwantowych: bardzo wątpliwe .