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

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

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

федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«Национальный исследовательский ядерный университет «МИФИ»

ФАКУЛЬТЕТ КИБЕРНЕТИКИ И ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ

КАФЕДРА УПРАВЛЯЮЩИХ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ (№ 29)

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

на курсовую учебно-исследовательскую работу

Тема: Специальные алгоритмы (квантовый алгоритм Гровера)

Ермошин Кирилл Дмитриевич

Москва, 2014



СОДЕРЖАНИЕ

ВВДЕНИЕ

1. ОБЩИЕ ПОЛОЖЕНИЯ

1.1 Общая характеристика квантового компьютера

1.2 Основные математические понятия квантовой механики

1.3 Понятие кубита, базиса и гейта

1.4 Квантовая система, ее преобразование, запутанное состояние

Выводы

2. АЛГОРИТМ РАБОТЫ ГРОВЕРА

2.1 Алгоритм поиска

2.2 Квантовые оракул и преобразование фазы

2.3 Оператор инверсии относительно среднего

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

2.5 Многократное применение алгоритма Гровера

2.6 Реализация программы

Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ВВЕДЕНИЕ

Алгоритм -- это точное и понятное предписание для исполнителя, о совершении последовательности действий, направленных на решение поставленной задачи. Слово «алгоритм» происходит от имени математика Аль Хорезми, который сформулировал правила выполнения арифметических действий [2].

Ранее часто писали «алгорифм», сейчас такое написание используется редко, но, тем не менее, имеет место.

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

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

В первой половине 20 века родился новый раздел физики -- квантовая механика.

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

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

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

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

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



1. ОБЩИЕ ПОЛОЖЕНИЯ

1.1 Общая характеристика квантового компьютера

Идея создания компьютера, работающего по законам микромира, была предложена математиком Ю.И. Маниным в 1980 году. Согласно этим законам частица может находиться сразу в двух состояниях (принцип суперпозиции), соответственно и в квантовом компьютере информация будет храниться не в привычных нам битах в виде нуля или единицы, а в кубитах, которые являются одновременно нулем и единицей [4].

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

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

Базой для вычислений служит кубит. На практике кубит может существовать в самых разных комбинациях этих значений, что в перспективе позволит создавать сверхбыстродействующие компьютеры. Кубиты станут строительными элементами будущих квантовых компьютеров, способных решать задачи, практически недоступные классическим цифровым компьютерам. Для выполнения вычислений на квантовом компьютере необходимо привести во взаимодействие несколько кубитов, причем таким образом, чтобы они образовали единую квантовую систему. Затем этой системе надо позволить развиваться по законам квантовой механики и спустя определенное время выяснить, в какое состояние она пришла. С ростом числа объединенных кубитов, вычислительная мощность такой квантовой системы экспоненциально растет [3]. Объединение кубитов есть не что иное, как квантовый регистр -- аналог обычного регистра в классическом компьютере.

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

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

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

Действительно важный шаг для создания квантового компьютера был сделан Сержом Арошом и Дэвидом Дж. Винландом, за что они и были удостоены Нобелевской премии по физике в 2012 году. Серж Арош и его коллеги разработали эксперимент по изучению квантовой механики микроволнового света в ловушке между двумя зеркалами -- резонаторами. Экспериментатор, Дэвид Винланд стал первым, кто использовал электромагнитные устройства, известные как ловушки Пола, для захвата ионов. Напомним, что если у атома результирующий заряд в |e| не равен нулю, то это ион.

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

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

Уже тогда (в 2012 году) осуществлена передача информации (квантового состояния) между 14 ионами, заключенными в ловушку, представленную Винландом.

В этом же году компанией IBM представлена чип с тремя кубитами.

Рис 1.1. Фотография кремниевого чипа, содержащего три кубита. Чип соединяется с вводом/выводом коаксиальными проводниками (масштаб: 8х4 мм). Источник: computerworld.com

На июль 2013 года, даже пока еще не очень совершенные квантовые вычислительные системы, пользуются огромным интересом у ведущих мировых компаний. D-Wave не является универсальным квантовым компьютером, хотя и может быть использован в качестве основы для его разработки. D-Wave -- это 512-кубитная вычислительная машина на сверхпроводящих кольцах, предназначенная для решения так называемых задач комбинаторной оптимизации, например анализа генома, вариантов сворачивания белков и т.п. Google будет использовать D-Wave для проектирования систем искусственного интеллекта, способного к самообучению.

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

1.2 Основные математические понятия квантовой механики

Рассмотрим состояние микроскопической системы (например фотона) как определенный вектор, который мы обозначим А, лежащий в определенном векторном пространстве (такое пространство называется Гильбертовым), причем другие элементы пространства представляют все другие возможные состояния системы. Такое пространство называется кэт--пространством (по предложению Дирака).

Также его можно представить как вектор -- столбец.

Под количеством состояний квантовой системы подразумевают количество линейно независимых состояний (не выражаются друг через друга). В свою очередь их количество является размерностью Гильбертово пространства.

Можно представить себе абстрактный автомат, который принимает на входе

кэт--векторы и детерминированным образом (то есть результат предопределен) выдает на выходе комплексные числа. Такую машину называют функционалом

?F| (|А? ) = ?_A

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

Бра--пространство есть пример того, что математики называют дуальным векторным пространством (т. е. дуальным к исходному кэт--пространству). Между элементами кэт--пространства и соответствующими элементами бра--пространства существует взаимно однозначное соответствие.

|А? <ДС> ?A|,

где ДС означает дуальное соответствие.

Произведение ?B|A? принято называть внутренним произведением бра и кэт. Внутреннее произведение практически совпадает со скалярным произведением векторов в некотором криволинейном пространстве.

Следую из этого можно говорить об ортогональности и о коллинеарности |А? и |B?

?A|B?=0 (ортогональны)

?A|B?=1 (коллинеарны)

?A|A?=1

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

Каждый линейный оператор U, действующий в d--мерном пространстве может быть представлен d Ч d матрицей.

Стоит отметить, что в общем случае умножение оператора на оператор некоммутативно.

Рассмотрим внутреннее произведение произвольного бра--вектора ?B| и кэт--вектора X |А?. Это не что иное, как внутренне произведение бра--вектора на кэт--вектор, получившийся путем действия на |А? оператора X. По соглашению тройное произведение ?B|, X и |А? можно записать:

?B|X|А?

Рассмотрим дуальный бра-вектор к X |А?. Этот бра-вектор антилинейно зависит от |А? и поэтому должен линейно зависеть от ?A|. Следовательно, этот вектор следует рассматривать как результат применения к ?A| некоторого линейного оператора. Этот оператор называют сопряженным к X и обозначают X^† . Таким образом, выполняется следующее. Если , то .

Оператор U является унитарным, если

UU ^†=I,

где I -- единичная матрица.

Возьмем внешнее произведение |А? на ?B|. Умножим это произведение справа на |С?. Тогда в силу коммутативности произведения кэт--вектора на число получаем:

|B??A|С?=?A|С?|B?

Таким образом, |А??B|, действуя на произвольный кэт--вектор |С?, приводит к другому кэт--вектору. Следовательно, внешнее произведение является оператором.

Существуют специальные кэт--векторы, которые называются собственными векторами оператора Х. Они обозначаются

|ч'?, |ч''?, |ч'''?, …

и обладают свойством

X |ч'? = ч'|ч'?, X |ч''? = ч''|ч''?, …

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

Если оператор о сопряжен самому себе, то такой оператор называется эрмитовым.

о =о ^†

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

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

2. Собственные значения, связанные с собственными кэт--векторами, совпадают с собственными значениями, связанными с собственными бра--векторами.

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

Предположим, что динамические переменные микроскопической системы (координата, импульс, спин и прочее) представляются линейными операторами.

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

Теперь под неким оператором X можно будет подразумевать динамическую переменную, а под кэт--вектором некоторое состояние.

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

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

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

1.3 Понятие кубита, базиса и гейта

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

Рассмотрим ситуацию, когда для записи одного бита информации используются два квантовых состояния какой-либо простой квантовой системы. Такую систему называют кубитом. Эти два состояния образуют полный набор базисных состояний, а значит, образуют двумерное гильбертово пространство. Два состояния образуют так называемый вычислительный базис, и обозначаются так: |0? и |1?.

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

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

|Ш?=a|0?+b|1?(1.1)

При этом если провести измерения в вычислительном базисе |0? или |1?, то вероятность появления состояний |0? и |1? есть соответственно |a|² и |b|².

Умножив выражение (1.1) на ?0| получим:

?0|Ш?=a?0|0?+b?0|1? => a=?0|Ш?

Аналогично: b =?1|Ш?

Это есть не что иное, как “проекция” вектора |Ш? на базисные состояния. То есть, вероятность появления некоторого состояние -- это проекция суперпозиции на выбранный нами вектор.

Базисным состояниям соответствуют вектор--столбцы вида

В квантовых вычислениях важную роль играет преобразование Адамара (его также называют преобразованием Уолша--Адамара). Операторная и матричная форма выглядит так

Если подействовать этим преобразованием на базисное состояние |0?, то в результате получится состояние однородной суперпозиции 0 и 1.

Также существует гейт NOT, который по аналогии с классической логической функцией НЕ меняет состояние на противоположное.

и сдвига фазы

Забегая вперед, отметим, что нас будут интересовать повороты либо на , либо которые вообще будут оставлять состояние неизменным. В любом случае, при разложении экспоненты по формуле Эйлера, комплексная составляющая будет равна нулю (). Помимо этого, cos и sin будут принимать только действительные значения.

1.4 Квантовая система, ее преобразование, запутанное состояние

Стоит начать с определения тензорного произведения векторов a=(a₁…a_n) и b=(b₁…b_m). Это такой вектор, для которого выполняется следующее условие:

a?b = (a₁b₁…a₁b_m , … , a₁b_m… a_nb_m )

Тензорно произведение для матриц A, B вычисляется следующим образом

Квантовая система из n кубитов описывается так

Легко заметить, что n кубитов находятся в суперпозиции 2ⁿ состояний. Каждое из них описывает одно из возможных устойчивых состояний со своей |z_i|² вероятностью при проекции на базисные состояния.

Эволюция квантовой системы, т.е. как она изменяется за определенный промежуток времени, задается унитарным оператором. Если текущее состояние |Ш?, то на следующем шаге оно будет таким |Ш'?=U |Ш?, где U -- унитарная матрица d Ч d.

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

Унитарное преобразование не меняет длины преобразуемого вектора, при этом длина вектора состояний |Ш? итак всегда равна единице, из чего следует, что любое квантовое преобразование можно трактовать как поворот вектора |Ш? на единичной сфере (поскольку все длины равны единице, то в совокупности они образуют сферу) в гильбертовом пространстве с размерностью 2ⁿ.

Состояние называется запутанным, если измерение одного из кубитов оказывает влияние на измерение состояния другого. В противном случае, состояние называется разложенным.



Выводы

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

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

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

Как преобразования, так и вектора можно представить в операторной и матричной форме.



2. АЛГОРИТМ ГРОВЕРА

2.1 Алгоритм поиска

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

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

Вероятность нахождение нужного нам элемента на первом шаге есть W₁=1/N. Вероятность найти его на втором шаге равна произведению вероятности отрицательного исхода первого шага 1-W₁ и вероятности удачного исхода второго шага 1/(N-1), следовательно, W₂=1/N. Далее процесс аналогичен и из этого вытекает, что общая формула для вероятности найти искомый элемент ровно на S-ом шаге есть Ws = 1/N. Среднее число шагов есть

Вынося за знак суммы и переходя к сумме первых N членов арифметической прогрессии, приходим к

В пределе при N>>1 получаем, что надо перебрать в среднем, приблизительно половину элементов базы.

