Ostatnio natknąłem się na artykuł Coudrona i Yuena na temat ekspansji losowości za pomocą urządzeń kwantowych. Głównym rezultatem pracy jest to, że możliwe jest wygenerowanie „nieskończonej” losowości ze stałej liczby źródeł (to znaczy liczba wygenerowanych bitów losowych zależy tylko od liczby rund protokołu, a nie od liczby źródeł ).
Naiwnie brzmi to dla mnie tak, jakby wynik pozwalał na derandomizację dowolnego randomizowanego algorytmu ze źródłami kwantowymi i sugerowałby pewnego rodzaju ograniczenie losowych klas złożoności wewnątrz odpowiedniej klasy kwantowej.
Ale tak naprawdę nie rozumiem kwantowej teorii informacji i jestem pewien, że brakuje mi wielu subtelności. Nie wspominając już o tym, że gdyby takie twierdzenia byłyby możliwe, autorzy by to zrobili. Więc moje pytanie brzmi:
Czy istnienie „nieskończonej ekspansji losowości”, jak opisano w artykule (i wszystkich powiązanych pracach), sugeruje jakieś stwierdzenia o derandomizacji losowych klas złożoności? A jeśli nie to dlaczego nie ?
Aktualizacja: Wskazano mi na doskonały przegląd tego obszaru na wysokim poziomie oraz powyższy artykuł autorstwa Scotta Aaronsona. Niestety nadal jestem zdezorientowany :).
źródło
Odpowiedzi:
To świetne pytanie, Suresh!
Nasz wynik ekspansji losowości nie implikuje żadnego wyniku teoretycznego złożoności. Oto jeden ze sposobów, aby zrozumieć wynik: uważamy, że mechanika kwantowa rządzi światem, i na tym założeniu, że są urządzenia kwantowe, które generują prawdziwy, prawdziwe informacje-teoretyczny losowości.
Wyobraź sobie jednak, że nie ufasz tym pudełkom, które twierdzą, że robią to chwiejne kwantowe rzeczy i generują losowość (dla niektórych może to nie wymagać zbyt wiele wyobraźni). Nie chcesz zajmować się kubitami. Wszystko, co rozumiesz, to klasyczne ciągi bitów.
Rozszerzanie losowości to protokół, w którym jako klasyczny weryfikator możesz wchodzić w interakcje z grupą czarnych skrzynek (myśl o nich jako o nie komunikujących się dowodach ), a po uruchomieniu protokołu z tymi czarnymi skrzynkami poświadczyłeś, że ich dane wyjściowe zawierają bardzo wysoka entropia - jeśli dowód przechodzi. Co więcej, ilość losowości, którą zacząłeś, jest znacznie mniejsza niż entropia wyjściowa, którą poświadczyłeś.
Innymi słowy, jest to interaktywny dowód generowania losowości.
Zatem jedynym aspektem „derandomizacji” jest argumentowanie, że sam protokół wymaga niewielkiej losowości przy uruchamianiu. Ale wynik jest bardzo niedandandomizowany: dane wyjściowe generowane przez pola to prawdziwa przypadkowość, a nie pseudolosowość (tj. Brak założeń obliczeniowych).
źródło