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

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

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

Реферат

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

Введение

Глава 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

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

Квантовые вычисления немыслимы без контроля над квантовым состоянием отдельных элементарных частиц. Двум физикам - французу Сержу Лрошу и американцу Дэвиду Вайнленду - это удалось. Лрош ловил в резонатор одиночные фотоны и надолго «отцеплял» их от внешнего мира. Вайнленд собирал в ловушку одиночные ионы с опреденными квантовыми состояниями и изолировал их от внешнего воздействия. Арош использовал атомы, чтобы наблюдать за состоянием фотона. Вайнленд применял фотоны, чтобы изменять состояния ионов. Им удалось продвинуться в изучении взаимоотношения квантового и классического миров. В 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" базовых состояний одновременно. Теоретически новая схема может работать в экспоненциальное число раз быстрее классической. Практически квантовый алгоритм поиска в базе данных показывает квадратичный прирост мощности против классических алгоритмов.

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

Под квантовой запутанностью, которую называют также «квантовой суперпозицией» , обычно понимается следующее: "Вообразите атом, который мог бы подвергнуться радиоактивному распаду в определенный промежуток времени. Или не мог бы. Мы можем ожидать, что у этого атома есть только два возможных состояния: «распад» и «не распад», /…/ но в квантовой механике у атома может быть некое объединенное состояние - «распада - не распада», то есть ни то, ни другое, а как бы между. Вот это состояние и называется «суперпозицией» .

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

Теория

Кубиты

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

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

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

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

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

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

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

Вычисление

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

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

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

Чем же квантовый компьютер лучше классического? Большая часть современных ЭВМ работают по такой же схеме: n бит памяти хранят состояние и каждый такт времени изменяются процессором. В квантовом случае система из n кубитов находится в состоянии, являющимся суперпозицией всех базовых состояний, поэтому изменение системы касается всех 2 n базовых состояний одновременно. Теоретически новая схема может работать намного (в экспоненциальное число раз) быстрее классической. Практически (квантовый) алгоритм Гровера поиска в базе данных показывает квадратичный прирост мощности против классических алгоритмов. Пока в природе их не существует.

Алгоритмы

Было показано, что не для всякого алгоритма возможно «квантовое ускорение».

Квантовая телепортация

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

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

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

Специфика применения

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

Основные проблемы, связанные с созданием и применением квантовых компьютеров:

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

Приложения к криптографии

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

Реализации

Канадская компания D-Wave заявила в феврале 2007 года о создании образца квантового компьютера, состоящего из 16 кубит (устройство получило название Orion). Однако информация об этом устройстве не отвечала строгим требованиям точного научного сообщения; новость не получила научного признания. Более того, дальнейшие планы компании (создать уже в ближайшем будущем 1024-кубитный компьютер) вызвали скепсис у членов экспертного сообщества .

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

В декабре 2008 года компания организовала проект Распределенных вычислений AQUA@home(A diabatic QU antum A lgorithms) , в котором тестируются алгоритмы, оптимизирующие вычисления на адиабатических сверхпроводящих квантовых компьютерах D-Wave.

См. также

Примечания

Литература

• Kilin S.Ya. Quanta and information / Progress in optics. - 2001. - Vol. 42. - P. 1-90.
• Килин С. Я. Квантовая информация / Успехи Физических Наук. - 1999. - Т. 169. - C. 507-527.
• Квантовые вычисления за и против. Под ред. Садовничего В. А.
• Квантовый компьютер и квантовые вычисления. Под ред. Садовничего В. А.
• Валиев К. А., Кокин А. А. Квантовые компьютеры: надежды и реальность. Москва, Ижевск: Регулярная и хаотическая динамика, 2004. 320 с. ISBN 5-93972-024-2

Ссылки

• Квантовый компьютер и его полупроводниковая элементарная база
• Китаев,А., Шень, А., Вялый, М. Классические и квантовые вычисления
• QWiki (англ.) и Quantiki (англ.) - Wiki-ресурсы по квантовой информатике
• Язык программирования QCL для квантовых компьютеров (англ.)
• Курс «Современные задачи теоретической информатики » (лекции по квантовым вычислениям: введение, суперплотное кодирование, квантовая телепортация, алгоритмы Саймона и Шора)
• InFuture.ru: Будущее квантовых компьютеров - в троичных вычислениях
• Валиев К. А. «Квантовые компьютеры и квантовые вычисления» УФН 175 3 (2005)

