Оглавление
1.Введение2
2.Основная часть2
2.1. Цели работы 2
2.2. Принцип работы классического компьютера 2
2.3. Принцип работы квантового компьютера 2
3.Вычисления3
3.1 Квантовые вентили 4
4. Квантовый алгоритм Гровера 5
5. Итог Работы 7
Введение
Современные компьютеры способны выполнять довольно широкий круг задач. С ростом количества информации растёт и требуемая вычислительная мощность компьютеров. Но с увеличением количества процессоров появляется проблема с их синхронизацией. К тому же классические компьютеры слабые в задачах с перебором.
Основная часть
2.1. Цели работы: Сравнение классического алгоритма с квантовым.
1) Изучить основы работы квантового компьютера.
2) Изучить алгоритм работы квантового компьютера.
Принцип работы классического компьютера
Классический компьютер использует биты как наименьший элемент хранения информации. Классический бит может принимать одно из двух значений 0 или 1.
Тогда n-битовый регистр способен хранить 
значения.
Принцип работы квантового компьютера
Квантовый же компьютер использует q-биты (quantumbit). Кубит - квантовый разряд или наименьший элемент для хранения информации в квантовом компьютере.
Кубит может находитсяв состоянии квантовой суперпозиции |Ψ> = α|1>+β|0>, то есть иметь состояние 1 и состояние 0 одновременно, что и дает большой выигрыш в вычислениях. Например, регистр из 4 кубитов может находится в квантовой суперпозиции |Ψ> = α|00>+β|01> +μ|10>+ τ|11>, где α, β, μ, τ комплексные числа.
Рис. 1. Представление нуля и едениницы в виде волн 
|α|²-вероятность получения 00.
|β|²-вероятность получения 01.
|μ|²-вероятность получения 10.
|τ|²-вероятность получения 11.
Тогда |α|²+|β|²+|μ|²+|τ|²=1 как полная вероятность.
Вычисления
Упрощённая схема вычисления на квантовом компьютере выглядит так: берётся система кубитов, на которой записывается начальное состояние. Затем состояние системы или её подсистем изменяется посредством унитарных преобразований, выполняющих те или иные логические операции. В конце измеряется значение, и это результат работы компьютера. Роль проводов классического компьютера играют кубиты, а роль логических блоков классического компьютера играют унитарные преобразования. Такая концепция квантового процессора и квантовых логических вентилей была предложена в 1989 году Дэвидом Дойчем.
С квантовыми системами можно производить только линейные унитарные преобразования, что эквивалентно поворотам вектора длиной 1 в трехмерном пространстве. Рассмотрим основные элементарные преобразования. Их можно выполнить при помощи так называемых квантовых вентилей (квантовых гейтов) — умножением матричной формы кет-вектора на матричную форму вентиля.
Таблица 1. Квантовые вентили
Квантовый алгоритм Гровера.
Пусть имеется база данных, состоящей из N записей. Одна из записей удовлетворяет некоторому заданному условию. Задача состоит в том, чтобы найти эту запись. Предполагается, что база данных представляет собой неупорядоченную, неструктурированную совокупность записей. В классическом случае поиск требуемой записи осуществляется методом полного перебора, по которому требуется проверить в среднем N/2 записей. Например, рассмотрим неупорядоченную базу данных, содержащую 1024 записей. Мы хотим найти ровно одну запись. Для того чтобы решить эту задачу на обычном компьютере, в худшем случае, нам придется перебрать все 1024 записей, а в среднем 512 — это очевидно. На квантовом компьютере необходимо и достаточно произвести 25 итераций, чтобы найти данную запись. Для 16384 записей в классическом среднем случае придется перебрать 8192 записи. На квантовом компьютере необходимо и достаточно произвести 100 итераций.
Задача
В коробке лежат 4 шара: красный, жёлтый, зелёный и синий. Требуется найти красныйшар(
).
Решение
Классический метод предусматривает перебор возможный вариантов. В лучшем случае удастся вынуть зелёный шар с первого раза, в худшем – с четвёртого. Таким образом нам придётся произвести 4 итерации для решения данной задачи.
Программная реализация классического алгоритма
Код на С++:
Квантовый метод
Квантовый метод предусматривает вынимание всех шаров за одну итерацию благодаря квантовому параллелизму.
Алгоритм включает в себя следующие шаги.
1. Приготовление начального состояния квантового регистра, состоящего из кубитов. Каждый кубит устанавливается в состояние |0>. Состояние регистра запишем вектор в виде: |Ψ> = | x > = |00>, где х – «Маркированный» шар.
| 
> = |x>= 
⊗ = 
2. Приготовление равновероятной (с равными амплитудами) суперпозиции состояний кубитов с помощью преобразования Уолша — Адамара:
| 
>* (Н⊗Н)= |x> = 
|00> + |01> + |10> + |11>
| > =0.5 
= 
3. Поворот амплитуды «маркированного» состояния
= I – 2|ω>*<ω| = 
– 2 
= 
| 
> = – | > = 
= 
4. ПреобразованиеАдамара:
| 
>* (Н⊗Н) =0.5 
= 
5. Вычисление инверсии относительно среднего:
= 2|ω>*<ω| – I = 
– = 
| 
> = – | > = 
=
6. Преобразование Адамара:
| 
>* (Н⊗Н)=0.5 
=