Есть две функции06.02.2017 22:18

Есть две булевы функции $n$ аргументов, одна — константная, другая — сбалансированная. На какую сам сядешь, на какую фронтендера посадишь? Вот только функции неизвестны, а вызвать их разрешается лишь один раз.

Если не знаешь, как решить подобную задачу, добро пожаловать под кат. Там я расскажу про квантовые алгоритмы и покажу как их эмулировать на самом народном языке — на Python.

I«ve come to talk with you again

Давайте чуть более формально поставим задачу о двух функциях. Пусть дана булева функция $f: \{0, 1\}^n \to \{0, 1\}$ и о ней априорно известно, что она или константна, то есть для любого из своих аргументов всегда возвращает либо 0, либо 1, или сбалансирована, то есть ровно на половине своих аргументов возвращает 0, а ровно на половине 1. Требуется определить, константна функция или сбалансирована. При этом считается, что время вызова функции несоизмеримо больше любых других операций, поэтому сложность алгоритма определяется количеством вызовов функции.

Пример:

$f(x_1, x_2) = x_1 \otimes x_2$ сбалансирована:
$x_1$

$x_2$

$f$

0 0 0
0 1 1
1 0 1
1 1 0
$f(x_1, x_2) = x_1 \vee x_2 \vee (\neg x_1 \wedge \neg x_2)$ константна:
$x_1$

$x_2$

$f$

0 0 1
0 1 1
1 0 1
1 1 1
$f(x_1, x_2) = x_1 \wedge x_2$ ни сбалансирована, ни константна:
$x_1$

$x_2$

$f$

0 0 0
0 1 0
1 0 0
1 1 1

$x_1$	$x_2$	$f$
0	0	0
0	1	1
1	0	1
1	1	0

$x_1$	$x_2$	$f$
0	0	1
0	1	1
1	0	1
1	1	1

$x_1$	$x_2$	$f$
0	0	0
0	1	0
1	0	0
1	1	1

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

Классическое детерминированное решение

Давайте, для начала, решим задачу в классической модели вычислений. Для этого в худшем случае понадобится вызвать функцию на $2^{n-1}+1$ аргументах: ровно на половине и ещё одном. Если все вычисленные значения одинаковы, то функция, очевидно, константна. Если же существуют хотя-бы два различных результата, функция сбалансирована. Сложность детерминированного алгоритма экспоненциальна и составляет $O(2^{n-1} + 1)$ .

Алгоритм на Python:

from itertools import product, starmap, tee

def pairwise(xs):
    a, b = tee(xs)
    next(b, None)
    return zip(a, b)

def is_constant(f, n):
    m = 2 ** (n - 1)

    for i, (x, y) in enumerate(pairwise(starmap(f, product({0, 1}, repeat=n)))):
        if i > m:
            break

        if x != y:
            return False

    return True

Классическое вероятностное решение

А что, если вместо половины аргументов мы проверим меньшее их число и вынесем вердикт? Точным ответ уже не будет, но с какой вероятностью мы ошибёмся? Допустим, мы вычислили функцию на $k < 2^{n-1} + 1$ аргументах. Если среди значений функции есть два различных, то всё просто — функция сбалансирована. Иначе, мы объявляем её константной с вероятностью $p(k) < 1$ . Предположим, что мы ошиблись и функция на самом деле сбалансирована. Посчитаем вероятность ошибки $1 - p(k)$ . Если мы выбирали аргументы равномерно, то вероятность того, что два подряд идущих значения функции одинаковы, равна $1/2$ , а вероятность же встретить $k$ одинаковых подряд идущих значений равна $1/2^k$ . Таким образом:

$1 - p(k) = \frac{1}{2^k},$

$p(k) = 1 - \frac{1}{2^k}.$

Обратная функция:

$k(p) = \log_2{\frac{1}{1 - p}}.$

При фиксированном $p$ сложность классического вероятностного алгоритма константна и равна $O(\log_2{\frac{1}{1 - p})}.$ Чтобы быть уверенным в ответе на 99.99%, необходимо вызвать функцию всего 14 раз.

Алгоритм на Python:

import random
from itertools import product, starmap, tee


