М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 54
Текст из файла (страница 54)
Согласно принципу Ландауэра, при этом расходуется энергия, которую необходимо учитывать при вычислении энергетических затрат на вычисления. Более подробно мы рассмотрим энергозатраты, связанные с исправлением ошибок, в подразд. 12.4.4. Итак, что же мы можем заключить, исходя из нашего рассмотрения обратимых вычислений? Основных выводов три. Во-первых, обратимость получается, когда мы следим за каждым битом информации; необратимость возникает только тогда, когда информация теряется или уничтожается. Во-вторых, проводя обратимые вычисления, мы избавляемся от необходимости тратить энерппо на вычисления.
В принципе любое вычисление можно провести без затрат энергии. В-третьих, обратимые вычисления можно провести эффективно, не выдавая мусорных битов, значения которых зависят от входных битов. Другими словами, если существует необратимая схема, вычисляющая функцию 1, то она может быть эффективно смоделирована с помощью обратимой схемы, действующей по правилу (т,р) -+ (з,у Ю Дх)). Каковы следствия всего этого для физики, информатики„а также для квантовых вычислений и квантовой теории информации? С точки зрения физика или инженера-компьютерщика, которого беспокоит выделение тепла, хорошие новости состоят в том, что в принципе возможно проводить вычисления без диссипации энергии, сделав их обратимыми, хотя на практике диссипэция энергии придает системе устойчивую нечувствительность к шуму.
На еще более фундаментальном уровне идеи, ведущие к обратимым вычислениям, приводят также к решению стоявшей сто лег проблемы физики — знаменитой проблемы де»«ава Максвелла. История этой проблемы и ее решение приведены во вставке 3.5. С точки зрения специалиста по информатике обратимые вычисления оправдывают использование необратимых элементов в вычислительных моделях, например в машине Тьюринга (поскольку модели с необратимыми элементами и без них полиномиально эквивалентны). Более того, поскольку физический мир в основе своей обратим, можно заключить, что классы сложности, основанные на обратимых моделях, более естественны, чем классы, основанные на необратимых моделях (мы еще вернемся к этому замечанию в задаче 3.9 и в разделе «История и дополнительная литература»).
С точки зрения квантовых вычислений и квантовой информации обратимые вычисления и 212 Глава 3. Введение в информатику крайне важны. Чтобы использовать эффективность квантовых вычислений в полную силу, все классические подпрограммы в квантовых алгоритмах должны быть обратимы и не выдавать мусорных битов, зависящих от классических входных данных. Вставка 8.5. Демон Максвелла Законы термодинамики показывают, какая работа может быть совершена системой, находящейся в термОдинамическом равновесии. Один из этих законов — второе начало термодинамики — утверждает, что энп»ролил замкнутой системы не может уменьшаться.
В 1871 г. Джеймс Кларк Максвелл предложил устройство, которое, этот закон нарушает. Представьте себе миниатюрного «демона», вроде того, что изображен на рисунке, который может уменьшить энтропию цилиндра с газом, Первоначально находящеюся в равновесии, разделяя быстрые и медленные молекулы по двум половинам цилиндра. Этот демон сидит у дверки, сделанной в середине перегородки цилиндра. Когда быстрая молекула приближается слева, демон открывает дверку, пропускает молекулы, а затем дверку закрывает.
Если проделать это много раз, то общая энтропия цилиндра уменьиаплся, что явно противоречит второму началу термодинамики. Решение этого парадокса состоит в том, что демон должен измерять скорости молекул; результаты этих измерений должны храниться в памяти демона. Поскольку любая память конечна, в какой-то момент демону придется стирать информацию, чтобы было куда записывать результаты новых измерений. Согласно принципу Ландауэра, акт стирания информации увеличивает полную энтропию системы, состоящей из демона, цилиндра и окружающей среды.
На самом деле более тщательный анализ показывает, что нз принципа Ландауэра вытекает, что полная энтропия при этом увеличивается как минимум на столько же, на сколько энтропия уменьшается в результате действий демона, так что в итоге второе начало термодинамики выполняется. 3.3 Перспективы информатики В таком кратком введении, как эта глава, совершенно невозможно подробно описать все важные идеи из такой богатой области, как информатика. Мы на- 3.3. Перспективы информатики 213 даемся, что смогли лишь отчасти объяснить, что означает ммслнпэь как специалист по информатике, и познакомить с основными терминами и концепциями, связанными с теорией вычислений. В завершение этой главы мы коротко коснемся некоторых более общих тем, чтобы вы смогли уяснить, как квантовые вычисления и квантовая теория информации вписываются в общие концепции информатики.
Наше обсуждение проводилось вокруг вычислительной модели, основанной на машине Тьюринга. Попробуем сравнить с этой моделью такие нестандартные модели вычислений, как компьютеры с широким использованием параллельных вычислений, ДНК-компьютеры и аналоговые компьютеры. Начнем с параллельных компьютеров.
Подавляющее большинство реальных компьютеров являются последовательными. Они обрабатывают инструкции одну за другой в некотором центральном процессоре. Параллельные компьютеры, напротив, могут обрабатывать несколько инструкций одновременно, что приводит к значительной экономии времени и денег. Тем не менее, в отношении эффективности параллельные вычисления не дают фундаментального преимущества по сравнению со стандартной машиной Тьюринга, поскольку машина Тьюринга может моделировать параллельный компьютер, причем ресурсы, требуемые для вычисления, — память и время — останутся полиномиально эквивалентными исходным.
Что параллельный компьютер выигрывает во времени, то он теряет в памяти, и в результате никакого существенного изменения эффективности вычислительной модели не происходит. Интересным частным случаем параллельных вычислений является техника ДНК-вычислений. Цепочка ДНК (дезоксирибонуклеиновой кислоты) представляет собой полимерную молекулу, состоящую из нуклеотидов четырех типов, обозначаемых буквами А (аденин), Ц (цитознн), Г (гуанин) и Т (тимин). При определенных условиях две цепочки могут соединиться и образовать двойную цепочку, если соответственно расположенные основания в этих цепочках комплементарны друг другу (А комплементарно Т, а Г комплементарно Ц).
С помощью различных химических приемов можно увеличивать количество цепочек, начинающихся или заканчивающихся опредевенными последовательностями оснований (реакция полимеразы), разделять цепочки по длине (гелевый электрофорез), разделять двойные цепочки на одинарные (изменяя температуру и рН), читать последовательность нуклеотидов на цепочке, разрезать цепочку и проверять, присутствует ли в пробирке определенная последовательность ДНК. Процедура надежного использования этой техники довольно сложна, но основную идею можно понять на примере. Задача об упорядоченном гамильтоновом пути — это простой вариант задачи о гамильтоновом цикле из подразд 3.2.2; она состоит в том, чтобы определить, сущесгвует ли в данном ориентированном графе С с Ф вершинами путь между двумя данными вершинами ~1 и (н, в который каждая вершина входит ровно один раз.
Эту задачу можно решить на ДНК-компьютере следующим образом. Обозначим различные последовательности оснований через х (а через зу обозначим их комплементарные дополнения), пары хахь кодируют ребра графа, а пары У зу кодируют вершины. Тйперь задача решается за пять шагов. 214 Глава 3. Введение в информатику (1) Сгенерировать случайным образом пути в графе С, создав смесь всевозможных цепочек ДНК, соответствующих вершинам и ребрам, и подождать, пока эти цепочки объединятся в пары. (2) Оставить только пути, начинающиеся с зг и заканчивающиеся на згг (увеличивая только количество удвоенных цепочек, начинающихся с й, и заканчивающихся на яу„) (3) Оставить только цепочки длины М, разделив цепочки по длинам. (4) Выбрать пути, в которые каждая вершина входит один раз: разделить ДНК на отдельные цепочки и по очереди пробовать объединять эти цепочки с цепочками, соответствуюшдми вершинами, каждый раз отбирая лишь те цепочки, которые действительно объединяются.
(5) Наконец, выяснить, осталось ли что-нибудь после этого отбора; если да, то путь существует, в противном случае нет. Чтобы обеспечить верный ответ с достаточно большой вероятностью, цепочки х можно выбирать достаточно длинными (порядка 30 нуклеотцдов), и в реакции надо использовать большое количество цепочек (порядка 10ы).в Эту схему можно улучшать с помощью различных эвристических методов, но, конечно, методы полного перебора, подобные вьппеприведенному, применимы лишь тогда, когда можно эффективно получать все возможные пути, так что число молекул должно экспоненциально расти с увеличением размера задачи (в нашем примере — с числом вершин). Молекулы ДНК относительно небольшие и легко синтезируются, а то обстоятельство, что огромное количество комбинаций нуклеотидов может умещаться в одной пробирке, может на некоторое время скомпенсировать экспоненциальный рост сложности (пока речь идет о нескольких десятках вершин), но в конечном счете экспоненциальный рост сложности ограничивает применимость этого метода.
Таким образом, хотя ДНК-вычисления представляют собой привлекательную и физически реализуемую модель вычислений, пригодную для решения некоторых задач, эта модель является классической, и никакого принципиального улучшения производительности по сравнению с машиной Тьюринга не дает. Еще одним вариантом вычислительной модели является аналоговый кампьннпер. Компьютер называется аналоговым, если используемое в нем физическое представление информации основано на непрерывно меняющихся величинах, а не на нулях и единицах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
