Квантовые вычисления со времен Демокрита - Скотт Ааронсон

дерандомизации мы должны думать об x как о строке совета, исходящей от некоего сверхразумного советчика с единственной целью замаскировать псевдослучайный генератор. Понимаете, поэтому-то нам и нужна была задача, трудная даже при наличии совета: нам нужно построить генератор псевдослучайной последовательности, неотличимой от случайной даже в присутствии «советчика» x.

Подведем итоги: если бы мы могли доказать, что определенные задачи достаточно трудны для неоднородных алгоритмов, то мы доказали бы, что P = BPP.

Это ведет нас к третьему различию между BPP и BQP: если большинство специалистов верит, что P = BPP, то опять же большинство определенно не верит, что P = BQP. (В самом деле, мы не можем в это верить, если мы верим, что разложение на простые множители — трудная задача для классических компьютеров.) У нас нет программы «деквантизации», которой можно было бы приписать хотя бы малую долю успеха программы дерандомизации. Опять же создается впечатление, что между квантовой теорией и классической теорией вероятностей существует принципиальная разница, которая позволяет некоторым идеям (таким как идеи Сипсера, Гача и Лаутемана, Адлемана, Импальяццо — Вигдерсона) работать для второй, но не для первой.

Кстати говоря, Кабанец и Импальяццо[40] (и другие) сумели продемонстрировать нечто обратное — в определенном смысле — теоремам дерандомизации. Они показали, что если мы хотим доказать, что P = BPP, то нам придется доказать, что определенные задачи трудны для неоднородных алгоритмов. Это можно воспринимать как своеобразное объяснение причины, по которой никому еще не удалось доказать, P = BPP, хотя это и предполагается. Говоря точнее, дело в том, что если вы хотите доказать, P = BPP, то вам придется доказывать, что определенные задачи трудны, а если вы хотите доказать, что эти задачи трудны, то вы (по крайней мере косвенно) должны будете разбираться с вопросом о P и NP. В теории вычислительной сложности едва ли не любой вопрос в конце концов сходится к проблеме P и NP.

Загадки

1. Вы с приятелем хотите бросать монетку, но единственная монетка, которая у вас имеется, явно неправильная: на ней выпадает орел с некоторой фиксированной, но неизвестной вероятностью p. Сможете ли вы с помощью этой монетки смоделировать бросание настоящей честной монетки? (Я имею в виду, идеально честной, а не просто приблизительно честной.)

2. n человек встали в круг. У каждого из них на голове либо красная, либо синяя шляпа, полученные случайно, равномерно и независимо. Каждый может видеть шляпы всех остальных, но не свою собственную. Эти люди хотят устроить голосование на тему того, является ли число красных шляп четным или нечетным. Все голосуют одновременно, так что голоса друг на друга не влияют. Какова максимальная вероятность, с которой люди могут выиграть в этой игре? (Под «выиграть» я подразумеваю, что результат голосования будет соответствовать истине.) Считать для простоты, что число n нечетное.

8. Крипто

Ответы на загадки из главы 7

Загадка 1. Нам дана неправильная монетка, при бросании которой орел выпадает с вероятностью p. При помощи этой монетки нужно «построить» механизм моделирования честной монетки.

Решение. Нужное нам решение — это так называемый фокус фон Неймана: бросаем монетку дважды, интерпретируя ОР как орла, а РО как решку. (Если выпадут ОО или РР, пробуем еще раз.) Теперь «орел» и «решка» равновероятны, поскольку в любом заданном испытании то и другое возникает с вероятностью p (1 — p). Следовательно, такая модель монетки работает честно (при условии, что выпадает ОР или РО).

Загадка 2.n человек сидят по кругу. У каждого из них на голове либо красная, либо синяя шляпа, полученные случайно, равномерно и независимо. Каждый может видеть шляпы всех остальных, но не свою собственную. Основываясь только на том, что видит, каждый высказывает свое мнение: является число красных шляп нечетным или нет. Существует ли схема, при которой результат голосования будет верным с вероятностью, большей 1/2?

Решение. Каждый человек определяется с голосованием так: если число видимых ему синих шляп больше, чем число видимых красных шляп, он голосует в соответствии с четностью числа видимых красных шляп. В противном случае — голосует наоборот. Если число красных шляп отличается от числа синих на две или больше, то эта схема срабатывает точно. Если нет, схема может и не сработать. Однако вероятность того, что число красных шляп отличается от числа синих меньше чем на 2, невелика — O (1/√N).

Крипто

Криптография уже более 3000 лет играет заметную роль в истории человечества. Немало войн было выиграно или проиграно благодаря хитроумности или глупости криптосистем. Если вам кажется, что я преувеличиваю, почитайте «Взломщиков кодов» Дэвида Кана[41] — и не забывайте, что эта книга написана еще до того, как стала известна крупнейшая криптографическая история всех времен: взлом нацистского военно-морского шифра во Второй мировой войне командой с участием Алана Тьюринга.

И все же, хотя криптография тысячелетиями влияла на человеческие дела, события последних тридцати лет полностью — да, именно полностью! — изменили наши представления о ней. Если нанести на шкалу времени основные математические открытия в области криптографии, то вы увидите несколько отметок в античности, несколько, может быть, от Средневековья до XIX века, одно в 1920-е гг. (одноразовые ключи), еще несколько во время и около Второй мировой войны — а затем, после рождения теории вычислительной сложности в 1970-е гг., они пойдут сплошным потоком, одно за одним…

Наше путешествие по истории криптографии начнется со знаменитого и жалкого «шифра Цезаря», использовавшегося в Римской империи. В нем обычное послание превращается в шифрованный текст простым добавлением 3 к номеру каждой буквы (с замыканием алфавита в кольцо, так что после Z снова идет A). Таким образом, D превращается в G, Y становится B, а DEMOCRITUS выглядит как GHPRFULWXV. Были и более сложные варианты шифра Цезаря (он же шифр замены), но при наличии достаточного количества зашифрованного текста все их нетрудно взломать при помощи (например) частотного анализа присутствия букв в зашифрованном тексте. Правда, это не очень-то останавливает людей в использовании подобных вещей! Представьте себе, совсем недавно, в 2006 г., глава сицилийской мафии[42] был наконец-то пойман после 40 лет охоты потому, что использовал шифр Цезаря — его оригинальную версию — для отправки записок своим подчиненным!

Может ли существовать криптосистема, безопасная с точки зрения теории информации, то есть доказуемо надежная вне зависимости от того, сколько компьютерного времени есть у перехватившей сообщение стороны на его