Vector Spaces

Шпаргалка

Всё, что нужно под рукой при чтении статей. Все векторы и матрицы здесь действительные: достаточно плоскости R2\mathbb{R}^2 и пространства R4\mathbb{R}^4.

Физика и математика

Физика Кубит Вектор в R2\mathbb{R}^2
Состояние спина электрона или поляризации фотона кубит единичный вектор ∣v⟩=d0∣b0⟩+d1∣b1⟩|v\rangle = d_0|b_0\rangle + d_1|b_1\rangle
Измерительный прибор: магнитная установка или фильтр выбор направления измерения упорядоченный ортонормированный базис (∣b0⟩, ∣b1⟩)(|b_0\rangle,\ |b_1\rangle)
Результат измерения: N или S, прошёл или нет бит 00 или 11 базисный вектор ∣b0⟩|b_0\rangle или ∣b1⟩|b_1\rangle
Вероятность исхода d02d_0^2 и d12d_1^2 квадраты коэффициентов, d02+d12=1d_0^2 + d_1^2 = 1
Вентиль преобразование кубита умножение на ортогональную матрицу
Две частицы два кубита вектор в R2⊗R2=R4\mathbb{R}^2 \otimes \mathbb{R}^2 = \mathbb{R}^4

Нотация Дирака

Запись Что это
∣v⟩|v\rangle, кет вектор-столбец, например [31]\begin{bmatrix}3\\1\end{bmatrix}
⟨w∣\langle w|, бра вектор-строка
⟨a∣b⟩\langle a|b\rangle число a1b1+a2b2a_1 b_1 + a_2 b_2
⟨a∣a⟩=1\langle a|a\rangle = 1 вектор ∣a⟩|a\rangle единичный
⟨a∣b⟩=0\langle a|b\rangle = 0 векторы ортогональны, исходы взаимоисключающие
∣a⟩⊗∣b⟩|a\rangle \otimes |b\rangle тензорное произведение, составная система
ru=stru = st у вектора r∣00⟩+s∣01⟩+t∣10⟩+u∣11⟩r|00\rangle + s|01\rangle + t|10\rangle + u|11\rangle нет запутанности

Три главных инструмента линейной алгебры

Пусть столбцы матрицы AA — векторы нового базиса ∣b1⟩,∣b2⟩|b_1\rangle, |b_2\rangle.

  1. Проверка ортонормированности. Если ATA=IA^T A = I, базис ортонормирован, а матрица AA ортогональна.
  2. Координаты в новом базисе. AT∣v⟩=[⟨b1∣v⟩⟨b2∣v⟩]A^T |v\rangle = \begin{bmatrix}\langle b_1|v\rangle \\ \langle b_2|v\rangle\end{bmatrix}.
  3. Длина через коэффициенты. Если ∣v⟩=c1∣b1⟩+c2∣b2⟩|v\rangle = c_1|b_1\rangle + c_2|b_2\rangle в ортонормированном базисе, то ∥ ∣v⟩ ∥2=c12+c22\big\|\,|v\rangle\,\big\|^2 = c_1^2 + c_2^2.

Вентили

Вентиль Матрица Действие
II [1001]\begin{bmatrix}1&0\\0&1\end{bmatrix} ничего не меняет
XX [0110]\begin{bmatrix}0&1\\1&0\end{bmatrix} квантовое НЕ: меняет ∣0⟩|0\rangle и ∣1⟩|1\rangle местами; отражение относительно прямой под углом 45∘45^\circ
ZZ [100−1]\begin{bmatrix}1&0\\0&-1\end{bmatrix} меняет знак у ∣1⟩|1\rangle; отражение относительно горизонтальной оси
YY [01−10]\begin{bmatrix}0&1\\-1&0\end{bmatrix} сначала XX, потом ZZ; поворот на 90∘90^\circ
HH 12[111−1]\dfrac{1}{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix} создаёт суперпозицию: H∣0⟩=12(∣0⟩+∣1⟩)H|0\rangle = \tfrac{1}{\sqrt2}(|0\rangle + |1\rangle); отражение относительно прямой под углом 22,5∘22{,}5^\circ
CNOTCNOT [1000010000010010]\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix} инвертирует второй бит, если первый равен 11: (x,y)↦(x, x⊕y)(x,y)\mapsto(x,\,x\oplus y). Базис: ∣00⟩,∣01⟩,∣10⟩,∣11⟩|00\rangle,|01\rangle,|10\rangle,|11\rangle

Цепь Белла: HH на первом кубите, затем CNOTCNOT. Она превращает ∣00⟩|00\rangle в 12(∣00⟩+∣11⟩)\tfrac{1}{\sqrt2}(|00\rangle + |11\rangle).

Алгоритмы

Задача Классический алгоритм Квантовый алгоритм
Дойча — Джозы 2n−1+12^{n-1}+1 запросов в худшем случае 11 запрос
Саймона экспоненциальное число запросов несколько запусков цепи и линейная система, класс BQPBQP
Поиск Гровера в списке из mm элементов в среднем m/2m/2 проверок порядка m\sqrt{m}, для m=4m=4 достаточно одного запроса
Разложение N=pqN = pq на простые множители для больших NN непосильно алгоритм Шора, полиномиальное время

Три запрета

  • Измерение меняет состояние: повторное измерение в другом базисе снова случайно.
  • Неизвестный кубит нельзя скопировать: вентиля-копировщика не существует.
  • Запутанность не передаёт сигнал быстрее света: нужны ещё классические биты.