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

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

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

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

РЕФЕРАТ

на тему:

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

Выполнил:

студент 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, атомы в кристалли¬ческой решетке при некоторых условиях. Но, поскольку система квантовая, ее пространство состо¬яний будет несравненно богаче. Математически кубит - это двумерное комплек¬сное пространство.

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