Градиенты высших порядков

Автор(ы):

• Синченко Семен

План лекции

В этой лекции мы посмотрим на ту математику, которая лежит “под капотом” у parameter-shift rule. Мы познакомимся с обобщением parameter shift, а также увидим, как можно оптимизировать этот метод. В конце мы узнаем, как можно посчитать производную второго порядка за минимальное количество обращений к квантовому компьютеру.

Для более детального погружения в вопрос можно сразу рекомендовать статью [MBK21].

Важность гейтов вращений

Если задуматься, то одним из основных (если не единственных) способов сделать параметризованную квантовую схему является использование гейтов вращений, таких как \(\hat{RX}, \hat{RY}, \hat{RZ}\). Более формально это можно выразить так, что нас больше всего интересуют операторы вида:

\[ U(\theta) = e^{-\frac{i}{2}H\theta} \]

где \(H\) – оператор “вращения”, который удовлетворяет условию \(H^2 = \mathbf{1}\). Другой возможный вариант записи – представить матрицу \(H\) как линейную комбинацию операторов Паули \(\sigma^x, \sigma^y, \sigma^z\).

Если представить схему, содержащую множество параметризованных операторов, то итоговая запись имеет вид:

\[ U_{j...k} = U_j, ..., U_k \ket{\Psi} \]

Производная от измерения

Давайте вспомним, как выглядит квантово-классическая схема обучения с VQC.

Fig. 70 Квантово-классическая схема

Видно, что мы хотим считать производную не от самой параметризованной схемы \(U_{j...k}\), а от наблюдаемой. Для тех, кто забыл, что такое наблюдаемая, рекомендуем вернуться к лекции про кубит. Если кратко, то это тот оператор, который мы “измеряем” на нашем квантовом компьютере. Математически производная, которая нам интересна, может быть записана для выбранного параметра \(i\) таким образом:

\[ G_i = \frac{\partial \bra{U_{j...k}\Psi}\hat{M}\ket{U_{j...k}\Psi}}{\partial \theta_i} \]

То есть нам важно посчитать производную от результата измерения, так как именно результат измерения у нас будет определять “предсказание” нашей квантовой нейронной сети. Причем нам нужно уметь считать производную от любого параметра \(\theta_i\) в цепочке \(\theta_j, ...\theta_i, ...\theta_k\).

Parameter-shift для гейтов Паули

Note

Тут мы для простоты предложим, что \(U_1\) это просто оператор вращения, иначе выкладки станут совсем сложными.

Тогда сам оператор \(U_i\) может быть также записан так:

\[ U_i = e^{-\frac{i}{2}P_i\theta_i} \]

Запишем результат математического ожидания через состояние \(\Psi_i\), которое пришло на вход \(i\)-го гейта в нашей последовательности:

\[ \langle M(\theta) \rangle = Tr(M U_{k, ..., 1} \rho_i U_{k, ..., 1}^\dagger) \]

где \(\rho\) это матрица плотности (\(\ket{\Psi}\bra{\Psi}\)). Подробнее о матрицах плотности можно почитать в ранней продвинутой лекции про смешанные состояния.

Тогда частная производная от математического ожидания по \(i\)-му параметру \(\theta_i\) записывается (подробнее в [MNKF18]) через коммутатор исходного состояния \(\rho\), которое “пришло” на вход гейта \(U_i\) и того оператора Паули \(P_i\), который мы используем в \(U_i\):

\[ \frac{\partial \langle M \rangle}{\partial \theta_i} = -\frac{i}{2}Tr(M U_{k, ..., i}[P_i, U_{i-1, ..., 1}\rho_i U_{i-1, ..., 1}^\dagger]U_{k, ..., i}^\dagger) \]

Этот коммутатор может быть переписан следующим образом:

\[ [P_i, \rho] = i[U_i \Bigl( \frac{\pi}{2} \Bigr ) \rho_i U_i^\dagger \Bigl ( \frac{\pi}{2} \Bigr ) - U_i \Bigl( -\frac{\pi}{2} \Bigr ) \rho_i U_i^\dagger \Bigl ( -\frac{\pi}{2} \Bigr )] \]

Тогда соответствующий градиент \(\frac{\partial}{\partial \theta_i}\) можно записать через смещения на \(\pm\frac{\pi}{2}\):

