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

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

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

(ФГБОУ ВПО «ВГТУ», ВГТУ)

Факультет радиотехники и электроники

Кафедра радиоэлектронных устройств и систем

Аттестационная работа

по дисциплине «Нанотехнологии производства электронных средств»

На тему: "Квантовые компьютеры"

Воронеж

2015

Введение

Квантовый компьютер - вычислительное устройство, работающее на основе квантовой механики. Квантовый компьютер принципиально отличается от классических компьютеров, работающих на основе классической механики. Полномасштабный квантовый компьютер является пока гипотетическим устройством, сама возможность построения которого связана с серьёзным развитием квантовой теории в области многих частиц и сложных экспериментов; эта работа лежит на переднем крае современной физики. Ограниченные (до 128 кубитов) квантовые компьютеры уже построены; элементы квантовых компьютеров могут применяться для повышения эффективности вычислений на уже существующей приборной базе.

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

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

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

Предпосылки создания

Начнем с предпосылок создания более скоростных, а значит, и более высокопроизводительных вычислительных систем. Можно с определенной уверенностью сказать, что современная технология создания вычислительных систем (компьютеров и др.) изживает себя. Микропроцессоры последних поколений содержат огромное число транзисторов (10 млн и более). Можно уменьшать физические размеры транзисторов и интегральных схем, применяя нанотехнологию (создание электронных и других элементов с использованием специальной техники для получения размеров 1нм=0,000000001м), но всему есть предел. Это лишь малая часть огромной проблемы, уже вставшей перед специалистами в сфере компьютерных технологий,- проблемы приближения к пределу быстродействия. Пример: за последние несколько лет появился такой положительный феномен, как перенос всей текстовой, графической и другой информации на компьютерные носители. Если раньше база данных с информацией в 1000 записей довольно быстро справлялась с поиском, то теперь, когда в базе данных стало 10 млн записей, это стало довольно затруднительно, и новые алгоритмы поиска не намного уменьшат время поиска. Вывод: нужны компьютеры с более высокими скоростными характеристиками. Поэтому специалисты во всем мире взялись за решение этой проблемы путем создания вычислительной системы будущего. На данный момент существует несколько вариантов ее решения: ведутся экспериментальные разработки квантового компьютера, нейрокомпьютера, оптического компьютера, вероятностного компьютера и др. В 1982 г. Ричард Фейнман написал революционную статью, в которой поставил вопрос о том, какие возможности при вычислениях нам дадут устройства, построенные на квантовых элементах.

История вопроса

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

В 1960-е годы американский физик Р. Ландауэр, работавший в корпорации IBM, пытался обратить внимание научного мира на то, что вычисления - это всегда некоторый физический процесс, а значит, невозможно понять пределы наших вычислительных возможностей, не уточнив, какой физической реализации они соответствуют. К сожалению, в то время среди ученых господствовал взгляд на вычисление как на некую абстрактную логическую процедуру, изучать которую следует математикам, а не физикам.

По мере распространения компьютеров ученые, занимавшиеся квантовыми объектами, пришли к выводу о практической невозможности напрямую рассчитать состояние эволюционирующей системы, состоящей всего лишь из нескольких десятков взаимодействующих частиц, например молекулы метана (СН4). Объясняется это тем, что для полного описания сложной системы необходимо держать в памяти компьютера экспоненциально большое (по числу частиц) количество переменных, так называемых квантовых амплитуд. С такой задачей не справиться даже суперкомпьютер с оперативной памятью, число битов которой равно числу атомов в видимой области Вселенной. И в то же время для исследования динамики такой системы можно просто поставить эксперимент с 30 электронами, поместив их в заданные потенциал и начальное состояние. На это, в частности, обратил внимание русский математик Ю. И. Манин, указавший в 1980 году на необходимость разработки теории квантовых вычислительных устройств. В 1980-е годы эту же проблему изучали американский физик П. Бенев, явно показавший, что квантовая система может производить вычисления, а также английский ученый Д. Дойч, теоретически разработавший универсальный квантовый компьютер, превосходящий классический аналог.

