Файл: Дойч. Структура Реальности.doc

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

Позвольте мне конкретизировать это заявление. Самыми первыми изобретениями для использования природы были инструменты, управ­ляемые силой человеческих мускулов. Они вывели наших предков на новый этап развития, но страдали от ограничения, которое заключалось в том, что они требовали постоянного внимания и усилий человека во время их использования. Дальнейшее развитие технологии позволило преодолеть это ограничение: люди сумели приручить некоторых жи­вотных и растения, изменив биологическую адаптацию этих организ­мов, приблизив их к человеку. Таким образом, урожай рос, а стороже­вые собаки охраняли дом, пока их владельцы спали. Еще один новый вид технологии появился, когда люди начали не просто использовать существующие адаптации (и существующие небиологические явления, например, огонь), а создали совершенно новые для мира адаптации в ви­де кирпичей, колес, гончарных и металлических изделий и машин. Что­бы сделать это, они должны были поразмыслить и понять законы приро­ды, управляющие вселенной, включая, как я уже объяснил, не только ее поверхностные аспекты, но и лежащую в основе структуру реальности. Последовали тысячи лет развития этого вида техники —использование некоторыхматериалов, силиэнергийфизики. В двадцатом веке, когда изобретение компьютеров позволило осуществить обработку сложной информации вне человеческого мозга, к этому списку добавиласьинфор­мация. Квантовоевычисление, которое сейчас находится в зачаточном состоянии, —качественно новый этап этого движения. Это будет пер­вая технология, которая позволит выполнять полезные задачи при учас­тии параллельных вселенных. Квантовый компьютер сможет распреде­лить составляющие сложной задачи между множеством параллельных вселенных, а затем поделиться результатами.

Я уже говорил о важности универсальности вычислений —о том, что один физически возможный компьютер может, при наличии до­статочного времени и памяти, выполнить любое вычисление, которое может выполнить любой другой физически возможный компьютер. За­коны физики, как мы понимаем их сейчас, допускают универсальность вычисления. Однако, настоящего определения универсальности недо­статочно, чтобы считать ее полезной или важной в общей схеме все­го. Она просто означает, что,в конечном итоге,универсальный ком­пьютер сможет делать то, что может делать любой другой компьютер. Другими словами, он универсаленпри наличии достаточного времени. Ачто делать, если времени недостаточно? Представьте универсальный компьютер, который мог бы выполнить только одно вычислительное действие за всю жизнь вселенной.Егоуниверсальность по-прежнему оставалась бы глубоким свойством реальности? Вероятно, нет. Говоря в общем, можно критиковать это узкое понятие универсальности, пото­му что оно относит любую задачу к разряду находящихся в репертуаре компьютера, не принимая во внимание физические ресурсы, которые придется израсходовать компьютеру на выполнение этой задачи. Так, например, мы рассмотрели пользователя виртуальной реальности, ко­торый готов отправиться в виртуальную реальность с остановкой мозга на миллиарды лет и повторным его запуском: в течение этого времени компьютер вычислит, что показывать дальше. Такое отношение вполне уместно при обсуждении верхних пределов виртуальной реальности. Но при рассмотрении ееполезности,или, что даже более важно, фун­даментальной роли, которую она играет в структуре реальности, нам следует быть более разборчивыми. Эволюция никогда бы не произошла, если бы задача передачи определенных свойств самых первых, простей­ших сред обитания не былалегко обрабатываемой(т. е. вычислимой в течение разумного периода времени) при использовании в качестве компьютеров легко доступных молекул. Точно так же никогда не нача­лось бы развитие науки и техники, если бы для создания инструмента из камня понадобились тысячи лет размышлений. Более того, то, что было истиной в самом начале, осталось абсолютным условием прогрес­са на каждом этапе. Универсальность вычислений была бы бесполезна для генов, независимо от количества содержащегося в них знания, если бы передача их организма не была легко обрабатываемой задачей — скажем, если бы один репродуктивный цикл занимал миллиарды лет.

