М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 41
Текст из файла (страница 41)
Второй аспект этого вопроса — указать ограничения на возможности алгоритмов решения задач. Например, можно найти нижние границы для числа операций, которые неизбежно выполнит любой алгоритм сортировки. В идеале ответы на эти два вопроса — как найти алгоритм для решения данной задачи и каковы ограничения на возможности любого такого алгоритма — полностью согласуются (т. е. мы знаем оптимальный алгоритм). На прак- 164 Глава 3.
Введение в информатику тике часто остается немалый разрыв между возможностями лучших известных алгоритмов и самыми сильными ограничениями. Цель этой главы — дать обзор средств, разработанных для анализа вычислительных задач, а также для построения и анализа алгоритмов для решения этих задач. Но почему же читатель, интересующийся яеантовыми вычислениями и кеаитоеоа теорией информации, должен тратить время на изучение классической информатики? На это есть три веские причины.
Во-первых, большое количество понятий и технических приемов классической информатики можно с большой пользой использовать в квантовых вычислениях и квантовой информатике. Многие замечательные результаты в области квантовых вычислений и квантовой информации получены в результате объединения старых идей из информатики с новыми идеями из квантовой механики.
Например, некоторые быстрые алгоритмы для квантовых компъютеров основаны на преобразовании Фурье — мощном инструменте, используемом во многих классических алгоритмах. Как только было понято, что квантовые компъютеры могут осуществлять некоторую разновидность преобразования Фурье гораздо быстрее, чем классические, это дало возможность разработать много важных квантовых алгоритмов. Во-вторых, специалисты по информатике затратили большие усилия на выяснение того, какие ресурсы необходимы для решения той или иной задачи на классическом компьютере. Эти результаты можно использовать в качестве основы для сравнения с квантовыми вычислениями и квантовой теорией информации.
Например, много внимания уделялось задаче нахождения простых множителей данного числа. Считается, что эта задача не имеет «эффектявного» решения на классическом компыатере (что здесь понимается под «эффективностью», будет разъяснено далее в этой главе). Однако же существует эффективное решение этой задачи на квантовом компьютере. Для задачи нахождения Простых множителей существует разрыв между возможностями квантового и классического компьютеров. Это интересно и само по себе и в том более широком смысле, что такой разрыв может существовать и для более широкого класса задач, чем нахождение простых множителей.
Возможно, в процессе дальнейшего изучения этой конкретной задачи удастся выделить те ее черты, благодаря которым на квантовом компьютере решить ее оказывается легче, чем на классическом, а затем воспользоваться этими знаниями для нахождения интересных квантовых алгоритмов, пригоднь|х для решения других задач. В-третьих, что более важно, необходимо научиться думашь, подобно сяециалися»у по ииформая»оке. Мышление специалистов по информатике совсем не такое, как у физиков или специалистов других естественных наук.
Тот, кто хочет глубоко понять квантовые вычисления и квантовую теорию информапди, должен время от времени мыслить как специалист по информатике; нужно научиться интуитивно понимать, какая техника и, что самое важное, какие задачи наиболее интересны специалисту по информатике. Эта глава построена следующим образом. В разд. 3.1 мы вводим две модели вычислений: машину Тьюринга и схемную модель.
Нашей базовой вычис- 3.1. Вычислительные модели 165 лительной моделью будет машина Тьюринга, но мы будем чаще использовать схемную модель, поскольку именно эта модель наиболее полезна при изучении квантовых вычислений. Познакомившись с этими двумя моделями, мы посвятим остальную часть главы обсуждению объема ресурсов, необходимого для вычислений. Раздел 3.2 начинается с обзора задач, которыми мы интересуемся, и рассмотрения некоторых связанных с ними вопросов о ресурсах.
Далее в этом разделе приводятся ключевые понятия, связанные со сложностью вычисгвний, — раздела математики, в котором рассматриваются требования к времени и памяти, необходимые для решения данной задачи, и дается классификация задач по трудности их решения. Завершается этот раздел рассмотревием энергетических ресурсов, необходимых для вычислений. Как ни странно, окгзывается, что энергия, требуемая для вычисления, может быть исчезающе малой, если только вычисление можно сделать обратимым. Мы объясняем, как сконструировать обратимые компъютеры, а также почему они важны как для классической, так и для квантовой теории вычислений. В завершающем главу равд 3.3 дается обзор теоретической информатики, причем особое внимание уделяется вопросам, играющим роль в области квантовых вычислений и квантовой информации. 3.1 Вычислительные модели ...
алгоритмы существуют независимо от какого бы то ни было язьога программирования. Дональд Кнут Что это значит, что для выполнения некоторой задачи имеется алгоритм? В детстве мы все изучаем способ, позволяющий сложить два сколь угодно больших числа. Это — пример алгоритма. Нахождение точного математического определения для понятия алгоритма и является целью этого раздела. Истоки понятия алгоритма уходят на много веков в историю; младшекурсники изучают алгоритм Евклида для нахождения наибольшего общего делителя двух натуральных чисел, и этому алгоритму две тысячи лет. Однако основные понятия современной теории алгоритмов (и тем самым информатики) были сформулированы только в 30-х г. ХХ века Алонзо Черчем, Аланом Тьюриигом и другими пионерами компьютерной эры.
Их работы появились как ответ на глубокий вопрос, поставленный великим математиком Давидом Гильбертом в начале ХХ века. Гильберт задался вопросом, существует ли алгоритм, способный (в принципе) решить все математические задачи, и ожидал, что ответ на этот вопрос (известный как ЕпггсЬеЫипбвргоЫеш) будет положительным. Удивительным образом оказалось, что на вопрос Гильберта надо ответить «петю не существует алгоритма, способного решить все математические задачи.
Чтобы доказать это, Черчу и Тьюриигу потребовалось решить глубокую проблему: как дать математическое определение алгоритма, согласующееся с его интуитивным пониманием. В процессе этой работы они заложили основы современной теории алгоритмов, а тем самым и современной информатики. 166 Глава 3. Введение в информатику В этой главе мы пользуемся двумя на первый взгляд различными подходами к теории вычислений. Первый подход был предложен Тьюрингом.
Для уточнения понятия алгоритма Тьюринг определил класс машин, известных в настоящее время машин, как машины Тьюринга. В подраэд. 3.1.1 мы описываем машины Тьюринга, а затем обсуждаем некоторые более простые варианты модели вычислений, основанной на машине Тьюринга.
Второй подход основан на схемкой модели вычислений; этот подход особенно пелагеи как подготовка к дальнейшему исследованию квантовых компьютеров. Схемная модель обсуждается в подразд. 3.1.2. Хотя при поверхностном рассмотрении эти две модели вычислений представляются различными, оказывается, что они эквивалентны. Можно спросить, зачем вводить несколько разных вычислительных моделей. Причина в том, что различные модели могут помочь по-разному понять одну и ту же задачу. Два (или более) способа рассмотрения лучше, чем один.
3.1.1 Машины Тьюринга Основные составные части машины Тьюринга изображены на рис. 3.1. Машина Тьюринга состоит из: (а) программзг (примерно как у обычного компьютера); (б) управляющего устройсгпва с конечным числам сасгпвяний, которое работаег как примитивный микропроцессор, координируя действия машины; (в) ленты, аналогичной памяти компъютера, и (г) читающей/пишущей головки, указывающей на то место ленты, где в данный момент можно что-то прочитать или записать. Опишем теперь каждую из этих частей более подробно.
Рис. 3.1. Основные составные части машины Тьюринга В тексте пробелы обознзчаютсл буквой б. Обратите внимание на знак Ы обозначающий начало ленты Управляющее устройсгпво с конечным числам соспюлний для машины Тьюринга имеет конечное число внутпренних свсгпояний вь..., в„,. Число т можно варьировать; оказывается, что для достаточно больших тп производительность машины от него по существу не зависит, так что без потери общности можно считать, что гп — это некоторая фиксированная константа. Управляющее 3.1. Вычислительные модели 167 устройство лучше всего рассматривать как разновидность микропроцессора, координирующего действия машины Тьюринга. Это устройство содержит временное хранилище денных вне ленты и является тем местом, где производятся вычисления. Наряду с состояниями дм..., в,„имеются два состояния дг и аь, называемые начальным (вгахг!пб) и заключительным (Ьа1г!пй) состояниями соответственно.
В начале вычислений машина Тьюринга находится в начальном состоянии д,. В процессе вычислений состояние меняется и в случае, если вычисления завершаются, машина Тьюринга оказывается в состоянии аь. Это означает, что машина закончила работу. Лента машины Тьюринга является одномерным объектом, простирающимся до бесконечности в одном направлении. Она представляет собой бесконечную последовательность ячеек, пронумерованных числами О, 1, 2, 3,....
Каждая ячейка содержит один символ из некоторого алфавита Г, состоящего из конечного числа различных символов. Пока что удобно предположить, что глфавит состоит из четырех символов О, 1, б (пробел) и ~> (символ начала ленты). Перед началом работы лента содержит о в левом конце и конечное число символов О и 1, а все остальные ячейки заполнены пробелами. Читающая/ пишущая гааовка указывает на ту ячейку ленты, которая в данный момент доступна машине Тьюринга.
Итак, магпина Тьюринга начинает работу, когда ее управляющее устрой-, спю находится в состоянии д„а головка указывает на самую левую ячейку— ячейку номер О. Затем вычисления проходят шаг за шагом в соответствие с щюграммой, как это будет объяснено ниже. Если текущее состояние есть аь, то вычисления завершаются, и результат вычислений — это содержимое ленты.
Программа машины Тьюринга представляет собой конечный упорядоченный список программных строк (ргойгаш !!пез) вида (д, х, д', х', з) . Первый элемент программной строки д — это одно из внутренних состояний машины. Второй элемент х принадлежит алфавиту à — множеству символов, которые могут появиться на ленте. Машина работает следующим образом. На каждом шаге машина Тьюринга последовательно просматривает список программных строк и ищет в нем строку, начинающуюся с (д, х, д', х', з), где д — текущее состояние машины, а х — символ на ленте, находящийся под головкой. Если такая программная строка не находится, внутреннее состояние машины переходит в дь и напила останавливается. Если строка находится, то она испалнлется.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