В начале 80-х годов прошлого века нобелевский лауреат Ричард Фейнман (Richard P. Feynman) из Калифорнийского технологического института, известный как автор «Фейнмановских лекций по физике», увлек научную общественность идеей точного моделирования явлений квантовой физики на компьютере принципиально нового типа - квантовом. Благодаря его авторитетному призыву число специалистов, обративших внимание на квантовые вычисления, увеличилось во много раз.

И все же долгое время оставалось неясным, можно ли использовать гипотетическую вычислительную мощь квантового компьютера для ускорения решения практических задач. Но вот в 1994 году американский математик, сотрудник фирмы Lucent Technologies (США) П. Шор ошеломил научный мир, предложив квантовый алгоритм, позволяющий проводить быструю факторизацию больших чисел. По сравнению с лучшим из известных на сегодня классических методов квантовый алгоритм Шора дает многократное ускорение вычислений, причем, чем длиннее факторизуемое число, тем значительней выигрыш в скорости. Алгоритм быстрой факторизации представляет огромный практический интерес для различных спецслужб.

В 1996 году коллега Шора по работе в Lucent Technologies Л. Гровер предложил квантовый алгоритм быстрого поиска в неупорядоченной базе данных. (Пример такой базы данных - телефонная книга, в которой фамилии абонентов расположены не по алфавиту, а произвольным образом.) Задача поиска, выбора оптимального элемента среди многочисленных вариантов очень часто встречается в экономических, военных, инженерных задачах, в компьютерных играх. Алгоритм Гровера позволяет не только ускорить процесс поиска, но и увеличить примерно в два раза число параметров, учитываемых при выборе оптимума.

Реальному созданию квантовых компьютеров препятствовала, по существу, единственная серьезная проблема - ошибки, или помехи. Дело в том, что один и тот же уровень помех гораздо интенсивнее портит процесс квантовых вычислений, чем классических. Пути решения этой проблемы наметил в 1995 году П. Шор, разработав схему кодирования квантовых состояний и коррекции в них ошибок.

Для решения задач в программировании важно понять эти подходы, т.к. они могут радикально изменить их мнение о вычислениях, программировании и сложности.

Вообще-то, время, которое необходимо для осуществления определённых вычислений, можно уменьшить, используя параллельные процессоры. Чтобы достичь экспоненциального уменьшения времени, требуется экспоненциально увеличить число процессоров, а, следовательно, и объём физического пространства. Тогда как в квантовой системе для экспоненциального уменьшения времени, требуется лишь линейное увеличение объёма необходимого физического пространства. Это явление связано непосредственно с квантовым параллелизмом.

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

Но за прошедшие несколько лет люди обнаружили нестандартные пути искусного решения задачи измерения, чтобы использовать преимущества квантового параллелизма. Манипуляции подобного рода не имеют аналогов в классической теории и требуют применения нетрадиционных приемов программирования. Один из таких приёмов заключается в управлении квантовым состоянием таким образом, чтобы могло быть считано общее свойство всех результирующих значений, такое как симметричность или период функции. Подобная техника используется в алгоритме разложения на множители Шора. При другом подходе квантовые состояния преобразуются так, чтобы увеличить вероятность считывания интересующего нас результата вычислений. Этот приём используется в поисковом алгоритме Гровера.

Теория квантовых вычислений

Идея квантовых вычислений, впервые высказанная Ю. И. Маниным и Р. Фейнманом состоит в том, что квантовая система из L двухуровневых квантовых элементов (кубитов) имеет 2L линейно независимых состояний, а значит, вследствие принципа квантовой суперпозиции, 2L-мерное гильбертово пространство состояний. Операция в квантовых вычислениях соответствует повороту в этом пространстве. Таким образом, квантовое вычислительное устройство размером L кубит может выполнять параллельно 2Lопераций.

Предположим, что имеется один кубит. В таком случае после измерения, в так называемой классической форме, результат будет 0 или 1. В действительности кубит - квантовый объект и поэтому, вследствие принципа неопределенности, может быть и 0, и 1 с определенной вероятностью. Если кубит равен 0 (или 1) со стопроцентной вероятностью, его состояние обозначается с помощью символа |0> (или |1>) -- в обозначениях Дирака. |0> и |1> -- это базовые состояния. В общем случае квантовое состояние кубита находится между базовыми и записывается, в виде a|0>+b|1>, где |a|2 и |b|2 -- вероятности измерить 0 или 1 соответственно, где а и b комплексные. Более того, сразу после измерения кубит переходит в базовое квантовое состояние, аналогичное классическому результату.