def pairwise(xs):
    a, b = tee(xs)
    next(b, None)
    return zip(a, b)


def is_constant(f, n, k=14):
    xs = list(product({0, 1}, repeat=n))
    random.shuffle(xs)
    xs = xs[:k]

    for x, y in pairwise(starmap(f, xs)):
        if x != y:
            return False

    return True

А если я скажу вам, что существует константное детермининированное решение со сложностью $O(1)$ , позволяющее вызвать функцию всего один раз?

Правда, прежде чем его рассмотреть, придётся отвлечься…

Because a vision softly creeping

Мифы

Пережде чем начать, хотелось бы обсудить несколько расхожих мифов, связанных с квантовыми вычислениями:

Квантовые алгоритмы — это сложно.
Да, их сложно синтезировать, ибо требуется для этого математическое воображение и проницательность. Их сложно реализовывать на настоящих квантовых компьютерах: для этого необходимо превосходно знать физику и засиживаться каждый день допоздна в лабаратории на кафедре. Но что точно не требует никаких особых знаний и невероятного количества усердия, так это их понимание. Я утверждаю, что каждый может понимать квантовые алгоритмы: они опираются на крайне простую математику, доступную любому первокурснику. Всё, что от вас требуется — лишь немного времени на изучение.
Уже существуют квантовые компьютеры на тысячи кубитов от D-Wave
Нет, это не настоящие квантовые компьютеры.
Не существует ни одного настоящего квантового компьютера
Нет, существуют. В лабораторных условиях и располагают они лишь несколькими кубитами.
Квантовые компьютеры позволят решать задачи, недоступные ранее
Нет, множество задач, вычислимых в классической и квантовой моделях, совпадают. Квантовые вычисления позволяют лишь снизить сложность небольшого подмножества этих задач.
На квантовом компьютере Crysis на максималках будет летать
За исключением некоторого подмножества задач, которые квантовая модель вычислений способна ускорить, остальные могут быть решены лишь эмуляцией классического компьютера. Что, как вы понимаете, очень медленно. Crysis, скорее всего, будет лагать.
Квантовый компьютер — это чёрная коробочка с входом и выходом, заглянув в которую можно всё испортить
Если вам 12 лет, такая аналогия сгодится. В любом другом случае она, как и все другие аналогии с коробками, котами, лупами и «связанными» нитками электронами, так активно продвигаемые во всех научно-популярных источниках, только лишь запутывает, создаёт иллюзию ложного понимания и скорее вредна, чем полезна. Откажитесь от этих аналогий.

Зачем?

Зачем прикладному математику (программисту) уметь разбираться в квантовых алгоритмах на прикладном уровне? Тут всё просто, я готов предложить вам два довода:

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

Left its seeds while I was sleeping

Самой базовой составляющей квантовых вычислений является квантовая система. Квантовая система — физическая система, все действия которой сравнимы по величине с постоянной Планка. Это определение и тот факт, что квантовые системы подчиняются законам матричной механики — все знания, которые нам потребуются из физики. Дальше — только математика.

Как и любая другая физическая система, квантовая система может находиться в определённом состоянии. Все возможные состояния квантовой системы образуют гильбертово пространство $\mathcal{H}$ над полем комплексных чисел. Надеюсь, с концепцией комплексных чисел читатель знаком — их понимание необходимо везде в дальнейшем. Если нет, советую познакомиться и возвращаться. Гильбертово пространство же является полным нормированным метрическим линейным пространством с нормой $\Vert x \Vert = \sqrt{(x, x)}$ , где $(x, y)$ — скалярное произведение. По порядку с конца:

Линейное (векторное) пространство — множество элементов $X$ с введёнными на нём операциями сложения элементов $x + y$ и умножения $x \cdot \lambda$ на элемент поля $K$ (в нашем случае поля комплексных чисел). Операции эти должны быть замкнуты (результат должен принадлежать множеству $X$ ) и должны выполняться 8 аксиом. Посмотреть полный их список, а так же познакомиться подробнее с линейными пространствами рекомендую здесь.
В метрическом пространстве для любых элементов определено расстояние , которое удовлетворяет требованиям (аксиомам метрического
пространства):
- $\rho(x, y) \geqslant 0$ , при этом $\rho(x, y) = 0$ тогда и только тогда, когда $x$ и $y$ совпадают;
- $\rho(x, y) = \rho(y, x)$ ;
- $\rho(x, y) \leqslant \rho(x, z) + \rho(z, y)$ — неравенство треугольника.
В нормированном пространстве для любого элемента существует вещественное число , называемое его нормой и удовлетворяюещее, опять же, трём аксиомам:
- $\Vert x \Vert \geqslant 0$ , если же $\Vert x \Vert = 0$ , то $x = 0$ — нулевой элемент;
- $\Vert \lambda \cdot x \Vert = \vert \lambda \vert \cdot \Vert x \Vert$ ;
- $\Vert x + y \Vert \leqslant \Vert x \Vert + \Vert y \Vert$ .

Введём в полученном пространстве скалярное произведение, удовлетворяющее обычным требованиям скалярного произведения, введём норму как показано выше и получим пространство Гильберта.

Обсудим ещё понятие сопряжённого пространства. Пространством, сопряжённым к $\mathcal{H}$ называется пространство $\mathcal{H^*}$ линейных операторов над $\mathcal{H}$ . Что такое линейный оператор? Можно думать о нём как об обобщении линейной функции: для линейноного оператора $A: \mathcal{H} \to Y$ должно выполняться:

$A (\lambda_1 x_1 + \lambda_2 x_2) = \lambda_1 A x_1 + \lambda_2 A x_2,$

где $x_1, x_2 \in \mathcal{H}$ , $\lambda_1, \lambda_2 \in K$ . (На самом деле, ещё и его норма должна быть ограничена на единичной гиперсфере, но, дабы избежать ещё десятка громоздких определений, ограничимся таким интуитивным представлением.)

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

$\left| \psi \right\rangle \in \mathcal{H}.$

Бра-вектором называется элемент сопряжённого пространства

$\langle\left \phi \right| \in \mathcal{H^*},$

такой что

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

Теперь можно сделать важную поправку: квантовую систему может описывать не любое гильбертово пространство, а лишь такое, что

$\langle\left \psi | \psi \right\rangle = 1\; \forall \left| \psi \right\rangle \in \mathcal{H},$

то есть норма каждого элемента равна единице.

Если мы выделим в нашем гильбертовом пространстве состояний некоторый базис $\{\left| e_i \right\rangle\}_{i=1}^m \subset \mathcal{H}$ , то любой кет-вектор сможем записать в виде вектора комплексных чисел — коэффициентов его разложения по этому базису:

$\left| \psi \right\rangle = \sum_{i=1}^m{\langle\left e_i | \psi \right\rangle \left| e_i \right\rangle},$

при этом матричная механика говорит нам, что квадраты модулей коэффициентов разложения $\vert \langle\left e_i | \psi \right\rangle \vert^2$ физически означают вероятности нахождения квантовой системы в соответствующем базисном состоянии при измерении в этом базисе.

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

Если мы можем представить элемент Гильбертова пространства вектором при некотором фиксированном базисе, то линейный оператор над этим пространством мы можем представить матрицей.

Действительно,

$A \left| \psi \right\rangle = \sum_{i=1}^m{\langle\left e_i | \psi \right\rangle A \left| e_i \right\rangle}$

эквивалентно

$A \left| \psi \right\rangle = \hat{A} \hat{\psi},$

где $\hat{A}$ получается поочерёдным применением оператора $A$ к базисным элементам $\left| e_i \right\rangle$ и выписыванием получившихся элементов по строкам, а $\hat{\psi}$ — разложение $\left| \psi \right\rangle$ в этом же базисе.

Пусть оператор $A$ представляется матрицей

$A = \begin{pmatrix} a_{11} & a_{12} & a_{13} & \dots & a_{1m} \\ a_{21} & a_{22} & a_{23} & \dots & a_{2m} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & a_{m3} & \dots & a_{mm} \end{pmatrix}.$

Элементы матрицы — комплексные числа. Давайте возьмём каждый элемент и заменим его комплексно сопряжённым (комплексно сопряжённым к $x + iy$ называется число $x - iy$ ) и, заодно, транспонируем всю матрицу:

