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

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

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

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

РЕФЕРАТ

на тему:

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

Выполнил:

студент 154 группы ФМФ

Безниско Евгений.

Руководитель:

к.ф.-м.н., доцент

Джалмухамбетов А.У.

Астрахань тАУ 2000 г.

Предпосылки создания квантовых компьютеров.

Уже сейчас существует множество систем, в работе которых квантоВнвые эффекты играют существенВнную роль. Одним из наиболее изВнвестных примеров может служить лазер: поле его излучения пороВнждается квантово-механическими событиями - спонтанным и инВндуцированным излучением света. Другим важным примером таких систем являются современные микросхемы - непрерывное ужесточение проектных норм приводит к тому, что квантовые эффекты начинают играть в их поведении существенную роль. В диодах Ганна возникают осцилВнляции электронных токов, в полуВнпроводниках образуются слоиВнстые структуры: электроны или дырки в различных запертых состояниях могут хранить информаВнцию, а один или несколько элекВнтронов могут быть заперты в так называемых квантовых ямах.

Сейчас ведутся разработки нового класса квантовых устройств - квантоВнвых компьютеров. Идея квантоВнвого компьютера возникла так.

Все началось в 1982 году, когда Фейнман написал очень интересВнную статью [1], в которой расВнсмотрел два вопроса. Он подошел к процессу вычисления как фиВнзик: есть чисто логические ограВнничения на то, что можно вычисВнлить (можно придумать задачу, для которой вообще нет алгоритВнма, можно придумать задачу, для которой любой алгоритм будет долго работать). А есть ли ограниВнчения физические? Вот есть закон сохранения энергии - вечный двигатель невозможен; а есть ли какое-нибудь физическое ограВнничение на функционирование компьютера, которое накладываВнет некие запреты на реализуемость алгоритмов? И Фейнман показал, что термодинамических ограниВнчений, типа второго начала терВнмодинамики, нет. Если мы будем уменьшать потери энергии, шумы, то мы можем сделать сколь угодВнно длинные вычисления со сколь угодно малыми затратами энерВнгии. Это означает, что вычисления можно сделать обратимым образом - потому что в необратимых проВнцессах энтропия возрастает. СобВнственно, Фейнмана это и заинтеВнресовало: ведь реальное вычисВнление на реальном компьютере необратимо. И полученный им результат состоит в том, что можВнно так переделать любое вычисВнление - без особой потери эфВнфективности, - чтобы оно стало обратимым. Те вычисления, котоВнрые делаются Влпросто такВ», коВннечно, необратимы, но Влрост неоВнбратимостиВ» пренебрежимо мал по сравнению, скажем, с шумами в современном компьютере. То есть необратимость - это тонкий эффект; тут вопрос не практичесВнкий а принципиальный: если представить себе, что технология дойдет до такого уровня, что этот эффект станет существенным, то можно так перестроить вычислеВнния, чтобы добиться обратимости.

И в этой же работе Фейнман обВнратил внимание на то, что если у нас имеется устройство квантовое, то есть подчиняющееся законам кванВнтовой механики, то его вычислиВнтельные возможности совершенно не обязательно должны совпадать с возможностями обычного устройВнства. Возникают некоторые дополВннительные возможности. Но пока непонятно, позволяют они полуВнчить какой-то выигрыш или нет. Фактически, он и поставил своей статьей такой вопрос.

Кстати, Ю.И. Манин в конце семидесятых годов написал две популярные книжки по логике - ВлВычислимое и невычислимоеВ» и ВлДоказуемое и недоказуемоеВ», и в одной из них есть сюжет про кванВнтовые автоматы, где он говорит о некоторых кардинальных отличиВнях этих автоматов от классических [2].

В середине восьмидесятых годов появились работы Дойча (D. Deutsch), Бернстайна и Вазирани (Е. Bernstein, U. Vazirani), Яo (A. Уао). В них были построены формальные модели квантового компьютера - наприВнмер, квантовая машина Тьюринга [3-6].

