М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 56
Текст из файла (страница 56)
Докажите, что существуют булевы функции, которые нельзя вычислить таким образом. Выведите отсюда, что элемент Тоффоли невозможно реализовать с помощью одно- и двухбитовых обратимых элементов даже с использованием вспомогательных битов. 218 Глава 3. Введение в информатику Задача 3.6 (трудность приближенного решения задачи коммивояжера). Пусть г > 1, и предположим, что для задачи коммивояжера существует приближенный алгоритм, позволяющий найти обход п городов кратчайшим с точностью до множителя г. Пусть С = (К Е) — произвольный граф с п вершинами. Рассмотрим следующую задачу коммивояжера: города — это вершины графа, причем расстояние между городами г и у равно 1, если (1,у) — ребро графа С, и (г1 'У~ + 1 в противном случае.
Покажите, что если применить наш приближенный алгоритм к этой задаче, то на выходе получится либо гамильтонов цикл, если такой существует, либо маршрут, длина которого превышает (г ~ Я. Из ХР-полноты задачи о гамильтоновом цикле выведите, что такой приближенный алгоритм существовать не может, если неверно, что Р = 1чР. Задача 3.7 (обратимые машины Тьюринга). (1) Обьясните, как сконструировать обратимую машину Тьюринга, которая может вычислять те же функции, что и обычная машина Тьюринга. ( Указание.
Вам может помочь многоленточная конструкция.) (2) Дайте оценки памяти и времени, необходимых вашей обратимой машине Тьюринга, через время 1(х) и память э(х), требуемые обычной одноленточной машине Тьюринга для вычисления той же функции у(з). Задача 3.8 (найти трудновычислимый класс функций — задача для исследования). Найдите естественный класс функций от п переменных, для вычисления которых булевыми схемами требуется сверхполиномиальное коли- чество булевых элементов. (3.9) (3.10) Л„Ч,Л„...Ч,„~р, если и четно Ч,, э'„Ч,„... Я,.„д, если и нечетно Докажите, что с помощью обратимой машины Тьюринга, работающей на по- линомиальной памяти, язык ЯЯАТ можно распознать. Таким образом, класс языков, распознаваемых обратимым компьютером, который работает на поли- номиальной памяти, совпадает с РЯРАСЕ.
Задача 3.10 (вспомогательные биты и эффективность обратимых вычислений). Пусть р,„— гп-ое простое число. Дайте набросок конструкции обратимой схемы, которая, получив на вход числа гп и и, где и > та, выдаег произведение р р„, т. е., (т,п) -+ (р р„,д(т, п)), где 9(т, п) — конечное состояние вспомогательных битов. Оцените количество вспомогательных битов, Задача 3.9 (обратимый РЯРАСЕ = РЯРАСЕ). Можно показать, что «задача выполнимости с кванторамиэ, или ЯЯАТ, является РЯРАСЕ-полной.
Это означает, что любой другой язык из класса РЯРАСЕ сводится к языку ЯЯАТ за полиномиэльное время. По определению, язык ЯЯАТ состоит из таких булевых формул ~р от и переменных хм...,з„, записанных в конъюнктивной нормальной форме, что 3.3. Перспективы информатики 219 необходимых вашей схеме. Докажите, что если можно построить обратимую схему, размер которой полиномиален (относительно !об и) и которая использует 0(1о8(1об п)) вспомогательных битов, то задача представления числа в виде произведения двух простых чисел принадлежит классу Р.
История и дополнительная литература Информатика — это большой предмет, в котором есть много интересных подразделов. Мы не будем пытаться дать ее полный обзор, но порекомендуем несколько изданий, представляющих общий интерес, а также некоторые работы, непосредственно связанные с тематикой нашей книги. Современная информатика началась с работы Тьюринга [388], датированной 1936 г. Тезис Черча-Тьюринга был впервые сформулирован Черчем в 1936 г. [87]; в дальнейшем он был более полно рассмотрен Тьюрингом с другой точки зрения.
Примерно в то же время несколько других исследователей пришли к аналогичным выводам. Многие из этих работ обсуждаются в книге под редакцией Дэвиса [113]. Интересное обсуждение тезиса Черча-Тьюринга можно найти у Хофштадтера [189] и Пенроуза [316]. Существует много прекрасных книг, посвященных разработке алгоритмов; мы упомянем только три. Во-первых, это классический трехтомник Кнута [224, 225, 226].
Во-вторых, отметим замечательную книгу Кормена, Лейзерсона и Ривеста [92]. Эта большая и хорошо написанная книга содержит много материала о разработке различных алгоритмов. Наконец, книга Мотвани и Рагавана [295] является превосходным обзором алгоритмов, использующих случайные числа. Современная теория вычислительной сложности возникла в значительной степени благодаря статьям Кука [99] и Карпа [209]. В России ко многим аналогичным идеям независимо пришел Левин [242], но, к сожалению, на Запад эти идеи проникли не сразу. Классическая книга Гэри и Джонсона [162] также оказала огромное влияние на работы по этой тематике. Пападимитриу написал прекрасную книгу [312], содержащую обзор многих идей теории сложности; большая часть материала, излагаемого в этой главе, основана на книге Пападимитриу.
В настоящей главе мы рассматривали только один тип сводимости, а именно сводимость за полиномиальное время. На самом деле понятий своди- мости существует несколько; их давний обзор можно найти у Ладнера, Линча и Селмана [256]. Изучение различных понятий сводимости выросло в отдельный предмет — тпеорию структпурноп сложносгии. Обзор на эту тему можно найти у Бальказара, Диаса и Габарро [38, 39].
Изучение связи между информацией, диссипецией энергии и вычислениями имеет долгую историю. Современное понимание возникло после вышедшей в 1961 г. статьи Ландауэра ]234], в которой был впервые сформулирован принцип Ландауэра. Сциллард ]383] и фон Нейман в своей лекции в 1949 г. [405] (с. 66) приходят к близким выводам, но они не в полной мере осознавали, что именно спшрание информации приводит к диссипации энергии. Обратимые машины Тьюринга были изобретены Лесерфом [240], а позднее (независимо) переоткрыты в оказавшей большое влияние статье Беннета [44].
220 Глава 3. Введение в информатику Фредкин и Тоффоли [156) ввели вычислительную модель, основанную на обратимых схемах. Исторический интерес представляют курсовая работа Бартона в М1Т [18) и дипломная работа Ресслера [338], в которой разработан проект обратимого аналога машины РПР-10. В наши дни обратимая логика имеет важное значение для разработки схем СМОЗ малой мощности [426). Демон Максвелла — интересная тема, имеющая долгую и захватывающую историю.
Максвелл выдвинул зту идею в 1871 г. [277]. В 1929 г. Сциллард опубликовал ключевую статью [383], в которой были предвосхищены многие детали полного решения проблемы демона Максвелла. В 1965 г. Фейнман [152] опубликовал решение частного случая задачи о демоне Максвелла. Беннет, основываясь на работе Ландауэра [234], написал две прекрасные работы на эту тему [46, 47], в которых решение проблемы было завершено. Интересная книга об истории демона Максвелла и его изгнании — сборник статей под редакцией Леффа и Рекса [267]. ДНК-вычисления были предложены Эдльманом; описываемое нами решение задачи об ориентированном гамильтоновом пути содержится в его статье [5].
Липтон показал, что задачи ЗЗАТ и выполнимости схемы также могут быть решены при помощи этой модели. Хорошая обзорная статья Эдльмана на эту тему опубликована в Яс~еп1фс Атег1сап [6]; относительно универсальности ДНК-операций см. работу Уинфри ]419]. По поводу надежных операций при наличии шума интересно посмотреть книгу Винограда и Коуэна [412]; мы еще обратимся к этой теме в гл.
10. Хорошим учебником по архитектуре компьютеров является книга Хеннесси, Гольдберга и Паттерсона [177). Задачи 3.1-3.4 следуют идеям, введенным Минским (в его прекрасной книге о вычислительных машинах [287]) и развитым Конуэем [97, 98). Язык Фрактран представляет собой одну из наиболее красивых и элегантных вычислительных моделей; мы продемонстрируем это на следующем примере, известном под названием РИМЕСАМЕ[98]. РШМЕСАМЕ задается списком рациональных чисел: 17 78 19 23 29 77 95' 77 1 11 13 15 1 55 91' 85' 51' 38' 33' 29' 23' 19' 17' 13' 11' 2 ' 7' 1 Удивительно,что, если подать на вход этой фрактрановской программы число 2, то все остальные возникающие степени двойки, а именно 2з,2з,2з, 2~, 2'~,2~~,..., будут в точности числом 2 в простых степенях в порядке возрастания. Задача 3.9 — пример из области исследований, занимающейся проблемами памяти при обратимых вычислениях.
См. статьи Беннета [48), а также Ли, Тромпа и Витаньи [272, 271]. Часть 11 Квантовые вычисления Глава 4 КВАНТОВЫЕ СХЕМЫ Теория вычислений традиционно изучалась абстрактно, как раздел чистой математики. При етом теряется ее суть. Компьютеры — зто физические обеекты, а вычисления— физические процессы. Чтб колтьютеры могут вычислить, а чтд — не могутп, опредагяется исключительно законами физика, а не чистой математикой.
Д. Дойч Подобно математике„теоретическая информатика несколько отличается от остальных наук в том отноигении, что имеет дело с искусственными законами, которые могут быть доказаны, в отличие опг законов природы, которые никогда не будут известны до конца. Д. Кнут Противоположностью глубокой истины может быть и другая гяубокол истина. Н. Вор Эта глава открывает вторую часть книги, где подробно рассматривается квантовые вычисления.
Здесь разрабатываются фундаментальные принципы квантовых вычислений и обсуждаются основные компоненты квантовых схем, являющихся основным языком описания сложных квантовых вычислений. Два основных квантовых алгоритма, известных в настоящее время, строятся с помощью квантовых схем в двух последующих главах. В гл. 5 речь идет о квантовом преобразовании Фурье и его приложениях к задачам определения собственного числа, вычисления периода и факторизации целого числа. Гл.
6 описывает квантовый алгоритм поиска и его приложения к поиску в базах 222 Глава 4. Квантовые схемы дшшых, задачам перечисления и ускорению решения ЖР-полных задач. В завершающей вторую часть гл. 7 обсуждается, каким образом квантовые вычисления могут быть когда-нибудь реализованы на практике. Две другие темы, вызывающие большой интерес в связи с квантовыми вычислениями, — квантовый шум н квантовое исправление ошибок, — вошли в третью часть книги, так как они представляют самостоятельный интерес независимо от квантовых вычислений. В данной главе вводятся две основные идеи. Во-псрвых, подробно объясняется фундаментальная модель квантовых вычислений — квантовые схемы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