Wikimedia Foundation . 2010 .

• Квантоворазмерный эффект
• Квантовые размерные эффекты

Смотреть что такое "Квантовые вычисления" в других словарях:

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

ТОПОЛОГИЧЕСКИЕ КВАНТОВЫЕ ТЕОРИИ ПОЛЯ - квантовомеханич. или квантовополевые теории, все корреляционные функции в к рых не зависят от выбора координат и метрики как в пространстве времени, так и в др. пространствах, участвующих в определении теории. Это позволяет использовать… … Физическая энциклопедия

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

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

Классические вычисления: AND, OR, NOT

Чтобы разобраться с квантовыми вычислениями, стоит для начала освежить знания о классических. Здесь единицей обрабатываемой информации является бит. Каждый бит может находиться только в одном из двух возможных состояний – 0 или 1. Регистр из N бит может содержать одну из 2 N возможных комбинаций состояний и представляется в виде их последовательности.

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

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

Квантовые вычисления. Физическая основа

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

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

Кубиты

В квантовых вычислениях физические свойства квантовых объектов реализованы в так называемых кубитах (q-bit). Классический бит может находиться только в одном состоянии – 0 или 1. Кубит до измерения может находиться одновременно в обоих состояниях, поэтому его принято обозначать выражением a|0⟩ + b|1⟩, где A и B - комплексные числа, удовлетворяющие условию |A| 2 +|B| 2 =1. Измерение кубита мгновенно «схлопывает» его состояние в одно из базисных – 0 или 1. При этом «облако» коллапсирует в точку, первоначальное состояние разрушается, и вся информация о нем безвозвратно теряется.

Одно из применений этого свойства – кот Шредингера генератор истинно случайных чисел. Кубит вводится в такое состояние, при котором результатом измерения могут быть 1 или 0 с одинаковой вероятностью. Это состояние описывается так:

Квантовые и классические вычисления. Первый раунд

Начнем с основ. Имеется набор исходных данных для вычислений, представленный в двоичном формате векторами длиной N.

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

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

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

Рассмотрим реальную задачу. Нужно определить, эквивалентны ли два бита.

Если при классических вычислениях на выходе получаем единицу, значит эквивалентны, иначе нет:

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

В примере мы сравниваем значения первого и второго кубитов. Результат будет в нулевом кубите - кубите-флаге. Данный алгоритм применим только к базовым состояниям – 0 или 1. Вот порядок квантовых преобразований.

1. Воздействуем на кубит-флаг гейтом «Не», выставляя его в 1.
2. Два раза применяем двухкубитный гейт «Контролируемое Не». Этот гейт меняет значение кубита-флага на противоположное только в случае, если второй кубит, участвующий в преобразовании, находится в состоянии 1.
3. Измеряем нулевой кубит. Если в результате получили 1, значит и первый, и второй кубиты либо оба в состоянии 1 (кубит-флаг два раза поменял свое значение), либо в состоянии 0 (кубит-флаг так и остался в состоянии 1). Иначе кубиты находятся в разных состояниях.

Следующий уровень. Квантовые однокубитные гейты Паули

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

В квантовых вычислениях обрабатываемая информация закодирована в квантовых битах – так называемых кубитах. В простейшем случае кубит, как и классический бит, может находиться в одном из двух базисных состояний: |0⟩ (краткое обозначение для вектора 1|0⟩ + 0|1⟩) и |1⟩ (для вектора 0|0⟩ + 1|1⟩). Квантовый регистр представляет собой тензорное произведение векторов кубит. В простейшем случае, когда каждый кубит находится в одном из базисных состояний, квантовый регистр эквивалентен классическому. Регистр из двух кубит, находящихся в состоянии |0>, можно расписать в таком виде:

(1|0⟩ + 0|1⟩)*(1|0⟩ + 0|1⟩) = 1|00⟩ + 0|01⟩ + 0|10⟩ + 0|11⟩ = |00⟩.

Для обработки и преобразования информации в квантовых алгоритмах используются так называемые квантовые вентили (гейты). Они представляются в виде матрицы. Для получения результата применения гейта, нам необходимо умножить вектор, характеризующий кубит, на матрицу гейта. Первая координата вектора – множитель перед |0⟩, вторая координата – множитель перед |1⟩. Матрицы основных однокубитных гейтов выглядит так:

А вот пример применения гейта Not:

X * |0⟩ = X * (1|0⟩ + 0|1⟩) = 0|0⟩ + 1|1⟩ = |1⟩

Множители перед базисными состояниями называются амплитудами и являются комплексными числами. Модуль комплексного числа равен корню из суммы квадратов действительной и мнимой частей. Квадрат модуля амплитуды, стоящей перед базисным состоянием, равен вероятности получить это базисное состояние при измерении кубита, поэтому сумма квадратов модулей амплитуд всегда равна 1. Мы могли бы использовать произвольные матрицы для преобразований над кубитами, но из-за того, что норма (длина) вектора всегда должна быть равна 1 (сумма вероятностей всех исходов всегда равна 1), наше преобразование должно сохранять норму вектора. Значит преобразование должно быть унитарным и соответствующая ему матрица унитарной. Напомним, что унитарное преобразование обратимо и UU † =I.

Для более наглядной работы с кубитами их изображают векторами на сфере Блоха. В такой интерпретации однокубитные гейты представляют собой вращение вектора кубита вокруг одной из осей. Например гейт Not (X) поворачивает вектор кубита на Pi относительно оси X. Таким образом, состояние |0>, представляемое вектором, направленным строго вверх, переходит в состояние |1>, направленное строго вниз. Состояние кубита на сфере Блоха определяется формулой cos(θ/2)|0⟩+e iϕ sin(θ/2)|1⟩

Квантовые двухкубитные гейты

Для построения алгоритмов нам недостаточно только однокубитных гейтов. Необходимы гейты, которые осуществляют преобразования в зависимости от некоторых условий. Основным таким инструментом является двухкубитный гейт CNOT. Этот гейт применяется к двум кубитам и инвертирует второй кубит только в том случае, если первый кубит находится в состоянии |1⟩. Матрица гейта CNOT выглядит так:

А вот пример применения:

CNOT *|10⟩ = CNOT * (0|00⟩ + 0|01⟩ + 1|10⟩ + 0|11⟩) = 0|00⟩ + 0|01⟩ + 1|11⟩ + 0|10⟩ = |11⟩

Применение гейта CNOT эквивалентно выполнению классической операции XOR с записью результата во второй кубит. Действительно, если посмотреть на таблицу истинности оператора XOR и CNOT, то увидим соответствие:

XOR			CNOT
0	0	0	00	00
0	1	1	01	01
1	0	1	10	11
1	1	0	11	10

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

Построение алгоритма - классическая и квантовая реализация

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

Пример применения гейта CNOT:

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

Итак, попробуем построить классический и квантовый алгоритм, который прибавляет 3 к аргументу.

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

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

Arg = #задаем аргумент result = #инициализируем результат carry1 = arg & 0x1 #складываем с 0b11, так что перенос от младшего бита появится в том случае, если у агрумента младший бит = 1 result = arg ^ 0x1 #складываем младшие биты carry2 = carry1 | arg #складываем с 0b11, так что перенос от старшего бита появится в том случае, если у агрумента старший бит = 1 или был перенос с младшего бита result = arg ^ 0x1 #складываем старшие биты result ^= carry1 #применяем перенос с младшего бита result ^= carry2 #применяем перенос со старшего бита print(result)
Теперь попробуем разработать аналогичную программу для квантового вычислителя:

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

1. Первым шагом до барьера мы выставляем аргумент в то же состояние, как и в классическом случае – 0b11.
2. С помощью оператора CNOT вычисляем значение первого переноса – результат операции arg & 1 равен единице только тогда, когда arg равен 1, в этом случае мы инвертируем второй кубит.
3. Следующие 2 гейта реализуют сложение младших бит – мы переводим кубит 4 в состояние |1⟩ и результат XOR записываем в него же.
4. Большим прямоугольником обозначен гейт CCNOT – расширение гейта CNOT. В этом гейте два управляющих кубита и третий инвертируется только в том случае, если первые два находятся в состоянии |1. Комбинация из 2 гейт CNOT и одного CCNOT дает нам результат классической операции carry2 = carry1 | arg. Первые 2 гейта выставляют перенос в единицу в том случае, если один из них равен 1, а гейт CCNOT обрабатывает случай, когда они оба равны единице.
5. Складываем старшие кубиты и кубиты переноса.

Промежуточные выводы

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

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

По материалам