\[\begin{split} \begin{gathered} \frac{\partial \langle M \rangle}{\partial \theta_i} = \frac{\langle M_i^+ \rangle - \langle M_i^- \rangle}{2} \\ \langle M_i^{\pm} \rangle = \frac{1}{2} Tr [M U_{k, ..., i+1} U_i(\pm \frac{\pi}{2})\rho_i^` U_i^\dagger (\pm \frac{\pi}{2}) U_{k, ..., i+1}^\dagger] \\ \rho_i^` = U_{j, ..., 1} \rho_i U_{j, ..., 1}^\dagger \end{gathered} \end{split}\]

По аналогии с классическими нейронными сетями и backpropagation (для тех, кто забыл это понятие, рекомендуем вернуться к вводным лекциями про классическое машинное обучение) тут явно можно выделить forward проход со смещением \(\theta_i\) на значения \(\frac{\pi}{2}\) и backward со смещением на \(-\frac{\pi}{2}\).

Обобщенный parameter-shift

Предложенное в [MNKF18] выражение может быть на самом деле получено в более общем виде из других соображений. Так, выражение для нашей наблюдаемой \(\langle M \rangle\) может всегда быть представлено [MBK21] как сумма вида:

\[ \bra{U_i(\theta_i)}\hat{M}\ket{U_i(\theta_i)} = \hat{A} + \hat{B}\cos{\theta_i} + \hat{C}\sin{\theta_i} \]

где \(\hat{A}, \hat{B}, \hat{C}\) – операторы, не зависящие от параметра \(\theta_i\).

Note

Действительно, явно выписав выражение для наблюдаемой и вспомнив формулы для косинуса и синуса двойного угла, а также воспользовавшись тем, что \(U(\theta) = e^{-\frac{1}{2}H\theta} = \cos{\frac{\theta}{2}}\mathbf{1} - i\sin{\frac{\theta}{2}}H\), получаем:

\[\begin{split} \begin{gathered} (\cos{\frac{\theta}{2}}\mathbf{1} + i\sin{\frac{\theta}{2}}H)\hat{M}(\cos{\frac{\theta}{2}}\mathbf{1} - i\sin{\frac{\theta}{2}}H) = \\ \cos^2{\frac{\theta}{2}}\hat{M} + i \sin{\frac{\theta}{2}}\cos{\frac{\theta}{2}}H\hat{M} - i \sin {\frac{\theta}{2}}\cos{\frac{\theta}{2}}\hat{M}H + \sin^2{\frac{\theta}{2}}H\hat{M}H = \\ \frac{1}{2} \cos{\theta}\hat{M}+\frac{1}{2}\hat{M}+\frac{i}{2} \sin{\theta}H\hat{M} - \frac{i}{2}\sin{\theta}\hat{M}H + \frac{1}{2}H\hat{M}H - \frac{1}{2}\cos{\theta}H\hat{M}H = \\ \frac{1}{2}(\hat{M} + H\hat{M}H) + \frac{1}{2}(\hat{M} - H\hat{M}H)\cos{\theta} + \frac{i}{2}(H\hat{M} - \hat{M}H)\sin{\theta} \end{gathered} \end{split}\]

Тогда можно воспользоваться правилами тригонометрии, а именно, тем что для любого \(s \neq k\pi, \text{ } k \in {1, 2, ..., }\) справедливо:

\[\begin{split} \begin{gathered} \frac{d \cos {\theta}}{d \theta} = \frac{\cos (\theta + s) - \cos (\theta - s)}{2\sin{s}} \\ \frac{d \sin {\theta}}{d \theta} = \frac{\sin (\theta + s) - \sin (\theta - s)}{2\sin{s}} \\ \end{gathered} \end{split}\]

И подставим это в выражение для \(\frac{\partial \langle M \rangle}{\partial \theta_i}\):

\[ \frac{\partial \langle M(\theta_i) \rangle}{\partial \theta_i} = \frac{\langle M(\theta_i + s) \rangle - \langle M(\theta_i - s) \rangle}{2\sin{s}} \]

Легко заметить, что подстановка сюда \(s = \frac{\pi}{2}\) дает нам классический parameter shift, описанный в [MNKF18].

Наконец, запишем полученное выражение в более удобном виде, который позволит нам более эффективно выписывать производные высших порядков. Для этого введем вектор \(\mathbf{e_i}\) – единичный вектор для \(i\)-го параметра, то есть вектор, где все компоненты кроме \(i\)-й равны нулю, а \(i\)-я равна 1. Тогда наше финальное выражение для обобщенного parameter shift примет следующий вид:

\[ \boxed{\frac{\partial f(\mathbf{\theta})}{\partial \theta_i} = \frac{f(\mathbf{\theta} + s\mathbf{e_i}) - f(\mathbf{\theta} - s\mathbf{e_i})}{2\sin{s}}} \]

Вторая производная и гессиан

В классической теории оптимизации, также как и в машинном обучении, очень часто на первый план выходят так называемые методы 2-го порядка. Эти методы похожи на обычный градиентный спуск, но для ускорения сходимости они также используют информацию из матрицы вторых производных, которая называется гессианом. Более подробно про методы 2-го порядка и гессиан можно посмотреть в вводных лекциях курса.

Методы второго порядка требуют больше вызовов, чтобы вычислить гессиан, но взамен они обеспечивают гораздо лучшую сходимость, а также менее склонны “застревать” в локальных минимумах. Это обеспечивает, в итоге, более быстрое обучение. В классических нейронных сетях вычисление гессиана это часто проблема, так как это матрица размерности \(\sim O(N^2)\), где \(N\) – число весов нейронной сети, и эта матрица получается слишком большой. Но, как мы помним, основная “фича” VQC это их экспоненциальная экспрессивность – возможность линейным числом параметров (и гейтов) обеспечить преобразование, эквивалентное экспоненциальному числу весов классической нейронной сети. А значит, для них проблема размерности гессиана не стоит так остро. При этом использование гессиана теоретически позволит в итоге обучить VQC за меньшее число вызовов. Именно поэтому методы второго порядка потенциально очень интересны в квантово-классическом обучении. Но для начала нам необходимо разобраться, как именно можно посчитать матрицу вторых производных.

Пользуясь обобщенным правилом parameter shift, можно выписать выражение для второй производной [MBK21]:

\[ \frac{\partial_2 f}{\partial \theta_i \theta_j} = \frac{f(\mathbf{\theta} + s_1\mathbf{e_i} + s_2\mathbf{e_j}) + f(\mathbf{\theta} - s_1\mathbf{e_i} - s_2 \mathbf{e_j}) - f(\mathbf{\theta} + s_1 \mathbf{e_i} - s_2 \mathbf{e_j}) - f(\mathbf{\theta} - s_1 \mathbf{e_i} + s_2 \mathbf{e_j})}{4\sin{s_1}\sin{s_2}} \]

Взяв \(s_1 = s_2\), можно упростить это выражение к следующему виду:

\[\begin{split} \begin{gathered} \frac{f(\mathbf{\theta} + s\mathbf{a}) + f(\mathbf{\theta} + s\mathbf{b}) - f(\mathbf{\theta} + s\mathbf{c}) - f(\mathbf{\theta} + s\mathbf{d})}{(2\sin{s}) ^2} \\ \mathbf{a} = \mathbf{e_i} + \mathbf{e_j} \\ \mathbf{b} = -\mathbf{e_i} - \mathbf{e_j} \\ \mathbf{c} = \mathbf{e_i} - \mathbf{e_j} \\ \mathbf{d} = -\mathbf{e_i} + \mathbf{e_j} \end{gathered} \end{split}\]

Но чаще всего нам необходимо не просто посчитать гессиан, а еще и посчитать градиент, так как в большинстве методов 2-го порядка требуются оба эти значения. В этом случае хочется попробовать подобрать такое значение для \(s_g\) при вычислении вектора градиента, а также такое значение \(s_h\) при вычислении гессиана, чтобы максимально переиспользовать результаты квантовых вызовов и уменьшить их общее количество.

Внимательно взглянув на выражение для 2-х производных, можно заметить, что оптимизация там возможна при расчете диагональных элементов гессиана. Давайте выпишем выражение для диагонального элемента явно:

\[ \frac{f(\mathbf{\theta} + 2s\mathbf{e_i}) + f(\mathbf{\theta} - 2s\mathbf{e_i}) - 2 f(\mathbf{\theta})}{(2\sin{s})^2} \]

Можно заметить, что, например, использование \(s = \frac{\pi}{4}\) для гессиана, а также “стандартного” \(s=\frac{\pi}{2}\) для градиента позволит полностью переиспользовать в диагональных элементах гессиана значения, которые мы получили при расчете градиента. А значение \(f(\mathbf{\theta})\) вообще считается один раз для всех диагональных вызовов.

Note

На самом деле, диагональные элементы гессиана можно использовать и сами по себе, например для квазиньютоновских методов оптимизации, где матрица Гессе аппроксимируется какой-то другой матрицей, чтобы не считать все вторые производные. Например, она может быть аппроксимирована диагональной матрицой, как в работе [And19].

Заключение

В этой лекции мы познакомились с классическим parameter shift rule, а также его обобщением. Также мы узнали, как можно посчитать гессиан VQC, и даже узнали маленькие хитрости, которые можно применять для уменьшения общего количества вызовов квантовой схемы.