Научная литература
booksshare.net -> Добавить материал -> Физика -> Стин Э. -> "Квантовые вычисления " -> 14

Квантовые вычисления - Стин Э.

Стин Э. Квантовые вычисления — НИЦ: Регулярная и хаотическая динамика, 2000. — 112 c.
Скачать (прямая ссылка): kvantovievichesleniya2000.pdf
Предыдущая << 1 .. 8 9 10 11 12 13 < 14 > 15 16 17 18 19 20 .. 45 >> Следующая

Если данное вычисление будет выполняться автоматически, то Боб сможет
узнать значение Н ¦ е, называемое синдромом ошибки без определения слова
и\ Если Боб сможет из величины Н ¦ е выделить значение ошибки е (можно
показать, что это возможно для всех исправляемых кодов), то он сумеет
исправить сообщение, удаляя из него ошибку е, даже не вникая в его смысл!
При исправлении квантовых ошибок данное действие является основным
объяснением тому, как можно исправить квантовое состояние не нарушая его.
Глава 3
Классическая теория вычислений
Теперь обратимся к теории вычислений. Главным образом, она затрагивает
такие вопросы, как "Что является определением вычислимости?", "Какие
средства необходимы для вычисления?".
Фундаментальными средствами, необходимыми для вычисления, являются
средствами хранения и обработки символов. Существенными вопросами
являются такие, как: "Насколько сложными должны быть символы и операции
над ними?", "Сколько символов и операций необходимо для вычисления?".
Основной вывод теории заключатся в том, что вычисление считается сложным
или неэффективным, если объем необходимых для него средств возрастает
экспоненциально в зависимости от размера задачи, которую необходимо
решить. Размер задачи задается количеством информации, необходимой для ее
описания. На базовом уровне из вышесказанного следует, что вычислительное
устройство должно уметь оперировать не только унарными1, но и двоичными
символами. В противном случае число ячеек памяти будет экспоненциально
зависеть от количества информации, которую необходимо обработать. С
другой стороны, нет необходимости использовать десятичную систему
счисления (10 символов) или любую другую систему, "алфавит" которой
состоит более чем из двух символов, что существенно упрощает структуру
компьютера и операции им выполняемые.
При работе с п двоичными символами нет необходимости оперировать сразу
всеми символами. Можно показать, что любое преобразование может
осуществляться при обработке одного или пары символов за раз. Двоичный
"логический гейт" имеет на входе два бита х, у и вычисляет функцию f(x,
у). Поскольку функция может принимать значения 0 и 1, и существует четыре
возможных варианта входных данных, то можно определить 16 возможных видов
функции /. Множество,
:В унарном обозначении используется лишь символ 1. Положительные целые
числа будут записываться следующим образом: 1, 11, 111, 1111 ...
38
Глава 3
состоящее из 16 различных логических гейтов, образует так называемое
"универсальное множество", поскольку, комбинируя такие гейты в
последовательности, можно осуществить любое преобразование п битов. Более
того, действие некоторых гейтов может быть воспроизведено посредством
комбинирования других гейтов. Таким образом, не нужно использовать все 16
функций, фактически потребуется лишь один гейт: И-НЕ (NAND gate) (на
выходе этого гейта появится 0, только если
оба входных значения равны 1).
Путем объединения логических гейтов можно обрабатывать символы, состоящие
из п битов (см. рис. 6). Данный подход называется сетевой моделью
вычисления. Он полезен в том смысле, что от него можно перейти к модели
квантового вычисления, которая на сегодняшний день находит широкое
применение в экспериментах. Основными составляющими данной модели
являются множество битов, многократно повторяющийся универсальный
логический гейт и связи между гейтами.
3.1. Универсальный компьютер. Машина Тьюринга
Слово "универсальный" по отношению к компьютерам приобретает более
глубокий смысл. Тьюринг показал, что возможно создать универсальный
компьютер, имитирующий работу любого другого вычислительного устройства
следующим образом: пусть машина Тьюринга Т обрабатывает входное значение
х, поступающее с входной ленты, и имеет на выходе значение Т(х) (рис. 7).
Полностью определить машину Тьюринга можно посредством зависимости
выходных значений от О и 1 на входной ленте для всех ее возможных
внутренних конфигураций, число которых конечно. Само по себе это
определение может быть представлено в виде двоичного числа Д[Т]. Тьюринг
показал, что существует машина U, называемая универсальной машиной
Тьюринга, которая обладает следующими свойствами:
>------------------------
Рис. 6. Классический компьютер может быть построен на основе сети
логических гейтов
U(d[T], X) = Т(х),
(18)
3.1. Универсальный компьютер. Машина Тьюринга 39
ДУГ1111 °1 °1ЛЩ [Тнчоы.нЯ?
Рис. 7. Машина Тьюринга. Представляет собой умозрительное механическое
устройство. Можно показать, что оно может эффективно имитировать все
классические методы вычислений. Машина содержит конечное множество
внутренних состояний и обладает жесткой схемой. За определенный момент
времени машина считывает с ленты один двоичный символ. Ответное действие
(реакция) машины зависит только от данного символа s и от внутреннего
состояния G и заключается в записи символа s' на место считываемого
символа s, перехода в новое состояние G' и сдвиге ленты на одну позицию в
Предыдущая << 1 .. 8 9 10 11 12 13 < 14 > 15 16 17 18 19 20 .. 45 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed