Реферат: Квантовые вычисления. Кратчайшее введение в квантовые вычисления (гостевой пост Романа Душкина) Квантовые расчеты

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

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

Реферат

Квантовые вычисления

Введение

Глава I. Основные понятия квантовой механики

Глава II. Основные понятия и принципы квантовых вычислений

Глава III. Алгоритм Гровера

Заключение

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

Введение

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

Тогда вы думаете о квантовом компьютере.

Идея вычислительного устройства, основанного на квантовой механике, впервые рассматривалась еще в ранних 1970-х годах и ранних 1980-х физиками и компьютерными учеными, такими, например, как Чарльз Х. Беннет из IBM Thomas J. Watson Research Center, Пол А. Бениофф из Аргоннской национальной лаборатории в Иллинойсе, Дэвидом Дойчем из Оксфордского университета, и позднее Ричардом П. Фейнманом из из Калифрнийского технологического института (Калтех). Идея возникла тогда, когда ученые заинтересовались фундаментальными ограничениями вычислений. Они поняли, что если технология будет продолжать следовать постепенному уменьшению размеров вычислительных сетей упакованных в кремниевые ЧИПы, то это приведет к тому, что индивидуальные элементы станут не больше чем несколько атомов. Тогда возникла проблема, так как на атомном уровне действуют законы квантовой физики, а не классической. А это подняло вопрос, можно ли сконструировать компьютер, основанный на принципах квантовой физики.

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

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

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

Глава I . Основные понятия квантовой механики

В конце 19 века среди ученых было широко распространено мнение, что физика – наука «практически завершенная» и для полной её «завершенности» осталось совсем немного: объяснить структуру оптических спектров атомов и спектральное распределение теплового излучения . Оптические спектры атома получаются при испускании или поглощении света (электромагнитных волн) свободными или слабо связанными атомами; такими спектрами обладают, в частности, одноатомные газы и пары.

Тепловое излучение – это механизм переноса тепла между пространственно разделёнными частями тела за счет электромагнитного излучения.

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

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

При решении проблемы спектрального состава излучения немецким физиком Максом Планком в 1900 году было высказано предположение о том, что излучение и поглощение света веществом происходит конечными порциями, или квантами. При этом энергия фотона - кванта электромагнитного излучения (в узком смысле - света) определяется выражением

Где - частота излучаемого (или поглощаемого) света, а – универсальная постоянная, называемая теперь постоянной Планка.

Часто используется постоянная Дирака

Тогда энергия кванта выражается как , где

Круговая частота излучения.

Противоречия между рассмотрением света как потока заряженных частиц и как волны привело к понятию корпускулярно-волнового дуализма.

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

Почти монохроматическое излучение с частотой испускаемое источником света, можно представить себе состоящим из «пакетов излучения», которые мы называем фотонами. Монохроматическое излучение – обладающее очень малым разбросом частот, в идеале - одной длиной волны.

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

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

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

В 1921 году опытом Штерна-Герлаха было подтверждено наличие у атомов спина и факт пространственного квантования направления их магнитных моментов (от англ. spin - вращаться, вертеться.). Спин -собственный момент количества движения элементарных частиц, имеющий квантовую природу и не связанный с перемещением частицы как целого. При введении понятия спина предполагалось, что электрон можно рассматривать как «вращающийся волчок», а его спин - как характеристику такого вращения. Спином называют также собственный момент импульса атомного ядра или атома; в этом случае спин определяется как векторная сумма (вычисленная по правилам сложения моментов в квантовой механике) спинов элементарных частиц, образующих систему, и орбитальных моментов этих частиц, обусловленных их движением внутри системы.

Спин измеряется в единицах (приведенных постоянных Планка, или постоянных Дирака) и равен , где J - характерное для каждого сорта частиц целое (в т. ч. нулевое) или полуцелое положительное число - спиновое квантовое число , которое обычно называют просто спином (одно из квантовых чисел). В связи с этим говорят о целом или полуцелом спине частицы. Однако не следует путать понятия спин и спиновое квантовое число. Спиновое квантовое число - это квантовое число, определяющее величину спина квантовой системы (атома, иона, атомного ядра, молекулы), т. е. её собственного (внутреннего) момента импульса. Проекция спина на любое фиксированное направление z в пространстве может принимать значения J , J-1, ..., -J. Т. о., частица со спином J может находиться в 2J + 1 спиновых состояниях (при J = 1 / 2 - в двух состояниях), что эквивалентно наличию у неё дополнительной внутренней степени свободы.

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

Движение фотона можно описать системой уравнений Максвелла, в то время как уравнение движения любой другой элементарной частицы типа электрона описывается уравнением Шрёдингера, которое более общее.

Система уравнений Максвелла инвариантна относительно преобразования Лоренца. Преобразованиями Лоренца в специальной теории относительности называются преобразования, которым подвергаются пространственно-временные координаты (x,y,z,t) каждого события при переходе от одной инерциальной системы отсчета к другой. По сути, эти преобразования представляют собой преобразования не только в пространстве, как преобразования Галилея, но и во времени.

Глава II . Основные понятия и принципы квантовых вычислений

Хотя компьютеры стали компактными и значительно быстрее, чем раньше, справляются со своей задачей, сама задача остается прежней: манипулировать последовательностью битов и интерпретировать эту последовательность как полезный вычислительный результат. Бит - это фундаментальная единица информации, обычно представляемая как 0 или 1 в вашем цифровом компьютере. Каждый классический бит физически реализуется макроскопической физической системой, такой как намагниченность на жестком диске или заряд конденсатора. Например, текст, составленный из n символов, и сохраненный на жестком диске типичного компьютера, описывается строкой из 8n нулей и единиц. Здесь и лежит фундаментальное отличие между вашим классическим компьютером и квантовым компьютером. В то время как классический компьютер подчиняется хорошо понятным законам классической физики, квантовый компьютер это устройство, которое использует квантово-механические явления (в особенности квантовую интерференцию ), чтобы осуществлять совершенно новый способ обработки информации.

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

Идеи о возможности построения квантового компьютера восходят к работам Р. Фейнмана 1982- 1986 гг. Рассматривая вопрос о вычислении эволюции квантовых систем на цифровом компьютере, Фейнман обнаружил "нерешаемость" этой задачи: оказывается, что ресурсы памяти и быстродействия классических машин недостаточны для решения квантовых задач. Например, система из n квантовых частиц с двумя состояниями (спины 1/2 ) имеет 2 n базисных состояний; для ее описания необходимо задать (и записать в память ЭВМ) 2 n амплитуд этих состояний. Отталкиваясь от этого негативного результата, Фейнман высказал предположение, что, вероятно, "квантовый компьютер" будет обладать свойствами, которые позволят решать на нем квантовые задачи.

"Классические" компьютеры построены на транзисторных схемах, обладающих нелинейными зависимостями между входными и выходными напряжениями. По существу, это бистабильные элементы; например, при низком входном напряжении (логический "0") входное напряжение высокое (логическая "1"), и наоборот. Такой бистабильной транзисторной схеме в квантовом мире можно сопоставить двухуровневую квантовую частицу: состоянию припишем значения логического , состоянию , - значение логической . Переходам в бистабильной транзисторной схеме здесь будут соответствовать переходы с уровня на уровень: . Однако квантовый бистабильный элемент, получивший название кубит, обладает новым, по сравнению с классическим, свойством суперпозиции состояний: он может быть в любом суперпозиционном состоянии , где - комплексные числа, . Состояния квантовой системы из п двухуровневых частиц имеют в общем случае вид суперпозиции 2 n базовых состоянии . В конечном счете квантовый принцип суперпозиции состояний позволяет придать квантовому компьютеру принципиально новые "способности".

Доказано, что квантовая ЭВМ может быть построена всего из двух элементов (вентилей): однокубитового элемента и двухкубитового элемента контролируемое НЕ (CNOT). Матрица 2x2 элемента имеет вид:

(1)

Вентиль описывает поворот вектора состояния кубита от оси z к полярной оси, заданной углами . Если - иррациональные числа, то многократным применением вектору состояния можно придать любую наперед заданную ориентацию. Именно в этом заключается "универсальность" однокубитового вентиля в форме (1). В частном случае получаем однокубитовый логический элемент НЕ (NOT): НЕ=, НЕ=. При физической реализации элемента НЕ необходимо воздействовать на квантовую частицу (кубит) импульсом извне, переводящим кубит из одного состояния в другое. Вентиль контролируемое НЕ исполняют, воздействуя на два взаимодействующих между собой кубита: при этом посредством взаимодействия один кубит контролирует эволюцию другого. Переходы под влиянием внешних импульсов хорошо известны в импульсной магниторезонансной спектроскопии. Вентиль НЕ соответствует перевороту спина под действием импульса (вращение намагниченности вокруг оси на угол ). Вентиль CNOT выполняется на двух спинах 1/2 с гамильтонианом (спин контролирует ). CNOT выполняется в три шага: импульс + свободная прецессия в течение времени - импульс . Если (контролирующий кубит в состоянии ), то при указанных воздействиях контролируемый кубит совершает переходы (или ). Если же (контролирующий кубит в состоянии ), то результат эволюции контролируемого кубита будет другим: (). Таким образом, спин , эволюционирует по-разному при : здесь в - состояние контролирующего кубита.

При рассмотрении вопроса о реализации квантового компьютера на тех или иных квантовых системах в первую очередь исследуют реализуемость и свойства элементарных вентилей НЕ и контролируемое НЕ.

Для дальнейшего полезно также ввести однокубитовое преобразование Адамара:

В технике магнитного резонанса эти вентили осуществляются импульсами :

Схема квантового компьютера представлена на рисунке. До начала работы компьютера все кубиты (квантовые частицы) должны быть приведены в состояние , т.е. в основное состояние. Это условие само по себе не тривиально.

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

В результате система перешла в состояние суперпозиции из 2 п базисных состояний с амплитудой 2 - n /2 . Каждое базисное состояние представляет собой двоичное число от до . Горизонтальные линии на рисунке обозначают оси времени.

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

Количество сомножителей в этом разложении определяет длительность (и сложность) вычислений . Все в (3) выполняются с применением операций NOT, CNOT, Н (или их разновидностей).

Замечательно, что линейный унитарный оператор действует одновременно на все члены суперпозиции

Результаты вычисления записываются в запасном регистре, который перед применением находился в состоянии . За один прогон вычислительного процесса мы получаем значения искомой функции f при всех значениях аргумента х = 0,..., 2 п - 1 . Этот феномен получил название квантового параллелизма.

Измерение результата вычислений сводится к проецированию вектора суперпозиции в (4) на вектор одного из базисных состояний :

(5)

Здесь проступает одно из слабых мест квантового компьютера: число в процессе измерения "выпадает" по закону случая. Чтобы найти при заданном , надо много раз провести вычисления и измерения, пока случайно не выпадет .

При анализе унитарной эволюции квантовой системы, совершающей вычислительный процесс, выявляется важность физических процессов типа интерференции. Унитарные преобразования совершаются в пространстве комплексных чисел, и сложение фаз этих чисел носит характер интерференции. Известна продуктивность преобразований Фурье в явлениях интерференции и спектроскопии. Оказалось, что и в квантовых алгоритмах неизменно присутствуют преобразования Фурье. Преобразование Адамара является простейшим дискретным фурье-преобразованием. Вентили типа NOT и СNOT могут быть осуществлены непосредственно на интерферометре Маха-Зендера с использованием явления интерференции фотона и вращения его вектора поляризации.

Исследуются различные пути физической реализации квантовых компьютеров. Модельные эксперименты по квантовому компьютингу выполнены на импульсном ядерном магнитно-резонансном спектрометре. В этих моделях работало два или три спина (кубита), например два спина ядер 13 С и один спин протона в молекуле трихлорэтилена

Однако в этих опытах квантовый компьютер был "ансамблевым": выходные сигналы компьютера сложены большим числом молекул в жидком растворе (~ 10 20).

К настоящему времени высказаны предложения о реализации квантовых компьютеров на ионах и молекулах в ловушках в вакууме, на ядерных спинах в жидкостях (см. выше), на ядерных спинах атомов 31 Р в кристаллическом кремнии, на спинах электронов в квантовых точках, созданных в двумерном электронном газе в гетероструктурах GaAs, на переходах Джозеф-сона. Как видим, в принципе, квантовый компьютер можно построить на атомных частицах в вакууме, жидкости, кристаллах. При этом в каждом случае предстоит преодолеть те или иные препятствия, однако среди них можно выделить несколько общих, обусловленных принципами действия кубитов в квантовом компьютере. Поставим задачу создать полномасштабный квантовый компьютер, содержащий, скажем, 10 3 кубитов (хотя и при п = 100 квантовый компьютер может стать полезным инструментом).

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

Для ионов в вакуумных ловушках сверхнизкое охлаждение ионов (атомов) достигается лазерными методами. Очевидна также необходимость холодного и сверхвысокого вакуума.

2. Необходимо иметь технологию избирательного воздействия импульсами на любой выбранный кубит. В области радиочастот и спинового резонанса это означает, что каждый спин должен обладать своей резонансной частотой (в терминах спектроскопического разрешения). Различия резонансных частот для спинов в молекулах обусловлены химическими сдвигами для спинов одного изотопа и одного элемента; необходимые различия частот имеются для спинов ядер различных элементов. Однако здравый смысл подсказывает, что эти дарованные природой различия резонансных частот вряд ли достаточны, чтобы работать с 10 3 спинов.

Более перспективными представляются подходы, когда можно управлять извне резонансной частотой каждого кубита. В предложении о кремниевом квантовом компьютере кубитом служит ядерный спин примесного атома 31 Р. Частота резонанса определяется константой А сверхтонкого взаимодействия ядерного и электронного спинов атома 31 Р. Электрическое поле на наноэлектроде, находящемся над атомом 31 Р, поляризует атом и изменяет константу А (соответственно резонансную частоту ядерного спина). Таким образом, наличие электрода встраивает кубит в электронную схему и настраивает его резонансную частоту.