Следующий этап - статья Шора (Р.W. Shor) 1994 года [7], вызвавшая лавинообразный рост числа публикаций о квантовых выВнчислениях. Шор построил кванВнтовый (то есть реализуемый на квантовом компьютере) алгоритм факторизации (разложения цеВнлых чисел на множители - исВнпользуется в том числе для вскрыВнтия зашифрованных сообщений). Все известные алгоритмы для обычного компьютера - экспоВнненциальные (время их работы растет как экспонента от числа знаВнков в записи факторизуемого чисВнла). Факторизация 129-разрядВнного числа потребовала 500 MIPS-лет, или восемь месяцев непреВнрывной работы системы из 1600 рабочих станций, объединенных через Интернет. А при числе разВнрядов порядка 300 это время суВнщественно превзойдет возраст Вселенной - даже если работать одновременно на всех существующих в мире машинах. Считается (хотя это и не доказано!), что быВнстрого алгоритма решения этой задачи не существует. Более того, гарантией надежности большинВнства существующих шифров явВнляется именно сложность решеВнния задачи факторизации или одВнной из родственных ей теоретиВнко-числовых задач, например - дискретного логарифма. И вдруг выясняется, что на квантовом комВнпьютере эта задача имеет всего лишь кубическую сложность! ПеВнред квантовым компьютером класВнсические банковские, военные и другие шифры мгновенно теряют всякую ценность. Короче говоря, работа Шора показала, что вся эта изысканная академическая деяВнтельность непосредственно касаВнется такой первобытной стихии, как деньги. После этого и началась настоящая популярность..

Впрочем, выясняется, что не тольВнко классическая, но и квантовая криптография (наука о шифроваВннии сообщений) часто не способна противостоять квантовой криптоаналитике (науке о расшифровке). Некоторые важные криптографиВнческие протоколы, такие как ВлподВнбрасывание монеты по телефонуВ», рушатся при переходе к квантовым вычислениям. Точнее, гарантией их надежности является отныне не сложность тех или иных алгоритВнмов, а сложность задачи создания квантового компьютера.

Таким образом возникает новая отрасль вычислений тАУ квантовые вычисления. Квантовые вычисления (КВ) - это, как можно догадаться, вычислеВнния на квантовом компьютере. Квантовых компьютеров на свете пока нет. Более того, до сих пор неясно, когда появятся практичеВнски полезные конструкции и пояВнвятся ли вообще. Тем не менее, квантовые вычисления - предВнмет, чрезвычайно модный сейчас в математике и физике, как теореВнтической, так и экспериментальВнной, и занимается им довольно много людей. Судя по всему, именно интеВнрес стимулировал первопроходВнцев - Ричарда Фейнмана, напиВнсавшего пионерскую работу, в коВнторой ставился вопрос о вычисВнлительных возможностях устВнройств на квантовых элементах; Дэвида Дойча, формализовавшеВнго этот вопрос в рамках современВнной теории вычислений; и Питера Шора, придумавшего первый неВнтривиальный квантовый алгоритм.

Типы квантовых компьютеров.

Строго говоря, можно выделить два типа квантовых комВнпьютеров. И те, и другие основаны на квантовых явлениях, только разного порядка.

Представителями первого типа являются, например, компьютеры, в основе которых лежит квантоваВнние магнитного потока на нарушеВнниях сверхпроводимости - Джозефсоновских переходах. На эфВнфекте Джозефсона уже сейчас деВнлают линейные усилители, аналого-цифровые преобразователи, СКВИДы и корреляторы. Известен проект создания RISC-процессора на RSFQ-логике (Rapid Single Flux Quantum). Эта же элементная база используется в проекте создания петафлопного (10¹⁵ оп./с) компьюВнтера. Экспериментально достигВннута тактовая частота 370 ГГц, коВнторая в перспективе может быть доведена до 700 ГГц. Однако время расфазировки волновых функций в этих устройствах сопоставимо со временем переключения отдельВнных вентилей, и фактически на ноВнвых, квантовых принципах реалиВнзуется уже привычная нам элементВнная база - триггеры, регистры и другие логические элементы.

Другой тип квантовых компьюВнтеров, называемых еще квантовыВнми когерентными компьютерами, требует поддержания когерентноВнсти волновых функций испольВнзуемых кубитов в течение всего вреВнмени вычислений - от начала и до конца (кубитом может быть люВнбая квантомеханическая система с двумя выделенными энергетичеВнскими уровнями). В результате, для некоторых задач вычислительная мощность когерентных квантовых компьютеров пропорциональна 2^N, где N - число кубитов в компьюВнтере. Именно последний тип устВнройств имеется в виду, когда гоВнворят о квантовых компьютерах.

Математические основы функционирования квантовых компьютеров.