Таким образом, факт существованиясложных организмов и непре­рывного ряда постепенно совершенствующихся изобретений и научных теорий (таких, как механика Галилея, механика Ньютона, механика Эйнштейна, квантовая механика, ...)говорит о том, универсальность вычислений какого рода существует в реальности. Он говорит нам, что действительные законы физики, по крайней мере, до сих пор, поддают­ся последовательной аппроксимации с помощью теорий, дающих луч­шие объяснения и предсказания, и что задача открытия каждой теории при наличии предыдущей легко решалась с помощью вычислений при наличии уже известных законов и уже имеющейся технологии. Струк­тура реальности должна бытьмногоуровневой(какой она и была) для более легкого доступа к самой себе. Подобным образом, если рассматри­вать саму эволюцию как вычисление, она говорит нам, что существо­вало достаточно много жизнеспособных организмов, закодированных ДНК, что позволило вычислить (т.е. эволюционировать) организмы с более высокой степенью адаптации, используя ресурсы, предостав­ленные их предками с низкой степенью адаптации. Таким образом, мы можем сделать вывод, что законы физики, кроме того, что удостове­ряют свою собственную постижимость через принцип Тьюринга, га­рантируют, что соответствующие эволюционные процессы, такие, как жизнь и мышление, не являются трудоемкими и требуют не слишком много дополнительных ресурсов, чтобы произойти в реальности.

Итак, законы физики не только позволяют (или, как я доказал, тре­буют)существование жизни и мышления, но требуют от них эффек­тивности, в некотором уместном смысле. Для выражения этого важно­го свойства реальности современные анализы универсальности обычно постулируют компьютеры, универсальные даже в более строгом смыс­ле, чем того потребовал бы в данной ситуации принцип Тьюринга: уни­версальные генераторы виртуальной реальности не только возможны, их можно построить так, что они не потребуют нереально больших ресурсов для передачи простых аспектов реальности. С настоящего мо­мента, говоря об универсальности, я буду иметь в виду именно такую универсальность, пока не приведу другого определения.

Насколько эффективно можно передать данные аспекты реальнос­ти? Другими словами, какие вычисления можно практически выпол­нить за данное время и при данных финансовых возможностях? Это основной вопрос теории вычислительной сложности, которая, как я уже сказал, занимается изучением ресурсов, необходимых для выполнения данных вычислительных задач. Теория сложности все еще в достаточ­ной степени не объединена с физикой и потому не дает много коли­чественных ответов. Однако она достигла успеха в определении полез­ного приближенного различия между легко-итруднообрабатываемыми вычислительными задачами. Общий подход лучше всего проиллюстри­ровать на примере. Рассмотрим задачу умножения двух достаточно больших чисел, скажем. 4 220 851и 2594209.Многие из нас помнят тот метод умножения, которому мы научились в детстве. Нужно по очере­ди перемножить каждую цифру одного числа на каждую цифру друго­го и, сложив результаты, дать окончательный ответ, в данном случае10949769651859.Вероятно, многие не захотят признать, что эта уто­мительная процедура делает умножение «легко обрабатываемым» хоть в каком-то обыденном смысле этого слова. (В действительности, су­ществуют более эффективные методы умножения больших чисел, но этот весьма нагляден). Однако с точки зрения теории сложности, ко­торая имеет дело с массивными задачами, решаемыми компьютерами которые не подвержены скуке и почти никогда не ошибаются, этот ме­тод определенно попадает в категорию «легко обрабатываемых».