3. Для выполнения операции CNOT (контролируемое НЕ) необходимо взаимодействие между кубитами и вида . Такое взаимодействие возникает между спинами ядер в молекуле, если ядра и разделены одной химической связью. В принципе, необходимо иметь возможность выполнять операцию для любых пар кубитов . Иметь физическое взаимодействие кубитов одного масштаба величины и по принципу "все со всеми" в природной среде вряд ли возможно. Очевидна потребность в способе настройки среды между кубитами извне путем введения электродов с управляемым потенциалом. Таким путем можно создать, например, перекрытие волновых функций электронов в соседних квантовых точках и возникновение взаимодействия вида между спинами электронов [. Перекрытие волновых функций электронов соседних атомов 31 Р обусловливает возникновение взаимодействия вида между ядерными спинами.

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

4. В ходе выполнения унитарного преобразования, соответствующего избранному алгоритму, кубиты компьютера подвергаются воздействию со стороны среды; в результате амплитуды и фазы вектора состояния кубита испытывают случайные изменения - декогеренизацию . По существу, декогеренизация - это релаксация тех степеней свободы частицы, которые используются в кубите. Время декогеренизации равно времени релаксации. В ядерном магнитном резонансе в жидкостях времена и релаксации составляют 1-10 с. Для ионов в ловушках с оптическими переходами между уровнями Е 0 и Е 1 временем декогеренизации выступают время спонтанного излучения и время столкновений с остаточными атомами. Очевидно, что декогеренизация - это серьезное препятствие квантовому вычислению: начатый вычислительный процесс приобретает черты случайности по истечении времени декогеренизации. Однако можно достичь устойчивого квантового вычислительного процесса в течение сколь угодно долгого времени т > та, если систематически использовать методы квантового кодирования и коррекции ошибок (фазовых и амплитудных). Доказано, что при относительно невысоких требованиях к безошибочному выполнению элементарных операций типа NОТ и СNОТ (вероятность ошибки не более 10 -5) методы квантовой коррекции ошибок (QEC) обеспечивают устойчивую работу квантового компьютера.

Возможно и активное подавление процесса декогеренизации, если над системой кубитов проводить периодические измерения. Измерение с большой вероятностью обнаружит частицу в "правильном" состоянии, а малые случайные изменения вектора состояния при измерении коллапсируют (квантовый эффект Зенона). Однако трудно пока сказать, насколько полезным может быть такой прием, поскольку такие измерения сами по себе могут воздействовать на вычислительный процесс и нарушить его.

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

К настоящему времени открыты квантовые алгоритмы, приводящие к экспоненциальному ускорению вычислений по сравнению с вычислениями на классическом компьютере. К ним относится алгоритм Шора определения простых множителей больших (многоразрядных) чисел. Эта чисто математическая проблема тесно связана с жизнью общества, так как на "невычислимости" таких множителей построены современные шифровальные коды. Именно это обстоятельство вызвало сенсацию, когда был открыт алгоритм Шора. Для физиков важно, что и решение квантовых задач (решение уравнения Шрёдингера для многочастичных систем) экспоненциально ускоряется, если использовать квантовый компьютер.

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

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

В обычном компьютере информация кодируется последовательностью битов, и эти биты последовательно обрабатываются булевскими логическими элементами, чтобы получить нужный результат. Аналогично квантовый компьютер обрабатывает кубиты, выполняя последовательность операций квантовыми логическими элементами, каждый из которых представляет собой унитарное преобразование, действующее на единичный кубит или пару кубитов. Последовательно выполняя эти преобразования, квантовый компьютер может выполнить сложное унитарное преобразование над всем набором кубитов приготовленных в некотором начальном состоянии. После этого можно произвести измерение над кубитами, которое и даст конечный результат вычислений. Это сходство вычислений между квантовым и классическим компьютером позволяет считать, что, по крайней мере, в теории, классический компьютер может в точности воспроизводить работу квантового компьютера. Другими словами, классический компьютер может делать все то же самое, что и квантовый компьютер. Тогда зачем вся эта возня с квантовым компьютером? Дело в том, что, хотя теоретически классический компьютер может симулировать квантовый компьютер, это очень неэффективно, настолько неэффективно, что практически классический компьютер не в состоянии решать многие задачи, которые по плечу квантовому компьютеру. Симуляция квантового компьютера на классическом компьютере вычислительно сложная проблема, потому что корреляции между квантовыми битами качественно отличается от корреляций между классическими битами, как было впервые показано Джоном Беллом. Для примера можно взять систему только из нескольких сотен кубитов. Она существует в пространстве Гильберта размерностью ~10 90 , что потребует, при моделировании классическим компьютером, использования экспоненциально больших матриц (чтобы выполнить расчеты для каждого отдельного состояния, которое также описывается матрицей). Это означает, что классическому компьютеру понадобится экпоненциально больше времени по сравнению даже с примитивным квантовым компьютером.

Ричард Фейнман был среди первых, кто осознал потенциал, заложенный в явлении квантовой суперпозиции для решения таких задач гораздо быстрее. Например, система из 500 кубитов, которую практически невозможно промеделировать классически, представляет собой квантовую суперпозицию из 2 500 состояний. Каждое значение такой суперпозиции классически эквивалентно списку из 500 единиц и нулей. Любая квантовая операция над такой системой, например, настроенный определенным образом импульс радиоволн, который может выполнить операцию управляемое НЕ над, скажем, 100-м и 101-м кубитом, будет одновременно воздействовать на 2 500 состояний. Таким образом, за один тик компьютерных часов квантовая операция вычисляет не одно машинное состояние, как обычные компьютеры, а 2 500 состояний сразу! Однако, в конце концов, над системой кубитов производится измерение, и система коллапсирует в единственное квантовое состояние, соответствующее единственному решению задачи, единственному набору из 500 единиц и нулей, как это диктуется измерительной аксиомой квантовой механики. Это поистине волнующий результат, поскольку это решение, найденное колективным процессом квантовых параллельных вычислений, берущим свои истоки в суперпозиции, эквивалентно выполнению той же самой операции на классическом суперкомпьютере с ~10 150 отдельных процессоров (что, конечно, невозможно)!! Первые исследователи в этой области были, конечно, вдохновлены такими гигантскими возможностями, и поэтому вскоре началась настоящая охота за подходящими задачами для такой вычислительной мощи. Питер Шор, исследователь и компьютерный ученый из компании AT&T"s Bell Laboratories в Нью Джерси, предложил такую задачу, которую можно было бы решить именно на квантовом компьютере и при помощи квантового алгоритма. Алгоритм Шора использует мощь квантовой суперпозиции, чтобы раскладывать большие числа (порядка ~10 200 двоичных разрядов и больше) на множители за несколько секунд. Эта задча имеет важное практическое применение для шифрования, где общепринятый (и лучший) алгоритм шифрования, известный как RSA, основан как раз на сложности разложения больших составных чисел на простые множители. Компьютер, который с легкостью решает такую задачу, конечно, представляет большой интерес для множества правительственных организаций, использующих RSA, который до сих пор считался "невзламываемым", и для любого кто заинтересован в безопсаности своих данных.

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

Глава III . Алгоритм Гровера

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

Реализуя данный алгоритм, можно используя то же самое оборудование, как в классическом случае, но задавая вход и выход в виде суперпозиции состояний, можно найти объект за O () квантовомеханических шагов вместо О( N )) классических шагов. Каждый квантовомеханический шаг состоит из элементарной унитарной операции, которые рассмотрим далее.

Для осуществления данного алгоритма нам необходимы следующие три элементарные операции. Первая - это приготовление состояния, в котором система находится с равной вероятностью в любом из ее N базисных состояний; вторая - это преобразование Адамара и третья - выборочный поворот фаз состояний.

Как известно основной операцией для квантовых вычислений является операция М , действующая на один бит, которая представляется следующей матрицей:

т. е. бит в состоянии 0 превращается в суперпозицию двух состояний: (1/, 1/). Аналогично, бит в состоянии 1 трансформируется в (1/, -1/,), т. е. величина амплитуды для каждого состояния равна 1/, но фаза в состоянии 1 перевернута. Фаза не имеет аналога в классических вероятностных алгоритмах. Она возникает в квантовой механике, где амплитуда вероятности комплексна. В системе, в которой состояние описывается п битами (т. е. имеется N = 2 п возможных состояний), мы можем осуществить преобразование М на каждом бите независимо, последовательно изменяя состояние системы. В случае, когда начальная конфигурация представляла собой конфигурацию с п битами в первом состоянии, полученная конфигурация будет иметь равные амплитуды для каждого из состояний. Это и есть способ создания суперпозиции с той же самой амплитудой для всех состояний.

Третье преобразование, которое нам понадобится, - это выборочное вращение фазы амплитуды в определенных состояниях. Преобразование, представленное здесь для системы из двух состояний, имеет форму:

где j = и - произвольные действительные числа. Заметим, что в отличие от преобразования Адамара и других матриц преобразования состояний, вероятность каждого состояния остается той же, т. к. квадрат абсолютной величины амплитуды в каждом состоянии остается прежним.

Рассмотрим задачу в абстрактной форме.

Пусть система имеет N = 2 п состояний, которые обозначаются как ,..., . Эти 2 п состояния представляются как n-битные строки. Пусть существует единственное состояние, скажем , которое довлетворяет условию C() = 1, тогда как для всех других состояний S, С( ,) = 0 (предполагается, что для любого состояния S условие оценивается за единицу времени). Задача состоит в распознании состояния ,

Перейдем собственно к алгоритму

Шаги (1) и (2) являются последовательностью элементарных унитарных операций описаных ранее. Шаг (3) есть завершающее измерение, осуществляемое внешней системой.

(1) Приводим систему в состояние суперпозиции:

с одинаковыми амплитудами для каждого из N состояний. Эта суперпозиция может быть получена за шагов.

(2) Повторим следующую унитарную операцию О( ) раз:

a . Пусть система будет в каком-нибудь состоянии S:

В случае С( S ) = 1, повернуть фазу на радиан;

В случае С(S) = 0, оставить систему неизмененной.

b . Применить преобразование диффузии D которое определяется матрицей D следующим образом:, если ;" и . D может быть реализована как последовательное выполнение унитарных преобразований: , где W – матрица преобразований Адамара, R – матрица фазового поворота.

