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

в 14:07, , рубрики: квантовые вычисления, квантовый компьютер, ненормальное программирование, Программирование, метки: ,

Хей, Амиго!
Я уже очень давно читаю Хабрахабр и встретил очень мало статей, посвященных квантовым компьютерам. И ни одной про квантовые вычисления.

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

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

Кубит или же квантовый бит — наименьший элемент для хранения информации в квантовом компьютере. Чем он похож на бит? Он тоже может находиться в одном из базовых состояний, обозначаемые как |0> и |1>. В матричной механике вот такие скобочки называются бра и кет, соотвественно < | и | >, от слова «bracket». Но чаще всего он находится в состоянии суперпозиции, которую можно рассматривать как кота Шредингера. Если быть точнее, то квантовый бит всегда находится в состоянии |Ψ> = a|0> + b|1>, где a и b — комплексные числа, и |a|^2 + |b|^2 = 1. Когда мы хотим считать информацию с кубита, он сразу переходит в одно из базовых состояний. Вероятности получить 0 и 1 равны, соответственно, |a|^2 и |b|^2.

Ладно, с кубитами пока закончим. Кому хочется еще -> Википедия.

Однокубитные вентили

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

NOT : |Ψ> -> NOT : (a|0> + b|1>) -> a|1> + b|0>

Но все же некоторые вентили подобным образом записывать неудобно, ну бывает такое. Квантовому состоянию кубита |Ψ> соотвествует столбец. То есть чистое однокубитное квантовое состояние будет выглядеть как:

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

А чистое двухкубитное квантовое состояние будет определяться суперпозицией двухкубитных базовых состояний:

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

Как выглядит трехкубитное состояние, думаю, вы уже догадались. Выглядит ужасно, но так уж устроен мир.

Однокубитные квантовые гейты можно представить в виде матрицы 2x2, n кубитные в виде матрицы 2^n x 2^n. То есть матрица квантового NOT будет выглядеть как:

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

Как вы видите, если мы хотим узнать результат, то надо умножить квантовое состояние бита на матрицу преобразования. Кстати, квантовые вентили всегда являются обратимыми, в отличие от многих классических. Для одного кубита можно построить бесконечное количество вентилей, чего не скажешь про классические биты. Но сколько нам понадобится? Любая 2x2 матрица может быть разложена по системе матриц Паули. Так что достаточно будет самих матриц Паули:

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

И еще плюс несколько часто используемых вариантов:

Преобразование Адамара. Является одним из самых важных вентилей, иногда его называют «квадратный корень из NOT”. Преобразует |0> в (|0>+|1>)/sqrt(2), а |1>, соответственно, в (|0>-|1>)/sqrt(2), что соответствует половине пути между |0> и |1> на сфере Римана:
Квантовые вычисления. Начало
S-фазовый вентиль:
Квантовые вычисления. Начало

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

Думаю, с однокубитными вентилями уже разобрались.

Контролируемые U вентили

В обычной цифровой электронике все же чаще используются AND, XOR и другие, нежели NOT. То есть контролируемые вентили, где один из входов является контролируемым, а другой — контролирующим.Входов может быть и больше двух. Запомните одно правило, в квантовых вентилях число входов всегда равно числу выходов. Итак, одними из важных вентилей являются контролируемые U (Controlled U-Gate).

Что за U? Откуда оно взялось? Успокойся, читатель, U – это вообще любой однокубитный вентиль.

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

Как вы видите, у него есть два входа и два выхода. Где какой — догадаться нетрудно. Вместо U можно подставить любую букву однокубитного вентиля. Одними из важнейших контролируемых вентилей являются универсальные контролируемое НЕ (CNOT) и вентиль Тоффоли (контролируемое контролируемое НЕ, CCNOT). А что это еще за контролируемое контролируемое? Да просто вместо U поставили CNOT, получился CCNOT. В общем виде контролируемое сколько хотите U выглядит так:

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

«Антенны» наверху — это контролирующие кубиты, а «ножки» — это контролирующие кубиты.

Напоследок матрицы преобразований CNOT и CCNOT. Что еще хочется сказать про вентиль Тоффоли — было доказано, что на базе только одного этого вентиля можно построить обратимый процессор.

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

Статья получилась уже большой, да и думаю, я вам уже надоел. Если Хабру вдруг будет интересно — напишу вторую часть. Если нет — так нет.

Автор: holmuk

Источник

Поделиться

* - обязательные к заполнению поля