www.yurii.ru

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

superbotanik.net

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

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

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

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

РЕФЕРАТ

на тему:

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

Выполнил:

студент 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). Эта же элементная база используется в проекте создания петафлопного (1015 оп./с) компьютера. Экспериментально достигнута тактовая частота 370 ГГц, которая в перспективе может быть доведена до 700 ГГц. Однако время расфазировки волновых функций в этих устройствах сопоставимо со временем переключения отдельных вентилей, и фактически на новых, квантовых принципах реализуется уже привычная нам элементная база — триггеры, регистры и другие логические элементы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вторая задача предложена Гровером (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. Количество информации, содержащееся в такой ячейке, и саму ячейку называют квантовым битом, или, сокращенно, кубитом. Согласитесь, ячейки в сложных состояниях весьма необычны для классической теории информации. Каждому возможному значению величины, представленной кубитом, соответствует вероятность, с которой это значение может быть получено при чтении. Эта вероятность равна квадрату модуля коэффициента, с которым собственная функция этого значения входит в линейную комбинацию. Именно вероятность и является информацией, записанной в кубит.

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

Из-за того, что для представления информации используются кубиты, в которых записано сразу оба значения — и , и 1, в процессе вычислений происходит параллельная обработка сразу всех возможных вариантов комбинаций битов в процессорном слове. Таким образом, в КК реализуется естественный параллелизм, недоступный классическим компьютерам. За счет возможности параллельной работы с большим числом вариантов, в идеале равным 2 N (где 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. Feynman R. Int. J. Theor. Phys. 21, 1982.

2. Манин Ю.И. Вычислимое и невычислимое. — М.: Советское радио, 1980.

3. Feynman R. Quantum mechanical computers. // Optics News, February 1985, 11, p.11.

4. Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer. — Proc. R. Soc. London A 400, 97, 1985.

5. Deutsch D. Quantum computational networks. — Proc. R. Soc. London A 425, 73, 1989.

6. Yao А. С.-С. Quantum circuit complexity. //Proceedings of the 34th Annual Symposium on the Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1993, p. 352.

7. Shor P.W. Algorithms for Quantum Computation: Discrete log and Factoring. // Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, edited by S. Goldwasser, IEEE Computer Society Press, Los Alamitos, CA, 1994, p.124.

8. Китаев A.Ю. Квантовые вычисления: алгоритмы и исправление ошибок. //Успехи математических наук.

9. Grover L. Afast quantum mechanical algorithm for database search. //Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 212-219.

10. Kitaev A.Yu. Quantum measurements and the Abelian stabilizer problem. — LANL e-print quant-ph/9511026, xxx.lanl.gov.

11. Shor P.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 Quantum Computing. — LANL e-print quant-ph/9701001, xxx.lanl.gov, to appear in SIAM J. On Computing.

www.ronl.ru

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

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

АСТРАХАНСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТкафедра теоретической физикиРЕФЕРАТ

на тему:

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

студент 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). Эта же элементная база используется в проекте создания петафлопного (1015 оп./с) компьютера. Экспериментально достигнута тактовая частота 370 ГГц, которая в перспективе может быть доведена до 700 ГГц. Однако время расфазировки волновых функций в этих устройствах сопоставимо со временем переключения отдельных вентилей, и фактически на новых, квантовых принципах реализуется уже привычная нам элементная база - триггеры, регистры и другие логические элементы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сильно отличается от двух предыдущих «компьютер в чашке кофе». Благодаря достоинствам данного метода этот компьютер является наиболее реальным претендентом на то, чтобы достигнуть разрядности 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. Feynman R. Int. J. Theor. Phys. 21, 1982.

2. Манин Ю.И. Вычислимое и невычислимое. - М.: Советское радио, 1980.

3. Feynman R. Quantum mechanical computers. // Optics News, February 1985, 11, p.11.

4. Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer. - Proc. R. Soc. London A 400, 97, 1985.

5. Deutsch D. Quantum computational networks. - Proc. R. Soc. London A 425, 73, 1989.

6. Yao А. С.-С. Quantum circuit complexity. //Proceedings of the 34th Annual Symposium on the Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1993, p. 352.

8. Китаев A.Ю. Квантовые вычисления: алгоритмы и исправление ошибок. //Успехи математических наук.

9. Grover L. Afast quantum mechanical algorithm for database search. //Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 212-219.

10. Kitaev A.Yu. Quantum measurements and the Abelian stabilizer problem. - LANL e-print quant-ph/9511026, http://xxx.lanl.gov.

11. Shor P.W. Fault-Tolerant Quantum Computation. - LANL e-print quant-ph/9005011, http://xxx.lanl.gov.

12. Bennett С.Н., Bernstein E., Brassard G., Vazirany U. Strengths and Weaknesses of Quantum Computing. - LANL e-print quant-ph/9701001, http://xxx.lanl.gov, to appear in SIAM J. On Computing.

bukvasha.ru

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

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

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

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

РЕФЕРАТ

на тему:

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

Выполнил:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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