В соответствии со стандартным определением для «легкости обра­ботки» важно не действительное время, затрачиваемое на умножение конкретной пары чисел, а важен факт, что при применении того же са­мого метода даже к большим числам, время увеличивается не слишком резко. Возможно это удивит вас, но этот весьма косвенный метод опре­деления легкости обработки очень хорошо работает на практике для многих (хотя и не всех) важных классов вычислительных задач. Напри­мер, при умножении нетрудно увидеть, что стандартный метод мож­но использовать для умножения чисел, скажем, в десять раз больших, Приложив совсем незначительные дополнительные усилия. Ради дока­зательства предположим, что каждое элементарное умножение одной цифры на другую занимает у определенного компьютера одну микросе­кунду (включая время, необходимое для сложения, переходов и других операций, сопровождающих каждое элементарное умножение). При ум­ножении семизначных чисел 4220851и 2594209каждую из семи цифр первого числа нужно умножить на каждую из семи цифр второго числа. Таким образом, общее время, необходимое для умножения (если опе­рации выполняются последовательно), будет равно семи, умноженному на семь, или 49микросекундам. При введении чисел, примерно в де­сять раз больших, содержащих по восемь цифр, время, необходимое для их умножения, будет равно 64микросекундам: увеличение составляет всего 31%.

Ясно, что числа из огромного диапазона —безусловно содержащего любые числа, которые когда-либо были измерены как численные значе­ния физических переменных —можно перемножить за крошечную долю секунды. Таким образом, умножение действительно легко поддается обработке для любых целей в пределах физики (или, по крайней мере, в пределах существующей физики). Вероятно, за пределами физики мо­гут появиться практические причины умножения гораздо больших чи­сел. Например, для шифровальщиков огромный интерес представляют произведения простых чисел, состоящих примерно из 125цифр. Наша гипотетическая машина могла бы умножить два таких простых числа, получив произведение, состоящее из 250цифр, примерно за одну сотую секунды. За одну секунду она могла бы перемножить два тысячезначных числа, а современные компьютеры легко могут осуществить более точный расчет этого времени. Только некоторые исследователи эзоте­рических областей чистой математики заинтересованы в выполнении таких непостижимо огромных умножений, однако, мы видим, что даже у них нет причины считать умножение трудно обрабатываемым.

Напротив, разложение на множители,по сути процесс, обрат­ный умножению, кажется гораздо сложнее. В начале вводится одно число, скажем, 10949769651859,задача заключается в том, чтобы найти два множителя, меньших числа, произведение которых равно10949769651859.Поскольку мы только что умножили эти числа, мы знаем, что в этом случае ответ будет 4220851и 2594209(и поскольку оба эти числа простые, это единственно правильный ответ). Но не об­ладая таким внутренним знанием, как мы нашли бы эти множители? В поисках простого метода вы обратитесь к детским воспоминаниям, но впустую, поскольку такого метода не существует.

Самый очевидный метод разложения на множители —делить вво­димое число на все возможные множители, начиная с 2и продолжая каждым нечетным числом, до тех пор, пока введенное число не разде­лится без остатка. По крайней мере, один из множителей (принимая, что введенное число не является простым) не может быть больше квад­ратного корня введенного числа, что позволяет оценить, сколько вре­мени может занять этот метод. В рассматриваемом нами случае наш компьютер найдет меньший из двух множителей, 2 594 209,примерно за одну секунду. Однако, если вводимое число будет в десять раз больше, а его квадратный корень примерно в три раза больше, то разложение его на множители по этому методу займет в три раза больше времени. Другими словами, увеличение вводимого числа на один разряд ужеут­роитвремя обработки. Увеличение его еще на один разряд снова утроит это время и т. д. Таким образом, время обработки будет увеличивать­ся в геометрической прогрессии, т.е. экспоненциально, с увеличением количества разрядов в раскладываемом на множители числе. Разложе­ние на множители числа с 25-значными множителями по этому методу заняло бы все компьютеры на Земле на несколько веков.

