М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 5
Текст из файла (страница 5)
Широкое признание этого тезиса положило начало развитию обширной теории информатики. Вскоре после появления работы Тьюринга были построены первые компьютеры на электронных компонентах. Джон фон Нейман разработал простую теоретическую модель, объясняющую, как на практике собрать компьютер, обладающий всеми свойствами универсальной машины Тьюринга. Тем не ме- 1.1. Глобальные перспективы 23 нее, настоящая разработка аппаратного обеспечения началась только в 1947 г., когда Джон Бардин, Уолтер Враттейн и Уилл Шокли создали транзистор.
С этого момента мощь компьютерного «железа» стала расти поразительными темпами. В 1966 г. Гордон Мур даже сформулировал закон этого роста, известный как закон гн ура, согласно которому производительность компьютеров, обеспечиваемая при одной и той же цене, будет удваиваться примерно каждые два года. Как это ни удивительно, закон Мура оставался приблизительно справедливым на протяжении десятилетий. Тем не менее, большинство наблюдателей ожидают, что этот сказочный рост прекратится где-то в районе первых двух десятилетий двадцать первого века. Традиционные подходы к разработке компьютерной технологии начинают упираться в фундаментальные трудности, связанные с размерами.
По мере того, кзк электронные устройства становятся все меньше и меньше, в их функционирование постепенно вмешиваются квантовые эффекты. Одним из возможных решений проблемы, связанной с прекращением действия закона Мура, является переход к другой вычислительной парадигме. Одна из таких парадигм предоставляется квантовой теорией вычислений, основанной на идее использования для выполнения вычислений квантовой механики, а не классической физики.
Оказывается, что несмотря на возможность применения классического компьютера для моделирования квантового компьютера, зффектпивное осуществление такого моделирования невозможно. Таким образом, квантовые компьютеры существенно превосходят по скорости классические компьютеры. Это преимущество в скорости настолько значительно, что по мнению многих исследователей никакой мыслимый прогресс в классических вычислениях не поможет преодолеть разрыв в производительности между классическим н квантовым компьютерами. Что имеется в виду под «эффективным» или «неэффективным» моделированием рвантового компьютера? Многие ключевые понятия, необходимые для ответа на этот вопрос, фактически появились еще до того, как возникла идея квантового компьютера. В частности, понятия зффектпивного и незффектпивного алгоритма обрели математическую точность в теории сложностпи вычислений.
Грубо говоря, эффективным является алгоритм, время выполнения которого полиномизльно зависит от объема решаемой задачи. Для выполнение неэффективного алгоритма, напротив, требуется сверхполиномиальное (обычно экспоненциальное) время. В конце 60-х и начале 70-х гг. было замечено„ что машина Тьюринга обладает как минимум такой же эффективностью, как и любая другая модель вычислений, в том смысле, что задача, которая может быть эффективно решена в рамках некоторой модели вычислений, может быть эффективно решена и на машине Тьюринга путем использования машины Тьюринга для моделирования другой модели вычислений. Это наблюдение было сформулировано в виде усиленной версии тезиса Черча-Тьюринга: Любой аагоритпмический процесс может бнтпь зффектпивно смоделирован на машине Тьюринга. 24 Глава 1.
Введение и общий обзор Усиление этой версии тезиса Черча-Тьюринга заключено в слове «эффективною Если сильный тезис Черча-Тьюринга верен, то из него следует, что независимо от типа машины, используемой для выполнения алгоритмов, эта машина может быть эффективно смоделирована при помощи стандартной машины Тьюринга. Это важное усиление, поскольку оно подразумевает, что для анализа возможности эффективного выполнения данной вычислительной задачи мы можем ограничиться анализом машины Тьюринга.
Некоторые аргументы против сильного тезиса Черча-Тьюринга нашлись в области аналоговых вв~числений. Уже после Тьюринга различные группы исследователей обнаружили, что некоторые типы аналоговых компьютеров могут эффективно решать задачи, не имеющие, по всей видимости, эффективного решения на машине Тьюринга.
На первый взгляд такие аналоговые компьютеры нарушают сильную форму тезиса Черча-Тьюринга. К сожалению, если сделать реалистичные предположения о наличии шума в аналоговых компьютерах, то они окажутся неэффективными во всех известных реализациях н не смогут решать задачи, не имеющие эффективного рергения на машине Тьюринга. Этот урок, состоящий в том, что при оценке эффективности модели вычислений необходимо учитывать влияние реального шума, стал одним из первых крупных вггзовов, брошенных квантовым вычислениям и квантовой информации. Ответом на него стала разработка теории кодов, исаравляюгаих квантовые ошибки, и устойчиво«к к ошибкам квантовых вычислений. Таким образом, в отличие от аналоговых вычислений квантовые вычисления в принципе допускают наличие конечного уровня шума, сохраняя свои вычислительные достоинства.
Первое серьезное возражение против сильного тезиса Черча-Тьюринга появилось в середине 70-х гг., когда Роберт Соловей и Волкер Штрассен показали, что проверить, является ли целое число простым или составным, можно с помощью вгроятносганого алгоритма.
В тесте Соловея-Штрассена случайность использовалась как сугцественная часть алгоритма. Алгоритм не давал достоверного ответа нв вопрос, является ли данное целое число простым или составным, определяя это лишь с некоторой вероягпностъю. Повторяя тест Соловея-Штрассена несколько раз, можно определить это почти наверняка. Нужно особо отметить., что во время появления теста Соловая-Штрассена не было известно какого-либо эффективного детерминированного алгоритма для проверки целых чисел на простоту.1 Получалось, что компьютеры, имеющие доступ к генератору случайных чисел, могли эффективно выполнять вычислительные задачи, для которых не было эффективного решения на традиционной детерминированной машине Тьюринга. Это открытие послужило толчком к поиску других вероятносгных алгоритмов, который полностью оправдал себя, приведя к созданию успешно развивающейся области исследований.
Вероятностные алгоритмы поставили под сомнение тезис Черчэ-Тьюринга, показав, что существуют эффективно решаемые задачи, которые, тем не менее, не могут быть эффективно решены на детерминированной машине Тьюринга. г Такой авгорятн появился в июле 2002 г. — Прим. ред. 1.1. Глобальные перспективы 25 Впрочем, возникшее затруднение легко устраняется простой модификацией те- зиса: Любой алгоритмический процесс мозюет быть эффективно смоделирован на вероятностной машине Тьюринга. Эта модификация сильного тезиса Черча-Тьюринга должна оставлять чувство неудовлетворенности. Не может ли оказаться так, что через некоторое время еще какая-нибудь модель вычислений позволит эффективно решать задачи, не имеющие эффективного решения в рамках модели вычислений Тьюринга? Можно ли найти модель вычислений, которая бы эффективно моделировала любую другую модель вычислений? Заинтересовавшись этим вопросом, Дэвид Дойч в 1988 г.
решил выяснить, можно ли использовать законы физики для вывода еще более сильной версии тезиса Черча-Тьюринга. Вместо принятия специальных гипотез Дойч стал искать физическую теорию для обоснования тезиса Черча-Тьюринга, которое было бы столь же надежным, как и статус самой этой теории. В частности, Дойч попытался описать вь|числительное устройство, которое было бы способно эффективно моделировать произвольную физическую систему. Поскольку законы физики в конечном счете являются квантовомеханическими, Дойч естественным образом пришел к рассмотрению вычислительных устройств, основанных на принципах квантовой механики. От этих устройств — квантовых аналогов машин, описанных Тьюрингом полвека назад — ведет свое начало концепция современного квантового компьютера, используемая в этой книге.
На момент написания книги еще не было ясно, достаточно ли универсального квантового компьютера Дойча для эффективного моделирования произвольной физической системы. Доказательство или опровержение этой гипотезы представляет собой одну из больших проблем в области квантовых вычислений и квантовой информации. Возможно, например, что некоторый эффект из квантовой теории поля или даже более эзотерический эффект, основанный на теории струн, квантовой гравитации или на какой-либо другой физической теории, может вывести нас за рамки универсального квантового компьютера Дойча, предоставив еще более мощную модель вычислений. На данном этапе мы этого просто не знаем. Модель квантового компьютера Дойча позволила оспорить сильную форму тезиса Черча-Тьюринга. Дойч задался вопросом, может ли квантовый компьютер эффективно решать вычислительные задачи, не имеющие эффективного решения на классическом компьютере, даже если это вероятностная машина Тьюринга.
Он построил простой пример, показывающий, что квантовые компьютеры действительно могут превосходить по вычислительной эффективности классические компьютеры. Этот выдающийся первый шаг, сделанный Дойчем, в последующие десять лет был развит многими людьми. Кульминация этого развития пришлась на 1994 г., когда Питер Шор продемонстрировал, что две исключительно важные задачи — поиск простых сомножителей целого числа и так называемая задача вычисления дискретного логарифма — могут быть эффективно решены на 26 Глава 1.
Введение и общий обзор квантовом компьютере. Это вызвало большой интерес, поскольку две указанные задачи считались (и по-прежнему считаются) эффективно неразрешимыми на классическом компьютере. Результаты Шоре убедительно показывали, что квантовые компьютеры превосходят по производительности машины Тьюринга, включая их вероятностный вариант.
Следующее доказательство эффективности квантовых компьютеров появилось в 1995 г., когда Лов Гровер показал, что выполнение другой важной задачи — проведения поиска в некотором неструктурированном поисковом пространстве — также может быть ускорено на квантовом компьютере.
Правда, алгоритм Гровера не давал такого эффектного ускорения, как алгоритмы Шора, но ввиду широкого применения методологий, основанных на поиске, он вызвал значительный интерес. Примерно в то же время, когда были открыты алгоритмы Шора и Гровера, многие разрабатывали идею Ричарда Фейнмана, высказанную им в 1982 г. Фейнман указал, что моделирование квантовомеханических систем на классических компьютерах сопряжено с существенными трудностями, и предположил, что построение компьютеров на основе принципов квантовой механики позволило бы этих трудностей взбежать.
В 90-х гг. несколько групп исследователей начали развивать эту идею, показав несомненную возможность использования квантовых компьютеров для эффективного моделирования систем, не имеющих какой-либо известной эффективной модели на классическом компьютере.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