В 1996 г. Лов Гровер показал, что если заняться поиском, воспользовавшись сформулированным им алгоритмом, то время поиска сокращается до величины, пропорциональной , т.е. до корневой зависимости от размеров базы. При больших N разница в скорости поиска оказывается весьма ощутимым.

2.2 Квантовый оракул и преобразование фазы

Предположим, что мы имеем некоторую неупорядоченную базу данных. Запись каждого элемента этой базы идентифицируется числом x, которое может принимать значения от 0 до N-1, где N = 2ⁿ. Задача состоит в том, чтобы найти запись, у которой x равно интересующему нас значению щ. Для простоты полагаем, что существует только одна такая запись. Введем функцию

f_щ(x)=

Вычислением этой функции занимается «оракул». На вход оракула подается значение x, а он выдает 0 или 1. Нам надо как можно быстрей получить то значение x, при котором f_щ(x)=1.

Сам квантовый оракул описывается некоторым унитарным оператором . Этот оператор действует в пространстве состояний |x?|y? системы, состоящий из n+1 кубитов. К изначально цепочке, содержащей все исходные состояния, добавлен вспомогательный кубит |y?.

Действуя на базисное состояние |x?|y?, оператор вычисляет функцию f_щ(x) и получившиеся значение логически складывает (сложение по модулю 2) с y .

Получим исходное состояние вспомогательного кубита |y?, подействовав на |0? гейтом NOT, что приведет к |1?,

Рассмотрим действие оракула на состояние |x?|y?:

Действительно, если подставить f_щ(x)=1 (при x =), и f_щ(x)=0 (при x), то равенство окажется верным. Если проанализировать это уравнение, то видно, что вспомогательный кубит |y? остался без изменений, а значит преобразование на него никак не влияет и его можно “выкинуть”.

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

Предположим, что унитарный оператор можно представить так:

(2.1)

где -- состояние, которое мы ищем.

Тогда, действуя им на произвольное состояние, получим (принимая во внимание, что одно из N значений x равно )

(2.2)

Что прекрасно согласуется с нашими выводами.

Дадим геометрическую интерпретацию унитарного преобразования .

Пусть

(2.4)

Также введем кэт--вектор

Этот вектор удовлетворяет следующим условиям

?Щ|щ?=0 и ?Щ|Щ?=?щ|щ?=1

Корень в знаменателе является постоянной величиной и на него можно домножить левую и правую часть. Затем подставляем получившиеся уравнение в (2.2) и в (2.3), получаем

Представим и как “орты” двумерной системы координат, изобразив на ней векторы (вектор какого--то произвольного состояния) и (вектор, на который подействано преобразованием (2.1)).

Рис 2.2. График, характеризующий действие преобразования

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

2.3 Оператор инверсии относительно среднего

Для начала приготовим входной регистр. Применим преобразование Адомара n раз к n кубитовому состоянию |00…0? (в конце учитываем, что )

Видим, что это выражение представляет все базисные векторы с одинаковыми амплитудами и фазами.

Из (2.4) следуют, что

В суперпозиции (2.4) все состояния представлены с равносильными вероятностями, равными 1/N.

(2.5)

Подействуем им на состояние (2.2)

Подставляем сюда выражение для , выносим за скобки, обобщаем сумму и получаем

(2.6)

где -- это среднее значение амплитуды вероятности, с которой представлено в .

Положим некоторым малым отклонением от среднего в исходном состоянии, тогда

Из этого следует, что после преобразования для всех амплитуд вероятности отклонение от среднего меняется на противоположное (подставляем (2.7) в (2.6)):

Поэтому называется оператором инверсии относительно среднего.



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

Отыскание нужно нам состояния |щ? заключается в последовательном применении унитарного оператора

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

С учетом того, что действие оператора меняет фазу одного единственного искомого состояния, можно говорить о том, что после его действия средняя амплитуда уменьшилась.

Затем подействуем оператором , т.е. инвертирую относительно среднего значения , получим, что амплитуда состояния равна

