Упражнения к темам
Введение
Умножение матриц
Чему равно произведение матриц
\begin{equation} \begin{pmatrix} 1 & 2 \\ 3 & 4 \\ \end{pmatrix} \begin{pmatrix} 3 & 4 \\ 1 & 2 \\ \end{pmatrix} \end{equation}Тензорное произведение
Найдите, чему равно тензорное произведение матрицы на саму себя
\begin{equation} \begin{pmatrix} 1/\sqrt{2} & 1/\sqrt{2} \\ 1/\sqrt{2} & -1/\sqrt{2} \\ \end{pmatrix} \end{equation}Является ли полученная матрица унитарной?
Однокубитные операции
Свойства операций
Доказать, что:
- \(HXH = Z\)
- \(HYH = -Y\)
- \(HZH = X\)
- \(T^2 = S\)
Представление на сфере Блоха
Докажите, что с точностью до общей фазы \(T\) является поворотом вокруг оси z на угол \(\pi/4\).
Представьте оператор Адамара \(H\) в виде произведения поворотов \(R_x\) и \(R_z\), а также общего фазового множителя \(e^{i\phi}\).
Пусть \(\hat{n} = (n_x,n_y,n_z)\) — вещественный трёхмерный единичный вектор. Определим оператор \(R_{\hat{n}}(\theta)\) следующим образом:
\begin{equation} R_{\hat{n}}(\theta) = \exp(-i \theta \hat{n} \cdot \vec{\sigma}/2) = \cos(\frac \theta 2) I - i \sin(\frac \theta 2)(n_x X + n_y Y + n_z Z), \end{equation}где \(\vec{\sigma} = (X,Y,Z)\) — вектор, составленный из матриц Паули.
Докажите, что \( (\hat{n} \cdot \vec{\sigma})^2 = I \).
Докажите, что произвольный унитарный оператор \(U\) можно записать в виде
\begin{equation} U = \exp(i \alpha) R_{\hat{n}}(\theta) \end{equation}для некоторых вещественных \(\alpha\) и \(\theta\) и вещественного трёхмерного единичного вектора \(\hat{n}\).
Найдите значения \(\alpha, \theta, \hat{n}\), при которых получится оператор Адамара \(H\).
Найдите значения \(\alpha, \theta, \hat{n}\), при которых получится оператор сдвига фазы \(S\).
Проверьте, что операторы \(Y\) и \(Z\) действительно задают повороты вокруг осей \(y\) и \(z\).
Многокубитные операции
Как выглядит матрица \(4 \times 4\) для схемы
\begin{quantikz} & \gate{H} & \qw \\ & \qw & \qw \\ \end{quantikz}Как выглядит матрица \(4 \times 4\) для схемы
\begin{quantikz} & \qw & \qw \\ & \gate{H} & \qw \\ \end{quantikz}Докажите, что матрицы для следующих схем совпадают:
\begin{quantikz} & \ctrl{1} & \qw \\ & \gate{Z} & \qw \\ \end{quantikz}и
\begin{quantikz} & \gate{Z} & \qw \\ & \ctrl{-1} & \qw \\ \end{quantikz}Пусть \(S_\alpha = \begin{pmatrix} e^{i\alpha} & 0 \\ 0 & e^{i\alpha} \end{pmatrix}\). Можно ли представить следующий оператор (см. схему) в виде произведения двух операторов, действующих на отдельные кубиты?
\begin{quantikz} & \ctrl{1} & \qw \\ & \gate{S_\alpha} & \qw \\ \end{quantikz}Пусть \(U = \exp(i\alpha)AXBXC\), и \(ABC=I\). Пусть \(S_\alpha = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\alpha}\\ \end{pmatrix}\) Какую операцию реализует следующая схема?
\begin{quantikz} \qw & \ctrl{1} & \qw & \ctrl{1} & \gate{S_\alpha} & \qw \\ \gate{C} & \targ{} & \gate{B} & \targ{} & \gate{A} & \qw \\ \end{quantikz}Оракулы
Проверьте, что способ, которым оракул \(O_2\) преобразуется в оракул \(O_1\), действительно работает.
Придумайте способ для преобразования оракула \(O_1\), задающего функцию изменением фазы помеченного состояния, в оракул \(O_1\), задающий ту же функцию при помощи вспомогательного кубита.
Убедитесь, что оракул \(U_{11}\) работает правильно
Является ли NOT обратимой функцией? Является ли AND обратимой функцией? Является ли XOR обратимой функцией?
Если да — приведите обратные функции для них. Если нет — докажите это.
Найдите обратную функцию \(F'\) для обратимой функции \(F\), построенной из произвольной булевой функции \(f\) при помощи вспомогательного входа.
Постройте гейт Фредкина из гейта Тоффоли.
Постройте гейт Тоффоли из гейта Фредкина.
Алгоритмы Дойча и Дойча-Йожи
Докажите, что для произвольного \(x \in \{0,1\}^n\)
\begin{equation*} H^n |x\rangle = \frac{1}{\sqrt{2^n}} \sum_{y=0}^{2^n-1} (-1)^{x\cdot y} |y\rangle, \end{equation*}где \(x\cdot y\) — сумма по модулю 2 произведений соответствующих битов \(x\) и \(y\): \(x\cdot y = x_1 y_1 \oplus x_2 y_2 \oplus \ldots \oplus x_n y_n\).
Алгоритм Саймона
Постройте классический алгоритм решения задачи Саймона. Докажите, что он работает за \(O(2^{n/2})\).
Докажите, что \((x \oplus s) \cdot y = (x \cdot y) \oplus (s \cdot y)\)
Алгоритм Гровера
Докажите, что условный сдвиг фазы в реализации оператора Гровера можно записать в виде:
\begin{equation*} 2 |0 \rangle \langle 0 | - I \end{equation*}Реализуйте условный сдвиг фазы, используя стандартные гейты X,Y,Z,H и контролируемые операции.
Докажите, что оператор Гровера \(G\) можно записать следующим образом:
\begin{equation*} G = 2 |\Psi_0 \rangle \langle \Psi_0 | - I \end{equation*}Квантовое преобразование Фурье
Взяв за основу make_qft, реализуйте обратное преобразование Фурье (в нём отличаются только знак угла поворота):
def make_qft_inverse(qubits): # your code here! pass