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

 

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

 

 

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

 

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

 

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

 

 Все началось в 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 дают радикальный  выигрыш. 

 

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

 

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