Классический компьютер состоит, грубо говоря, из некоторого числа битов, с которыми можно выполВннять арифметические операции. Основным элементом квантоВнвого компьютера (КК) являются квантовые биты, или кубиты (от Quantum Bit, qubit). Обычный бит - это классическая система, у которой есть только два возможВнных состояния. Можно сказать, что пространство состояний бита - это множество из двух элеменВнтов, например, из нуля и единицы. Кубит же - это квантовая система с двумя возможными состояниями. Имеется ряд примеров таких квантовых систем: электрон, у коВнторого спин может быть равен либо +1/2 либо тАУ1/2, атомы в кристаллиВнческой решетке при некоторых условиях. Но, поскольку система квантовая, ее пространство состоВняний будет несравненно богаче. Математически кубит - это двумерное комплекВнсное пространство.

В такой системе можно выВнполнять унитарные преобразования проВнстранства состояний системы. С точки зрения геометрии такие преВнобразования - прямой аналог вращении и симметрий обычного трехмерного пространства. Согласно принципу суперпозиции вы можете складывать состояния, вычитать их, умВнножать на комплексные числа. Эти состояния образуют фазовые пространства. При объединении двух сисВнтем полученное фазовое пространство будет их тензорным произведением. ЭвоВнлюция системы в фазовом проВнстранстве описывается унитарными преобразованиями фазового проВнстранства.

Так вот, в квантовом компьютеВнре аналогичная ситуация. Он тоже работает с нулями и единицами. Но его функциональные элеменВнты реализуют действия прямо в фазовом пространстве некоторой квантовой системы - при помоВнщи унитарных преобразований этого пространства.

Конечно, унитарные преВнобразования не могут быть произВнвольными - они должны удовлетВнворять некоторым естественным огВнраничениям. Например, в случае обычной логики достаточно иметь три операции: конъюнкция, дизъВнюнкция, отрицание. Все можно реВнализовать, используя только эти три операции. Точно так же и в квантоВнвом случае есть некоторый набор операторов, действующих только на три бита, с помощью которых можВнно все реализовать. Там есть даже более тонкие результаты: можно ограничиться классическими операВнторами на нескольких битах, а кванВнтовые операторы будут действовать только на один бит. То есть классиВнческий набор операций {конъюнкВнция, дизъюнкция, отрицание} можВнно заменить на такой: {конъюнкция, дизъюнкция, квантовое отрицание}, где квантовое отрицание - это проВнизвольное унитарное преобразоВнвание одного кубита.

Фазовое пространство КК есть тензорное произведение кубитов. Если в каждом кубите фиксирован базис (он будет состоять из двух векторов), то фазовое пространВнство - это комплексное линейное пространство, базис которого инВндексирован словами из нулей и единиц. Таким способом двоичВнное слово на входе определяет базисный вектор.

Итак, вход - двоичное слово, определяющее один из базисных векторов. Сам же алгоритм - предписанная последовательность элементарных операторов. ПриВнменяем эту последовательность к вектору на входе, в результате поВнлучаем некоторый вектор на выхоВнде.

Так вот, согласно квантовой механике (КМ), пока система эволюционирует под дейВнствием наших унитарных оператоВнров, мы не можем сказать, в каком именно классическом состоянии она находится. То есть она находится в каком-то квантовом состоянии, но измеряем-то мы, когда общаемся с системой, все равно какие-то классические значения. Как это понимаВнется в КМ? В фазовом пространстве фиксируется некоторый базис, и векВнтор состояния разлагается по этому базису. Это математическая формаВнлизация процедуры измерения в КМ. То есть если мы имеем дело с сисВнтемой, у которой Влто ли спин влево, то ли спин вправоВ», и если мы все-таки посмотрим, какой спин, то мы получим одно из двух в любом слуВнчае. А вот вероятности того, что мы получим тот или другой резульВнтат, - это как раз квадраты модуля коэффициентов разложения. КМ утВнверждает, что точно предсказать реВнзультат измерения нельзя, но вероВнятности возможных результатов выВнчислить можно.

Вероятность возниВнкает в процессе измерения. А пока система живет, для нас существенВнно, что там есть сам этот вектор.

Другими словами, существенно, что система Влнаходится одновременно во всех возможных состоянияхВ». Как пишут многие авторы популярВнных введений в KB, возникает соВнвершенно чудовищный параллелизм вычислении: к примеру, в случае нашей системы из двух кубитов мы как бы оперируем одновременно со всеми возможными ее состояниями: 00, 01, 11, 10.

Чтобы интерпретировать ответ, надо заранее условиться, что какой-то бит - допустим, первый - это бит ответа. Пусть алгоритм проработал, у нас получился каВнкой-то вектор, не обязательно баВнзисный. Тогда мы можем сказать, что первый бит с некоторой вероятВнностью равен 1. И требование к алВнгоритму такое: если ответ ВлдаВ», то вероятность того, что первый бит равен 1, должна быть больше двух третей. А если ответ ВлнетВ», вероятВнность того, что будет ноль, должна быть тоже больше двух третей.

