Ponieważ nie udzielono odpowiedzi, ustawiono flagę z prośbą o przekształcenie tego pytania w wiki społeczności.
Komentarze Aarona Sterlinga, Sasho Nikolova i Vora zostały zsyntetyzowane do następującej rozdzielczości, która jest otwarta na dyskusję wiki społeczności:
Rozwiązane: W odniesieniu do klasycznych algorytmów, które generują liczby, próbki lub trajektorie symulacji, ścisła logika matematyczna wymaga, aby albo wszystkie cztery następujące zdania były akceptowane, albo żadna z nich:
- Możemy wykluczyć klasyczny algorytm wielomianowy do generowania liczb losowych. [1]
- „Możemy wykluczyć klasyczny algorytm wielomianowy do próbkowania rozkładu wyjściowego komputera kwantowego, przy założeniu, że hierarchia wielomianowa jest nieskończona”. [2]
- „Nie możemy symulować [trajektorii mechaniki kwantowej] w zwykły sposób… jest zbyt wiele zmiennych”. [3]
- Rozszerzona teza Churcha-Turinga (ECT) jest wykluczona z tego rygorystycznego powodu, że klasyczne algorytmy nie mogą generować liczb losowych. [4]
Aby zainicjować dyskusję, oto twierdzące i negatywne odpowiedzi, które, choć każda jest możliwa do obrony, są celowo zawyżone. Zdecydowanie twierdzącym argumentem może być:
Twierdzenie : Te cztery stwierdzenia odzwierciedlają twierdzenia, które szanując rygor, wymagają od nas, abyśmy nigdy nie mówili o klasycznych algorytmach generujących liczby losowe, próbki losowe lub symulacje kwantowe, ale raczej o klasycznych algorytmach generujących liczby pseudolosowe i (przez rozszerzenie) próbki pseudolosowe i symulacje pseudo-kwantowe.
Biorąc to pod uwagę, wszystkie cztery stwierdzenia są prawdziwe. Ponadto, aby uniknąć dwuznaczności i zapobiec nieporozumieniom, matematycy powinni zachęcać naukowców i inżynierów do umieszczania przedrostka „pseudo-” na prawie wszystkich zastosowaniach „losowych”, „próbnych” i „kwantowych”.
Mocno negatywnym argumentem może być:
Negatywne: te stwierdzenia (i powiązane z nimi twierdzenia formalne) są drogowskazami, które kierują nas do dzielnicy matematyki w stylu Lakatos „czerwonych latarni”, gdzie jesteśmy zachęcani do entuzjastycznego przyjęcia (jak to można nazwać) dyscyplin pseudolosowych , pseudo-próbkowanie i pseudo-symulacja… praktyki matematyczne, które są zabawne z wyjątkowo grzesznego powodu: osiągają efekty matematyczne, które według logiki formalnej są niemożliwe. Co może być bardziej magicznego i zabawnego niż ten wniosek: cztery stwierdzenia zawarte w rezolucji są formalnie prawdziwe, ale praktycznie fałszywe?
Biorąc to pod uwagę, wszystkie cztery stwierdzenia są fałszywe. Co więcej, ponieważ najbardziej praktyczne objęcia „losowości”, „próbkowania” i „symulacji kwantowej” występują w tym magicznym środowisku - w którym kwestie związane ze złożonością Kołmogorowa i ocenami wyroczni są umyślnie pomijane - matematycy powinni zmienić ich użycie.
Realistycznie jednak, w jaki sposób teoretycy złożoności powinni sformułować swoje ustalenia dotyczące losowości, próby i symulacji… z jednej strony, w celu utrzymania rozsądnej równowagi jasności, zwięzłości i dyscypliny… z drugiej strony, z myślą w kierunku utrzymania cichej komunikacji z innymi dyscyplinami STEM? Ten ostatni cel jest szczególnie ważny, ponieważ praktyczne możliwości stale rosną w takich dziedzinach, jak kryptografia, testy statystyczne, uczenie maszynowe i symulacja kwantowa.
Bardzo pomocne (i przyjemne) byłoby również przeczytanie dobrze uzasadnionych odpowiedzi, zarówno twierdzących, jak i negatywnych.
Pytanie brzmi:
Jaka jest / są ogólnie akceptowana rola (role) weryfikacji w teoretycznych złożoności definicji związanych z próbkowaniem, symulacją i testowaniem rozszerzonej tezy Church-Turinga (ECT)?
Preferowaną odpowiedzią są odniesienia do artykułów, monografii lub podręczników, które szczegółowo omawiają te kwestie.
Jeśli ta literatura okaże się rzadka lub w inny sposób niezadowalająca, wówczas (po dwóch dniach) przekonwertuję to pytanie na wiki społeczności z pytaniem:
Jaka jest / są uzasadniona i właściwa (-e) rola (-y) weryfikacji w teoretycznych złożoności definicji związanych z próbkowaniem, symulacją i testowaniem pracy rozszerzonej Church-Turinga (ECT)?
tło
Zadane pytanie jest motywowane ostatnim wątkiem: „Co by to znaczyło obalić tezę Turinga?”. , w szczególności (doskonałe IMHO) odpowiedzi udzielone przez Gila Kalai i Timothy Chow
W zadanym pytaniu wyrażenie „właściwe i / lub przyjęte definicje teoretyczne złożoności” należy interpretować jako powstrzymujące Alice przed nieprawdopodobnymi twierdzeniami, takimi jak:
Alice: Oto moja eksperymentalna próbka naprawdę losowych cyfr binarnych obliczonych przez moją (jednofotonową) liniową sieć optyczną.
Bob: Oto moja symulowana próbka pseudolosowych cyfr obliczonych przez klasyczną maszynę Turinga.
Alice: Przepraszam Bob ... twoja próbka jest kompresowalna algorytmicznie, a moja nie. Dlatego moje dane eksperymentalne pokazują, że ECT jest fałszywe! ”
Wobec braku jakiegokolwiek powiązania weryfikacji z pobieraniem próbek, rozumowanie Alice jest bez zarzutu. Innymi słowy, czy teoretycy złożoności powinni uważać, że ECT zostało już formalnie obalone… dekady temu?
Z praktycznego punktu widzenia metody symulacji związane z próbkowaniem trajektorii kwantowej w odmianowych przestrzeniach stanów znajdują szerokie zastosowanie w wielu dyscyplinach nauki i inżynierii. Właśnie dlatego teoretyczne definicje próbkowania, które uwzględniają centralną rolę weryfikacji (która jest nierozerwalnie związana z powtarzalnością) w nauce i inżynierii, byłyby bardzo mile widziane dla praktykujących naukowców i inżynierów… szczególnie, gdyby tym definicjom towarzyszyły twierdzenia opisujące złożoność obliczeniową zweryfikowane próbkowanie.
Dodano Edycja: Dzięki współpracy między Uniwersytetem Genewskim a firmą Quantique , wykonanie tego ćwiczenia w rzeczywistości jest całkowicie wykonalne.
Oto 1024 losowe bity, które są certyfikowane przez id Quantique jako algorytmicznie nieściśliwe:
0110001000010111111100010111001000101110110001001100000010010110
0101000110100011101001110110000001010110011101111110101010110100
1001001110001110101000001110000101000110000001010001101001000000
0110101010110000110101001110011010010101000000110000010000010111
0100110110001011011101110000010110000100110001001110011000000011
1111010100010110110010011000110110110010101101010000010010001111
1101111000111101111010000110100110011000101101010110110110000101
1110111100000111000111101111110011101101110111101001001111111110
1000001011001000011101001000001110101110101010000111100000111010
1010011001110111101001100010110000101101100100101100000110111111
1000001101111001111011100011110101011010010100000010100101100010
0011101000111100000001101100111110100100010100100010011000001000
0000001001110101010111110001010010000111010011000100001101101000
1011111010001000110101110101111101010111111011011111110010010111
0111000010000111000100110110010101110100000110101001111010101001
0100011110011101000011000100110110010000100001111100101001010011
Czy powinniśmy teraz zaakceptować twierdzenie: „Teza ECT jest obalona”?
Jeśli nie, jakie podstawy powinniśmy podać?
źródło
Odpowiedzi:
Istota pytania polega na tym, biorąc pod uwagę, że prawdopodobieństwo kwantowe jest źródłem prawdziwej przypadkowości, w jaki sposób wpływa to na rozszerzoną (lub efektywną lub wielomianową) tezę Turinga?
Odpowiedź jest taka, że zgodnie z przypuszczeniem nie ma na to wpływu. Ludzie przypuszczają, że BPP = P, tj. Że algorytmy losowe można zdemandomizować za pomocą generatorów liczb pseudolosowych z wielomianowym obciążeniem. Wiara w PRNG jako zamiennik prawdziwej przypadkowości jest jednym z powodów, dla których ludzie uwierzyliby w rozszerzoną tezę Turinga, gdyby nie obliczenia kwantowe.
źródło