М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 55
Текст из файла (страница 55)
Например, термометр представляет информацию в аналоговой форме. Аналоговые схемы, использующие резисторы, конденсаторы и усилители, также называются аналоговыми вычислителями. В идеале ресурсы таких машин неограничены, поскольку непрерывные переменные, например координаты или разности потенциалов, могут содержать неограниченный объем информации. Но это утверждение верно только в отсутствие шума. При наличии шума число различгьмых состояний аналогового устройства будет конечно, и благодаря этому аналоговые компьютеры могут обрабатывать только конечное количество информации. На практике при наличии шума аналоговые компъютеры оказываются не более производительными, е Число 10ы подходит при решении задачи на графе с числом вершин, меньшим 20.
Если решать задачу на графе с 200 вершинами (такие задачи удается решать на обычных суперкомпьютерах), то потребуется больше 10зсе цепочек, что значительно превышает число элементарных частиц в наблюдаемой части Вселенной — Прим. ред. 3.3. Перспективы информатики 215 чем цифровые и машины Тьюринга. Можно было бы подумать, что квантовые компьютеры являются разновидностью аналоговых компьютеров, поскольку при описании состояний кубитов используются непрерывные параметры; однако оказывается, что влияние шума на квантовый компьютер может быть оцифроваио. В результате преимущества квантовых компьютеров сохраняются даже при наличии конечного шума (мы увидим это в гл.
10). А как влияет шум на цифровые компьютеры? В начале компьютерной эры шум был серьезной проблемой. У некоторых из первых компьютеров вакуумные трубки давали сбой раз в несколько минут. Даже в наши дни шум представляет собой проблему для таких устройств, как модемы и жесткие диски. Значительные усилия были затрачены на то, чтобы понять, как можно строить надежные компьютеры из ненадежных компонент. Фон Нейман доказал, что это действительно возможно, причем ресурсы, необходимые для вычислений, возрастают при этом лишь полиномиэльно. Однако по иронии судьбы в современных компьютерах результаты этих разработок не используются, поскольку компоненты современных компьютеров фантастически надежны.
Вероятности ошибки в 10 '~ и ниже — это обычные показатели для современной электроники. По этой причине сбои случаются столь редко, что никто не считает нужным предпринимать дополнительные усилия, направленные на борьбу с ними. С другой стороны, мы увидим, что квантовые компьютеры — устройства весьма деликатные и требуют надежной техники для исправления ошибок.
В компьютерах разной архитектуры влияние шума проявляется по-разному. Если, например, шум влияния не оказывает, то переход на параллельные вычисления может и не повлиять на количество операций, необходимое для выполнения задачи. Однако параллельная система может оказаться значительно более устойчивой к шуму, чем последовательная, поскольку у шума будет меньше времени на то, чтобы его эффекты накопились. Следовательно, при реалистическом анализе параллельная версия алгоритма может иметь существенные преимущества перед последовательной.
Проблемы архитектуры хорошо разработаны для классических компьютеров. Для квантовых компьютеров аналогичных исследований почти не проводилось, но изучение влияния шума уже подсказывает некоторые желательные черты будущих квантовых компьютеров, в частности, высокую степень параллелизма. Четвертая модель вычислений — это распределенные вычисления, при которых два или более разнесенных в пространстве вычислительных устройства используются для решения одной задачи.
Разумеется, эта вычислительная модель не более производительна, чем машина Тьюринга, в том смысле, что на машине Тьюринга ее можно эффективно моделировать. Однако распределенные вычислЕния подсказывают новую и интригующую задачу о ресурсах: как наилучшим образом использовать несколько вычислительных устройств в условиях, когда высока цена передачи информации от одного устройства к другому. Эта задача становится особенно интересной, если компьютеры соединены высокоскоростной сетью: хотя суммарная вычислительная производительность всех компьютеров в сети может быть весьма высока, использовать этот потенциал непросто.
Наиболее интересные задачи трудно разбить на незави- 216 Глава 3. Введение в информатику симые части, которыми можно заниматься по отдельности. Часто требуется связь между различными компьютерами в сети для обмена промежуточными результатами или синхронизации состояний. С целью изучения этих проблем была развита теория коммуникационной сложности, в которой вычисляется стоимость обмена информацией при решении задач. Если доступны квантовые ресурсы, которыми можно обмениваться по сетям, то в некоторых случаях коммуникационяую сложность можно значительно уменьшить. Основная мысль, которая проходит через эти заключительные замечания, да и через всю эту книгу, такова: несмотря на то, что традиционно информатика не зависит от физических ограничений, в конечном счете законы физики оказывают огромное влияние не только на физическую реализацию компьютеров, но и на то, какого рода задачи подцаются решению.
Успех квантовых вычислений и квантовой теории информации как физически осмысленной альтернативной модели вычислений выдвигает идеи информатики на передний край физики. Цель, преследуемая авторами остальной части данной книги— соединить идеи этих двух далеких областей знания и получить удовольствие от полученного результата. Задача 3.1 (мшпины Минского).
Машина Минского состоит из конечного числа регистров тм тг..., ть, в каждом из которых может храниться произвольное целое неотрицательное число, и программы, состоящей из дирекшив двух типов. Директивы первого типа имеют следующий вид: т п Я Интерпретировать это надо следующим образом: при выполнении директивы та содержание регистра ту увеличивается на единицу, и управление передается в точку, соответствующую директиве н. Второй тип директивы таков н Эта директива интерпретируется так: при выполнении директивы ш содержание регистра т, уменьшается на единипу, если в нем записано положительное число, и управление передается в точку, соответствующую директиве и; если же в регистре т записан нуль, то его значение не меняется, а управление передается в точку, соответствующую директиве р.
Программа для машины Минского состоит из набора таких директив, записанного, например, в виде 1 1 3.3. Перспективы информатики 217 Начало программы (а также все возможные точки остановки) обычно обозначается числом нуль. Эта программа берет содержимое регистра г~ и прибавляет его к содержимому регистра гэ, последовательно уменьшая содержимое регистра г~ до нуля. (1) Докажите, что все вычислимые (с помощью машины Тьюринга) функции вычислимы и на машине Минского в том смысле, что для данной вычнслимой функции 1 ( ) существует такая программа для машины Минского, что если в начале работы регистры находятся в состоянии (и, О,..., 0), то в конце они будут в состоянии (7'(и), О,..., 0). (2) Дайте набросок доказательства того факта, что любая функция, вычислимая на машине Минского в описанном выше смысле, вычислима и на машине Тьюринга.
Задача 3.2 (векторные игры). Векшорнал игра задается конечным списком целочисленных векторов одной размерности. Сама игра состоит в следующем: берется вектор х с целыми неотрицательными координатами и к нему прибавляется первый из тех векторов списка, сумма которого с х имеет неотрицательные координаты; далее процесс повторяется, пока это возможно. Докажите, что для любой вычислимой функции 7 ( ) существует векторная игра, которая, будучи начатой с вектора (п,О,...,0), завершается на векторе Щп),0,..., 0). (Уяиание.
Покажите, что с помощью векторной игры размерности й + 2 можно моделировать машину Минского с й регистрами.) Задача 3.3 (Фрактран). Программа на языке Фрактран задается с помощью последовательности положительных рациональных чисел дм..., д„. При подаче на вход целого положительного числа т оно заменяется на д;гп, где 1— наименьший номер, для которого число д;гп целое, после чего процесс повторяется. Если в какой-то момент такого 1 не находится, программа останавливается.
Докажите, что для любой вычислимой функции 7( ) существует программа на Фрактране, которая при подаче на вход числа 2" останавливается на числе 2Д"~, причем в процессе вычислений другие степени двойки не появляются. ( Укаэанне.
Воспользуйтесь предыдущей задачей.) Задача 3.4 (неразрешнмость динамических систем). Программа на Фрактране является по существу очень простой динамической системой на множестве целых положительных чисел. Покажите, что не существует алгоритма, позволяющего выяснить, содержит ли какая-либо траектория такой системы число 1. Задача 3.5 (двухбитовая обратимая логика не универсальна). Пусть мы пытаемся строить схемы, используя только одно- и двухбитовые обратимые эремевты, а также вспомогательные биты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