(3) Произвести измерение полученного состоянии. Это состояние будет состоянием С( )„ (т. е. искомым состоянием, удовлетворяющим условию (C() = 1) с вероятностью, по крайней мере, не меньшей, чем 0.5. Заметим, что шаг (2а) - это фазовое вращение. В его реализацию должна быть включена процедура распознания состояния и последующего определения осуществлять или нет поворот фазы. Она должна проводиться таким образом, чтобы не оставлять следа на состоянии системы, так, чтобы была уверенность, что пути, приводящие к тому же самому конечному состоянию, неразличимы и могут интерферировать. Заметим, что эта процедура не включает классического измерения.

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

Заключение

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

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

1. Квантовые вычисления: за и против. Под ред. В.А. Садовничего. – Ижевск: Издательский дом «Удмуртский университет», 1999. – 212 с.

2. Белонучкин В.E., Заикин Д.А., Ципенюк Ю.М., Основы физики. Курс общей физики: Учебн. В 2 т. Т. 2. Квантовая и статистическая физика. – М.: ФИЗМАТЛИТ, 2001. – 504 с.

3. Валиев К.А. «Квантовые компьютеры: можно ли их сделать «большими»?», Успехи физических наук, т. 169, № 6, 1999г.

4. Валиев К.А. «Квантовая информатика: компьютеры, связь и криптография», ВЕСТНИК РОССИЙСКОЙ АКАДЕМИИ НАУК, том 70, № 8, с. 688-695, 2000г.

5. Маслов. Д. «Квантовые вычисления и коммуникация: реальность и перспективы», Компьютерра, №46 , 2004г.

6. Халфин Л.А. «Квантовый эффект Зенона», Успехи физических наук, т. 160, № 10, 1990г.

7. Холево А. «Квантовая информатика: прошлое, настоящее, будущее»,

В МИРЕ НАУКИ, №7, 2008г.

8. Centre for Quantum Technologies, National University of Singapore www.quantumlah.org

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

Экспоненциальный рост размерности при попытке расчетов реальных систем или самых простых квантовых систем является непреодолимым препятствием для классических компьютеров. Однако в 1980 году Юрий Манин и Ричард Фейнман (в 1982 году, но более подробно) независимо выдвинули идею использования квантовых систем для вычислений. В отличие от классических современных компьютеров, в квантовых схемах при вычислениях используются кубиты (квантовые биты), которые по своей природе являются квантовыми двухуровневыми системами и обеспечивают возможность прямого использования феномена квантовой суперпозиции. Другими словами это означает, что кубит может одновременно находится в состояниях |0> и |1>, а два связанных между собой кубита - одновременно в состояниях |00>, |10>, |01> и |11>. Именно это свойство квантовых систем должно обеспечить экспоненциальный рост производительности параллельных вычислений, сделав квантовые компьютеры в миллионы раз быстрее самых мощных современных суперкомпьютеров.

В 1994 году Питером Шором предложен квантовый алгоритм разложения чисел на простые множители. Вопрос существования эффективного классического решения данной задачи является крайне важным и до сих пор открыт, при этом квантовый алгоритм Шора обеспечивает экспоненциальное ускорение относительно наилучшего классического аналога. Например, современный суперкомпьютер петафлопсного диапазона (10 15 операций/сек) позволяет разложить число с 500 десятичными знаками за 5 миллиардов лет, квантовый компьютер мегагерцового диапазона (10 6 операций/сек) решил бы ту же задачу за 18 секунд. Важно отметить, что сложность решения данной задачи является основой популярного алгоритма криптографической защиты RSA, который после создания квантового компьютера попросту потеряет актуальность.

В 1996 году Ловом Гровером предложен квантовый алгоритм решения задачи перебора (поиска) с квадратичным ускорением. Несмотря на то, что ускорение алгоритма Гровера заметно ниже алгоритма Шора, важным является его широкий спектр применения, и очевидная невозможность ускорения классического варианта перебора. Сегодня известно более 40 эффективных квантовых алгоритмов, большинство из которых основаны на идеях алгоритмов Шора и Гровера, реализация которых является важным шагом к созданию универсального квантового компьютера.

Реализация квантовых алгоритмов - одна из приоритетных задач НОЦ ФМН. Наши исследования в этой области направлены на разработку многокубитных сверхпроводящих квантовых интегральных схем для создания универсальных квантовых систем обработки информации и квантовых симуляторов. Базовым элементом таких схем являются джозефсоновские туннельные переходы, состоящие из двух сверхпроводников, разделенных тонким барьером - диэлектриком толщиной порядка 1 нм. Сверхпроводящие кубиты на основе джозефсоновских переходов при охлаждении в криостатах растворения практически до температуры абсолютного нуля (~20 мК) проявляют квантово-механические свойства, демонстрируя квантование электрического заряда (зарядовые кубиты), фазы или потока магнитного поля (потоковые кубиты) в зависимости от их конструкции. Для объединения кубитов в схемы используются емкостные или индуктивные соединительные элементы, а также сверхпроводящие копланарные резонаторы, а управление осуществляется микроволновыми импульсами с контролируемыми амплитудой и фазой. Сверхпроводящие схемы особенно привлекательны благодаря тому, что они могут быть изготовлены планарными массовыми технологиями, используемыми в полупроводниковой промышленности. В НОЦ ФМН мы используем оборудование (R&D класса) ведущих мировых производителей, специально спроектированное и созданное для нас с учетом особенностей технологических процессов изготовления сверхпроводящих квантовых интегральных схем.

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

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

Благодаря нелинейным свойствам при ультра низких потерях (по своей природе) и возможности масштабирования (изготовление литографическими методами) джозефсоновские переходы крайне привлекательны для создания квантовых сверхпроводящих схем. Зачастую для изготовления квантовой схемы требуется сформировать сотни и тысячи джозефсоновских переходов с характерными размерами порядка 100 нм нп кристалле. При этом надежная работа схем реализуется только при условии точного воспроизведения параметров переходов. Другими словами все переходы квантовых схем должны быть абсолютно одинаковыми. Для этого прибегают к использованию самых современных методов электронно-лучевой литографии и последующего высокоточного теневого напыления через резистивные или жесткие маски.

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

В ФМН разработана алюминиевая технология формирования джозефсоновских переходов Al–AlOx–Al с минимальными размерами в диапазоне 100-500 нм и воспроизводимостью параметров переходов по критическому току не хуже 5%. Продолжающиеся технологические исследования направлены на поиск новых материалов, усовершенствование технологических операций формирования переходов, подходов по интеграции с новыми маршрутными технологическими процессами и повышение воспроизводимости изготовления переходов при увеличении их количества до десятков тысяч штук на кристалле.

Джозефсоновские кубиты (квантовая двухуровневая система или «искусственный атом») характеризуются типичным расщеплением энергии основного возбужденного состояния на уровни и управляются стандартными микроволновыми импульсами (внешняя подстройка расстояния между уровнями и собственных состояний) на частоте расщепления в гигагерцовом диапазоне. Все сверхпроводящие кубиты можно разделить на зарядовые (квантование электрического заряда) и потоковые кубиты (квантование магнитного поля или фазы), а основными критериями качества кубитов с точки зрения квантовых вычислений являются время релаксации (T1), время когерентности (T2, дефазировки) и время на выполнение одной операции. Первый зарядовый кубит был реализован в лаборатории компании NEC (Япония) научной группой под руководством Y. Nakamura и Ю. Пашкина (Nature 398, 786–788, 1999). За прошедшие 15 лет времена когерентности сверхпроводящих кубитов были улучшены ведущими научными группами почти на шесть порядков с наносекуд до сотен микросекунд, обеспечив возможность выполнения сотен двухкубитных операций и реализации алгоритмов коррекции ошибок.

В НОЦ ФМН мы разрабатываем, изготавливаем и тестируем зарядовые и потоковые кубиты различных конструкций (потоковые, флаксониумы, 2D/3D трансмоны, X-моны и т.п.) с алюминиевыми джозефсоновскими переходами, проводим исследования новых материалов и методов создания высококогерентных кубитов, направленные на улучшение основных параметров сверхпроводящих кубитов.

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

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

Научные группы из различных областей физики давно занимаются исследованием возможности когерентного взаимодействия (связи) квантовых двухуровневых систем с квантовыми гармоническими осцилляторами. До 2004 года такого взаимодействия удавалось добиться только в экспериментах атомной физики и квантовой оптики, где одиночный атом когерентно обменивается одиночным фотоном с одномодовым излучением. Эти эксперименты внесли большой вклад в понимание механизмов взаимодействия света с веществом, квантовой физики, физики когерентности и декогерентности, а также подтвердили теоретические основы концепции квантовых вычислений. Однако в 2004 году научной группой под руководством A. Wallraff (Nature 431, 162-167 (2004)) была впервые продемонстрирована возможность когерентной связи твердотельной квантовой схемы с одиночным фотоном микроволнового диапазона. Благодаря этим экспериментам и после решения ряда технологических проблем были разработаны принципы создания управляемых твердотельных двухуровневых квантовых систем, которые составили основу новой парадигмы схем квантовой электродинамики (QED схем) активно исследуемых в последние годы.

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

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

Исследования и разработки в области квантовых вычислений проводятся в тесной кооперации с ведущими российскими научными коллективами ИФТТ РАН, МИСИС, МФТИ, НГТУ и РКЦ под управлением известных в мире российских ученых.

Историческая справка

Квантовые вычисления немыслимы без контроля над квантовым состоянием отдельных элементарных частиц. Двум физикам - французу Сержу Лрошу и американцу Дэвиду Вайнленду - это удалось. Лрош ловил в резонатор одиночные фотоны и надолго «отцеплял» их от внешнего мира. Вайнленд собирал в ловушку одиночные ионы с опреденными квантовыми состояниями и изолировал их от внешнего воздействия. Арош использовал атомы, чтобы наблюдать за состоянием фотона. Вайнленд применял фотоны, чтобы изменять состояния ионов. Им удалось продвинуться в изучении взаимоотношения квантового и классического миров. В 2012 г. им была вручена Нобелевская премия по физике за «прорывные экспериментальные методы, которые сделали возможными измерение отдельных квантовых систем и управление ими».

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

В нашем случае это означает, что имеется 2" базовых состояний, а компьютер может оперировать суперпозицией из этих 2" базовых состояний.

Заметим, что воздействие на какой-либо кубит немедленно приводит к одновременному изменению всех 2” базовых состояний. Это свойство носит название «квантовый параллелизм ».

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

Под унитарной матрицей будем понимать квадратную матрицу ||aj|, произведение которой на комплексную сопряженную и транспонированную матрицу || aJI дает единичную матрицу. Числа a jk и a ki комплексные. Если числа a ik являются действительными числами, то унитарная матрица будет ортогональной. Некоторое число кубитов формирует квантовый регистр компьютера. В такой цепочке квантовых битов можно проводить одно- и двухбитовые логические операции подобно тому, как в классическом регистре проводятся операции НЕ, И-НЕ, 2 ИЛИ-HE и т.д. (рис. 5.49).

Определенное число N регистров формируют по существу квантовый компьютер. Работа квантового компьютера происходит в соответствии с разработанными алгоритмами вычислений.

Рис. 5.49.

NOT - булевское НЕ; CNOT - контролируемое НЕ

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

где p i - населенность или вероятность i- го состояния, так что р { + р 2 + р 3 + + Ра = 1-

Свойство когерентных квантовых состояний иметь сумму вероятностей, равную единице, называется запутыванием, или сцеплением, состояний. Запутанные, или сцепленные, квантовые объекты связаны между собой независимо от того, насколько далеко они расположены друг от друга. Если измеряется состояние одного из сцепленных объектов, то немедленно получаются сведения о состоянии других объектов.

Если два кубита сцеплены между собой, то они лишены индивидуальных квантовых состояний. Они зависят друг от друга так, что измерение для одного тина дает «О», а для другого - «1» и наоборот (рис. 5.50). В этом случае говорят, что максимально сцепленная пара несет один e-бит сцеплснности.

Запутанные состояния являются ресурсом устройств квантового вычислителя, и для пополнения числа запутанных состояний необходимо разработать методы надежной генерации сцепленных кубитов. Одним из мето-

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

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

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

Алгоритм Дойна - Йожи позволяет «за одно вычисление» определить, является ли функция двоичной переменной /(/?) постоянной (f x {ri) = О, f 2 {ri) = 1 независимо от п) или «сбалансированной» (f 3 (0) = 0,/ 3 (1) = 1;/ 4 (0) = 1, / 4 (1) = 0).

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

Алгоритм Гровера позволяет найти решение уравнения f(x) = 1 для 0 х за время O(VN) и предназначен для поиска в базе данных. Квантовый алгоритм Гровера является заведомо более эффективным, чем любой алгоритм для неупорядоченного поиска на классическом компьютере.

Алгоритм факторизации Шора позволяет определить для простых множителей аиЬ заданное целое число М= a"Xb путем использования соответствующей квантовой схемы. Этот алгоритм позволяет находить сомножители А-значного целого числа. С его помощью можно оценить время вычислительного процесса. Одновременно алгоритм Шора можно интерпретировать как пример процедуры определения энергетических уровней квантовой вычислительной системы.

Алгоритм Залки - Визнера позволяет моделировать унитарную эволюцию квантовой системы п частиц за почти линейное время с использованием О(п) кубитов.

Алгоритм Саймона решает проблему «черного ящика» экспоненциально быстрее, чем любой классический алгоритм, включая вероятностные алгоритмы.

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

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

Квантовый компьютер прогрессивнее классического по ряду показателей. Большинство современных компьютеров работают по фон-нейманов- ской либо по гарвардской схеме: п бит памяти хранят состояние и каждый такт времени изменяются процессором. В квантовом компьютере система из п кубитов находится в состоянии, являющимся суперпозицией всех базовых состояний, поэтому изменение системы касается всех 2" базовых состояний одновременно. Теоретически новая схема может работать в экспоненциальное число раз быстрее классической. Практически квантовый алгоритм поиска в базе данных показывает квадратичный прирост мощности против классических алгоритмов.

"Классические" компьютеры построены на транзисторных схемах, обладающих нелинейными зависимостями между входными и выходными напряжениями. По существу, это бистабильные элементы; например, при низком входном напряжении (логический "0") входное напряжение высокое (логическая "1"), и наоборот. Такой бистабильной транзисторной схеме в квантовом мире можно сопоставить двухуровневую квантовую частицу: состоянию припишем значения логического, состоянию, - значение логической. Переходам в бистабильной транзисторной схеме здесь будут соответствовать переходы с уровня на уровень: . Однако квантовый бистабильный элемент, получивший название кубит, обладает новым, по сравнению с классическим, свойством суперпозиции состояний: он может быть в любом суперпозиционном состоянии, где -- комплексные числа, . Состояния квантовой системы из п двухуровневых частиц имеют в общем случае вид суперпозиции 2 n базовых состоянии. В конечном счете квантовый принцип суперпозиции состояний позволяет придать квантовому компьютеру принципиально новые "способности".

Вентиль описывает поворот вектора состояния кубита от оси z к полярной оси, заданной углами . Если -- иррациональные числа, то многократным применением вектору состояния можно придать любую наперед заданную ориентацию. Именно в этом заключается "универсальность" однокубитового вентиля в форме (1). В частном случае получаем однокубитовый логический элемент НЕ (NOT): НЕ=, НЕ=. При физической реализации элемента НЕ необходимо воздействовать на квантовую частицу (кубит) импульсом извне, переводящим кубит из одного состояния в другое. Вентиль контролируемое НЕ исполняют, воздействуя на два взаимодействующих между собой кубита: при этом посредством взаимодействия один кубит контролирует эволюцию другого. Переходы под влиянием внешних импульсов хорошо известны в импульсной магниторезонансной спектроскопии. Вентиль НЕ соответствует перевороту спина под действием импульса (вращение намагниченности вокруг оси на угол). Вентиль CNOT выполняется на двух спинах 1/2 с гамильтонианом (спин контролирует). CNOT выполняется в три шага: импульс + свободная прецессия в течение времени - импульс. Если (контролирующий кубит в состоянии), то при указанных воздействиях контролируемый кубит совершает переходы (или). Если же (контролирующий кубит в состоянии), то результат эволюции контролируемого кубита будет другим: (). Таким образом, спин, эволюционирует по-разному при: здесь в - состояние контролирующего кубита. Валиев К.А. «Квантовая информатика: компьютеры, связь и криптография», ВЕСТНИК РОССИЙСКОЙ АКАДЕМИИ НАУК, том 70, № 8, с. 688-695, 2000г.

Для дальнейшего полезно также ввести однокубитовое преобразование Адамара:

В технике магнитного резонанса эти вентили осуществляются импульсами:

Схема квантового компьютера представлена на рисунке. До начала работы компьютера все кубиты (квантовые частицы) должны быть приведены в состояние, т.е. в основное состояние. Это условие само по себе не тривиально.

В результате система перешла в состояние суперпозиции из 2 п базисных состояний с амплитудой 2 -n/2 . Каждое базисное состояние представляет собой двоичное число от до. Горизонтальные линии на рисунке обозначают оси времени.

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

Количество сомножителей в этом разложении определяет длительность (и сложность) вычислений. Все в (3) выполняются с применением операций NOT, CNOT, Н (или их разновидностей).

Замечательно, что линейный унитарный оператор действует одновременно на все члены суперпозиции

Результаты вычисления записываются в запасном регистре, который перед применением находился в состоянии. За один прогон вычислительного процесса мы получаем значения искомой функции f при всех значениях аргумента х = 0,..., 2 п -- 1 . Этот феномен получил название квантового параллелизма.

Однако в этих опытах квантовый компьютер был "ансамблевым": выходные сигналы компьютера сложены большим числом молекул в жидком растворе (~ 1020).

К настоящему времени высказаны предложения о реализации квантовых компьютеров на ионах и молекулах в ловушках в вакууме, на ядерных спинах в жидкостях (см. выше), на ядерных спинах атомов 31 Р в кристаллическом кремнии, на спинах электронов в квантовых точках, созданных в двумерном электронном газе в гетероструктурах GaAs, на переходах Джозеф-сона. Как видим, в принципе, квантовый компьютер можно построить на атомных частицах в вакууме, жидкости, кристаллах. При этом в каждом случае предстоит преодолеть те или иные препятствия, однако среди них можно выделить несколько общих, обусловленных принципами действия кубитов в квантовом компьютере. Поставим задачу создать полномасштабный квантовый компьютер, содержащий, скажем, 10 3 кубитов (хотя и при п = 100 квантовый компьютер может стать полезным инструментом).

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

3. Для выполнения операции CNOT (контролируемое НЕ) необходимо взаимодействие между кубитами и вида. Такое взаимодействие возникает между спинами ядер в молекуле, если ядра и разделены одной химической связью. В принципе, необходимо иметь возможность выполнять операцию для любых пар кубитов. Иметь физическое взаимодействие кубитов одного масштаба величины и по принципу "все со всеми" в природной среде вряд ли возможно. Очевидна потребность в способе настройки среды между кубитами извне путем введения электродов с управляемым потенциалом. Таким путем можно создать, например, перекрытие волновых функций электронов в соседних квантовых точках и возникновение взаимодействия вида между спинами электронов [. Перекрытие волновых функций электронов соседних атомов 31Р обусловливает возникновение взаимодействия вида между ядерными спинами.

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

4. В ходе выполнения унитарного преобразования, соответствующего избранному алгоритму, кубиты компьютера подвергаются воздействию со стороны среды; в результате амплитуды и фазы вектора состояния кубита испытывают случайные изменения -- декогеренизацию. По существу, декогеренизация -- это релаксация тех степеней свободы частицы, которые используются в кубите. Время декогеренизации равно времени релаксации. В ядерном магнитном резонансе в жидкостях времена и релаксации составляют 1-10 с. Для ионов в ловушках с оптическими переходами между уровнями Е0 и Е1 временем декогеренизации выступают время спонтанного излучения и время столкновений с остаточными атомами. Очевидно, что декогеренизация -- это серьезное препятствие квантовому вычислению: начатый вычислительный процесс приобретает черты случайности по истечении времени декогеренизации. Однако можно достичь устойчивого квантового вычислительного процесса в течение сколь угодно долгого времени т > та, если систематически использовать методы квантового кодирования и коррекции ошибок (фазовых и амплитудных). Доказано, что при относительно невысоких требованиях к безошибочному выполнению элементарных операций типа NОТ и СNОТ (вероятность ошибки не более 10-5) методы квантовой коррекции ошибок (QEC) обеспечивают устойчивую работу квантового компьютера.

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

В обычном компьютере информация кодируется последовательностью битов, и эти биты последовательно обрабатываются булевскими логическими элементами, чтобы получить нужный результат. Аналогично квантовый компьютер обрабатывает кубиты, выполняя последовательность операций квантовыми логическими элементами, каждый из которых представляет собой унитарное преобразование, действующее на единичный кубит или пару кубитов. Последовательно выполняя эти преобразования, квантовый компьютер может выполнить сложное унитарное преобразование над всем набором кубитов приготовленных в некотором начальном состоянии. После этого можно произвести измерение над кубитами, которое и даст конечный результат вычислений. Это сходство вычислений между квантовым и классическим компьютером позволяет считать, что, по крайней мере, в теории, классический компьютер может в точности воспроизводить работу квантового компьютера. Другими словами, классический компьютер может делать все то же самое, что и квантовый компьютер. Тогда зачем вся эта возня с квантовым компьютером? Дело в том, что, хотя теоретически классический компьютер может симулировать квантовый компьютер, это очень неэффективно, настолько неэффективно, что практически классический компьютер не в состоянии решать многие задачи, которые по плечу квантовому компьютеру. Симуляция квантового компьютера на классическом компьютере вычислительно сложная проблема, потому что корреляции между квантовыми битами качественно отличается от корреляций между классическими битами, как было впервые показано Джоном Беллом. Для примера можно взять систему только из нескольких сотен кубитов. Она существует в пространстве Гильберта размерностью ~10 90 , что потребует, при моделировании классическим компьютером, использования экспоненциально больших матриц (чтобы выполнить расчеты для каждого отдельного состояния, которое также описывается матрицей). Это означает, что классическому компьютеру понадобится экпоненциально больше времени по сравнению даже с примитивным квантовым компьютером.

Ричард Фейнман был среди первых, кто осознал потенциал, заложенный в явлении квантовой суперпозиции для решения таких задач гораздо быстрее. Например, система из 500 кубитов, которую практически невозможно промеделировать классически, представляет собой квантовую суперпозицию из 2 500 состояний. Каждое значение такой суперпозиции классически эквивалентно списку из 500 единиц и нулей. Любая квантовая операция над такой системой, например, настроенный определенным образом импульс радиоволн, который может выполнить операцию управляемое НЕ над, скажем, 100-м и 101-м кубитом, будет одновременно воздействовать на 2 500 состояний. Таким образом, за один тик компьютерных часов квантовая операция вычисляет не одно машинное состояние, как обычные компьютеры, а 2 500 состояний сразу! Однако, в конце концов, над системой кубитов производится измерение, и система коллапсирует в единственное квантовое состояние, соответствующее единственному решению задачи, единственному набору из 500 единиц и нулей, как это диктуется измерительной аксиомой квантовой механики. Это поистине волнующий результат, поскольку это решение, найденное колективным процессом квантовых параллельных вычислений, берущим свои истоки в суперпозиции, эквивалентно выполнению той же самой операции на классическом суперкомпьютере с ~10 150 отдельных процессоров (что, конечно, невозможно)!! Первые исследователи в этой области были, конечно, вдохновлены такими гигантскими возможностями, и поэтому вскоре началась настоящая охота за подходящими задачами для такой вычислительной мощи. Питер Шор, исследователь и компьютерный ученый из компании AT&T"s Bell Laboratories в Нью Джерси, предложил такую задачу, которую можно было бы решить именно на квантовом компьютере и при помощи квантового алгоритма. Алгоритм Шора использует мощь квантовой суперпозиции, чтобы раскладывать большие числа (порядка ~10 200 двоичных разрядов и больше) на множители за несколько секунд. Эта задча имеет важное практическое применение для шифрования, где общепринятый (и лучший) алгоритм шифрования, известный как RSA, основан как раз на сложности разложения больших составных чисел на простые множители. Компьютер, который с легкостью решает такую задачу, конечно, представляет большой интерес для множества правительственных организаций, использующих RSA, который до сих пор считался "невзламываемым", и для любого кто заинтересован в безопсаности своих данных.

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

Ограниченные возможности современных компьютеров

О квантовых компьютерах и квантовых вычислениях часто говорят как об альтернативе кремниевым технологиям создания микропроцессоров, что, в общем-то, не совсем верно. Собственно, почему вообще приходится искать альтернативу современным компьютерным технологиям? Как показывает вся история существования компьютерной индустрии, вычислительная мощность процессоров возрастает экспоненциально. Ни одна другая индустрия не развивается столь бурными темпами. Как правило, когда говорят о темпах роста вычислительной мощности процессоров, вспоминают так называемый закон Гордона Мура, выведенный в апреле 1965 года, то есть всего через шесть лет после изобретения первой интегральной схемы (ИС).

По просьбе журнала «Электроникс» (“Electronics”) Гордон Мур написал статью, приуроченную к 35-й годовщине издания. Он сделал прогноз относительно того, как будут развиваться полупроводниковые устройства в течение ближайших десяти лет. Проанализировав темпы развития полупроводниковых устройств и экономические факторы за прошедшие шесть лет, то есть начиная с 1959 года, Гордон Мур предположил, что к 1975 году количество транзисторов в одной интегральной микросхеме составит 65 тыс.

Фактически по прогнозу Мура количество транзисторов в одной микросхеме за десять лет должно было увеличиться более чем в тысячу раз. В то же время это означало, что каждый год количество транзисторов в одной микросхеме должно удваиваться.

Впоследствии в закон Мура были внесены коррективы (дабы соотнести его с реальностью), но смысл от этого не поменялся: количество транзисторов в микросхемах увеличивается экспоненциально. Естественно, увеличение плотности размещения транзисторов на кристалле возможно лишь за счет сокращения размеров самих транзисторов. В связи с этим уместен вопрос: до какой степени можно уменьшать размеры транзисторов? Уже сейчас размеры отдельных элементов транзисторов в процессорах сопоставимы с атомарными, например ширина диоксидного слоя, отделяющего диэлектрик затвора от канала переноса заряда, составляет всего несколько десятков атомарных слоев. Понятно, что существует чисто физический предел, делающий невозможным дальнейшее уменьшение размеров транзисторов. Даже если предположить, что в будущем они будут иметь несколько иную геометрию и архитектуру, теоретически невозможно создать транзистор или подобный ему элемент с размером менее 10 -8 см (диаметр атома водорода) и рабочей частотой более 10 15 Гц (частота атомных переходов). А потому, хотим мы того или нет, неизбежен тот день, когда закон Мура придется сдать в архив (если, конечно, его в очередной раз не подкорректируют).

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

Как мы увидим в дальнейшем, квантовые компьютеры никоим образом не представляют собой попытку решения проблемы миниатюризации базовых элементов процессоров.

Решение проблемы миниатюризации транзисторов, поиск новых материалов для создания элементной базы микроэлектроники, поиск новых физических принципов для приборов с характерными размерами, сравнимыми с длиной волны Де-Бройля, имеющей величину порядка 20 нм, - эти вопросы стоят на повестке дня уже почти два десятилетия. В результате их решения была разработана нанотехнология. Серьезной проблемой, с которой пришлось столкнуться при переходе в область наноэлектронных устройств, является уменьшение рассеиваемой энергии в процессе вычислительных операций. Мысль о возможности «логически обратимых» операций, не сопровождающихся рассеянием энергии, впервые высказал Р.Ландауер еще в 1961 году. Существенный шаг в решении данной задачи был сделан в 1982 году Ч.Беннеттом, который теоретически доказал, что универсальный цифровой компьютер может быть построен на логически и термодинамически обратимых вентилях таким образом, что энергия будет рассеиваться только за счет необратимых периферийных процессов ввода информации в машину (приготовление исходного состояния) и соответственно вывода из нее (считывание результата). К типичным обратимым универсальным вентилям относятся вентили Фредкина и Тоффоли.

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

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

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

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

Если требуется разложить на простые множители число х , имеющее n знаков в двоичной записи, то очевидный способ решения этой задачи заключается в том, чтобы попробовать последовательно разделить его на числа от 2 до Для этого придется перебрать 2 n/2 вариантов. К примеру, если рассматривается число, у которого 100 000 знаков (в двоичной записи), то потребуется перебрать 3x10 15 051 вариантов. Если предположить, что для одного перебора требуется один процессорный такт, то при скорости в 3 ГГц для перебора всех чисел будет нужно время, превышающее возраст нашей планеты. Существует, правда, хитроумный алгоритм, решающий ту же задачу за exp(n 1/3) шагов, но даже в этом случае с задачей разложения на простые множители числа, имеющего миллион знаков, не справится ни один современный суперкомпьютер.

Задача разложения числа на простые множители относится к классу задач, которые, как говорят, не решаются за полиномиальное время (NP-полная задача - Nondeterministic polynomial-time complete). Такие задачи входят в класс невычисляемых в том смысле, что они не могут быть решены на классических компьютерах за время, полиномиально зависящее от числа битов n , представляющих задачу. Если говорить о разложении числа на простые множители, то по мере увеличения разрядности числа время, необходимое для решения задачи, возрастает экспоненциально, а не полиномиально.

Забегая вперед, отметим, что с квантовыми вычислениями связывают перспективы решения NP-полных задач за полиномиальное время.

Квантовая физика

Конечно, квантовая физика слабо связана с тем, что называют элементной базой современных компьютеров. Однако, говоря о квантовом компьютере, избежать упоминания некоторых специфических терминов квантовой физики просто невозможно. Мы понимаем, что далеко не все изучали легендарный третий том «Теоретической физики» Л.Д.Ландау и Е.М.Лифшица и для многих такие понятия, как волновая функция и уравнение Шредингера, - это что-то из потустороннего мира. Что же касается специфического математического аппарата квантовой механики, то это сплошные формулы и малопонятные слова. Поэтому мы постараемся придерживаться общедоступного уровня изложения, избегая по возможности тензорного анализа и прочей специфики квантовой механики.

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

История квантовой физики началась 14 декабря 1900 года. Именно в этот день немецкий физик и будущий нобелевский лауреат Макс Планк доложил на заседании Берлинского физического общества о фундаментальном открытии квантовых свойств теплового излучения. Так в физике появилось понятие кванта энергии, а среди других фундаментальных постоянных - постоянная Планка.

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

Уже в 1926 году Эрвин Шредингер сформулировал свое знаменитое волновое уравнение, а Энрико Ферми и Поль Дирак получили квантово-статистическое распределение для электронного газа, учитывающее заполнение отдельных квантовых состояний.

В 1928 году Феликс Блох произвел анализ квантово-механической задачи о движении электрона во внешнем периодическом поле кристаллической решетки и показал, что электронный энергетический спектр в кристаллическом твердом теле имеет зонную структуру. Фактически это стало началом нового направления в физике - теории твердого тела.

Весь XX век - это период интенсивного развития квантовой физики и всех тех разделов физики, для которых квантовая теория стала прародителем.

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

Идея использования квантовых вычислений впервые была высказана советским математиком Ю.И. Маниным в 1980 году в его знаменитой монографии «Вычислимое и невычислимое». Правда, интерес к его труду возник лишь два года спустя, в 1982 году, после опубликования статьи на ту же тему американского физика-теоретика нобелевского лауреата Ричарда Фейнмана. Он заметил, что определенные квантово-механические операции нельзя в точности переносить на классический компьютер. Это наблюдение привело его к мысли, что подобные вычисления могут быть более эффективными, если их осуществлять при помощи квантовых операций.

Рассмотрим, к примеру, квантово-механическую задачу об изменении состояния квантовой системы, состоящей из n спинов, за определенный промежуток времени. Не вникая в подробности математического аппарата квантовой теории, отметим, что общее состояние системы из n спинов описывается вектором в 2 n -мерном комплексном пространстве, а изменение ее состояния - унитарной матрицей размером 2 n x2 n . Если рассматриваемый промежуток времени очень мал, то матрица устроена очень просто и каждый из ее элементов легко вычислить, зная взаимодействие между спинами. Если же необходимо узнать изменение состояния системы за большой промежуток времени, то нужно перемножать такие матрицы, причем для этого требуется экспоненциально большое количество операций. Опять мы сталкиваемся с PN-полной задачей, нерешаемой за полиномиальное время на классических компьютерах. В настоящее время способа упростить данное вычисление не существует, и, скорее всего, моделирование квантовой механики является экспоненциально сложной математической задачей. Но если классические компьютеры не способны решать квантовые задачи, то, возможно, для этого целесообразно использовать саму квантовую систему? И если это действительно возможно, то подходят ли квантовые системы для решения других вычислительных задач? Подобные вопросы как раз и рассматривались Фейнманом и Маниным.

Уже в 1985 году Дэвид Дойч предложил конкретную математическую модель квантовой машины.

Однако вплоть до середины 90-х годов направление квантовых вычислений развивалось довольно вяло. Практическая реализация квантовых компьютеров оказалась весьма сложной. К тому же в научном сообществе с пессимизмом относились к тому, что квантовые операции способны ускорить решение определенных вычислительных задач. Так продолжалось вплоть до 1994 года, когда американский математик Питер Шор предложил для квантового компьютера алгоритм разложения n -значного числа на простые множители за время, полиномиально зависящее от n (квантовый алгоритм факторизации). Квантовый алгоритм факторизации Шора стал одним из основных факторов, приведших к интенсивному развитию квантовых методов вычислений и появлению алгоритмов, позволяющих решать некоторые NP-проблемы.

Естественно, возникает вопрос: почему, собственно, предложенный Шором квантовый алгоритм факторизации привел к таким последствиям? Дело в том, что задача разложения числа на простые множители имеет прямое отношение к криптографии, в частности к популярным системам шифрования RSA. Благодаря возможности разложения числа на простые множители за полиномиальное время квантовый компьютер теоретически позволяет расшифровывать сообщения, закодированные при помощи многих популярных криптографических алгоритмов, таких как RSA. До сих пор этот алгоритм считался сравнительно надежным, так как эффективный способ разложения чисел на простые множители для классического компьютера в настоящее время неизвестен. Шор придумал квантовый алгоритм, позволяющий разложить на простые множители n -значное число за n 3 (log n ) k шагов (k = const ). Естественно, практическая реализация такого алгоритма могла иметь скорее негативные, чем позитивные последствия, поскольку позволяла подбирать ключи к шифрам, подделывать электронные подписи и т.п. Впрочем, до практической реализации настоящего квантового компьютера еще далеко, а потому в течение ближайших десяти лет можно не опасаться, что шифры могут быть взломаны с помощью квантовых компьютеров.

Идея квантовых вычислений

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

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

Данные обозначения (бра/кэт-обозначения) были введены Дираком и имеют строго математическое определение (векторы базисных состояний), которое обусловливает правила работы с ними, однако, дабы не углубляться в математические дебри, мы не станем детально рассматривать эти тонкости.

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

Теперь обобщим пример с поляризацией фотона на любую двухуровневую квантовую систему.

Предположим, имеется произвольная двухуровневая квантовая система, которая характеризуется базисными ортогональными состояниями |1 и |0. Согласно законам (постулатам) квантовой механики (принцип суперпозиции) возможными состояниями квантовой системы будут также суперпозиции y = a|1+b|0, где a и b - комплексные числа, называемые амплитудами. Отметим, что аналога состояния суперпозиции в классической физике не существует.

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

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

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

Итак, чтобы измерить квантовую систему, необходимо каким-то образом подействовать на нее классическим объектом, после чего ее первоначальное состояние будет нарушено. Кроме того, можно утверждать, что в результате измерения квантовая система будет переведена в одно из своих базисных состояний. К примеру, для измерения двухуровневой квантовой системы требуется как минимум двухуровневый классический объект, то есть классический объект, который может принимать два возможных значения: 0 и 1. В процессе измерения состояние квантовой системы будет преобразовано в один из базисных векторов, причем если при измерении классический объект принимает значение равное 0, то квантовый объект преобразуется к состоянию |0, а в случае если классический объект принимает значение равное 1, то квантовый объект преобразуется к состоянию |1.

Таким образом, хотя квантовая двухуровневая система может находиться в бесчисленном множестве состояний суперпозиции, но в результате измерения она принимает только одно из двух возможных базисных состояний. Квадрат модуля амплитуды |a| 2 определяет вероятность обнаружения (измерения) системы в базисном состоянии |1, а квадрат модуля амплитуды |b| 2 - в базисном состоянии |0.

Однако вернемся к нашему примеру с поляризованным фотоном. Для измерения состояния фотона (его поляризации) нам потребуется некоторое классическое устройство с классическим базисом {1,0}. Тогда состояние поляризации фотона a|1+b|0 будет определено как 1 (горизонтальная поляризация) с вероятностью |a| 2 и как 0 (вертикальная поляризация) с вероятностью |b| 2 .

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

Вектор состояния двухуровневой квантовой системы называется также волновой функцией квантовых состояний y двухуровневой системы, или, в интерпретации квантовых вычислений, кубитом (quantum bit, qubit). В отличие от классического бита, который может принимать только два логических значения, кубит - это квантовый объект, и число его состояний, определяемых суперпозицией, неограниченно. Однако еще раз подчеркнем, что результат измерения кубита всегда приводит нас к одному из двух возможных значений.

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

В общем случае если квантовая система состоит из L кубитов, то у нее имеется 2 L возможных классических состояний, каждое из которых может быть измерено с некоторой вероятностью. Функция состояния такой квантовой системы запишется в виде:

где |n - базисные квантовые состояния (например, состояние |001101, а |c n | 2 - вероятность нахождения в базисном состоянии |n .

Для того чтобы изменить состояние суперпозиции квантовой системы, необходимо реализовать селективное внешнее воздействие на каждый кубит. С математической точки зрения такое преобразование представляется унитарными матрицами размера 2 L x2 L . В результате будет получено новое квантовое состояние суперпозиции.

Структура квантового компьютера

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

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

Квантовый регистр представляет собой совокупность некоторого числа L кубитов. До ввода информации в компьютер все кубиты квантового регистра должны быть приведены в базисные состояния |0. Эта операция называется подготовкой, или инициализацией. Далее определенные кубиты (не все) подвергаются селективному внешнему воздействию (например, с помощью импульсов внешнего электромагнитного поля, управляемых классическим компьютером), которое изменяет значение кубитов, то есть из состояния |0 они переходят в состояние |1. При этом состояние всего квантового регистра перейдет в суперпозицию базисных состояний |n с, то есть состояние квантового регистра в начальный момент времени будет определяться функцией:

Понятно, что данное состояние суперпозиции можно использовать для бинарного (двоичного) представления числа n .

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

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

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

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

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

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

физическая система, представляющая собой полномасштабный квантовый компьютер, должна содержать достаточно большое число L >103 хорошо различимых кубитов для выполнения соответствующих квантовых операций;
необходимо обеспечить максимальное подавление эффектов разрушения суперпозиции квантовых состояний, обусловленных взаимодействием системы кубитов с окружающей средой, в результате чего может стать невозможным выполнение квантовых алгоритмов. Время разрушения суперпозиции квантовых состояний (время декогерентизации) должно по крайней мере в 104 раз превышать время выполнения основных квантовых операций (время такта). Для этого система кубитов должна быть довольно слабо связана с окружением;
необходимо обеспечить измерение с достаточно высокой надежностью состояния квантовой системы на выходе. Измерение конечного квантового состояния является одной из основных проблем квантовых вычислений.

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

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

На данный момент наибольший квантовый компьютер составлен всего из семи кубитов. Этого достаточно, чтобы реализовать алгоритм Шора и разложить число 15 на простые множители 3 и 5.

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

В ЯМР-спектрометре спины ядер исследуемой молекулы образуют кубиты. Каждое ядро имеет свою частоту резонанса в данном магнитном поле. При воздействии импульсом на ядро на его резонансной частоте оно начинает эволюционировать, остальные же ядра не испытывают никакого воздействия. Для того чтобы заставить эволюционировать другое ядро, нужно взять иную резонансную частоту и дать импульс на ней. Таким образом, импульсное воздействие на ядра на резонансной частоте представляет собой селективное воздействие на кубиты. При этом в молекуле есть прямая связь между спинами, поэтому она является идеальной заготовкой для квантового компьютера, а сам спектрометр представляет собой квантовый процессор.

Первые эксперименты на ядерных спинах двух атомов водорода в молекулах 2,3-дибромотиофена SCH:(CBr) 2:CH и на трех ядерных спинах - одном в атоме водорода H и двух в изотопах углерода 13 C в молекулах трихлорэтилена CCl 2:CHCl - были поставлены в 1997 году в Оксфорде (Великобритания).

В случае использования ЯМР-спектрометра важно, что для селективного воздействия на ядерные спины молекулы необходимо, чтобы они заметно различались по резонансным частотам. Позднее были осуществлены квантовые операции в ЯМР-спектрометре с числом кубитов 3, 5, 6 и 7.

Главным преимуществом ЯМР-спектрометра является то, что в нем можно использовать огромное количество одинаковых молекул. При этом каждая молекула (точнее, ядра атомов, из которых она состоит) представляет собой квантовую систему. Последовательности радиочастотных импульсов, выполняющие роль определенных квантовых логических вентилей, осуществляют унитарные преобразования состояний соответствующих ядерных спинов одновременно для всех молекул. То есть селективное воздействие на отдельный кубит заменяется одновременным обращением к соответствующим кубитам во всех молекулах большого ансамбля. Компьютер такого рода получил название ансамблевого (bulk-ensemble quantum computer) ЯМР квантового компьютера. Такие компьютеры могут работать при комнатной температуре, а время декогерентизации квантовых состояний ядерных спинов составляет несколько секунд.

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

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

Другое ограничение ЯМР квантовых компьютеров связано с тем, что измеряемый на выходе системы сигнал экспоненциально убывает с ростом числа кубитов L . Кроме того, число ядерных кубитов в отдельной молекуле с сильно различающимися резонансными частотами ограничено. Это приводит к тому, что ЯМР квантовые компьютеры не могут иметь больше десяти кубитов. Их следует рассматривать лишь как прототипы будущих квантовых компьютеров, полезные для отработки принципов квантовых вычислений и проверки квантовых алгоритмов.

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

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