以下ではQAOAによって最適解が求められる理由を、周辺の知識も合わせて示します。

量子状態と重ね合わせの原理

量子状態は波動関数$\psi$によって表されます。ある量子状態$\psi$は別の量子状態$\psi_1, \psi_2, \cdots, \psi_n$の線型結合）で表すことができます。（重ね合わせの原理）
$$
\begin{align}
\psi = \sum_{i}^{n} c_{i} \psi_{i} = \sum_{i} a_{i} \quad(c_{i} \in C)
\end{align}
\tag{4}
$$

ブラケット記法

量子力学において量子状態を記述するための記法です。ある量子状態が複数の量子状態の線型結合で表される場合、その要素を列ベクトルの要素として並べたものがブラケット記法で表すものです。
次の式はケットベクトルと呼ばれるものです。量子状態を表すベクトルであることから状態ベクトルとも呼ばれます。
$$
\begin{align}
\label{ket}
\ket{\psi} = (a_0, a_1, \cdots, a_n)^\top
\end{align}
\tag{5}
$$
ケットベクトルの随伴行列（行列Aの各要素を複素共役な数をとり、さらに行列に転置を施したもの）はブラベクトルと呼ばれ、次の式で表されます。
$$
\begin{align}
\label{bra}
\bra{\psi} = \ket{\psi}^{\dagger} = (a_0^*, a_1^*, \cdots, a_n^*)
\end{align}
\tag{6}
$$

期待値

古典的な系の物理量$A$の期待値$\def\ev#1{\mathinner{\left\langle{#1}\right\rangle}} \ev{A}$は、確率密度関数$P(x)$を用いて次の式で定義されます。
$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
\def\ev#1{\mathinner{\left\langle{#1}\right\rangle}}
\begin{align}
\label{exp}
\ev{A} = \int_{-\infty}^{\infty} A P(x) dx
\end{align}
\tag{7}
$$
確率密度関数$P(x)$は以下の規格化条件を満たします。
$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
\def\ev#1{\mathinner{\left\langle{#1}\right\rangle}}
\begin{align}
\label{norm}
\int_{-\infty}^{\infty} P(x) dx = 1
\end{align}
\tag{8}
$$
さらにある量子状態$\ket{\psi(x)}$の確率密度関数$P(x)$は次の式で表されます
$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
\def\ev#1{\mathinner{\left\langle{#1}\right\rangle}}
\begin{align}
\label{prob}
P(x) = \ket{\psi(x)}^* \ket{\psi(x)} = \braket{\psi(x)}{\psi(x)}
\end{align}
\tag{9}
$$
天下り的ではありますが、物理量$A$が量子的な系の場合の期待値$\def\ev#1{\mathinner{\left\langle{#1}\right\rangle}}\ev{A}$は、その演算子を$\hat{A}$とした時、次の式で表されます。
$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
\def\ev#1{\mathinner{\left\langle{#1}\right\rangle}}
\begin{align}
\label{exp_q}
\ev{A}
&= \int_{-\infty}^{\infty} \hat{A} P(x) dx\\
&= \hat{A} \braket{\psi(x)}{\psi(x)}\\
\end{align}
\tag{10}
$$
ここで、演算子$\hat{A}$が$A$に対する固有値で、$\ket{\psi(x)}$がそれに対する固有ベクトルだとすると、固有ベクトルの定義より固有値と固有ベクトルの間には
$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
\def\ev#1{\mathinner{\left\langle{#1}\right\rangle}}
\begin{align}
\label{equ:eigen}
A \ket{\psi(x)} = \hat{A} \ket{\psi(x)}
\end{align}
\tag{11}
$$
が成立するので、量子的な物理量$A$の期待値$\def\ev#1{\mathinner{\left\langle{#1}\right\rangle}}\ev{A}$は次の式で表されます。
$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
\def\ev#1{\mathinner{\left\langle{#1}\right\rangle}}
\def\evv#1#2{\mathinner{\left\langle{#2}|{#1}|{#2}\right\rangle}}
\begin{align}
\label{equ:braket-exp-2}
\begin{split}
\ev{A}
&= \hat{A} \braket{\psi(x)}{\psi(x)}\\
&= \evv{\hat{A}}{\psi(x)}\\
&= \evv{A}{\psi(x)}\\
\end{split}
\end{align}
tag{12}
$$

