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

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

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

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

Кубит или же квантовый бит — наименьший элемент для хранения информации в квантовом компьютере. Чем он похож на бит? Он тоже может находиться в одном из базовых состояний, обозначаемые как |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>

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

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

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

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

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

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

Преобразование Адамара. Является одним из самых важных вентилей, иногда его называют «квадратный корень из 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. Что еще хочется сказать про вентиль Тоффоли — было доказано, что на базе только одного этого вентиля можно построить обратимый процессор.

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