Задачи, реализуемые на КВ.

Известно два примера нетриВнвиальных задач, в которых KB дают радикальный выигрыш.

Первый из них - задача разлоВнжения целых чисел на простые мноВнжители и, как следствие, вычислеВнния дискретного логарифма (ДЛ). Дальше речь пойдет именно о ДЛ.

Пусть у нас есть поле вычетов по модулю простого числа. В нем есть первообразные корни - такие выВнчеты, чьи степени порождают все ненулевые элементы. Если задан такой корень и задана степень, то возвести в степень можно быстро (например, сначала возводим в квадрат, потом получаем четвертую стеВнпень, и т. д.) Дискретный логаВнрифм - это обратная задача. Дан первообразный корень и какой-то элемент поля; найти, в какую степень нужно возвести этот корень, чтобы получить данный элемент. Вот эта задача уже считается сложной. НаВнстолько сложной, что ряд совреВнменных криптографических систем основан на том предположении, что вычислить ДЛ за приемлемое время невозможно, если модуль - достаВнточно большое простое число.

Так вот, для дискретного логаВнрифма есть эффективный квантоВнвый алгоритм. Его придумал Шор в конце 1994 года. ПосВнле его статьи и начался взрыв публиВнкаций по КВ. Независимо от него, Алексей Китаев из ИТФ им. Ландау построил квантовый алгоритм для этой и некоторых более общих заВндач [8]. Идеи у них были разные.

Шор использовал примерно такую идею, она существенно квантовая: рассмотВнрим базис в фазовом пространстве. Он состоит из классических состояний. Но в линейном пространстве много базисов. Мы можем найти некий оператор, который эффективно строит другой базис; мы можем к нему перейти, сделать там какие-то вычисления, вернуться обратно и получить нечто совершенно отличВнное от того, что мы имели бы в классическом базисе. Одна из возВнможностей использовать квантовость состоит в том, что мы строим какой-то странный базис, в нем что-то делаем, возвращаемся обратно и интерпретируем результат. Шор именно эту идею и реализовал. ПриВнчем преобразование оказалось таВнкое, которое и в физике, и в матемаВнтике имеет принциВнпиальное значение - дискретное преобразование Фурье.

Его можно представить в виде тензорного произведения операВнторов, которые действуют на кажВндый из кубитов такой матрицей:

Китаев придумал примерно следующее. Есть некотоВнрая ячейка - основной регистр, где мы записываем наши данные нулями и единицами. И еще есть один управляющий кубит. Мы раВнботаем так: у нас реализована проВнцедура умножения на первообразВнный корень, на квадрат первообВнразного корня, и т. д. УправляюВнщий кубит переводим в некоторое смешанное состояние, дальше строим такой оператор, который, в зависимости оттого, ноль или едиВнница в этом управляющем кубите, либо применяет умножение к наВншему основному регистру, либо не применяет. А потом кубит опять возвращаем в смешанное состояВнние. Оказывается, что это эффекВнтивный способ проделать некотоВнрое измерение. То есть Китаев заВнметил, что одна из вещей, которые мы можем эффективно делать на квантовом компьютере, - это имитировать процесс квантового измерения. В данной задаче из результатов этих измерений эфВнфективно извлекается ответ.

Сам процесс вычислений, происходит так: мы все время умножаем одну и ту же ячейВнку на некие константы, результаты измерений записываем, а потом производим своего рода обработВнку результатов эксперимента - уже чисто классическими вычисВнлениями. Вся квантовая часть закВнлючается в том, что где-то рядом с нашим регистром находится в некоем смешанном состоянии коррелированный с ним кубит, и мы его периодически наблюдаем.

Для выВнчисления ДЛ числа, записанного N битами, нужно потратить N ³ едиВнниц времени. Вполне реализуеВнмо - на КК, естественно. Но здесь надо заметить, что никто пока не доказал, что не существует столь же быстрого алгоритма для выВнчисления ДЛ на обычной машине.

Вторая задача предложена Гровером (L. Grover) [9]. Рассмотрим базу данВнных, содержащую 2^N записей. Мы хотим найти ровно одну запись. Имеется некая процедура опредеВнления того, нужную запись мы взяли или нет. Записи не упоряВндочены. С какой скоростью мы можем решить эту задачу на обычВнном компьютере? В худшем слуВнчае нам придется перебрать все 2^Nзаписей - это очевидно. Оказывается, что на КК достаточно числа запросов поВнрядка корня из числа записей тАУ 2^N/2.