変分法

ハミルトニアン$H$はエルミート行列であるため、その固有値$\lambda$は実数である。ハミルトニアン$H$に対する固有値を$E$とし、それに対する固有ベクトルを$\ket{\psi}$とする。さらに、固有値の最小値を$E_0$とし、それに対する固有ベクトルを$\ket{\psi_0}$とします。このとき、固有値と固有ベクトルの関係から次の式が成り立ちます。
$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
\def\ev#1{\mathinner{\left\langle{#1}\right\rangle}}
\def\evv#1#2{\mathinner{\left\langle{#2}|{#1}|{#2}\right\rangle}}
\begin{align}
\begin{split}
H\ket{\psi} &= E\ket{\psi}\\
H\ket{\psi_0} &= E_0\ket{\psi_0}
\end{split}
\end{align}
\tag{13}
$$
$E_0$は固有値の最小値であるため$E \ge E_0$です。よって任意の状態$\ket{\psi}$に対し、次の式が成り立ちます。

$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
\def\ev#1{\mathinner{\left\langle{#1}\right\rangle}}
\def\evv#1#2{\mathinner{\left\langle{#2}|{#1}|{#2}\right\rangle}}
\begin{align}
\evv{H}{\psi} \ge E_0
\end{align}
\tag{14}
$$

最適化問題に対するQAOA:Quantum Approximate Optimization Algorithm

以上で説明した内容を踏まえ、論文中でoriginal approachと紹介された手法について整理します。

• step1
  組合せ最適化問題を定式化し目的関数$C(z)$を作成
  $$
  \begin{align}
  \begin{split}
  C(\bm{z}) &= \sum_{\alpha=1}^m C_{\alpha}(\bm{z})\\
  \bm{z} &= (z_1, z_2, \cdots, z_n)
  \end{split}
  \end{align}
  \tag{15}
  $$
• step2
  初期状態
  $$
  \begin{align}
  \ket{\psi} = \frac{1}{\sqrt{2^n}} \sum_{\bm{z}} \ket{\bm{z}}
  \end{align}
  \tag{16}
  $$
  を作成
• step3
  初期状態に作用するユニタリ演算子を以下のように定義する。
  $$
  \begin{align}
  U(C,\gamma) = e^{-i\gamma C} = \prod_{\alpha=1}^m e^{-i\gamma C_{\alpha}}
  \end{align}
  \tag{17}
  $$
  $$
  \begin{align}
  \begin{split}
  U(C,\beta) &= e^{-i\beta B} = \prod_{j=1}^n e^{-i\beta \sigma_j^x}\\
  B &= \sum_{j=1}^n X_j
  \end{split}
  \end{align}
  \tag{18}
  $$
  また、初期状態に対しそれぞれ$p$個の$U(C,\gamma)$と$U(C,\beta)$を適用したものを次の式で表します。
  $$
  \begin{align}
  \begin{split}
  \ket{\bm{\gamma}, \bm{\beta}} = U(B,\beta_p)U(C,\gamma_p) \cdots U(B,\beta_1)U(C,\gamma_1) \ket{\psi}
  \end{split}
  \end{align}
  \tag{19}
  $$
  パラメータ$\beta, \gamma$に対して上式で定義した$\ket{\bm{\gamma}, \bm{\beta}}$を量子回路上で設計します。
• step4
  $C(z)$の期待値$\def\evv#1#2{\mathinner{\left\langle{#2}|{#1}|{#2}\right\rangle}} \evv{C(z)}{\bm{\gamma}, \bm{\beta}}$を量子コンピュータを用いて計算し、古典コンピュータで$C(z)$の期待値が小さくなるようにパラメータ$\beta, \gamma$を更新します。
• step5
  step2~step4を繰り返し、最適なパラメータ$\beta’, \gamma’$を得ます。得られた$\beta’, \gamma’$に対し$\ket{\bm{\gamma’}, \bm{\beta’}}$から$\bm{z}$を取得し、これが最適化問題の解となります。