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

Автор(ы):

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

План лекции

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

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

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

Если задуматься, то одним из основных (если не единственных) способов сделать параметризованную квантовую схему является использование гейтов вращений, таких как $\widehat{RX},\widehat{RY},\widehat{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|\mathrm{\Psi }⟩$$

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

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

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

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

$$G_i=\frac{\partial ⟨U_{j...k}\mathrm{\Psi }|\hat{M}|U_{j...k}\mathrm{\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}$$

Запишем результат математического ожидания через состояние ${\mathrm{\Psi }}_i$, которое пришло на вход $i$-го гейта в нашей последовательности:

$$⟨M(\theta )⟩=Tr(M{U}_{k,...,1}{\rho }_i{U}_{k,...,1}^{†})$$

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

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

$$\frac{\partial ⟨M⟩}{\partial {\theta }_i}=-\frac{i}{2}Tr(M{U}_{k,...,i}[P_i,U_{i-1,...,1}{\rho }_i{U}_{i-1,...,1}^{†}]U_{k,...,i}^{†})$$

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

$$[P_i,\rho ]=i[U_i(\frac{\pi }{2}){\rho }_i{U}_i^{†}(\frac{\pi }{2})-U_i(-\frac{\pi }{2}){\rho }_i{U}_i^{†}(-\frac{\pi }{2})]$$

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

$$\begin{array}{r}\begin{array}{c}\frac{\partial ⟨M⟩}{\partial {\theta }_i}=\frac{⟨M_i^{+}⟩-⟨M_i^{-}⟩}{2}\\ ⟨M_i^{\pm }⟩=\frac{1}{2}Tr[M{U}_{k,...,i+1}{U}_i(\pm \frac{\pi }{2}){\rho }_i^{‘}{U}_i^{†}(\pm \frac{\pi }{2})U_{k,...,i+1}^{†}]\\ {\rho }_i^{‘}=U_{j,...,1}{\rho }_i{U}_{j,...,1}^{†}\end{array}\end{array}$$

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

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

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

$$⟨U_i({\theta }_i)|\hat{M}|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{array}{r}\begin{array}{c}(\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{array}\end{array}$$

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

$$\begin{array}{r}\begin{array}{c}\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{array}\end{array}$$

И подставим это в выражение для $\frac{\partial ⟨M⟩}{\partial {\theta }_i}$:

$$\frac{\partial ⟨M({\theta }_i)⟩}{\partial {\theta }_i}=\frac{⟨M({\theta }_i+s)⟩-⟨M({\theta }_i-s)⟩}{2\sin s}$$

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

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

$$\boxed{{\displaystyle \frac{\partial f(\theta )}{\partial {\theta }_i}=\frac{f(\theta +s{\mathbf{e}}_{\mathbf{i}})-f(\theta -s{\mathbf{e}}_{\mathbf{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(\theta +s_1{\mathbf{e}}_{\mathbf{i}}+s_2{\mathbf{e}}_{\mathbf{j}})+f(\theta -s_1{\mathbf{e}}_{\mathbf{i}}-s_2{\mathbf{e}}_{\mathbf{j}})-f(\theta +s_1{\mathbf{e}}_{\mathbf{i}}-s_2{\mathbf{e}}_{\mathbf{j}})-f(\theta -s_1{\mathbf{e}}_{\mathbf{i}}+s_2{\mathbf{e}}_{\mathbf{j}})}{4\sin s_1\sin s_2}$$

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

$$\begin{array}{r}\begin{array}{c}\frac{f(\theta +s\mathbf{a})+f(\theta +s\mathbf{b})-f(\theta +s\mathbf{c})-f(\theta +s\mathbf{d})}{(2\sin s{)}^2}\\ \mathbf{a}={\mathbf{e}}_{\mathbf{i}}+{\mathbf{e}}_{\mathbf{j}}\\ \mathbf{b}=-{\mathbf{e}}_{\mathbf{i}}-{\mathbf{e}}_{\mathbf{j}}\\ \mathbf{c}={\mathbf{e}}_{\mathbf{i}}-{\mathbf{e}}_{\mathbf{j}}\\ \mathbf{d}=-{\mathbf{e}}_{\mathbf{i}}+{\mathbf{e}}_{\mathbf{j}}\end{array}\end{array}$$

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

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

$$\frac{f(\theta +2s{\mathbf{e}}_{\mathbf{i}})+f(\theta -2s{\mathbf{e}}_{\mathbf{i}})-2f(\theta )}{(2\sin s{)}^2}$$

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

Note

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

Заключение

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