Пример:

Имеется кубит в квантовом состоянии 3/5|0>-4/5|1>.

В этом случае, вероятность получить при измерении

0 составляет (4/5)2=16/25 = 64 %, 1 (-3/5)2=9/25 = 36 %.

В данном случае, при измерении мы получили 0 с 64 % вероятностью.

Тогда кубит перескакивает в новое квантовое состояние 1*|0>+0*|1>=|0>, то есть, при следующем измерении этого кубита мы получим 0 со стопроцентной вероятностью.

Перейдём к системе из двух кубитов. Измерение каждого из них может дать 0 или 1. Поэтому у системы 4 классических состояния: 00, 01, 10 и 11. Аналогичные им базовые квантовые состояния: |00>, |01>, |10> и |11>. И наконец, общее квантовое состояние системы имеет вид a|00>+b|01>+c|10>+d|11>. Теперь |a|2 -- вероятность измерить 00 и т. д. Отметим, что |a|2+|b|2+|c|2+|d|2=1 как полная вероятность.

В общем случае, системы из L кубитов у неё 2L классических состояний (00000, 00001, … , 11111), каждое из которых может быть измерено с вероятностями 0--100 %.

Рис. 1. Квантовый бит

Кубит является основной ячейкой квантового компьютера. Кубит может принимать 2 значения 0 или 1. Двум значениям кубита могут соответствовать, например, основное и возбужденное состояния атома, направления вверх и вниз спина атомного ядра, направление тока в сверхпроводящем кольце, два возможных положения электрона в полупроводнике и т.п.

Квантовый регистр устроен почти так же, как и классический. Это цепочка квантовых битов, над которыми можно проводить одно- и двухбитовые логические операции.

Рис. 2. Квантовый регистр

К базовым состояниям квантового регистра, образованного L кубитами, относятся, так же как и в классическом, все возможные последовательности нулей и единиц длиной L. Всего может быть 2L различных комбинаций. Их можно считать записью чисел в двоичной форме от 0 до 2L-1 и обозначать 0,1,2,3, ... 2L-1. Однако эти базовые состояния не исчерпывают всех возможных значений квантового регистра (в отличие от классического), поскольку существуют еще и состояния суперпозиции, задаваемые комплексными амплитудами, связанными условием нормировки. Классического аналога у большинства возможных значений квантового регистра (за исключением базовых) просто не существует.

Представьте, что на регистр осуществляется внешнее воздействие, например, в часть пространства поданы электрические импульсы или направлены лазерные лучи. Если это классический регистр, импульс, который можно рассматривать как вычислительную операцию, изменит L переменных. Если же это квантовый регистр, то тот же импульс может одновременно преобразовать до 2L переменных. Таким образом, квантовый регистр, в принципе, способен обрабатывать информацию в 2L / L раз быстрее по сравнению со своим классическим аналогом. Отсюда сразу видно, что маленькие квантовые регистры (L<20) могут служить лишь для демонстрации отдельных узлов и принципов работы квантового компьютера, но не принесут большой практической пользы, так как не сумеют обогнать современные ЭВМ, а стоить будут заведомо дороже. В действительности квантовое ускорение обычно значительно меньше, чем приведенная грубая оценка сверху (это связано со сложностью получения большого количества амплитуд и считывания результата), поэтому практически полезный квантовый компьютер должен содержать тысячи кубитов. Но, с другой стороны, понятно, что для достижения действительного ускорения вычислений нет необходимости собирать миллионы квантовых битов. Компьютер с памятью, измеряемой всего лишь в килокубитах, будет в некоторых задачах несоизмеримо быстрее, чем классический суперкомпьютер с терабайтами памяти. Принципиальная схема работы квантового компьютера показана на рисунке 1.

Рис. 3. Схематическая структура квантового компьютера

