Jaka jest właściwa rola weryfikacji w próbkowaniu kwantowym, symulacji i testowaniu metodą rozszerzonego kościoła-Turinga (ECT)?

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”. $\psi(t)$ [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ć?

quantum-computing program-verification sample-complexity

— John Sidles
źródło

przez weryfikację masz na myśli, że stwierdzenie „algorytm A ma właściwość P w modelu obliczeniowym M” może być testowane w skończonym czasie, dla dowolnej określonej długości wejściowej? Np. Właściwość „algorytm probabilistyczny A zatrzymuje się na kroków na dowolnym wejściu o rozmiarze , używając co najwyżej bitów losowych i akcentując język z prawdopodobieństwem ” można zweryfikować w skończonym czasie dla dowolnego . Zweryfikowany w skończonym czasie miałby na myśli deterministyczną maszynę Turinga jako niezawodny model obliczeniowy?

1000 n

$1000n$

n

$n$

\log_{2} n

$\log_2 n$

L

$L$

2 / 3

$2/3$

n

$n$

— Sasho Nikolov

Myślę, że to świetne pytanie. Ale w twoim przykładzie, skąd Alicja wie, że jej ciąg cyfr nie podlega kompresji algorytmicznej?

— Aaron Sterling

W sprawie pobierania próbek / wyszukiwania równoważności: scottaaronson.com/papers/samprel.ps

— Marzio De Biasi

@John: tylko wyjaśnienie (podkreślam, że nie jestem ekspertem): „ ... są poświadczone przez id Quantique jako algorytmicznie nieściśliwe ”, ale jak mogą to poświadczyć? Oczywiście złożoności łańcucha Kołmogorowa nie da się obliczyć, więc zdanie wydaje się fałszywe. Nawet jeśli po prostu powiedzą „ potwierdzamy, że sekwencja jest (kwantowa) losowa ”, mam pewne wątpliwości: proces fizyczny (sprzęt) jest trudny do zrównoważenia, więc używają rozproszenia Von Neumanna, co jest dobre, ale nie gwarantuje, że wynik jest naprawdę losowy .

— Marzio De Biasi

@John Sidles: podczas gdy robisz solidne i interesujące obserwacje, nie rozumiem, czego szukasz. Jasne jest, co Aaronson i współautorzy rozumieją przez „wykluczenie”: jeśli PH jest nieskończony, nie ma określonego algorytmu w danym modelu. przypuszczam, że pytasz, czy założenia modelowania są weryfikowalne. zauważ, że celem modelu jest weryfikacja tylko założenia modelowania, zamiast testowania dowolnego możliwego algorytmu / twierdzenia

— Sasho Nikolov

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.

— Greg Kuperberg
źródło