То есть искомая амплитуда становится больше. Таким образом, применение оператора к начальному состоянию «поворачивает» вектор этого состояния в направлении к искомому состоянию .

2.5 Многократное применение алгоритма Гровера

Рассмотрим процедуру многократного применения алгоритма Гровера. Каждое последующее состояние выражается через предыдущее следующим образом

Запишем результат первой итерации

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

Для k-ой итерации обозначим одинаковые действительные амплитуды всех состояний с x ? щ как , а действительную амплитуду состояния с x = щ как , т.е.

Тогда

Где

(2.9)

Подставляя (2.9) в (2.8), можно написать следующие равенства

Эти рекуррентные соотношения надо решать с условием k=0:

(2.10)

Амплитуды вероятности должны удовлетворять уравнению нормировки:

(2.11)

(2.12)

Теперь выразим рекуррентные соотношения через углы и

Где

а значит

(2.15)

Из соотношений (2.13) и (2.14) следует, что углы образуют арифметическую прогрессию

При k=0 имеем уравнения (2.10). Тогда из (2.10), (2.11) и (2.12) получаем

(2.16)

Из сопоставления (2.13) с (2.14) видим что . Следовательно, решение рекуррентных соотношений можно записать в следующем виде

Амплитуда (2.11), при больших N, будет крайне мала, с другой стороны, амплитуда (2.12) будет значительно больше. Она достигает своего максимума () при условии , следовательно

(2.17)

Когда можно произвести замену

Подставляя (2.13) в (2.15) приходим к тому, что число шагов, необходимое для достижения максимальной амплитуды равно

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

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

2.6 Реализация программы

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

Оператор записывается так

Единицу представляем как единичную матрицу

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

Оператор записывается так

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

Как получается описано выше.

В матричной реализации на C++ нет ничего сверхъестественного, но, тем не менее, это усложнит читабельность кода и будет трудно уловить именно смысл этого алгоритма. Поэтому я решил реализовать ее в среде Scilab. Scilab -- пакет прикладных математических программ, для решения различных задач, на сегодняшний день являющийся общедоступным. Ее текст представлен в приложении 1.



Выводы

В данной главе был описан алгоритм Гровера с помощью математических методов,

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

Кроме того, написана программа, с помощью которой проверяется действенность алгоритма.



ЗАКЛЮЧЕНИЕ

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

Детально разобран сам алгоритм Гровера. Приведено описание двух основных операторов и результаты их действия на состояние системы. Помимо этого, произведен перевод из операторного представления в матричное. Была написана программа в среде Scilab 5.5.0. Это позволило наглядно представить суть алгоритма Гровера, не вдаваясь в математические подробности действий над матрицами.

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

Реализовано графическое представление амплитуд вероятности для конечного состояния.

Все задание на курсовую работу было выполнено в полном объеме и в срок.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Кулик С.Д., Берков А.В., Яковлев В.П. Введение в теорию квантовых вычислений (методы квантовой механики и кибернетике). -- Кн.2. --Москва: МИФИ, 2008. --212 с.

2. Википедия [Электронный ресурс]. -- Электрон. дан. -- Режим доступа: https://ru.wikipedia.org/wiki, свободный. -- загл. с экрана. -- (дата обращения: 12.10.2014).

3. Сайт выпускников школы № 1227 [Электронный ресурс]. -- Электрон. дан. -- Режим доступа: http://school1227.ru/index.php/2011-05-07-18-11-49/178-computer-science/1913----2013- , свободный. -- загл. с экрана. -- (дата обращения: 12.10.2014).

4. TheRunet [Электронный ресурс]. -- Электрон. дан. -- Режим доступа: http://therunet.com/articles/1824-magiya-i-realnost-kvantovyh-vychisleniy, свободный. -- загл. с экрана. -- (дата обращения: 12.10.2014).

5. Гайнутдинова А.Ф. Методическое пособие по квантовым исчислениям, -- Казань, 2007 -- 73 с.

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

...