У квантового компьютера будет, возможно, и квантовый канал связи, основанный на эффекте, который называется «квантовая телепортация». Принцип квантовой телепортации основан на эффекте запутывания квантовых состояний двух частиц, который анализировался еще в 1935 году Эйнштейном -- Подольским -- Розеном. Запутанные состояния возникают при взаимодействии двух квантовых частиц и последующем их разъединении; при этом они оказываются в некоем «запутанном» состоянии, в котором состояние первой частицы строго коррелировано с состоянием второй. Существуют физические приборы для измерения подобных квантовых систем; например, в системе двух спинов, если один из них будет обнаружен в одном состоянии, то другой всегда будет в состоянии, диктуемом корреляцией, хотя давно с ним и не взаимодействует. То есть подобные корреляции были заложены именно в момент взаимодействия, после чего частицы были пространственно разъединены. Таким образом, квантовый канал связи -- это генератор коррелированных пар и разнесенные в пространстве квантовые частицы. Естественно, при этом сохраняется информация, которая была заложена в момент корреляции; этим можно пользоваться для составления протокола квантовой телепортации. Если имеется квантовая поделенная пара, квантовый канал связи и телефонный канал связи, то можно взять третью квантовую частицу в неизвестном квантовом состоянии и передать его от одного участника связи другому. Для этого нужно «заставить» ее провзаимодействовать с той частью поделенной пары, которая находится у «передающего». В результате частица в неизвестном состоянии оказывается коррелирована с частицей, находящейся у «принимающего». В то же время опосредованно состояние частицы у «передающего» коррелировано с состоянием частицы в неизвестном состоянии. Тогда, после измерения квантового состояния частицы у «передающего», он сообщает по телефону результат «принимающему», а последний по специальным таблицам смотрит, какое воздействие нужно оказать на его частицу, чтобы она перешла в состояние третьей частицы в неизвестном квантовом состоянии. При этом «принимающий» узнает неизвестное квантовое состояние третьей частицы, хотя «передающий» не знает, какое оно. Квантовая телепортация не противоречит фундаментальным физическим принципам, так как сама информация не передается быстрее скорости света. Все это -- чистая физика, которая когда-нибудь воплотится в реальные приборы.

Вычислительные машины

Существует большое множество предложений по созданию квантового компьютера с использованием ионных ловушек, ядерного магнитного резонанса (ЯМР), оптики и твёрдого тела. Все текущие предложения сводятся к решению проблемы увеличения числа кубитов. Необходим качественно новый уровень вычислений, чтобы обрабатывать не десятки, а сотни кубитов информации.

На сегодняшний день технологии с использованием ЯМР и ионных ловушек являются наиболее разрабатываемыми, однако использование оптики и твёрдого тела также подаёт надежды.

Компьютер на ядерно-магнитном резонансе

Теоретических моделей квантового компьютера множество. Проблема, скорее, в том, чтобы найти разумные пути создания реального прибора. Существует как минимум два подхода к осуществлению идеи такого устройства. Ученые, сами того не предполагая, уже создали квантовый компьютер. Его первый «опытный образец» -- это импульсный ядерный магнитно-резонансный (ЯМР) спектрометр высокого разрешения. Спины ядер, входящих в состав атомов, в свою очередь образующих исследуемую в ЯМР-спектрометре молекулу -- это Q-биты, единицы измерения квантовой информации. Каждое ядро имеет свою частоту резонанса в данном магнитном поле. При воздействии импульсом на резонансной частоте одного из ядер оно начинает эволюционировать, остальные же ядра «молчат». Для того чтобы заставить эволюционировать второй атом, надо взять другую частоту и дать импульс на ней. Иными словами, процесс вычислений управляется импульсами переменного магнитного поля, -- нужно только написать алгоритм поставленной задачи. Например, 1000 в степени 3 (то есть миллиард) операций в алгоритме Шора для 1000-разрядного числа -- это миллиард воздействий на отдельные спины и на их пары. При этом в молекуле есть прямая связь между спинами, и поэтому она является идеальной заготовкой для квантового компьютера, а сам спектрометр -- просто готовый «процессор» для этого компьютера. Однако в настоящее время удается работать с системами с общим числом спинов не более пяти-семи, в то время как для решения полномасштабных задач их необходимо порядка 1000. Подобного рода работы в России не ведутся, ибо, как считают наши ученые, принципиально невозможно увеличить количество спинов до требуемого числа.

Компьютер на ионных ловушках

