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

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

Предположим, нам нужна теория скрытых параметров, детерминистская, как у Бома, но применимая к квантовым состояниям в конечном числе измерений. Что же произойдет, если мы применим унитарное преобразование U, отображающее состояние |0〉 на

В этом случае первоначально скрытый параметр с определенностью равен |0〉; в конце он равен |0〉 с вероятностью 1/2 и |1〉 с вероятностью 1/2. Иными словами, применение U увеличивает энтропию скрытого параметра с нуля до единицы. Поэтому, чтобы решить, в каком направлении изменяется скрытый параметр, Природе, очевидно, придется кидать монетку!

Приверженец теории Бома сказал бы, что детерминизм здесь не годится, потому что наша волновая функция «вырождена», то есть не удовлетворяет условиям непрерывности и дифференцируемости, необходимым для дифференциальных уравнений Бома. Но в гильбертовом пространстве конечной размерности всякая волновая функция будет вырожденной в этом смысле! Вот почему если наша Вселенная дискретна на планковском масштабе, то она не может быть детерминистской в предложенном Бомом смысле.

13. Доказательства

Начнем, пожалуй, с того, что отступим из Квантландии назад, в безопасные земли вычислительной сложности. Посмотрим, в частности, как в 1980-е и 1990-е гг. теория вычислительной сложности заново изобрела тысячелетнюю концепцию математического доказательства — придав ей вероятностный, интерактивный и криптографический характер. Но затем, подготовив новомодные инструменты, мы вернемся в Квантландию и соберем урожай. В частности, я покажу вам, почему если бы можно было видеть траекторию скрытого параметра целиком, то можно было бы решать любые задачи, принимающие «статистический протокол доказательства с нулевым разглашением», в том числе такие задачи, как задача об изоморфизме графов, для которой пока неизвестен эффективный квантовый алгоритм.

Что такое доказательство?

Исторически в математике бытовало два очень разных понятия доказательства.

Первое состоит в том, что доказательство — это то, что внушает аудитории (или, по крайней мере, самому доказывающему!) интуитивное ощущение уверенности в том, что результат верен. С этой позиции доказательство — это внутреннее трансформирующее переживание, способ, при помощи которого ваша душа входит в контакт с вечными истинами Платоновых небес.

Второе понятие состоит в том, что доказательство — это всего лишь последовательность символов, подчиняющихся определенным правилам, — или, в более общем плане, если мы хотим довести эту концепцию до ее, на мой взгляд, логического завершения, доказательство есть вычисление. Иными словами, доказательство это физический, механический процесс, такой что если он завершается с определенным результатом, то вам следует признать данную теорему верной. Естественно, вы не можете испытывать большую уверенность в истинности теоремы, чем ваша уверенность в законах, которые управляют работой машины. Но, как хорошо понимали великие логики от Лейбница до Фреге и Гёделя, слабость этой концепции доказательства является одновременно ее силой. Если доказательство представляет собой чисто механический процесс, то в принципе вы можете открывать новые математические истины просто поворотом рубильника, без какого-либо понимания или озарения. (Как, по представлению Лейбница, будут когда-нибудь разрешаться юридические споры: «Джентльмены, давайте посчитаем!»)

Противоречия между двумя концепциями доказательства обострились в 1976 г., когда Кеннет Аппель и Вольфганг Хакен анонсировали доказательство знаменитой теоремы о четырех красках, которая гласит, что любую плоскую карту можно раскрасить при помощи четырех красок так, чтобы никакие две соседние области не оказались окрашены в один цвет. Доказательство, в сущности, состояло из тупого перебора нескольких тысяч случаев, сделанного компьютером; ни один человек не в состоянии охватить это доказательство во всей полноте.

Если теорема о четырех красках была доказана, по существу, методом грубой силы, то как можно быть уверенным, что оно охватило все без исключения возможности? Новый технический вклад, который пришлось здесь внести математикам-людям, состоял именно в том, чтобы свести задачу к конечному числу случаев, точнее, примерно к 2000 вариантов, — которые затем можно было проверить при помощи компьютера. Тот факт, что с тех пор доказательство было проделано еще раз другой группой ученых, которым удалось снизить число случаев с примерно 2000 до примерно 1000, естественно, повышает нашу уверенность в нем.

Далее, люди могут спросить: откуда вы знаете, что компьютер не совершил ошибки? Очевидный ответ: математики-люди тоже совершают ошибки. Я имею в виду, что Роджер Пенроуз любит говорить о непосредственном контакте с Платоновой реальностью, но, откровенно говоря, ситуация, когда ты уверен, что наладил такой контакт, а на следующее утро все твои рассуждения оказываются ошибочными, выбивает из колеи!

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

Вероятностные доказательства

Вспомните, что доказательство можно рассматривать как своего рода расчет — чисто механический процесс, выплевывающий готовые теоремы. Но что вы скажете о расчете, который ошибается с вероятностью 2–1000, — это доказательство или нет? То есть можно ли считать расчеты в классе BPP законными доказательствами? Ну, если мы сумеем сделать вероятность ошибки такой маленькой, что скорее комета попадет в наш компьютер и разобьет его вдребезги, чем он ошибется в доказательстве, то такой вариант, безусловно, кажется допустимым!

А помните NP — класс задач с полиномиального размера сертификатами (для ответа «да»), которые можно проверить за полиномиальное время? А раз мы думаем о рандомизированных алгоритмах, сама собой возникает идея «совместить» NP и BPP и создать таким образом новый класс сложности, где вы получаете полиномиального размера сертификат на ответ «да» и можете использовать для проверки этого сертификата рандомизированный алгоритм полиномиального времени. Так вот, такой гибридный класс действительно был предложен Ласло Бабаи в 1980-е гг. Но вы, вероятно, ни за что не догадаетесь, как Бабаи назвал свой класс, если не знаете этого заранее. Сдаетесь? Он называется MA — «Мерлин — Артур». Бабаи видел это как игру, где «Мерлин» — всемогущий,