$A^\dagger = \overline{A}^T = \begin{pmatrix} \overline{a_{11}} & \overline{a_{21}} & \overline{a_{31}} & \dots & \overline{a_{m1}} \\ \overline{a_{12}} & \overline{a_{22}} & \overline{a_{32}} & \dots & \overline{a_{m2}} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \overline{a_{1m}} & \overline{a_{2m}} & \overline{a_{3m}} & \dots & \overline{a_{mm}} \end{pmatrix}.$

Такая матрица $A^\dagger$ называется эрмитово-сопряжённой к $A$ . Если $A A^\dagger = A^\dagger A = I$ , где $I$ — единичный оператор (с единичной матрицей), то соответствующий оператор называется унитарным.

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

$U \left| \psi_0 \right\rangle = \left| \psi_1 \right\rangle,$

то можно применить обратное преобразование

$U^\dagger \left| \psi_1 \right\rangle = U^\dagger U \left| \psi_0 \right\rangle = \left| \psi_0 \right\rangle$

и получить исходное состояние системы.

Напоследок самое важное: тензорное произведение. Тензорным произведением двух гильбертовых пространств $\mathcal{H}_1$ и $\mathcal{H}_2$ называется гильбертово пространство, обозначаемое $\mathcal{H}_1 \otimes \mathcal{H}_2$ . Я не буду приводить формальное определение, лишь отмечу важные нам свойства:

Размерность получившегося пространства равна произведению размерностей исходных пространств:
$\dim{\mathcal{H}_1 \otimes \mathcal{H}_2$} = \dim{\mathcal{H}_1} \cdot \dim{\mathcal{H}_2}$ ;
Если $\{\left| e_i \right\rangle\}_{i=1}^m$ — базис $\mathcal{H}_1$ , а $\{\left| f_i \right\rangle\}_{i=1}^n$ — базис $\mathcal{H}_2$ , то $\{\left| e_i \otimes f_j \right\rangle\}_{i=1, j=1}^{m, n}$ — порождающий базис $\mathcal{H}_1 \otimes \mathcal{H}_2$ .

Тензорным же произведенем операторов $A$ из $\mathcal{H}_1^*$ и $B$ из $\mathcal{H}_2^*$ (оператор $A$ представлен матрицей, показанной выше) называется оператор $A \otimes B$ из $\big[ \mathcal{H}_1 \otimes \mathcal{H}_2 \big]^*$ с матрицей

$A \otimes B = \begin{pmatrix} a_{11} \cdot B & a_{12} \cdot B & a_{13} \cdot B & \dots & a_{1m} \cdot B \\ a_{21} \cdot B & a_{22} \cdot B & a_{23} \cdot B & \dots & a_{2m} \cdot B \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{m1} \cdot B & a_{m2} \cdot B & a_{m3} \cdot B & \dots & a_{mm} \cdot B \end{pmatrix}.$

Такое произведение ещё называется произведением Кронекера: мы умножаем вторую матрицу на каждый элемент первой матрицы и из получившихся блоков составляем блочную матрицу. Если размерность $A$ равнялась $n \times n$ , а размерность $B$ равнялась $m \times m$ , то размерность матрицы, полученной в ходе тензорного произведения, будет равна $n \cdot m \times n \cdot m$ .

Пример:

$A = \begin{bmatrix} 1 & 2 \\ 3 & 0 \end{bmatrix},\; B = \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix},$

$A \otimes B = \begin{bmatrix} 1 \cdot \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix} & 2 \cdot \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix} \\ 3 \cdot \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix} & 0 \cdot \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix} \end{bmatrix} = \begin{bmatrix} 1 & 1 & 2 & 2 \\ 1 & 2 & 2 & 4 \\ 3 & 3 & 0 & 0 \\ 3 & 6 & 0 & 0 \\ \end{bmatrix}.$

$A = \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix},\; B = \begin{bmatrix} 1 \\ 2 \end{bmatrix},$

$A \otimes B = \begin{bmatrix} 1 \\ 2 \\ 0 \\ 0 \\ \end{bmatrix}.$