Другой подход основан на использовании ионных ловушек, или «подвешенных» в вакууме ионы. За изобретение ионных ловушек ученому Боннского университета Паулю в свое время была присуждена нобелевская премия. Еще одна нобелевская премия за изобретение методов лазерного охлаждения атомов в газе и ионов в ловушке досталась в прошлом году двум американцам и одному французу, что, кстати, вызвало резкую критику со стороны отечественных ученых, считающих, что приоритет в данной области принадлежит России. Эти ионные ловушки удалось «растянуть» и получить одномерный ионный кристалл, удерживаемый и в осевом, и в радиальном направлении внешними полями. У каждого иона кристалла берутся два уровня энергии -- это один Q-бит; между собой эти ионы связаны через колебания внутри одномерного кристалла, который имеет набор резонансных частот. Больше всего экспериментов по квантовым вычислениям с использованием таких кристаллов предложили ученые Инсбрукского университета в Австрии, а осуществили их больше всего ученые из Лос-Аламосской лаборатории в США. И оказалось, что больших кристаллов не удается получить, на сегодняшний день получена цепочка из 30 ионов. Но дальнейший прогресс в увеличении числа ионов связывают с созданием трехмерной лазерной стоячей волны -- трехмерной совокупности точек с минимумами потенциальной энергии для поляризованных атомов. Иными словами, это трехмерная решетка, которая уже хорошо изучена; изучена также и методология лазерного охлаждения, и поэтому сейчас стоит задача в каждый минимум «положить» атом, его охладить, чтобы он не «вылезал» оттуда, и начать с ним работать. Конечно, в этом направлении очень много работы, но само направление, безусловно, верное.

Рис. 4. Ионная ловушка, как квантовый процессор

После кремния будет кремний

И третий подход -- квантовый компьютер на твердом теле. Это могут быть сверхпроводники, как предлагают ученые из Института Ландау. Мы же предпочитаем подход, который в позапрошлом году высказал австралийский физик Кейн: делать квантовый компьютер точно на том кремнии, на котором сегодня работает традиционная микроэлектроника. В нужных местах на расстояниях порядка 100 ангстрем располагают атомы фосфора -- обычная примесь в кремнии, которая прекрасно изучена. Если на таком расстоянии расположить два атома фосфора, то облака внешних электронов немного пересекутся, что необходимо для их взаимодействия, и атомы смогут обмениваться состояниями. Один атом управляет электронами другого. Над этими атомами делаются 50-ангстремные электродики, и с помощью напряжения на этом электроде меняют резонансную частоту спина ядра атома фосфора. Очень похоже на полевой транзистор -- как бы те же затворы, только вместо тока -- состояния атома. Мы предложили работать не на одном атоме, а на серии атомов; под этими электродами должна быть последовательность атомов, чтобы они действовали параллельно, тогда сформируется относительно больший сигнал, который легче регистрировать.

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

Применение

Криптография

Алгоритм шифрования с открытым ключом RSA встроен в большинство продаваемых операционных систем, а также во множество других приложений, используемых в различных устройствах - от смарткарт до сотовых телефонов. На сегодняшний день фирма RSA Data Security, Inc. продала уже более 450 миллионов лицензий.

Почему же алгоритм RSA оказался так важен? Представим, что нам необходимо быстро обменяться сообщением с человеком, находящимся далеко. Благодаря развитию Интернета такой обмен стал доступен сегодня большинству людей - надо только иметь компьютер с модемом или сетевой картой. Естественно, что, обмениваясь информацией по сети, мы бы хотели сохранить свои сообщения в тайне от посторонних. Однако полностью защитить протяженную линию связи от прослушивания невозможно. Значит, при посылке сообщений их необходимо зашифровать, а при получении - расшифровать. Но как нам и нашему собеседнику договориться о том, каким ключом вы будете пользоваться? Если послать ключ к шифру по той же линии, то подслушивающий злоумышленник легко его перехватит. Можно, конечно, передать ключ по какой-нибудь другой линии связи, например отправить его телеграммой. Но такой метод обычно неудобен и к тому же не всегда надежен: другую линию тоже могут прослушивать. Хорошо, если мы и наш адресат заранее знали, что будете обмениваться шифровками, и потому заблаговременно передали друг другу ключи. А как быть, например, если мы хотим послать конфиденциальное коммерческое предложение возможному деловому партнеру или купить по кредитной карточке понравившийся товар в новом Интернет-магазине?

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

