М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 53
Текст из файла (страница 53)
Действие втой схемы можно представить в виде (х,а) -+ (7(х),д(х)). Теперь мы знаем, как вычислять функции обратимым образом. К сожале- нию, при таком вычислении возникают нежелательные мусорные биты. Если 208 Глава 3. Введение в информатику слегка модифицировать этот метод, то окажется, что можно провести вычисления таким образом, что все мусорные биты окажутся в спюндартлиом состоянии. Эта конструкция является ключевой для квантовых компьютеров, поскольку мусорные биты, значения которых зависят от х, будут, вообще говоря, разрушать свойства интерференции, необходимые для квантовых вычислений.
Чтобы понять эту конструкцию, удобно предположить, что мы имеем в своем распоряжении элемент нот, так что можно считать, что все вспомогательные биты равны нулю (для превращения вспомогательных нулей во вспомогательные единицы установим элементы ноттем, где это необходимо). Удобно также предположить, что в нашем распоряжении есть классический элемент «управляемое нот», определенный аналогично квантовому определению из подразд. 1.3.2, т.
е. этот элемент переводит вход (с, $) в выход (с, с Ю1), где Ю обозначает сложение по модулю 2. Отметим, что при Ф = 0 получаем (с, О) — » (с, с), так что управляемое иотможно использовать как обратимый вариант операции гАНОБТ, не оставляющий мусора на выходе. Добавив дополнительные элементы потна входе, ьюжно записать действие схемы в виде (х, О) -+ Щз), д(х)). Мы могли бы также добавить на входе схемы элементы ОХОТ, чтобы создать копию х, сохраняемую в процессе последующих вычислений.
С учетом этих модификаций действие схемы можно записать в виде (я,0,0) «(х,7(х),д(х)). (3.7) Формула (3.7) — это очень удобный способ записи действия обратимой схемы, поскольку она приводит к идее обращения вычисления, с помощью которого можно избавиться от мусорных битов за счет небольшого увеличения времени работы. Предположим, что мы имеем четырехрегистровый компьютер с нз чальным состоянием (х, О, О, д). Во втором регистре будет храниться результат вычислений, в третьем — мусорные биты д(х). Зачем нужен четвертый регистр, мы объясним позже, а пока будем считать, что в начальном состоянии в нем хранится произвольная информация у. Начнем, как и выше, с вычисления ?' с помощью обратимой схемы, что даст на выходе (я, 7(я), д(х), у).
Затем воспользуемся элементами СКОТ для побитового сложения 7'(х) с содержимым четвертого регистра, в результате получим состояние (х, Дя), д(з), у Ю у (х)) . Однако все этапы вычисления ? (з) были обратимы и не затрагивали четвертого регистра, так что применяя элементы исходной схемы, использованной для вычисления 7', в обратном порядке получим (з, О, О, д Ю,7(х) ). Обычно в таких записях мы будем опускать вспомогательные нули и записывать действие схемы в виде (х, у) -+ (я, у Ю,? (х)) (3.8) Обычно под обратимой схемой, вычисляющей 7", мы будем иметь в виду именно эту схему, хотя в принципе существует и много других обратимых схем, с помощью которых можно вычислять ?.
Какие дополнительные ресурсы нужны для обратимого вычисления? Чтобы ответить на этот вопрос, нужно сосчитать количество требуемых вспомогательных битов и сравнить количество элементов в обратимой и классической 3.2. Анализ вычислительных задач 209 схемах. Ясно, что число элементов в обратимой схеме то же, что и в классической, с точностью до постоянного множителя, указывающего, сколько элементов Фредкина необходимо для реализации одного элемента в необратимой схеме (этот множитель надо еще умножить на два для учета обращения вычисления), плюс количество элементов СКОТ, участвующих в обратимом вычислении, которое линейно зависит от количества битов. Аналогично количество требуемых вспомогательных битов линейно зависит от количества элементов в необратимой схеме, поскольку каждый элемент в необратимой схеме реализуется с помощью постоянного числа вспомогательных битов.
В результате, классы сложности Р и ХР получаются одни и те же независимо от того, обратимая или необратимая вычислительная модель используется для их определения. Для других классов сложности, например РЯРАСЕ, ситуация не настолько очевидна; см. задачу 3.9 и разд. еИстория и дополнительная литература» по поводу этих тонкостей.
Упражнение 3.31 (обратимый полусумматор). Постройте обратимую схему, которая, получив на входе биты х и у, выдает (х, у, с,х Ф у), где с— бит переноса. Элемент Фредкина и его биллиардная модель обеспечивают красивую реализацию обратимых вычислений. Существует еще один обратимый логический элемент, элемент Тог)1фоли, также являющийся универсальным с точки зрения классических вычислений. Хотя элемент Тоффоли не обладает такой же элегантной физической простотой, что и элемент Фредкина, при исследовании квантовых вычислений он будет полезнее.
Мы уже имели дело с элементом Тоффоли в подразд. 1.4.1, но для удобства укажем его свойства и здесь. У элемента Тоффоли три входных бита а, Ь и с; биты а и Ь называются первым и вторым уаравллющими битами, бит с называется ущиеллема»м битам. Элемент оставляет оба управляющих бита неизменными, меняет значение управляемого бита на противоположное, если оба управляющих бита установлены в единицу, и оставляет управляемый бит неизменным в противном случае.
Таблица значений для элемента Тоффоли и его условное обозначение представлены на рис. 3.17. Ь Ь с с®аЬ Рис. 3.17. Таблица значений длл элемента Тоффоли и его условное обозначение 14 Квюп а»» ен» 210 Глава 3. Введение в информатику Как можно проводить универсальные вычисления с помощью элемента Тоффоли? Предположим, что мы хотим провести операцию ХАХП над битами а и 6. Чтобы сделать это с помощью элемента Тоффоли, подадим а и 6 на вход в качестве управляющих битов, а вспомогательный бит, установленный в 1, подадим в качестве управляемого бита (см. рис.3.18). Как следовало ожидать из предыдущего рассмотрения элемента Фредкина, реализация ИАХЭ с помощью элемента Тоффоли требует вспомогательного бита на входе, а некоторые из выходных битов являются мусором.
= -(а6) Рис. 3.18. Реализация элемента МАМО при помощи элемента Тоффоли. Два верхних бита представляют вход элемента МАМО, третий бит устанавливают в состояние 1. Выход элемента МАМΠ— третий бит С помощью элемента Тоффоли можно также реализовать операцию гАХОУТ, подав вспомогательный бит 1 в качестве первого управляющего бита, а бит а — в качестве второго управляющего бита, что даст на выходе 1, а, а. Это проиллюстрировано на рис. 3.19. Вспоминая, что элементы г1Аг1Гг и гА?яОУТ позволяют реализовать любое вычисление, мы получаем, что любую схему можно эффективно моделировать с помощью обратимой схемы, состоящей только из элементов Тоффоли и вспомогательных битов, и что обращения вычислений можно добиться теми же методами, которые были использованы при обсуждении элемента Фредкина.
1 1 0 а Рис. 3.19. Реализация ЕАМОПТ при помощи элемента Тоффоли Второй бит — вход элемента гАМОПТ, два других входных бита — вспомогательные Выход элемента РАМООТ вЂ” второй и третий биты. Наш интерес к обратимым вычислениям вызван желанием понять, какие затраты энергии требуются для вычислений. Ясно, что при отсутствии шума биллиардная модель вычислений энергии не потребляет; что можно сказать о моделях, основанных на элементе Тоффоли? На этот вопрос можно ответить, 3.2. Анализ вычислительных задач 211 только рассматривая конкретные реализации этого элемента. В гл. 7 мы обсудим некоторые из них и увидим, что элемент Тоффоли действительно можно реализовать без затрат энергии.
Говоря о том, что вычисления можно проводить без затрат энергии, следует проявлять большую осторожность. Как мы уже отмечали, биллиардная модель вычислений весьма чувствительна к шуму, и это же верно применительно ко многим другим моделям обратимых вычислений. Чтобы ликвидировать воздействие шума, необходимо в той или иной форме производить исправление ошибок.
Обычно исправление ошибок подразумевает проведение измерений с тем, чтобы выяснить, ведет ли себя система ожидаемым образом или произошли ошибки. Поскольку память компьютера конечна, результаты этих измерений должны быть в какой-то момент уничтожены, чтобы освободить место для записи новых измерений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
