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

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

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

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

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

РЕФЕРАТ

на тему:

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

Выполнил:

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

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

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

Страницы: 1 2 3