Интересная задача - создаВнние оптимальных микросхем. Пусть есть функция, которую нужно реВнализовать микросхемой, и эта функция задана программой, исВнпользующей полиномиально огВнраниченную память. Построение нужной микросхемы с минимальВнным числом функциональных элеВнментов - задача PSPACE. ПоВнэтому появление устройств, эфВнфективно решающих PSPACE-задачи, позволило бы единообразно проектировать оптимальные по своим показателям вычислительВнные устройства обычного типа. Кроме того, в PSPACE попадает большинство задач Влискусственного интеллектаВ»: машинное обучение, распознавание образов и т.д.

Так вот, точно установлено, что KB находятся где-то между обычВнными вероятностными вычислеВнниями и PSPACE. Если все же окаВнжется, что KB можно эффективно реализовать на классических веВнроятностных машинах, не будет смысла в физической реализации квантовых машин. Если же выясВннится, что при помощи KB можно эффективно решать те или иные PSPACE-задачи, то физическая реализация КК откроет принциВнпиально новые возможности.

Есть еще одна область применения КК, где заведомо возможен радикальный выигрыш у существующих техноВнлогий. Это моделирование самих квантовых систем.

Давайте посмотрим на такой вопрос: как можно эволюцию квантовой системы изучать на обычном компьютере? Это постоВнянно делается, так как это задача важна для химии, молекуВнлярной биологии, физики и т.п. Но, за счет экВнспоненциального роста размерВнности при тензорном произведеВннии, для моделирования десяти спинов вам нужно оперировать с тысячемерным пространством, сто спинов - это уже конец. А если вспомнить, что в молекуле белка десятки тысяч атомов, то.. Там, правда, не всюду существенно именно квантовое моделирование, но в целом ясно, что есть очень серьезные препятствия для модеВнлирования квантовых систем на классических компьютерах. Так что если создать вычислительное устройство, которое ведет себя квантовым образом, то по крайВнней мере один важный класс заВндач на нем есть смысл решать - можно моделировать реальные квантовые системы, возникающие в физике, химии, биологии.

Проблемы создания КК.

Когда начался бум вокруг квантовых вычислений, физики высказывались об этом боВнлее чем скептически. Модель кванВнтовых вычислений не противореВнчит законам природы, но это еще не значит, что ее можно реализовать. К примеру, можно вспомнить создание атомВнного оружия и управляемый термояд.

А если говорить о КК, надо отмеВнтить одну очень серьезную проблеВнму. Дело в том, что любая физичесВнкая реализация будет приближенВнной. Во-первых, мы не сможем сдеВнлать прибор, который будет давать нам произвольный вектор фазовоВнго пространства. Во-вторых, работа любого устройства подвержена всяВнческим случайным ошибкам. А уж в квантовой системе - пролетит каВнкой-нибудь фотон, провзаимодействует с одним из спинов, и все поменяется. Поэтому сразу возник вопрос, можно ли, хотя бы в принВнципе, организовать вычисления на ненадежных квантовых элементах, чтобы результат получался со сколь угодно большой достоверностью. Такая задача для обычных компьюВнтеров решается просто - наприВнмер, за счет введения дополнительВнных битов.

В случае КК эта проблема гоВнраздо глубже. То место, где возВнникает новое качество KB по сравВннению с обычными вычисленияВнми, - это как раз сцепленные состояния - лиВннейные комбинации базисных векВнторов фазового пространства. У вас есть биты, но они не сами по себе живут в каких-то состояниях - это был бы просто вероятВнностный компьютер (компьютер, дающий тот или иной ответ с определенной вероятностью), - а они наВнходятся в некоем смешанном соВнстоянии, причем согласованно-смешанном. Из-за этого в КК нельзя, например, просто взять и скопировать один бит в другой! Обычная интуиция из теории алгоритмов здесь неприменима.

Так что проблема надежности довольно сложна, даже на уровне чистой теории. Те люди, которые активно занимаются KB, активно ее решали и добились успеха: доказано, что, как и в классике, можно делать вычисления на элементах с заВнданной надежностью сколь угодВнно точно. Это реализовано с поВнмощью некоего аналога кодов, исВнправляющих ошибки.

Что касается технической стоВнроны появляются сообщения, что создаВнются реальные квантовые систеВнмы с небольшим числом битов - с двумя, скажем. ЭкспериментальВнные, в железе, так сказать.