Этот метод можно усовершенствовать, однако всемсовременным методам разложения числа на множители присуще это свойство экспо­ненциального увеличения. Самое большое число, которое было «в гневе» (а это было действительно так) разложено на множители, —число, мно­жители которого тайно выбрали одни математики, чтобы бросить вы­зов другим математикам, —имело 129разрядов. Разложение на множи­тели выполнили с помощью сети Интернет глобальными совместными усилиями, задействовав тысячи компьютеров. Дональд Кнут, специа­лист по вычислительной технике, подсчитал, что разложение на мно­жители 250-значного числа при использовании самых эффективных из известных методов, с помощью сети, состоящей из миллиона компью­теров, заняло бы более миллиона лет. Такие вещи трудно оценить, но даже если Кнут чрезмерно пессимистичен, то попробуйте хотя бы взять числа на несколько разрядов большие, и задача во много раз усложнит­ся. Именно это мы имеем в виду, когда говорим, что разложение на множители больших чисел с трудом поддается обработке. Все это весь­ма отличается от умножения, где как мы видели, задачу умножения пары 250-значных чисел можно элементарно решить с помощью домаш­него компьютера. Никто не может даже представить себе, как можно разложить на множители числа, состоящие из тысячи или миллиона разрядов.

По крайней мере, этого никто не могпредставить до недавнего Времени.

В 1982году физик Ричард Фейнман занимался компьютерным мо­делированием квантово-механических объектов. Его отправной точкой было нечто, что уже было известно в течение некоторого времени, одна­ко важность чего не оценили, а именно, что задача предсказания пове­дения квантово-механических систем (или, как мы можем это описать, Передача квантово-механических сред в виртуальной реальности), в об­щем случае, с трудом поддается обработке. Одна из причин того, что важность этого не оценили, в том, что никто и не ожидал, что предска­зание интересных физических явлений с помощью компьютера будет особо легким. Возьмите, например, прогноз погоды или землетрясения. Несмотря на то, что известны нужные уравнения, сложность их применения для реальных ситуаций общеизвестна. Все это недавно вынесли на всеобщее обозрение в популярных книгах и статьях похаосуи «эф­фекту бабочки». Эти эффекты не ответственны за трудность обработки о которой говорил Фейнман, по простой причине, что они имеют место только в классической физике —т. е. не в реальности, поскольку реаль­ность квантово-механическая. Тем не менее, я хочу сделать несколько замечаний относительно классических «хаотических» движений, толь­ко чтобы подчеркнуть достаточно различный характер невозможности получения классических и квантовых предсказаний.

Теория хаоса касается ограничений получения предсказаний в клас­сической физике, проистекающих из факта внутренней неустойчивости всех классических систем. «Неустойчивость», о которой идет речь, не имеет ничего общего с какой-либо тенденцией буйного поведения или распада. Она связана с чрезмерной чувствительностью к начальным условиям. Допустим, что нам известно настоящее состояние какой-то физической системы, например, комплекта бильярдных шаров, катаю­щихся по столу. Если бы система подчинялась законам классической физики, что она и делает в хорошем приближении, то мы смогли бы определить ее будущее поведение (скажем, попадет ли определенный шар в лузу) из соответствующих законов движения точно так же, как мы можем предсказать солнечное затмение или парад планет, исходя из этих же законов. Но на практике мы никогда не можем абсолютно точно определить начальные положения и скорости. Таким образом, возника­ет вопрос: если мы знаем их с некоторой разумной степенью точности, можем ли мы предсказать их будущее поведение с разумной степенью точности? Обычный ответ: не можем. Разница между реальной траек­торией и предсказанной траекторией, вычисленной из слегка неточных данных, стремится расти экспоненциально и нерегулярно («хаотичес­ки») во времени, так что через некоторое время первоначальное состоя­ние, содержащее небольшую погрешность, уже не сможет быть ключом к поведению системы. Компьютерное предсказание говорит о том, что движение планет, классическая предсказуемость в миниатюре, —нети­пичная классическая система. Чтобы предсказать поведение типичной классической системы всего лишь через небольшой промежуток време­ни, необходимо определить начальное состояние этой системы с невоз­можно высокой точностью. Поэтому говорят, что, в принципе, бабочка, находящаяся в одном полушарии, взмахом своих крылышек может вы­звать ураган в другом полушарии. Неспособность дать прогноз погоды и тому подобное приписывают невозможности учесть каждую бабочку на планете.