Реферат: Квантовые компьютеры
МИНИСТЕРСТВООБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РФ
АСТРАХАНСКИЙГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ
кафедратеоретической физики
РЕФЕРАТ
натему:
«Квантовыекомпьютеры»
Выполнил:
студент154 группы ФМФ
БезнискоЕвгений.
Руководитель:
к.ф.-м.н.,доцент
ДжалмухамбетовА.У.
Астрахань– 2000 г.
Предпосылкисоздания квантовых компьютеров.
Уже сейчассуществует множество систем, в работе которых квантовые эффекты играютсущественную роль. Одним из наиболее известных примеров может служить лазер:поле его излучения порождается квантово-механическими событиями — спонтанным ииндуцированным излучением света. Другим важным примером таких систем являютсясовременные микросхемы — непрерывное ужесточение проектных норм приводит ктому, что квантовые эффекты начинают играть в их поведении существенную роль. Вдиодах Ганна возникают осцилляции электронных токов, в полупроводникахобразуются слоистые структуры: электроны или дырки в различных запертыхсостояниях могут хранить информацию, а один или несколько электронов могутбыть заперты в так называемых квантовых ямах.
Сейчас ведутсяразработки нового класса квантовых устройств — квантовых компьютеров. Идеяквантового компьютера возникла так.
Все началось в1982 году, когда Фейнман написал очень интересную статью [1], в которой рассмотрелдва вопроса. Он подошел к процессу вычисления как физик: есть чисто логическиеограничения на то, что можно вычислить (можно придумать задачу, для которойвообще нет алгоритма, можно придумать задачу, для которой любой алгоритм будетдолго работать). А есть ли ограничения физические? Вот есть закон сохраненияэнергии — вечный двигатель невозможен; а есть ли какое-нибудь физическое ограничениена функционирование компьютера, которое накладывает некие запреты нареализуемость алгоритмов? И Фейнман показал, что термодинамических ограничений,типа второго начала термодинамики, нет. Если мы будем уменьшать потериэнергии, шумы, то мы можем сделать сколь угодно длинные вычисления со скольугодно малыми затратами энергии. Это означает, что вычисления можно сделатьобратимым образом — потому что в необратимых процессах энтропиявозрастает. Собственно, Фейнмана это и заинтересовало: ведь реальное вычислениена реальном компьютере необратимо. И полученный им результат состоит в том, чтоможно так переделать любое вычисление — без особой потери эффективности, — чтобы оно стало обратимым. Те вычисления, которые делаются «просто так», конечно,необратимы, но «рост необратимости» пренебрежимо мал по сравнению, скажем, сшумами в современном компьютере. То есть необратимость — это тонкий эффект; тутвопрос не практический а принципиальный: если представить себе, что технологиядойдет до такого уровня, что этот эффект станет существенным, то можно так перестроитьвычисления, чтобы добиться обратимости.
И в этой жеработе Фейнман обратил внимание на то, что если у нас имеется устройство квантовое,то есть подчиняющееся законам квантовой механики, то его вычислительныевозможности совершенно не обязательно должны совпадать с возможностями обычногоустройства. Возникают некоторые дополнительные возможности. Но поканепонятно,позволяют они получить какой-то выигрыш или нет. Фактически, он и поставилсвоей статьей такой вопрос.
Кстати, Ю.И.Манин в конце семидесятых годов написал две популярные книжки по логике — «Вычислимое и невычислимое» и «Доказуемое и недоказуемое», и в одной из нихесть сюжет про квантовые автоматы, где он говорит о некоторых кардинальных отличияхэтих автоматов от классических [2].
В серединевосьмидесятых годов появились работы Дойча (D. Deutsch), Бернстайна иВазирани (Е.Bernstein, U. Vazirani), Яo (A. Уао). В нихбыли построены формальные модели квантового компьютера — например, квантоваямашина Тьюринга [3-6].
Следующий этап — статья Шора (Р.W. Shor) 1994 года [7], вызвавшая лавинообразныйрост числа публикаций о квантовых вычислениях. Шор построил квантовый (тоесть реализуемый на квантовом компьютере) алгоритм факторизации (разложения целыхчисел на множители — используется в том числе для вскрытия зашифрованныхсообщений). Все известные алгоритмы для обычного компьютера — экспоненциальные(время их работы растет как экспонента от числа знаков в записи факторизуемогочисла). Факторизация 129-разрядного числа потребовала 500MIPS-лет,или восемь месяцев непрерывной работы системы из 1600 рабочих станций,объединенных через Интернет. А при числе разрядов порядка 300 это время существеннопревзойдет возраст Вселенной — даже если работать одновременно на всех существующихв мире машинах. Считается (хотя это и не доказано!), что быстрого алгоритмарешения этой задачи не существует. Более того, гарантией надежности большинствасуществующих шифров является именно сложность решения задачи факторизации илиодной из родственных ей теоретико-числовых задач, например — дискретногологарифма. И вдруг выясняется, что на квантовом компьютере эта задача имеетвсего лишь кубическую сложность! Перед квантовым компьютером классическиебанковские, военные и другие шифры мгновенно теряют всякую ценность. Корочеговоря, работа Шора показала, что вся эта изысканная академическая деятельностьнепосредственно касается такой первобытной стихии, как деньги. Послеэтого и началась настоящая популярность...
Впрочем, выясняется, чтоне только классическая, но и квантовая криптография (наука о шифрованиисообщений) часто не способна противостоять квантовой криптоаналитике (науке орасшифровке). Некоторые важные криптографические протоколы, такие как «подбрасываниемонеты по телефону», рушатся при переходе к квантовым вычислениям. Точнее,гарантией их надежности является отныне не сложность тех или иных алгоритмов,а сложность задачи создания квантового компьютера.
Таким образомвозникает новая отрасль вычислений – квантовые вычисления. Квантовыевычисления (КВ) — это, как можно догадаться, вычисления на квантовомкомпьютере. Квантовых компьютеров на свете пока нет. Более того, до сих порнеясно, когда появятся практически полезные конструкции и появятся ли вообще.Тем не менее, квантовые вычисления — предмет, чрезвычайно модный сейчас вматематике и физике, как теоретической, так и экспериментальной, и занимаетсяим довольно много людей. Судя по всему, именно интерес стимулировалпервопроходцев — Ричарда Фейнмана, написавшего пионерскую работу, в которойставился вопрос о вычислительных возможностях устройств на квантовых элементах; Дэвида Дойча,формализовавшего этот вопрос в рамках современной теории вычислений; и ПитераШора, придумавшего первый нетривиальный квантовый алгоритм.
Типы квантовыхкомпьютеров.
Строго говоря,можно выделить два типа квантовых компьютеров. И те, и другие основаны наквантовых явлениях, только разного порядка.
Представителямипервого типа являются, например, компьютеры, в основе которых лежит квантованиемагнитного потока на нарушениях сверхпроводимости — Джозефсоновских переходах.На эффекте Джозефсона уже сейчас делают линейные усилители, аналого-цифровыепреобразователи, СКВИДы и корреляторы. Известен проект создания RISC-процессорана RSFQ-логике(Rapid Single Flux Quantum). Эта же элементная база используется в проектесоздания петафлопного (1015 оп./с) компьютера. Экспериментальнодостигнута тактовая частота 370 ГГц, которая в перспективе может бытьдоведена до 700 ГГц. Однако время расфазировки волновых функций в этихустройствах сопоставимо со временем переключения отдельных вентилей, ифактически на новых, квантовых принципах реализуется уже привычная намэлементная база — триггеры, регистры и другие логические элементы.
Другой типквантовых компьютеров, называемых еще квантовыми когерентными компьютерами,требует поддержания когерентности волновых функций используемых кубитов в течение всеговремени вычислений — от начала и до конца (кубитом может быть любая квантомеханическаясистема с двумя выделенными энергетическими уровнями). В результате, длянекоторых задач вычислительная мощность когерентных квантовых компьютеровпропорциональна 2N, где N — число кубитов в компьютере.Именно последний тип устройств имеется в виду, когда говорят о квантовыхкомпьютерах.
Математическиеосновы функционирования квантовых компьютеров.
Классическийкомпьютер состоит, грубо говоря, из некоторого числа битов, с которыми можновыполнять арифметические операции. Основным элементом квантового компьютера(КК) являются квантовые биты, или кубиты (от Quantum Bit,qubit).Обычный бит — это классическая система, у которой есть только два возможныхсостояния. Можно сказать, что пространство состояний бита — это множество издвух элементов, например, из нуля и единицы. Кубит же — это квантоваясистема с двумя возможными состояниями. Имеется ряд примеров таких квантовыхсистем: электрон, у которого спин может быть равен либо +1/2 либо –1/2, атомыв кристаллической решетке при некоторых условиях. Но, поскольку системаквантовая, ее пространство состояний будет несравненно богаче. Математически кубит — это двумерноекомплексное пространство.
В такой системеможно выполнятьунитарныепреобразования пространства состояний системы. С точки зрения геометрии такиепреобразования — прямой аналог вращении и симметрий обычного трехмерногопространства. Согласно принципу суперпозиции вы можете складывать состояния,вычитать их, умножать на комплексные числа. Эти состояния образуют фазовыепространства. При объединении двух систем полученное фазовое пространствобудет их тензорным произведением. Эволюция системы в фазовом пространствеописывается унитарными преобразованиями фазового пространства.
Так вот, вквантовом компьютере аналогичная ситуация. Он тоже работает с нулями иединицами. Но его функциональные элементы реализуют действия прямо в фазовомпространстве некоторой квантовой системы — при помощи унитарных преобразованийэтого пространства.
Конечно,унитарные преобразования не могут быть произвольными — они должны удовлетворятьнекоторым естественным ограничениям. Например, в случае обычной логикидостаточно иметь три операции: конъюнкция, дизъюнкция, отрицание. Все можно реализовать,используя только эти три операции. Точно так же и в квантовом случае естьнекоторый набор операторов, действующих только на три бита, с помощью которыхможно все реализовать. Там есть даже более тонкие результаты: можноограничиться классическими операторами на нескольких битах, а квантовые операторыбудут действовать только на один бит. То есть классический набор операций {конъюнкция,дизъюнкция, отрицание} можно заменить на такой: {конъюнкция,дизъюнкция, квантовое отрицание}, где квантовое отрицание — это произвольноеунитарное преобразование одного кубита.
Фазовоепространство КК есть тензорное произведение кубитов. Если в каждом кубитефиксирован базис (он будет состоять из двух векторов), то фазовое пространство- это комплексноелинейное пространство, базис которого индексирован словами из нулей и единиц.Таким способом двоичное слово на входе определяет базисный вектор.
Итак, вход — двоичное слово, определяющее один из базисных векторов. Сам же алгоритм — предписаннаяпоследовательность элементарных операторов. Применяем эту последовательность квектору на входе, в результате получаем некоторый вектор на выходе.
Так вот,согласно квантовой механике (КМ), пока система эволюционирует под действиемнаших унитарных операторов, мы не можем сказать, в каком именно классическомсостоянии она находится. То есть она находится в каком-то квантовом состоянии,но измеряем-то мы, когда общаемся с системой, все равно какие-то классическиезначения. Как это понимается в КМ? В фазовом пространстве фиксируетсянекоторый базис, и вектор состояния разлагается по этому базису. Этоматематическая формализация процедуры измерения в КМ. То есть если мы имеемдело с системой, у которой «то ли спин влево, то ли спин вправо», и если мывсе-таки посмотрим, какой спин, то мы получим одно из двух в любом случае. Авот вероятности того, что мы получим тот или другой результат, — это как разквадраты модуля коэффициентов разложения. КМ утверждает, что точно предсказатьрезультат измерения нельзя, но вероятности возможных результатов вычислитьможно.
Вероятностьвозникает в процессе измерения. А пока система живет, для нас существенно,что там есть сам этот вектор.
Другими словами,существенно, что система «находится одновременно во всех возможных состояниях».Как пишут многие авторы популярных введений в KB, возникает совершенночудовищный параллелизм вычислении: к примеру, в случае нашей системы из двухкубитов мы как бы оперируем одновременно со всеми возможными ее состояниями:00, 01, 11, 10.
Чтобыинтерпретировать ответ, надо заранее условиться, что какой-то бит — допустим,первый — это бит ответа. Пусть алгоритм проработал, у нас получился какой-товектор, не обязательно базисный. Тогда мы можем сказать, что первый бит снекоторой вероятностью равен 1. И требование к алгоритму такое: если ответ«да», то вероятность того, что первый бит равен 1, должна быть больше двухтретей. А если ответ «нет», вероятность того, что будет ноль, должна быть тожебольше двух третей.
Задачи,реализуемые на КВ.
Известно двапримера нетривиальных задач, в которых KB даютрадикальный выигрыш.
Первый из них — задача разложения целых чисел на простые множители и, как следствие, вычислениядискретного логарифма (ДЛ). Дальше речь пойдет именно о ДЛ.
Пусть у нас естьполе вычетов по модулю простого числа. В нем есть первообразные корни — такие вычеты,чьи степени порождают все ненулевые элементы. Если задан такой корень и заданастепень, то возвести в степень можно быстро (например, сначала возводим вквадрат, потом получаем четвертую степень, и т. д.) Дискретный логарифм — это обратнаязадача. Дан первообразный корень и какой-то элемент поля; найти, в какуюстепень нужно возвести этот корень, чтобы получить данный элемент. Вот этазадача уже считается сложной. Настолько сложной, что ряд современныхкриптографических систем основан на том предположении, что вычислить ДЛ заприемлемое время невозможно, если модуль — достаточно большое простое число.
Так вот, длядискретного логарифма есть эффективный квантовый алгоритм. Его придумал Шор вконце 1994 года. После его статьи и начался взрыв публикаций по КВ.Независимо от него, Алексей Китаев из ИТФ им. Ландау построил квантовыйалгоритм для этой и некоторых более общих задач [8]. Идеи у них былиразные.
Шор использовалпримерно такую идею, она существенно квантовая: рассмотрим базис в фазовомпространстве. Он состоит из классических состояний. Но в линейном пространствемного базисов. Мы можем найти некий оператор, который эффективно строит другойбазис; мы можем к нему перейти, сделать там какие-то вычисления, вернутьсяобратно и получить нечто совершенно отличное от того, что мы имели бы в классическомбазисе. Одна из возможностей использовать квантовость состоит в том, что мыстроим какой-то странный базис, в нем что-то делаем, возвращаемся обратно иинтерпретируем результат. Шор именно эту идею и реализовал. Причемпреобразование оказалось такое, которое и в физике, и в математике имеетпринципиальное значение — дискретное преобразование Фурье.
Его можнопредставить в виде тензорного произведения операторов, которые действуют накаждый из кубитов такой матрицей:
/>
Китаев придумалпримерно следующее. Есть некоторая ячейка — основной регистр, где мызаписываем наши данные нулями и единицами. И еще есть один управляющий кубит.Мы работаем так: у нас реализована процедура умножения на первообразный корень,на квадрат первообразного корня, и т. д. Управляющий кубит переводим в некотороесмешанное состояние, дальше строим такой оператор, который, в зависимости оттого,ноль или единица в этом управляющем кубите, либо применяет умножение к нашемуосновному регистру, либо не применяет. А потом кубит опять возвращаем всмешанное состояние. Оказывается, что это эффективный способ проделать некотороеизмерение. То есть Китаев заметил, что одна из вещей, которые мы можемэффективно делать на квантовом компьютере, — это имитировать процесс квантовогоизмерения. В данной задаче из результатов этих измерений эффективноизвлекается ответ.
Сам процессвычислений, происходит так: мы все время умножаем одну и ту же ячейку на некиеконстанты, результаты измерений записываем, а потом производим своего родаобработку результатов эксперимента — уже чисто классическими вычислениями.Вся квантовая часть заключается в том, что где-то рядом с нашим регистромнаходится в некоем смешанном состоянии коррелированный с ним кубит, и мы егопериодически наблюдаем.
Для вычисленияДЛ числа, записанного N битами, нужнопотратить N3<sup/> единиц времени. Вполне реализуемо — на КК, естественно. Но здесь надо заметить, что никто пока не доказал, что несуществует столь же быстрого алгоритма для вычисления ДЛ на обычной машине.
Вторая задачапредложена Гровером (L. Grover) [9]. Рассмотрим базу данных, содержащую 2N записей. Мыхотим найти ровно одну запись. Имеется некая процедура определения того,нужную запись мы взяли или нет. Записи не упорядочены. С какой скоростью мыможем решить эту задачу на обычном компьютере? В худшем случае нам придетсяперебрать все 2Nзаписей — этоочевидно. Оказывается, что на КК достаточно числа запросов порядка корня изчисла записей – 2N/2.
Интереснаязадача — создание оптимальных микросхем. Пусть есть функция, которую нужно реализоватьмикросхемой, и эта функция задана программой, использующей полиномиально ограниченнуюпамять. Построение нужной микросхемы с минимальным числом функциональных элементов- задача PSPACE. Поэтомупоявление устройств, эффективно решающих PSPACE-задачи, позволило быединообразно проектировать оптимальные по своим показателям вычислительныеустройства обычного типа. Кроме того, в PSPACE попадаетбольшинство задач «искусственного интеллекта»: машинное обучение, распознаваниеобразов и т.д.
Так вот, точноустановлено, что KB находятся где-то между обычными вероятностнымивычислениями и PSPACE. Если все же окажется, что KB можноэффективно реализовать на классических вероятностных машинах, не будет смыслав физической реализации квантовых машин. Если же выяснится, что при помощи KB можноэффективно решать те или иные PSPACE-задачи, то физическая реализация ККоткроет принципиально новые возможности.
Есть еще однаобласть применения КК, где заведомо возможен радикальный выигрыш у существующихтехнологий. Это моделирование самих квантовых систем.
Давайтепосмотрим на такой вопрос: как можно эволюцию квантовой системы изучать наобычном компьютере? Это постоянно делается, так как это задача важна для химии,молекулярной биологии, физики и т.п. Но, за счет экспоненциального ростаразмерности при тензорном произведении, для моделирования десяти спинов вамнужно оперировать с тысячемерным пространством, сто спинов — это уже конец. Аесли вспомнить, что в молекуле белка десятки тысяч атомов, то… Там, правда,не всюду существенно именно квантовое моделирование, но в целом ясно, что естьочень серьезные препятствия для моделирования квантовых систем на классическихкомпьютерах. Так что если создать вычислительное устройство, которое ведет себяквантовым образом, то по крайней мере один важный класс задач на нем естьсмысл решать — можно моделировать реальные квантовые системы, возникающие вфизике, химии, биологии.
Проблемысоздания КК.
Когда началсябум вокруг квантовых вычислений, физики высказывались об этом более чемскептически. Модель квантовых вычислений не противоречит законам природы, ноэто еще не значит, что ее можно реализовать. К примеру, можно вспомнить созданиеатомного оружия и управляемый термояд.
А если говоритьо КК, надо отметить одну очень серьезную проблему. Дело в том, что любаяфизическая реализация будет приближенной. Во-первых, мы не сможем сделатьприбор, который будет давать нам произвольный вектор фазового пространства.Во-вторых, работа любого устройства подвержена всяческим случайным ошибкам. Ауж в квантовой системе — пролетит какой-нибудь фотон, провзаимодействует содним из спинов, и все поменяется. Поэтому сразу возник вопрос, можно ли, хотябы в принципе, организовать вычисления на ненадежных квантовых элементах,чтобы результат получался со сколь угодно большой достоверностью. Такая задачадля обычных компьютеров решается просто — например, за счет введениядополнительных битов.
В случае КК этапроблема гораздо глубже. То место, где возникает новое качество KB по сравнению собычными вычислениями, — это как раз сцепленные состояния — линейныекомбинации базисных векторов фазового пространства. У вас есть биты, но они несами по себе живут в каких-то состояниях — это был бы просто вероятностныйкомпьютер (компьютер, дающий тот или иной ответ с определенной вероятностью), — а они находятся в некоем смешанном состоянии, причем согласованно-смешанном.Из-за этого в КК нельзя, например, просто взять и скопировать один бит вдругой! Обычная интуиция из теории алгоритмов здесь неприменима.
Так что проблеманадежности довольно сложна, даже на уровне чистой теории. Те люди, которыеактивно занимаются KB, активно ее решали и добились успеха: доказано, что,как и в классике, можно делать вычисления на элементах с заданной надежностьюсколь угодно точно. Это реализовано с помощью некоего аналога кодов, исправляющихошибки.
Что касаетсятехнической стороны появляются сообщения, что создаются реальные квантовыесистемы с небольшим числом битов — с двумя, скажем. Экспериментальные, вжелезе, так сказать.
Так чтоэксперименты есть, но пока очень далекие от реальности. Два бита — это и дляклассического и для квантового компьютера слишком мало! Чтобы моделироватьмолекулу белка, нужно порядка ста тысяч кубитов. Для ДЛ, чтобы вскрыватьшифры, достаточно примерно тысячи кубитов.
Задача эта возникласлишком недавно, и не исключено, что она потребует каких-то фундаментальныхисследований в самой физике. Поэтому в обозримом будущем ожидать появленияквантовых компьютеров не приходится.
Но можно ожидатьраспространения через не очень долгое время квантовых криптографическихсистем. Квантовая криптография позволяет обмениваться сообщениями так, чтовраг, если попытается подслушать, сможет разве что разрушить ваше сообщение.То есть оно не дойдет до адресата, но перехватить его в принципе будет нельзя.Подобные системы, которые уже реализованы, используют световод. УниверсальныйКК здесь не нужен. Нужно специализированное квантовое устройство, способноевыполнять только небольшой набор операций, — своего рода квантовый кодек.
Физической системе,реализующей квантовый компьютер, можно предъявить пять требований:
1. Система должнасостоять из точно известного числа частиц.
2. Должна бытьвозможность привести систему в точно известное начальное состояние.
3. Степень изоляцииот внешней среды должна быть очень высока.
4. Надо уметьменять состояние системы согласно заданной последовательности унитарныхпреобразований ее фазового пространства.
5. Необходимо иметьвозможность выполнять «сильные измерения» состояния системы (то есть такие,которые переводят ее в одно из чистых состояний).
Из этих пятизадач наиболее трудными считаются третья и четвертая. От того, насколько точноони решаются, зависит точность выполнения операций. Пятая задача тоже весьманеприятна, так как измерить состояние отдельной частицы нелегко.
Физическиеосновы организации КК.
Итак, что же этоза тайное оружие такое — КК? Остроумная идея заключается в использовании дляхранения, передачи и обработки информации существенно квантовых свойстввещества. В основном такие свойства проявляют объекты микромира: элементарныечастицы, атомы, молекулы и небольшие сгустки молекул, так называемые кластеры.(Хотя, конечно, и в жизни макромира квантовая механика играет важную роль. Вчастности, только с ее помощью можно объяснить такое явление, какферромагнетизм.) Одним из квантовых свойств вещества является то, чтонекоторые величины при измерении (наблюдении) могут принимать значения лишьиз заранее определенного дискретного набора. Такой величиной, например,является проекция собственного момента импульса, или, иначе говоря, спинаэлементарной частицы, на любую заданную ось. Например, у электрона возможнотолько два значения проекции: +1/2 или –1/2. Таким образом, количествоинформации, необходимое для сообщения о проекции, равно одному биту. Записав вклассическую однобитную ячейку памяти определенное значение, мы именно его оттудаи прочтем, если не произойдет какой-нибудь ошибки.
Классическойячейкой может послужить и спин электрона. Однако квантовая механика позволяетзаписать в проекции спина больше информации, чем в классике.
Для описанияповедения квантовых систем было введено понятие волновой функции. Существуютволновые функции, называемые собственными для какой-то конкретной измеряемойвеличины. В состоянии, описываемом собственной функцией, значение этой величиныможет быть точно предсказано до ее измерения. Именно с такими состояниямиработает обычная память. Квантовая же система может находиться и в состоянии сволновой функцией, равной линейной комбинации собственных функции,соответствующих каждому из возможных значений (назовем здесь такие состояниясложными). В сложном состоянии результат измерения величины не может бытьпредсказан заранее. Заранее известно только, с какой вероятностью мы получимто или иное значение. В отличие от обычного компьютера, в квантовом дляпредставления данных используются такие ячейки памяти, которые могут находитьсяв сложном состоянии. В нашем примере мы определили бы, что спин электрона сопределенной вероятностью смотрит вверх и вниз, то есть можно сказать, что вкубит записаны сразу и 0, и 1. Количество информации, содержащееся в такойячейке, и саму ячейку называют квантовым битом, или, сокращенно, кубитом.Согласитесь, ячейки в сложных состояниях весьма необычны для классическойтеории информации. Каждому возможному значению величины, представленной кубитом,соответствует вероятность, с которой это значение может быть получено причтении. Эта вероятность равна квадрату модуля коэффициента, с которым собственнаяфункция этого значения входит в линейную комбинацию. Именно вероятность иявляется информацией, записанной в кубит.
Квантовуюмеханику не случайно называют иногда волновой механикой. Дело в том, чтоквантово-механические волновые функции ведут себя подобно световой иликакой-либо другой волне. И для волновых функций, благодаря их способностиинтерферировать, также может быть введено понятие когерентности. Именно этосвойство используется в когерентном квантовом компьютере. Набор кубитовпредставляется когерентными волновыми функциями. Оказывается, что существуетвполне определенный класс воздействий на квантовую систему, называемыйунитарными преобразованиями, при которых не теряется записанная в кубитинформация и не нарушается когерентность волновых функций кубитов. Унитарныепреобразования обратимы — по результату можно восстановить исходные данные.После прохождения через квантовый процессор, использующий унитарные преобразования,волновые функции кубитов заставляют интерферировать друг с другом, наблюдаяполучающуюся картину и судя по ней о результате вычисления.
Из-за того, чтодля представления информации используются кубиты, в которых записано сразу обазначения — и, и 1, в процессе вычислений происходит параллельнаяобработка сразу всех возможных вариантов комбинаций битов в процессорномслове. Таким образом, в КК реализуется естественный параллелизм, недоступныйклассическим компьютерам. За счет возможности параллельной работы с большимчислом вариантов, в идеале равным 2N (где N — число кубитов), квантовому компьютеру необходимо гораздо меньше времени длярешения определенного класса задач. К ним относятся, например, задачаразложения числа на простые множители или поиск в большой базе данных. Для когерентногокомпьютера уже предложены алгоритмы, использующие его уникальные свойства.Кроме того, предполагается использовать КК для моделирования квантовых систем,что трудно или вообще невозможно сделать на обычных компьютерах из-за нехваткимощности или по принципиальным соображениям.
Все существующиена сегодняшний день обычные компьютеры, даже с параллельной обработкой информациина многих процессорах, могут быть смоделированы так называемым клеточнымавтоматом Тьюринга. Это существенно детерминированная и дискретная машина. Свозникновением и обсуждением идей квантовых вычислений стала активноразвиваться квантовая теория информации и, в частности, теория квантовых клеточныхавтоматов — ККА. Квантовый клеточный автомат является обобщением автоматаТьюринга для КК. Сформулирована гипотеза, гласящая, что каждая конечнымобразом реализуемая физическая система может быть достаточно хорошосмоделирована универсальной моделью квантовой вычислительной машины, использующейограниченное количество ресурсов. Для одного из предложенных типов ККАтеоретически уже доказано, что он подходит для такого моделирования и непротиворечит квантовой теории.
Пытаясьосуществить свой замысел, ученые упираются в проблему сохранения когерентностиволновых функций кубитов, так как потеря когерентности хотя бы одним изкубитов разрушила бы интерференционную картину. В настоящее время основные усилияэкспериментальных рабочих групп направлены на увеличение отношения временисохранения когерентности ко времени, затрачиваемому на одну операцию (этоотношение определяет число операций, которые можно успеть провести надкубитами). Главной причиной потери когерентности является связь состояний,используемых для кубитов, со степенями свободы, не участвующими в вычислениях.Например, при передаче энергии электрона в возбужденном атоме в поступательноедвижение всего атома. Мешает и взаимодействие с окружающей средой, например,с соседними атомами материала компьютера или магнитным полем Земли, но этоне такая важная проблема. Вообще, любое воздействие на когерентную квантовуюсистему, которое принципиально позволяет получить информацию о каких-либокубитах системы, разрушает их когерентность. Потеря когерентности можетпроизойти и без обмена энергией с окружающей средой.
Воздействием,нарушающим когерентность, в частности, является и проверка когерентности. Прикоррекции ошибок возникает своего рода замкнутый круг: для того чтобыобнаружить потерю когерентности, нужно получить информацию о кубитах, а это,в свою очередь, также нарушает когерентность. В качестве выхода предложеномного специальных методов коррекции, представляющих также и большойтеоретический интерес. Все они построены на избыточном кодировании.
Если в областипередачи информации уже созданы реально работающие системы и до коммерческихпродуктов осталось лишь несколько шагов, то коммерческая реализация квантовогокогерентного процессора — дело будущего. К настоящему времени КК научилсявычислять сумму 1+1! Это большое достижение, если учесть, что в видерезультата он выдает именно 2, а не 3 и не. Кроме того,не следует забывать, что и первые обычные компьютеры были не особенно мощны.
Сейчас ведетсяработа над двумя различными архитектурами процессоров: типа клеточного автоматаи в виде сети логических элементов. Пока не известно о каких-либопринципиальных преимуществах одной архитектуры перед другой. Как функциональнаяоснова для логических элементов квантового процессора более или менее успешноиспользуется целый ряд физических явлений. Среди них — взаимодействиеодиночных поляризованных фотонов или лазерного излучения с веществом илиотдельными атомами, квантовые точки, ядерный магнитный резонанс и — наиболеемногообещающий — объемный спиновый резонанс. Процессор,построенный на последнем принципе, в шутку называют «компьютером в чашке кофе»- из-за того, что в нем работают молекулы жидкости при комнатной температуре иатмосферном давлении. Кроме этих эффектов есть довольно хорошо развитаятехнология логических элементов и ячеек памяти на джозефсоновских переходах,которую можно при соответствующих условиях приспособить под когерентныйпроцессор.
Теорию,описывающую явления, лежащие в основе первого типа логических ячеек, называютквантовой электродинамикой в полости или резонаторе. Кубиты хранятся в основныхи возбужденных состояниях атомов, расположенных некоторым образом на равныхрасстояниях в оптическом резонаторе. Для каждого атома используется отдельныйлазер, приводящий его в определенное состояние с помощью короткого импульса.Взаимовлияние атомных состояний происходит посредством обмена фотонов врезонаторе. Основными причинами разрушения когерентности здесь служат спонтанноеизлучение и выход фотонов за пределы резонатора.
В элементах наоснове ионов в линейных ловушках кубиты хранятся в виде внутренних состоянийпойманных ионов. Для управления логикой и для манипулирования отдельнымикубитами также используются лазеры. Унитарные преобразования осуществляютсявозбуждением коллективных квантованных движений ионов. Источниками некогерентностиявляется спонтанный распад состояний ионов в другие внутренние состояния ирелаксация в колебательные степени свободы.
Сильноотличается от двух предыдущих «компьютер в чашке кофе». Благодаря достоинствамданного метода этот компьютер является наиболее реальным претендентом на то,чтобы достигнуть разрядности 10 бит в ближайшее время. В компьютере на коллективномспиновом резонансе работают молекулы обычных жидкостей (без всяких квантовыхвывертов типа сверхтекучести). В качестве кубитов используется ориентация ядерныхспинов. Работа логических ячеек и запись кубитов осуществляетсярадиочастотными электромагнитными импульсами со специально подобраннымичастотой и формой. В принципе, прибор похож на обычные приборы ядерного магнитногорезонанса (ЯМР) и использует аналогичную аппаратуру. Жизнеспособность этогоподхода обеспечивается, с одной стороны, очень слабой связью ядерных спинов сокружением и, потому, большим временем сохранения когерентности (до тысяч секунд).Эта связь ослаблена из-за экранирования ядерных спинов спинами электронов изоболочек атомов. С другой стороны, можно получить сильный выходной сигнал, таккак для вычислений параллельно используется большое количество молекул. «Не такуж сложно измерить спин четвертого ядра у какого-то типа молекул, если у васимеется около числа Авогадро (~1023) таких молекул», — говорит ДиВинченцо(Di Vincenzo),один из исследователей. Для определения результата непрерывно контролируютизлучение всего ансамбля. Такое измерение не приводит к потере когерентности вкомпьютере, как было бы в случае использования только одной молекулы.
Ядерные спины вмолекулах жидкости при комнатной температуре хаотически разупорядочены, ихнаправления равномерно распределены от 0 до 4p. Проблема записи и считывания кажется непреодолимойиз-за этого хаоса. При воздействии магнитного поля спины начинаюториентироваться по полю. После снятия поля через небольшое время система сноваприходит к термодинамическому равновесию, и в среднем лишь около миллионнойдоли всех спинов остается в состоянии с ориентацией по направлению поля. Однакоблагодаря тому, что среднее значение сигнала от хаотически направленныхспинов равно нулю, на этом фоне можно выделить довольно слабый сигнал от«правильных» спинов. Вот в этих-то молекулах с правильными ядерными спинами иразмещают кубиты. Для коррекции ошибок при записи N кубитов используют 2Nили больше спинов. Например, для N=1выбираются такие жидкости, где какие-то два спина ядер в одной молекуле послеопределенного воздействия полем могут быть ориентированны только одинаково.Тогда по направлению второго спина при снятии результата обработки можноотсеять нужные молекулы, никак не влияя на первый спин.
Как уже былосказано, обработка битов осуществляется радиоимпульсами. Основным логическимэлементом является управляемый инвертор. Из-за спин-спинового взаимодействиярезонансная частота, при которой происходит опрокидывание одного спина, зависитот направления другого.
Что касается квантовойпередачи данных, к настоящему времени экспериментально реализованы системыобмена секретной информацией по незащищенному от несанкционированного доступаканалу. Они основаны на фундаментальном постулате квантовой механики о невозможностиизмерения состояния без оказания влияния на него. Подслушивающий всегдаизменяет состояние кубитов, которые он подслушал, и это может бытьзафиксировано связывающимися сторонами. Данная система защиты информации абсолютнонадежна, так как способов обойти законы квантовой механики пока еще никто невыдумал.
Вместозаключения…
Пока квантовымкомпьютерам по плечу только наиболее простые задачи — например, они уже умеютскладывать 1 и 1, получая в результате 2. Было такжезапланировано взятие другого важного рубежа — факторизации числа 15, егопредстоит разложить на простые множители — 3 и 5. А там, глядишь, дойдет делои до более серьезных задач.
Опытные образцысейчас содержат менее десяти квантовых битов. По мнению Нейла Гершенфельда(Nell Gershenfeld),участвовавшего в создании одной из первых действующих моделей квантовогокомпьютера, необходимо объединить не менее 50-100 кубитов, чтобы решатьполезные с практической точки зрения задачи. Интересно, что добавлениекаждого следующего кубита в квантовый компьютер на эффекте объемного спиновогорезонанса требует увеличения чувствительности аппаратуры в два раза. Десятьдополнительных кубитов, таким образом, потребуют увеличения чувствительности в1000 раз, или на 60 дБ. Двадцать — в миллион раз, или на 120 дБ...
He исключено, чтов информационном обществе появление квантового компьютера сыграет ту же роль,что в свое время, в индустриальном, — изобретение атомной бомбы. Действительно,если последняя является средством «уничтожения материи», то первый может статьсредством «уничтожения информации» — ведь очень часто то, что известно всем,не нужно никому.
Литература,содержащая основную информацию о КК.
1. FeynmanR. Int. J. Theor. Phys. 21, 1982.
2. Манин Ю.И.Вычислимое и невычислимое. — М.: Советское радио, 1980.
3. FeynmanR. Quantum mechanical computers. // Optics News, February 1985, 11, p.11.
4. DeutschD. Quantum theory, the Church-Turing principle and the universal quantum computer. — Proc.R. Soc. London A 400, 97, 1985.
5. DeutschD. Quantum computational networks. — Proc. R. Soc.London A 425, 73, 1989.
6. Yao А. С.-С.Quantum circuit complexity. //Proceedings of the 34th Annual Symposiumon the Foundations of Computer Science, IEEE Computer Society Press, LosAlamitos, CA, 1993, p. 352.
7. ShorP.W. Algorithms for Quantum Computation: Discrete log and Factoring. // Proceedingsof the 35th Annual Symposium on the Foundations of Computer Science, edited byS. Goldwasser, IEEE Computer Society Press, Los Alamitos, CA, 1994, p.124.
8. Китаев A.Ю. Квантовыевычисления: алгоритмы и исправление ошибок. //Успехи математических наук.
9. GroverL. Afast quantum mechanical algorithm for database search. //Proceedings of the28th Annual ACM Symposium on Theory of Computing, 1996, pp. 212-219.
10. KitaevA.Yu. Quantum measurements and the Abelian stabilizer problem. — LANL e-printquant-ph/9511026, xxx.lanl.gov.
11. ShorP.W. Fault-Tolerant Quantum Computation. — LANL e-print quant-ph/9005011,xxx.lanl.gov.
12. Bennett С.Н.,Bernstein E., Brassard G., Vazirany U. Strengths and Weaknesses of QuantumComputing. — LANL e-print quant-ph/9701001, xxx.lanl.gov, to appear inSIAM J. On Computing.