Так что эксперименты есть, но пока очень далекие от реальносВнти. Два бита - это и для классиВнческого и для квантового компьВнютера слишком мало! Чтобы моВнделировать молекулу белка, нужВнно порядка ста тысяч кубитов. Для ДЛ, чтобы вскрывать шифры, достаточно примерно тысячи кубитов.

Задача эта возникла слишком недавно, и не исключено, что она потребует каких-то фундаментальВнных исследований в самой физиВнке. Поэтому в обозримом будущем ожидать появления квантовых комВнпьютеров не приходится.

Но можно ожидать распростВнранения через не очень долгое время квантовых криптографиВнческих систем. Квантовая крипВнтография позволяет обмениваться сообщениями так, что враг, если попытается подслушать, сможет разве что разрушить ваше сообВнщение. То есть оно не дойдет до адресата, но перехватить его в принципе будет нельзя. Подобные системы, котоВнрые уже реализованы, используют свеВнтовод. Универсальный КК здесь не нужен. Нужно специаВнлизированное квантовое устройВнство, способное выполнять только небольшой набор операций, - своВнего рода квантовый кодек.

Физической системе, реализующей квантовый компьютер, можно предъявить пять требований:

1. Система должна состоять из точно известного числа частиц.

2. Должна быть возможность привести систему в точно известное начальное состояние.

3. Степень изоляции от внешней среды должна быть очень высока.

4. Надо уметь менять состояние системы согласно заданной последовательности унитарных преобразований ее фазового пространства.

5. Необходимо иметь возможность выполнять Влсильные измеренияВ» состояния системы (то есть такие, которые переводят ее в одно из чистых состояний).

Из этих пяти задач наиболее трудными считаются третья и четвертая. От того, насколько точно они решаются, зависит точность выполнения операций. Пятая задача тоже весьма неприятна, так как измерить состояние отдельной частицы нелегко.

Физические основы организации КК.

Итак, что же это за тайное оружие такое - КК? Остроумная идея заВнключается в использовании для храВннения, передачи и обработки инВнформации существенно квантовых свойств вещества. В основном такие свойства проявляют объекты микВнромира: элементарные частицы, атомы, молекулы и небольшие сгуВнстки молекул, так называемые клаВнстеры. (Хотя, конечно, и в жизни макромира квантовая механика игВнрает важную роль. В частности, только с ее помощью можно объяснить таВнкое явление, как ферромагнетизм.) Одним из квантовых свойств вещеВнства является то, что некоторые веВнличины при измерении (наблюдеВннии) могут принимать значения лишь из заранее определенного дискретВнного набора. Такой величиной, наВнпример, является проекция собстВнвенного момента импульса, или, инаВнче говоря, спина элементарной часВнтицы, на любую заданную ось. НаВнпример, у электрона возможно только два значения проекции: +1/2 или тАУ1/2. Таким образом, количество информации, необходимое для соВнобщения о проекции, равно одному биту. Записав в классическую одноВнбитную ячейку памяти определенВнное значение, мы именно его оттуда и прочтем, если не произойдет каВнкой-нибудь ошибки.

Классической ячейкой может послужить и спин электрона. ОдВннако квантовая механика позволяВнет записать в проекции спина больВнше информации, чем в классике.

Для описания поведения кванВнтовых систем было введено понятие волновой функции. Существуют волновые функции, называемые собственными для какой-то конВнкретной измеряемой величины. В состоянии, описываемом собственВнной функцией, значение этой велиВнчины может быть точно предсказаВнно до ее измерения. Именно с такиВнми состояниями работает обычная память. Квантовая же система может находиться и в состоянии с волноВнвой функцией, равной линейной комбинации собственных функции, соответствующих каждому из возВнможных значений (назовем здесь такие состояния сложными). В сложном состоянии результат изВнмерения величины не может быть предсказан заранее. Заранее изВнвестно только, с какой вероятноВнстью мы получим то или иное знаВнчение. В отличие от обычного комВнпьютера, в квантовом для представВнления данных используются такие ячейки памяти, которые могут наВнходиться в сложном состоянии. В нашем примере мы определили бы, что спин электрона с определенной вероятностью смотрит вверх и вниз, то есть можно сказать, что в кубит записаны сразу и 0, и 1. Количество информации, содержащееся в таВнкой ячейке, и саму ячейку называют квантовым битом, или, сокращенВнно, кубитом. Согласитесь, ячейки в сложных состояниях весьма неВнобычны для классической теории информации. Каждому возможноВнму значению величины, представВнленной кубитом, соответствует веВнроятность, с которой это значение может быть получено при чтении. Эта вероятность равна квадрату моВндуля коэффициента, с которым собВнственная функция этого значения входит в линейную комбинацию. Именно вероятность и является инВнформацией, записанной в кубит.

