Реферат: Квантовые компьютеры

МИНИСТЕРСТВООБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РФ

АСТРАХАНСКИЙГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ

кафедратеоретической физики

РЕФЕРАТ

натему:

«Квантовыекомпьютеры»

Выполнил:

студент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.

еще рефераты
Еще работы по кибернетике