Как раз такая криптографическая схема и применяется в алгоритме RSA - самом распространенном методе шифрования с открытым ключом. Причем для создания пары открытого и закрытого ключей используется следующая важная гипотеза. Если имеется два больших (требующих более сотни десятичных цифр для своей записи) простых числа M и K, то найти их произведение N=MK не составит большого труда (для этого даже не обязательно иметь компьютер: достаточно аккуратный и терпеливый человек сможет перемножить такие числа с помощью ручки и бумаги). А вот решить обратную задачу, то есть, зная большое число N, разложить его на простые множители M и K (так называемая задача факторизации) - практически невозможно! Именно с этой проблемой столкнется злоумышленник, решивший "взломать" алгоритм RSA и прочитать зашифрованную с его помощью информацию: чтобы узнать закрытый ключ, зная открытый, придется вычислить M или K.

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

Оказывается, используя законы квантовой механики, можно построить такие компьютеры, для которых задача факторизации (и многие другие!) не составит большого труда. Согласно оценкам, квантовый компьютер с памятью объемом всего лишь около 10 тысяч квантовых битов способен разложить 1000-значное число на простые множители в течение всего нескольких часов!

Задачи поиска

Большой класс задач можно определять как задачи поиска вроде «найти x из множества возможных решений, такое, что утверждение Р(х) -- истинно». Диапазон подобных задач широк: от поиска информации в базе данных до закраски графа. Например, задачу закраски графа можно рассматривать как поиск такого обозначения цветов вершин, что утверждение «все примыкающие вершины имеют разные цвета» является верным. Аналогично задача сортировки может быть рассмотрена, как поиск перестановки, для которой утверждение «перестановка х переводит первоначальное состояние сортировки в желаемое» являлось бы верным.

В задаче неупорядоченного поиска ничего не известно о структуре пространства решений и об утверждении Р. Например, определение Р(х0) не дает никакой информации о возможном значении Р(х1) для х0  х1. В задаче упорядоченного поиска можно использовать информацию о пространстве поиска и об утверждении Р.

Например, поиск по алфавитному списку является задачей упорядоченного поиска, и алфавитный порядок используется для построения алгоритма. В других случаях, скажем, в задачах, где нужно найти хотя бы одно решение (закраска графа) структуру задачи можно использовать для построения эвристических алгоритмов, которые быстро дают решения для некоторых отдельных случаев. Но в общем случае, когда мы имеем задачу неупорядоченного поиска, лучшее, что можно сделать классическим путём -- это последовательно проверять истинность каждого утверждения P(x1) Для поискового пространства из N элементов обычная задача неупорядоченного поиска требует Q(N) проверок Р. На квантовом же компьютере, как показал Гровер, задачу неупорядоченного поиска можно решить с большой вероятностью производя около Q(N) проверок Р. Таким образом, квантовый алгоритм Гровера является заведомо более эффективным, чем любой алгоритм для неупорядоченного поиска, выполняемый на классическом компьютере.

Оказывается, для неупорядоченного поиска алгоритм Гровера является оптимальным. Однако для большинства поисковых задач требуется упорядоченный поиск. Поскольку существуют классические эвристические алгоритмы, использующие упорядоченность, то можно ожидать, что существуют также и эффективные квантовые алгоритмы для упорядоченного поиска. Брассард и др., опираясь на алгоритм Гровера, показали, что общий классический эвристический поиск имеет квантовый аналог с квадратичным ускорением.

Есть некоторая надежда на то, что для некоторых упорядоченных задач существует ускорение большее, чем квадратичное. Возможно, подобные алгоритмы потребуют новых подходов, которые заключаются не просто в квантовом исполнении классических алгоритмов. Если алгоритм Шора рассматривать в качестве поиска множителей, то он может послужить примером алгоритма, который достигает экспоненциального ускорения, используя структуру задачи (теорию чисел) нестандартным способом, уникальным для квантовых вычислений.

