М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 44
Текст из файла (страница 44)
— Прим. Верее. 3.1. Вычислительные модели 175 вычислить функцию остановки. Является ли проблема остановки неразрешимой на этой модели? Другими словами, существует ли машина Тьюринга с оракулом для проблемы остановки, которая определяет, останавливается ли заданная машина Тьюринга с оракулом для проблемы остановки при заданном входе? 3.1.2 Схемы Машины Тьюринга — довольно идеализированные модели вычислительных устройств. Настоящие компьютеры имеют конечные размеры, тогда как длина ленты машины Тьюринга не ограничена.
В этом разделе мы изучим альтернативную модель вычислений, а именно схемндю модель, которая эквивалентна машине Тьюринга с точки зрения вычислительных возможностей, но более удобна и реалистична во многих приложениях. В частности, схемная модель вычислений особенно важна в качестве подготовки к нашему исследованию квантовых компъютеров. Схема состоит из проводов, переносящих информацию, и эламемпзов, производящих простые вычислительные операции.
Например, на рис. 3.2 изобрзэкена простая схема, на вход которой поступает один бит а. Этот бит пропускается через элемент НОТ, который обращает его, переводя 1 в О и О в 1. Провода перед и после элемента НОТ служат только для того, чтобы перенести бит через элемент; они представляют движение бита в пространстве а, может быть, и просто во времени. Вообще, у схемы может быть много входных и выходных битов, проводов и логических элементов.
Логическим эламенпзом называется функция 7": 10,1)Я -а (О, 1)~, переводящая набор из и входных битпов в набор из 1 выходных битов (к и 1 фиксировальа). Например, элемент НОТ вЂ” это элемент с одним входным и одним выходным битом, вычисляющий функцию у'1а) = 1®а, где а — бит, а цу — сложение по модулю 2. Обычно считают, что в схеме нет циклов (чтобы избежать неустойчивости, как на рис. 3.3). Мы будем говорить, что схема без циклов ациклична, и придерживаться соглашения, что все схемы в схемной модели вычислений ацикличны. Рис.
3.2. Элементарная схема, производящая одну операцию МОТ над одним битом Существует много других элементарных логических элементов, полезных для вычислений. В частности, в их число входят элементы АНО, ОН, ХОН, НАНО и ИОН. Каждый из этих элементов принимает два бита на входе и выдает один бвт на выходе. Элемент АНО выдает 1 тогда и только тогда, когда оба входных бита равны 1. Элемент ОН выдает 1 тогда и только тогда, когда хотя бы один яз входных битов равен 1. Элемент ХОВ. выдает сумму своих входных битов 176 Глава 3. Введение в информатику Рис. 3.3. Схемы, содерчсащие циклы, могут быть неустойчивы и обычно не допускаются в схем- ной модели вычислений, а аймоь а мот а (а) (Ь) ~ ~ — а ока ахой Ь (а) а (а) Ь а мамо Ь (б а ь а мой Ь Рис.
3.4. Элементарные схемы, выполняющие операции АМО, Ой, Хой, МАМО и Мой. На рис. 3.4 отсутствуют два важных «элемента», а именно РАХО11Т и СВОЯЯОУЕН. В схемах нередко приходится «заставлять» бит «делитьсям Тогда вместо одного бита получаются две его копии. Эта операция и называется РА1т'ОУТ. Кроме того, иногда нужно поменять местами значения двух битов. Это достигается операцией СНОЯЯОУЕВ,. Третья операция, отсутствующая на рис. 3.4 и вообще не являющаяся логическим элементом, — это подготовка доооднотеаьных, или рабочих, битов, что обеспечивает дополнительное рабочее пространство во время вычисления.
по модулю 2. Элементы НА1ьП1 и НОВ применяют АХП и ОВ соответсвенно к своим входным битам, а затем — операцию НОТ к полученным результатам. Действие этих элементов проиллюстрировано на рис. 3.4. 3.1. Вычислительные модели 177 Эти простейшие элементы схем можно соединять и выполнять таким образом очень большое количество вычислений. Ниже мы покажем, что с помощью этих элементов можно вычислить любую функцию, а пока остановимся на простом примере схемы, вкладывающей два и-битовых числа с использованием по существу того же самого алгоритма, который изучают школьники во всем мире.
Основной составной частью этой схемы является схема меньшего размера, известная под названием иалусулалеатор (Ьа11-асЫег, сокращенно НА). Схема полусумматора изображена на рис. 3.5. Полусумматор получает на вход два бита х и у и выдает х тр у — их сумму по модулю 2, бит иеремоса с, равный 1, если и х, и у равны 1, и О в противном случае. х О+у У Рис. 3.5. Схема лолусумматора Бит переноса с устанавливается в единицу, если и и у равны единице, в лротивном случае с = О. Соединив два полусумматора, можно получить сумматор 1тп1!-аоаег, сокращенно гА), изображенный на рис. З.б.
Сумматор получает на входе три бита х, у и с. Виты х и у — это данные, которые требуется сложить, а с — бит переноса, полученный при предыдущем вычислении. Схема выдает на выходе два бита. Один из них — это сумма х Ю у Щ с трех входных битов по модулю 2. Второй выходной бит с' является битом переноса, который устанавливается в единипу тогда и только тогда, когда два или более входных бита равны 1. хО+у О+с Рис. З.б. Схема сумматора. Соединяя сумматоры, мы получаем схему, складываюшую два и-битовьпс целых числа (см. рис. 3,7 для случая и = 3). Выше мы отмечали, что с помощью фиксированного набора элементов можно вычислить любую функцию у: (О, Ц" -ч (О, Ц™. Теперь докажем упрощенный вариант этого утверждения: для функций у: (О, Ц" -» (О, Ц с и входными битами и одним выходным битом.
Такая функция называются булевой функцией„а соответствующая схема — булевой схемой. Универсальность схем в общем 12 х»» нн»н» 178 Глава 3. Введение в информатику случае следует из частного случая булевых функций. Доказательство проводится индукцней по кч При а = 1 существуют четыре функции: тождественная, которой соответствует схема, состоящая из одного провода; обращение бита, получаемое с помощью одного элемента (ь(ОТ; функция, замещающая входной бит на О, которую можно реализовать путем применения операции А%Э к входному биту и рабочему биту, равному О, и, наконец, функция, переводящая входной бит в 1, которую можно реализовать, применяя операцию ОВ к входному биту и рабочему биту, равному 1.
Х г Уг Х У, Х У, Рис. 3Л. Схема, складыаающал деа трекоитоаык целых числа з = иас1со и р = рашко с помощью алгоритма, изучаемого школькиками Чтобы провести индукционный шаг, предположим, что любую функцию от и битов можно вычислить с помощью схемы и пусть 7' — функция от п + 1 бита. Определим и-битовые функции Уо и у1 формулами Уо(хы. хп) ы 1(о,хм...,х„) и Яхы...,х„) = У(1,хы...,х„). Обе эти функции являются и-битовыми и, следовательно, по предположению индукции могут быть вычислены с помощью схем. Теперь легко построить схему, вычисляющую функцию 1. Эта схема, изображенная на рис. 3.8, вычисляет уо и 11 от последних и битов. Затем в зависимости от того, равен первый бит нулю или единице, она выдаег соответствующий ответ. Тем самым индукция завершается.
В конструкции универсальной схемы можно выделить пять компонентов: (1) провода, сохраняющие состояния битов; (2) приготовленные в стандартных состояниях вспомогательные биты, которые используются при доказательстве для случая и = 1; (3) элемент гАг(ОПТ, получающий на вход один бит и выдающий две копии'этого бита; (4) элемент СКО8807ЕК, менявзщнй местами значения двух битов; (5) элементы Аг1Р, ХОВ.
и ВОТ. В главе 4 мы определим квантовые схемы подобно тому, как мы определили классические схемы. Любопытно отметить, что при построении квантовых аналогов указанных классических элементов возникают интересные проблемы: не очевидно, что хотя бы в принципе можно создать хорошие квантовые провода, в которых будут сцхраняться кубиты, операцию гАг(ОПТ в квантовой механике нельзя реализовать непосредственно (ввиду теоремы о невозможности копирования, о которой шла речь в подразд. 1.3.5), а элементы Аг1П и ХОК не являются обратимыми и тем 3.1. Вычислительные модели 179 самым не могут быть непосредственно реализованы как унитарные квантовые элементы.
Конечно, при определении квантовой схемной модели есть о чем подумать! «г «л Рис. З.о. Схема, вычисляющая произвольную и+ 1-битовую функцию; ло предположению индукции существуют схемы, вычисляющие я битовые функции уо и ут Упражнение 3.8 (уннверсальность элемента 1к?АХР). Покажите, что с помощью элемента МА)к!П можно реализовать элементы Аг!П, ХОВ и г!ОТ, если использовать провода, вспомогательные биты и РАНОПТ. Вернемся теперь к свойствам классических схем.
Ранее мы отмечали, что машина Тьюринга эквивалентна схемной модели вычислений. Но что же мы понимаем под этой эквивалентностью? При поверхностном рассмотрении эти две модели представляются совершенно разными. Неограниченность машин Тьюринга делает их более полезными для абстрактного определения понятия алгоритма, тогда как схемы более удачно имитируют то, что происходит в настоящих компьютерах. Две названные модели связываются с помощью понятия однородного селсейсвзеа схем. По определению, семейство схем состоит из набора схем (С„), пронумерованных натуральными числами п.
Схема С„имеет п входных битов и может иметь любое конечное число вспомогательных и выходных битов. Результат применения схемы С„к числу, длина записи которого не превышает п битов, обозначается Ся(х) . Мы накладываем условие, чтобы семейство было соацсствным, т. е. чтобы при т < п выполнялось равенство С (х) = С„(х) для любого числа х, содержащего не более пт битов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
