Смекни!
smekni.com

Квантовые компьютеры (стр. 1 из 4)

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

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

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

РЕФЕРАТ

на тему:

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

Выполнил:

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

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