Третье важное свойство квантовых систем: две квантовые системы могут находиться в состоянии суперпозиции, при этом новое пространство состояний представляет собой тензорное произведение исходных пространств, а состояние новой системы будет являться тензорным произведением состояний исходных систем. Так, суперпозицией систем в состояниях $\left| \psi \right\rangle \in \mathcal{H}_1$ и $\left| \phi \right\rangle \in \mathcal{H}_2$ будет новая система в состоянии $\left| \psi \right\rangle \otimes \left| \phi \right\rangle$ , описываемая гильбертовым пространством $\mathcal{H}_1 \otimes \mathcal{H}_2$ .

And the vision that was planted in my brain

Вот и вся математика, что нам понадобится. На всякий случай, резюмируя:

При фиксированном базисе квантовую систему можно описать комплексным вектором, а эволюцию этой системы — унитарной комплексной матрицей;
Квантовую систему можно измерить в каком-либо базисе и она перейдёт в одно из базисных состояний в соответствии с заранее определёнными вероятностями.

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

Кубит

Давайте рассмотрим некоторую квантовую систему, описываемую двумерным гильбертовым пространством $\mathcal{H}^2$ и выделим в ней некоторый базис, вектора которого обозначим как $\left| 0 \right\rangle$ и $\left| 1 \right\rangle$ . Внутри скобок записывается индекс базисного вектора в двоичной системе счисления, начиная с нуля без дополнительных символов. Такие обозначения окажутся очень удобными. Таким образом,

$\left| 0 \right\rangle = \begin{bmatrix} 1 \\ 0 \end{bmatrix},\; \left| 1 \right\rangle = \begin{bmatrix} 0 \\ 1 \end{bmatrix},$

и произвольный вектор $\left| \psi \right\rangle \in \mathcal{H}^2$ можно выразить следующим образом:

$\left| \psi \right\rangle = \alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle,$

где $\alpha$ и $\beta$ — некоторые комплексные числа, такие что $\vert \alpha \vert^2 + \vert \beta \vert^2 = 1$ (всплмните интерпретацию коэффициентов разложения и условие нормировки из предыдущего параграфа). Так вот, такая простая квантовая система называется кубитом (quantum bit, qbit). Кубит — аналог классического бита в квантовой модели вычислений. Нетрудно видеть, что пространство всевозможных состояний одного кубита $\mathcal{H}^2$ представляет из себя трёхмерную сферу, называемую сферой Блоха, где $\left| 0 \right\rangle$ соответствует нижнему полюсу, а $\left| 1 \right\rangle$ — верхнему.

Регистр

Один кубит, как и один бит — слишком скучно, поэтому сразу рассмотрим суперпозицию нескольких кубитов. Такая суперпозиция называется квантовым регистром (quantum register, qregister) из $n$ кубитов. Например, квантовый регистр из 2 кубитов будет описываться пространством $\mathcal{H}^4$ и иметь 4 базисных состояния:

$\left| 00 \right\rangle = \left| 0 \right\rangle \otimes \left| 0 \right\rangle = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix},$

$\left| 01 \right\rangle = \left| 0 \right\rangle \otimes \left| 1 \right\rangle = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix},$

$\left| 10 \right\rangle = \left| 1 \right\rangle \otimes \left| 0 \right\rangle = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix},$

$\left| 11 \right\rangle = \left| 1 \right\rangle \otimes \left| 1 \right\rangle = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}.$

Соответственно, любое состояние такого регистра $\left| \phi \right\rangle \in \mathcal{H}^4$ можно представить в виде

где $\vert \alpha_1 \vert^2 + \vert \alpha_2 \vert^2 + \vert \alpha_1 \vert^3 + \vert \alpha_4 \vert^2 = 1$ . Заметьте, что в наших обозначениях базисный вектор с единицей на $k$ -ом месте обозначется числом $k$ , записанным в двоичном виде.

Далее аналогично. Квантовый регистр из $m$ кубитов будет описываться $2^m$ -мерным гильбертовым пространством $\mathcal{H}^{2^m}$ , иметь $2^m$ базисных состояний, формируемых аналогичным образом. Не откладывая надолго, научимся эмулировать квантовые регистры:

import numpy as np


class QRegister:
    def __init__(self, n_qbits, init):
        self._n = n_qbits
        assert len(init) == self._n

        self._data = np.zeros((2 ** self._n), dtype=np.complex64)
        self._data[int('0b' + init, 2)] = 1

3 строчки кода для создания квантового регистра — совсем не сложно, согласитесь. Использовать можно таким образом:

a = QRegister(1, '0')    # |0>
b = QRegister(1, '1')    # |1>
c = QRegister(3, '010')  # |010>

Квантовый алгоритм включает в себя:

Инициализацию квантового регистра;
Набор унитарных преобразований над ним;
Измерение результата.

Измерение

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

def measure(self):
    probs = np.real(self._data) ** 2 + np.imag(self._data) ** 2
    states = np.arange(2 ** self._n)
    mstate = np.random.choice(states, size=1, p=probs)[0]
    return f'{mstate:>0{self._n}b}'

Генерируем вероятности probs выбора одного из $2^n$ состояний states и случайно выбираем его с помощью np.random.choice. Остаётся только вернуть бинарную строку с соответствующим количеством дополняющих нулей. Очевидно, что для базисных состояний ответ всегда будет одинаков и равен самому этому состоянию. Проверим:

>>> QRegister(1, '0').measure()
'0'
>>> QRegister(2, '10').measure()
'10'
>>> QRegister(8, '01001101').measure()
'01001101'

Почти всё готово, чтобы решить нашу задачу! Осталось лишь научиться влиять на квантовые регистры. Мы уже знаем, что сделать это можно унитарными преобразованиями. В квантовой информатике унитарное преобразование называется гейтом (quantum gate, qgate, gate).

Гейты

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

Единичный

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

$I = \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix}.$

Он никак не изменяет кубит, на который действует:

однако не стоит считать его бесполезным — он нам понадобится, и не раз.

Гейт Адамара

$H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix}$

Не составляет труда проверить, что матрица унитарна:

$H H^\dagger = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix} \cdot \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix} = \frac{1}{2} \begin{bmatrix} 2 & 0\\ 0 & 2 \end{bmatrix} = I.$

Рассмотрим действие гейта Адамара на базисные кубиты:

$H \left| 0 \right\rangle = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix} \begin{bmatrix} 1\\ 0 \end{bmatrix} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1\\ 1 \end{bmatrix} = \frac{1}{\sqrt{2}} (\left| 0 \right\rangle + \left| 1 \right\rangle),$

$H \left| 1 \right\rangle = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix} \begin{bmatrix} 0\\ 1 \end{bmatrix} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1\\ -1 \end{bmatrix} = \frac{1}{\sqrt{2}} (\left| 0 \right\rangle - \left| 1 \right\rangle).$

Или в общем виде [1]:

$H \left| x \right\rangle = \frac{1}{\sqrt{2}} \sum_{y \in \lbrace 0,1 \rbrace} (-1)^{x \cdot y} \left| y \right\rangle.$

Как можно заметить, гейт Адамара любое базисное состояние переводит в равновероятное — при измерении с равной вероятностью можно получить любой результат.

Гейты Паули

Три карйне важных гейта, которым соответствуют матрицы, введённые Вольфгангом Паули:

$X = \begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix},\; Y = \begin{bmatrix} 0 & -i\\ i & 0 \end{bmatrix},\; Z = \begin{bmatrix} 1 & 0\\ 0 & -1 \end{bmatrix}.$

Гейт $X$ ещё называется NOT-гейтом:

$X \left| 0 \right\rangle = \left| 1 \right\rangle, \; X \left| 1 \right\rangle = \left| 0 \right\rangle,$

, а геометрически его применение эквивалентно повороту на сфере Блоха на $\pi$ радиан вокруг оси $x$ .

Гейты $Y$ и $Z$ аналогичны гейту $X$ за тем исключением, что вращение производится вокруг соответствующей оси.

Существует теорема, согласно которой с помощью гейтов $I$ , $X$ , $Y$ и $Z$ можно выразить любой