Тед Хогг также разработал несколько эвристических квантовых алгоритмов упорядоченного поиска. Его подход является совершенно неклассическим, в нём используются весьма нетривиальные свойства квантовых вычислений. Единственный минус его подхода заключается в том, что, как и во многих эвристических алгоритмах, использование упорядоченности является усложнённым, и при этом очень трудно определить вероятность получения верного ответа при одной итерации алгоритма. Следовательно, пока ещё не понятно, насколько эффективны алгоритмы Хогга. В классической теории эффективность эвристических алгоритмов оценивается с помощью эмпирического тестирования. Но, поскольку, при моделировании квантовых операций на классическом компьютере наблюдается экспоненциальное замедление, то эмпирическое тестирование квантовых алгоритмов сегодня невозможно, разве что за небольшими исключением. Алгоритм Хогга в применении к некоторым задачам упорядоченного поиска, является более эффективным, чем алгоритм Гровера, но ускорение при этом является полиномиальным. С теоретической точки зрения -- это менее интересно, но с практической -- даже малое полиномиальное ускорение этих вычислительных задач имеет огромное значение. До тех пор, пока не будет создано больших квантовых компьютеров или лучших приёмов для анализа таких алгоритмов, эффективность нельзя будет определить точно.

Конкретные проекты

Среди ведущих мировых ученых, активно воплощающих идеи квантового компьютинга в жизнь, следует отметить прежде всего доктора Айзека Чуанга (Isaac Chuang) из центра IBM Алмейден (IBM's Almaden Research Center, Сан-Хосе, Калифорния). Возглавляемые им команды специалистов создали в 1998 г. в Калифорнийском университете Беркли первый в мире двухкубитовый квантовый компьютер, в следующем году - трехкубитовый образец, который с использованием алгоритма Гровера совершал поиск в базе данных, а позднее был продемонстрирован метод упорядочения на квантовом компьютере с разрядностью 7 кубит. Ученые в центре IBM Алмейден выполнили одно из наиболее сложных квантовокомпьютерных вычислений. Они создали 7-кубитовый квантовый компьютер из миллиарда миллиардов изготовленных по заказу молекул, который с помощью алгоритма Шора решил простую версию математической проблемы, лежащую в основе многих из сегодняшних криптографических систем защиты данных. Хотя решённая им задача вряд ли способна поразить воображение (компьютер верно определил, что делителями числа 15 являются числа 5 и 3), это самое сложное вычисление за всю историю квантовых компьютеров. Он может быть "запрограммирован" при помощи электромагнитных импульсов разной частоты, а для получения результатов работы устройства используется ЯМР-сканер.

Канадская компания D-Wave в 13 февраля текущего года продемонстрировала первый квантовый компьютер Orion в Компьютерном музее в Калифорнии (Computer History Museum in Mountain View). Представитель компании сказал, что D-Wave планирует начать продажу квантовых вычислительных мощностей корпоративным заказчикам в I квартале 2008 г.

Рис. 5. Симикубитовая молекула

Рис. 6. Элементы квантового компьютера Orion компании D-Wave: а - квантовый процессор в сборе; б - электронные модули для связи с квантовым чипом; в - кремниевый квантовый чип с 16 кубитами

Компьютер D-Wave's построен на кремниевом чипе (рис. 5, а), который содержит 16 кубитов (эквивалентных битам в обычном компьютере), соединенных друг с другом. Каждый кубит состоит из кристалла ниобия, помещенного в катушку индуктивности.

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

«Кубиты ведут себя согласно некоторому своду правил, - сказал один из основателей компании Джорди Роуз (Geordie Rose). - Квантовые вычисления - это перевод квантовых законов в формат, который мы можем понять».

В конечном счете, компьютер Orion - аналоговое устройство. Работа программ квантового компьютера - это процесс аналогового физического моделирования, а программы в цифровых вычислительных машинах по существу выполняют математические процедуры.

В силу присущих ему квантовых свойств компьютер фирмы D-Wave's оптимизирован для реализации сложных, часто повторяющихся задач моделирования: например, необходимо выяснить, что произойдет при вариации переменных в сложной финансовой модели, или как различные белки взаимодействуют с различными синтетическими лекарствами, разрабатываемыми в фармацевтической промышленности. Система также может использоваться и в других областях, скажем, при анализе патентных баз данных для поиска пар одинаковых или перекрывающихся объектов интеллектуальной собственности.

«Мы рассматриваем эти машины как генераторы распределения вероятности, - сказал г-н Роуз, - и хотим создать физический аналог сложной математической задачи».

Сейчас Orion - доказательство работоспособности концепции квантового компьютера - демонстрация того, как будет выглядеть конечный продукт. На ней была показана программа для решения проблемы Sudoku (Судоку - головоломка, которая стала популярной в 1986 г. в Японии, а в 2005 г. - во всем мире. Ее часто называют «кубиком Рубика XXI в.». Относится к классу трудно решаемых задач).

Была также представлена система поиска молекул, подобных активному ингредиенту в препарате Prilosec (лекарство против изжоги и для восстановления кислотности фирмы AstraZeneca) в химической базе данных. Компьютер нашел несколько молекул, которые имели элементы, схожие с конструкцией Prilosec, но самой близкой молекулой оказался активный ингредиент в другом препарате под названием Nexium. Это продемонстрировало точность квантового вычислителя. Nexium - фактически зеркальное изображение молекулы в Prilosec, а фармацевтическая компания AstraZeneca «разработала» его для обеспечения патентной чистоты.

В другом примере квантовый компьютер решил известную задачу размещения гостей за столом, где каждый гость имел свои требования. (Клеопатра не может находиться рядом с теми, кто ест мясо. Чингисхан ест мясо и т. д.) Он рассчитал план размещения гостей с минимальным числом нарушений протокола.

Собственно компьютер, который функционирует при температуре 0,004К (-273,15 ?С) и охлаждается жидким гелием, находился в Канаде. Посетители только видели результаты его работы на экране. Однако, по словам г-на Роуза, это была самая большая демонстрация квантового компьютера когда-либо.

Как сообщил генеральный директор компании Герб Мартин (Herb Martin), к концу года D-Wave будет иметь 32-кубитовую систему и планирует сдавать в аренду время на своих квантовых компьютерах корпоративным клиентам в I квартале следующего года.

«Заказчик не обязан изучать специальные методы программирования и другие тонкости работы системы, чтобы воспользоваться преимуществом квантового компьютера; достаточно отправить задание D-Wave, подобно заказу, как это принято в любой другой компании, - говорит г-н Мартин. - Позже D-Wave планирует сдавать в аренду или продавать компьютеры», - добавил он.

Во II квартале 2008 г. компания планирует создать 512-кубитовую систему, а к концу года и 1024-кубитовую.

«Квантовые компьютеры, - подчеркнул Герб Мартин, - не заменят цифровых вычислительных машин. Вместо этого они будут служить как сопроцессоры для решения больших проблем».

Но имеется ли рынок для аренды вычислительных ресурсов? Sun Microsystems несколько лет назад открыла сервер, который сдает как хранилище баз данных для химических и фармацевтических компаний. Его используют уже несколько заказчиков.

«Некоторые проблемы у D-Wave могут возникнуть потому, что квантовый компьютер будет способен решать намного более сложные проблемы, чем те, которыми занимаются компании в настоящее время», - сказал Стив Джарветсон (Steve Jurvetson), партнер компании Draper Fisher Jurvetson и инвестор D-Wave. Например, многие медицинские фирмы искусственно ограничивают возможности своих исследований, чтобы они соответствовали существующим вычислительным мощностям. D-Wave имеет 100 доступных зарегистрированных приложений и 35 грантов.

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

Холодильная установка потребляет мощность 20 кВт, которая все еще мала по сравнению с большинством тяжелых серверов - хранилищ данных. «Рост числа кубитов на чипе не потребует значительного увеличений охлаждения», - добавил г-н Роуз.

Даже с объяснениями квантовые концепции могут быть слишком сложными для широкой публики. Попытки понять атомные взаимодействия ведутся до настоящего времени и лежат в основе квантовых вычислений

Заключение

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

квантовый компьютер вычислительный

Список литературы

http://quantumcomputers.narod.ru/

А.Китаев, А.Шень, М.Вялый. Классические и квантовые вычисления. М.: МЦНМО, 1999, 192 с.

http://ru.wikipedia.org/

http://www.nsu.ru/psj/lector/neizvestniy/

http://itc.ua/print.phtml?ID=27644

Размещено на Allbest.ru