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

2

НОУ ВПО «БАЛТИЙСКИЙ ИНСТИТУТ ЭКОНОМИКИ И ФИНАНСОВ»

«БИЭФ»

Кафедра физики

Контрольная работа по дисциплине: Концепция современного естествознания

На тему:                                        КВАНТОВЫЕ КОМПЬЮТЕРЫ

                                                                                                      Студентка          Ескина А.В.

                                                                                       Курс, группа      I, 3011

                                                                                                  Дата сдачи    ______________

                                                                                                  Дата проверки _____________

         Проверил преподаватель______

                                                                 Юров А.В.

Калининград

2011

СОДЕРЖАНИЕ

Введение……………………………………………………………...…………………….3

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

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

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

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

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

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

Заключение………………………………………………………………………………..14

Список использованных источников……………………………………………………15

Введение

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

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

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

Идея кванто­вого компьютера возникла так.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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