Квантовую механику не случайВнно называют иногда волновой меВнханикой. Дело в том, что квантово-механические волновые функции ведут себя подобно световой или какой-либо другой волне. И для волновых функций, благодаря их способности интерферировать, также может быть введено понятие когерентности. Именно это свойВнство используется в когерентном квантовом компьютере. Набор кубитов представляется когерентныВнми волновыми функциями. ОкаВнзывается, что существует вполне определенный класс воздействий на квантовую систему, называеВнмый унитарными преобразованияВнми, при которых не теряется запиВнсанная в кубит информация и не нарушается когерентность волноВнвых функций кубитов. Унитарные преобразования обратимы - по результату можно восстановить исВнходные данные. После прохождеВнния через квантовый процессор, использующий унитарные преобВнразования, волновые функции куВнбитов заставляют интерферировать друг с другом, наблюдая получаюВнщуюся картину и судя по ней о результате вычисления.

Из-за того, что для представлеВнния информации используются кубиты, в которых записано сразу оба значения - и 0, и 1, в процессе вычислений происходит паралВнлельная обработка сразу всех возВнможных вариантов комбинаций биВнтов в процессорном слове. Таким образом, в КК реализуется естестВнвенный параллелизм, недоступный классическим компьютерам. За счет возможности параллельной работы с большим числом вариантов, в идеале равным 2^N (где N - число кубитов), квантовому компьютеру необходимо гораздо меньше вреВнмени для решения определенного класса задач. К ним относятся, наВнпример, задача разложения числа на простые множители или поиск в большой базе данных. Для когеВнрентного компьютера уже предлоВнжены алгоритмы, использующие его уникальные свойства. Кроме того, предполагается использовать КК для моделирования квантовых систем, что трудно или вообще невозможно сделать на обычных компьютерах из-за нехватки мощности или по принципиальным соображениям.

Все существующие на сегодняшВнний день обычные компьютеры, даВнже с параллельной обработкой инВнформации на многих процессорах, могут быть смоделированы так наВнзываемым клеточным автоматом Тьюринга. Это существенно детерВнминированная и дискретная машиВнна. С возникновением и обсуждениВнем идей квантовых вычислений стаВнла активно развиваться квантовая теория информации и, в частности, теория квантовых клеточных автоВнматов - ККА. Квантовый клеточный автомат является обобщением автоВнмата Тьюринга для КК. СформулиВнрована гипотеза, гласящая, что кажВндая конечным образом реализуемая физическая система может быть досВнтаточно хорошо смоделирована универсальной моделью квантовой вычислительной машины, испольВнзующей ограниченное количество ресурсов. Для одного из предложенных типов ККА теоретически уже доказано, что он подходит для такоВнго моделирования и не противореВнчит квантовой теории.

Пытаясь осуществить свой заВнмысел, ученые упираются в проВнблему сохранения когерентности волновых функций кубитов, так как потеря когерентности хотя бы одВнним из кубитов разрушила бы инВнтерференционную картину. В наВнстоящее время основные усилия экспериментальных рабочих групп направлены на увеличение отноВншения времени сохранения когеВнрентности ко времени, затрачиваеВнмому на одну операцию (это отноВншение определяет число операций, которые можно успеть провести над кубитами). Главной причиной поВнтери когерентности является связь состояний, используемых для куВнбитов, со степенями свободы, не участвующими в вычислениях. НаВнпример, при передаче энергии элекВнтрона в возбужденном атоме в поВнступательное движение всего атоВнма. Мешает и взаимодействие с окВнружающей средой, например, с соВнседними атомами материала комВнпьютера или магнитным полем ЗемВнли, но это не такая важная проблема. Вообще, любое воздействие на коВнгерентную квантовую систему, коВнторое принципиально позволяет получить информацию о каких-лиВнбо кубитах системы, разрушает их когерентность. Потеря когерентноВнсти может произойти и без обмена энергией с окружающей средой.

Воздействием, нарушающим когерентность, в частности, являВнется и проверка когерентности. При коррекции ошибок возникает своВнего рода замкнутый круг: для того чтобы обнаружить потерю когеВнрентности, нужно получить инВнформацию о кубитах, а это, в свою очередь, также нарушает когерентВнность. В качестве выхода предлоВнжено много специальных методов коррекции, представляющих такВнже и большой теоретический интеВнрес. Все они построеВнны на избыточном кодировании.

Если в области передачи инфорВнмации уже созданы реально рабоВнтающие системы и до коммерческих продуктов осталось лишь несколько шагов, то коммерческая реализация квантового когерентного процессоВнра - дело будущего. К настоящему времени КК научился вычислять сумВнму 1+1! Это большое достижение, если учесть, что в виде результата он выдает именно 2, а не 3 и не 0. Кроме того, не следует забывать, что и перВнвые обычные компьютеры были не особенно мощны.

Сейчас ведется работа над двуВнмя различными архитектурами процессоров: типа клеточного авВнтомата и в виде сети логических элементов. Пока не известно о каВнких-либо принципиальных преВнимуществах одной архитектуры перед другой. Как функциональВнная основа для логических элеВнментов квантового процессора боВнлее или менее успешно используВнется целый ряд физических явлеВнний. Среди них - взаимодействие одиночных поляризованных фоВнтонов или лазерного излучения с веществом или отдельными атоВнмами, квантовые точки, ядерный магнитный резонанс и - наибоВнлее многообещающий - объемВнный спиновый резонанс. Процессор, построВненный на последнем принципе, в шутку называют Влкомпьютером в чашке кофеВ» - из-за того, что в нем работают молекулы жидкости при комнатной температуре и атВнмосферном давлении. Кроме этих эффектов есть довольно хорошо развитая технология логических элементов и ячеек памяти на джозефсоновских переходах, которую можно при соответствующих усВнловиях приспособить под когеВнрентный процессор.

Теорию, описывающую явлеВнния, лежащие в основе первого типа логических ячеек, называют квантовой электродинамикой в поВнлости или резонаторе. Кубиты храВннятся в основных и возбужденных состояниях атомов, расположенВнных некоторым образом на равных расстояниях в оптическом резонаВнторе. Для каждого атома испольВнзуется отдельный лазер, приводяВнщий его в определенное состояние с помощью короткого импульса. Взаимовлияние атомных состояВнний происходит посредством обВнмена фотонов в резонаторе. ОсВнновными причинами разрушения когерентности здесь служат спонВнтанное излучение и выход фотоВннов за пределы резонатора.

В элементах на основе ионов в линейных ловушках кубиты храВннятся в виде внутренних состояний пойманных ионов. Для управлеВнния логикой и для манипулироваВнния отдельными кубитами также используются лазеры. Унитарные преобразования осуществляются возбуждением коллективных кванВнтованных движений ионов. ИсточВнниками некогерентности является спонтанный распад состояний иоВннов в другие внутренние состояния и релаксация в колебательные стеВнпени свободы.

Сильно отличается от двух преВндыдущих Влкомпьютер в чашке коВнфеВ». Благодаря достоинствам данного метода этот комВнпьютер является наиболее реальВнным претендентом на то, чтобы достигнуть разрядности 10 бит в блиВнжайшее время. В компьютере на колВнлективном спиновом резонансе раВнботают молекулы обычных жидкоВнстей (без всяких квантовых вывертов типа сверхтекучести). В качестве куВнбитов используется ориентация ядерных спинов. Работа логических ячеек и запись кубитов осуществляВнется радиочастотными электромагВннитными импульсами со специальВнно подобранными частотой и форВнмой. В принципе, прибор похож на обычные приборы ядерного магВннитного резонанса (ЯМР) и испольВнзует аналогичную аппаратуру. ЖизВннеспособность этого подхода обесВнпечивается, с одной стороны, очень слабой связью ядерных спинов с окружением и, потому, большим временем сохранения когерентноВнсти (до тысяч секунд). Эта связь осВнлаблена из-за экранирования ядерВнных спинов спинами электронов из оболочек атомов. С другой стороны, можно получить сильный выходВнной сигнал, так как для вычислений параллельно используется большое количество молекул. ВлНе так уж сложно измерить спин четвертого ядра у какого-то типа молекул, если у вас имеется около числа Авогадро (~10²³) таких молекулВ», - говорит Ди Винченцо (Di Vincenzo), один из исследователей. Для определения результата непрерывно контролиВнруют излучение всего ансамбля. ТаВнкое измерение не приводит к потере когерентности в компьютере, как было бы в случае использования тольВнко одной молекулы.

Ядерные спины в молекулах жидкости при комнатной темпераВнтуре хаотически разупорядочены, их направления равномерно расВнпределены от 0 до 4p. Проблема записи и считывания кажется неВнпреодолимой из-за этого хаоса. При воздействии магнитного поля спины начинают ор

Вместе с этим смотрят:

80386 процессор

Access

Arvutite ja interneti kasutamine eesti elanike hulgas

Intel

Internet