量子情報における半正定値計画問題 1. 半正定値計画問題の基礎

はじめに

量子情報で現れる量子状態と測定は、どちらも複素ヒルベルト空間の線形演算子なのですが、さらにどちらも半正定値演算子です。したがって、あるタスクを最適にこなす量子状態あるいは量子測定を探したい、という問題は、自然と「半正定値計画問題(Semidefinite Programming, SDP)」と呼ばれる問題になることが多いです。本シリーズ「量子情報における半正定値計画問題」では、量子情報理論に半正定値計画問題がどのように使われているか、数値計算をどのようにするかといった話を記載します。

本稿「1. 半正定値計画問題の基礎」ではまず、半正定値計画問題のざっくりとした(おそらく厳密ではない)整理を行います。コメント大歓迎です！

参考文献

[1] Watrous, The Theory of Quantum Information (Cambridge University Press, Cambridge, UK, 2018).

[2]寒野善博，土谷隆，『最適化と変分法』，東京大学工学教程編纂委員会（編），丸善出版，2014．

本稿では[1]の1.2.3節の半正定値計画問題のまとめの内容を、[2]などを読んで得た知見をもとに自分なりに数式や言葉を補って解説します。

表記

ここでは主に、半正定値演算子、量子状態、量子通信路、POVM測定などに対して使用する表記を整理します。各々の詳細は教科書を参照ください。(早速[1]と違っていてすみません笑)

表記	意味
$\mathrm{A}$（立体の大文字）	量子系
$\mathcal H_\mathrm{A}$	量子系$\mathrm{A}$に付随する複素ヒルベルト空間（有限次元を仮定）
$\mathcal{L}(\mathcal H_\mathrm{A},\mathcal H_\mathrm{B})$	$\mathcal H_\mathrm{A}$から$\mathcal H_\mathrm{B}$への線形演算子の集合
$\mathcal{L}(\mathcal H_\mathrm{A})$	$\mathcal H_\mathrm{A}$から$\mathcal H_\mathrm{A}$の線形演算子の集合
$\mathcal L_\mathrm{Her}(\mathcal H_\mathrm{A})$	$\mathcal H_\mathrm{A}$のエルミート演算子の集合
$X_\mathrm{A}\succeq 0_\mathrm{A}$	$X_\mathrm{A}\in\mathcal L_\mathrm{Her}(\mathcal H_\mathrm{A})$が半正定値演算子
$X_\mathrm{A}\succ 0_\mathrm{A}$	$X_\mathrm{A}\in\mathcal L_\mathrm{Her}(\mathcal H_\mathrm{A})$が正定値演算子
$X_\mathrm{A}\succeq Y_\mathrm{A}$, $X_\mathrm{A}\succ Y_\mathrm{A}$	$X_\mathrm{A}-Y_\mathrm{A}\succeq 0_\mathrm{A}$, $X_\mathrm{A}-Y_\mathrm{A}\succ 0_\mathrm{A}$
$\mathscr T(\mathrm{A}\to\mathrm{B})$($\mathscr T$は花文字のT)	$\mathcal{L}(\mathcal H_\mathrm{A})$から$\mathcal{L}(\mathcal H_\mathrm{A})$への線形写像の集合

半正定値計画問題とそのラグランジュ双対問題

主問題の標準形

[1]をベースに、半正定値計画問題の標準形として以下の問題を掲げます。
与えられた$J_\mathrm{A}\in\mathcal L_\mathrm{Her}(\mathcal H_\mathrm{A}), K_\mathrm{B}\in\mathcal L_\mathrm{Her}(\mathcal H_\mathrm{A})$およびエルミート性保存写像$\Phi_{\mathrm{A}\to\mathrm{B}}\in\mathscr T(\mathrm{A}\to\mathrm{B})$に対して、

\begin{align}
\underset{X_\mathrm{A}}{\text{Maximize}}\quad &\mathrm{Tr}[J_\mathrm A X_\mathrm A]\\
\text{subject to}\quad &\Phi_{\mathrm{A}\to\mathrm{B}}(X_\mathrm A)=K_\mathrm B\\
\quad &X_\mathrm A\succeq 0_\mathrm A.
\end{align}

以下でこの問題の双対問題というものを導出するので、この問題を「主問題」と呼びます。

ラグランジュ双対問題

上の半正定値計画問題の標準形は最大化をしていますが、その最適値を上から抑えることのできる最小化問題をシステマチックに導出できます。まず、ラグランジアンと呼ばれる関数を定義します。

L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A):=
\begin{cases}
\mathrm{Tr}[J_\mathrm A X_\mathrm A]+\mathrm{Tr}[Y_\mathrm{B}\{K_\mathrm{B}-\Phi_{\mathrm{A}\to\mathrm{B}}(X_\mathrm A)\}]+\mathrm{Tr}[Z_\mathrm{A}X_\mathrm{A}]\quad &(Z_\mathrm A\succeq 0_\mathrm A)\\
+\infty\quad &(\text{otherwise}).
\end{cases}

ここで導入した$Y_\mathrm{B}, Z_\mathrm A$のことを「ラグランジュ未定乗数」といいます。注意として、今の段階で$X_\mathrm A$は一般のエルミート行列で、半正定値に限りません。半正定値の制約が後から自然に入ってくることを見ます。

$\inf_{Y_\mathrm B,Z_\mathrm A}L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)$を計算すると、以下のようになります。

\inf_{Y_\mathrm B,Z_\mathrm A}L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)=
\begin{cases}
    \mathrm{Tr}[J_\mathrm A X_\mathrm A]\quad (\Phi_{\mathrm{A}\to\mathrm{B}}(X_\mathrm A)=K_\mathrm B,X_\mathrm A\succeq0_\mathrm A)\\
    -\infty\quad (\text{otherwise}).
\end{cases}

実際に確認してみましょう。まず$Z_\mathrm{A}$でinfを取るので、いつでも$+\infty$となる$Z\nsucceq 0_\mathrm{A}$ではなく、$Z_\mathrm A\succeq 0_\mathrm{A}$の場合を考えます。この場合において、今は$Y_\mathrm B$を好きに、$Z_\mathrm A$も$Z_\mathrm A\succeq 0_\mathrm{A}$の範囲で好きに動かせるので、$K_\mathrm{B}-\Phi_{\mathrm{A}\to\mathrm{B}}(X_\mathrm A)=0_\mathrm{A},X_\mathrm A\succeq0_\mathrm A$が成り立っていない場合はいくらでもラグランジアンを小さく取れてしまいます。このようにして無事、$K_\mathrm{B}-\Phi_{\mathrm{A}\to\mathrm{B}}(X_\mathrm A)=0_\mathrm{A},X_\mathrm A\succeq0_\mathrm A$という制約を$\inf_{Y_\mathrm B,Z_\mathrm A}L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)$の中に入れることができました。

以上より、オリジナルの最適化問題はラグランジアンを使って以下のように書けます。

\sup_{X_\mathrm{A}}\inf_{Y_\mathrm B,Z_\mathrm A}L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A).

そして双対問題は、このsupとinfを入れ替えた以下の問題です。

\inf_{Y_\mathrm B,Z_\mathrm A}\sup_{X_\mathrm{A}}L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A).

これを制約条件付き双対問題に書き換えていきましょう。$Z_\mathrm A\succeq 0_\mathrm A$のラグランジアンは以下のように書き直すことができます。

L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)=\mathrm{Tr}[K_\mathrm B Y_\mathrm B]+\mathrm{Tr}[(J_\mathrm A-\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm B)+Z_\mathrm A)X_\mathrm A]

ラグランジアンの世界では$X_\mathrm A$は半正定値のような制約のない、一般のエルミート演算子であることに再度注意すると、$J_\mathrm A-\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm B)+Z_\mathrm A$が$0_\mathrm A$でないと、第二項が$X_\mathrm A$に対するsupで無限大に発散します。つまり

\sup_{X_\mathrm{A}}L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)=
\begin{cases}
    \mathrm{Tr}[K_\mathrm B Y_\mathrm B]\quad &(J_\mathrm A-\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm B)+Z_\mathrm A=0_\mathrm{A})\\
    +\infty \quad &(\text{otherwise})
\end{cases}

更に$Z_\mathrm A\succeq 0_\mathrm A$であったことをここに追加すると、以下のような双対問題が得られます。与えられた$J_\mathrm{A}\in\mathcal L_\mathrm{Her}(\mathcal H_\mathrm{A}), K_\mathrm{B}\in\mathcal L_\mathrm{Her}(\mathcal H_\mathrm{A})$およびエルミート性保存写像$\Phi_{\mathrm{A}\to\mathrm{B}}\in\mathscr T(\mathrm{A}\to\mathrm{B})$に対して、

\begin{align}
\underset{Y_\mathrm{B}\in\mathcal L_\mathrm{Her}(\mathcal H_\mathrm B)}{\text{Minimize}}\quad &\mathrm{Tr}[K_\mathrm B Y_\mathrm B]\\
\text{subject to}\quad &\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm B)\succeq J_\mathrm A
\end{align}

弱双対性と強双対性

どのような$X_\mathrm A,Y_\mathrm B,Z_\mathrm A$にたいしても、$\inf_{Y_\mathrm B,Z_\mathrm A}L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)\le L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)$が成り立ちます。したがって、どのような$X_\mathrm A,Y_\mathrm B,Z_\mathrm A$にたいしても、$\inf_{Y_\mathrm B,Z_\mathrm A}L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)\le \sup_{X_\mathrm A}L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)$となります。ここから、以下の不等式を得ます。

\sup_{X_\mathrm{A}}\inf_{Y_\mathrm B,Z_\mathrm A}L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)\le \inf_{Y_\mathrm B,Z_\mathrm A}\sup_{X_\mathrm{A}}L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A).

これは、双対問題の最適値は主問題よりも小さくはならないことを意味します。これを「弱双対性」と呼びます。弱双対性はこのようにいつでも成り立っているのですが、さらに両者の最適値が一致するとき、これを「強双対性」といいます。強双対性が成り立つための十分条件を以下で述べます。

※主問題がmaximizeだったから、双対問題の最適値が主問題のそれ以上になっています。主問題がminimizeだったら、双対問題の最適値は主問題それ以下になります。

スレーターの定理

さて、主問題と双対問題の最適値を以下のように書きましょう。

\begin{align}
\alpha&:=\sup_{X_\mathrm A\in\mathcal P_\mathrm{F}} \mathrm{Tr}[J_\mathrm{A}X_\mathrm{A}],\\
\beta&:=\inf_{Y_\mathrm B\in\mathcal D_\mathrm{F}}\mathrm{Tr}[K_\mathrm{B}Y_\mathrm{B}].
\end{align}

ここで

\begin{align}
\mathcal P_\mathrm{F}&:=\{X_\mathrm{A}\in\mathcal L_{\mathrm{Her}}(\mathcal H_\mathrm A)|\Phi_{\mathrm{A}\to\mathrm{B}}(X_\mathrm A)=K_\mathrm B,X_\mathrm{A}\succeq 0_\mathrm{A}\},\\
\mathcal D_\mathrm{F}&:=\{Y_\mathrm{B}\in\mathcal L_{\mathrm{Her}}(\mathcal H_\mathrm B)|\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm B)\succeq J_\mathrm{A}\}
\end{align}

は主問題と双対問題の実行可能解の集合です。

強双対性は「スレーター条件」の下で成り立つことが知られています([1]のTheorem 1.18も参照)。

• 主問題の最適値$\alpha$が有限、かつ双対問題が内点実行可能解を持つ(つまり$\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm B)\succ J_\mathrm{A}$となる解がある)ならば、主問題と双対問題の最適値は一致。さらにこのとき、主問題の$\sup_{X_\mathrm A}$のsupを達成する解が存在する。
• 双対問題の最適値$\beta$が有限、かつ主問題が内点実行可能解を持つ($X_\mathrm{A}\succ 0_\mathrm{A}$という解がある)ならば、主問題と双対問題の最適値は一致。さらにこのとき、双対問題の$\inf_{Y_\mathrm B}$のinfを達成する解が存在する。

量子情報で出くわすSDPの中にはしばしば、主問題が内点実行可能ではないこともあります(フルランクの行列では制約条件を満たせないことがあったりする)。この場合、双対問題が内点実行可能解を持つことを示せれば、スレーターの定理から強双対性および主問題の最適解の存在を示せる、といったことがあります。つまり、主問題に最適解があることを知るために、双対問題を利用できるという点で、双対問題が単なる言い換えではないということがわかります。

ちなみにしばしば論文で、双対問題が内点実行可能解を持つのでスレーターの定理から強双対性が成り立っていることを述べてから、双対問題側の最適解を利用して証明を進めてしまうのを見かけるのですが、これは厳密には問題だと思います。というのも、スレーターの定理が保証するのは双対問題が内点実行可能解をもつなら主問題に最適解が存在する、ということだけであり、双対問題に最適解があるかどうかはわからないからです。こういう場合、双対問題の最適解を利用する証明は適切でなく、最適値よりも$ε(>0)$だけずれた$ε$-最適解を利用して議論を進め、最後に$ε\to 0$の極限をとる、という議論をするべきだと思います。

カルーシュ-クーン-タッカー条件

さて、上で述べたスレーター条件が成り立ち、強双対性が成り立ち、かつ主問題も双対問題も最適解がある場合を想定します。このとき、ある解が最適解であるための必要十分条件がカルーシュ-クーン-タッカー(KKT)条件で、それは以下の4つです。

• 主問題の実行可能性
• 双対問題の実行可能性
• 相補スラック性 (complementary slackness)
• 停留性 (stationarity)

最初の２つは良いかと思いますが、3番目と4番目について見ていきます。

双対問題の導出の際に「$J_\mathrm A-\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm B)+Z_\mathrm A=0_\mathrm A$でないと$X_\mathrm A$でinfを取るときにいくらでも小さくなる」というところから$\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm B)\succeq J_\mathrm A$というのが出てきましたが、この$Z_\mathrm A$、すなわち

Z_\mathrm A=\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm B)-J_\mathrm A

を「スラック変数」と呼びます。

相補スラック性

相補スラック性は

\mathrm{Tr}[Z_\mathrm A X_\mathrm A]=0

というものです。ただし、$Z_\mathrm A\succeq 0_\mathrm A$なので$Z^{1/2}_\mathrm A$をつかって

\mathrm{Tr}[Z^{1/2}_\mathrm A X_\mathrm A Z^{1/2}_\mathrm A]=0

とでき、さらに$X_\mathrm{A}\succeq 0_\mathrm{A}$でもあったので

Z^{1/2}_\mathrm{A} X_\mathrm{A} Z^{1/2}_\mathrm{A}\succeq 0_\mathrm{A}

ですから、相補スラック性は結局トレースを除いて

Z^{1/2}_\mathrm{A}X_\mathrm{A}Z^{1/2}_\mathrm{A}=0_\mathrm A

あるいは

Z_\mathrm A X_\mathrm A=0_\mathrm{A}

が成り立つということです。スラック変数と主問題の変数の積がゼロと言うのはどういうことかというと、「主問題の変数の正定値性$X_\mathrm A\succ 0_\mathrm A$と、双対問題の制約がstrict$\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm B)\succ J_\mathrm A$になる、という２つの条件が、最適ならば同時に満たされることはない」ということです。主問題も双対問題も変数に"余裕"がある(不等式がstrict)だと、まだ改善の余地があるというイメージです。逆に言えば、相補スラック性の成立は改善の余地が潰されているイメージです。

停留条性

ラグランジアンの$X_\mathrm A$に対する微分を考えます。ラグランジアンが

L(X_\mathrm A+\epsilon\Delta X_\mathrm A, Y_\mathrm B, Z_\mathrm A)=L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)+\epsilon \mathrm{DF}(X_\mathrm A)[\Delta X_\mathrm A]+o(\epsilon)

こう書けるとき、$\mathrm{DF}(X_\mathrm A)$を$X_\mathrm A$でのフレシェ微分、$\mathrm{DF}(X_\mathrm A)[\Delta X_\mathrm A]$はフレシェ微分を$\Delta X_\mathrm A$方向に適用したものです。

双対問題の導出のところでラグランジアンを

L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)=\mathrm{Tr}[K_\mathrm B Y_\mathrm B]+\mathrm{Tr}[(J_\mathrm A-\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm B)+Z_\mathrm A)X_\mathrm A]

と書き直しました。すると$L(X_\mathrm A+\epsilon\Delta X_\mathrm A, Y_\mathrm B, Z_\mathrm A)$はトレースの線形性から

L(X_\mathrm A+\epsilon\Delta X_\mathrm A, Y_\mathrm B, Z_\mathrm A)=L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)+\epsilon \mathrm{Tr}[(J_\mathrm A-\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm B)+Z_\mathrm A)\Delta X_\mathrm A]

となるわけなので、

\mathrm{DF}(X_\mathrm A)[\Delta X_\mathrm A]=\mathrm{Tr}[(J_\mathrm A-\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm B)+Z_\mathrm A)\Delta X_\mathrm A]

です。ようやく準備が揃いましたが、停留性条件は「$\mathrm{DF}(X_\mathrm A)[\Delta X_\mathrm A]$がすべての方向$\Delta X_\mathrm A$でゼロ」ということです。それはすなわち$J_\mathrm A-\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm B)+Z_\mathrm A=0_\mathrm A$ですね。

ところで双対問題は、$J_\mathrm A-\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm B)+Z_\mathrm A=0_\mathrm A$でないと、$X_\mathrm A$でinfを取ると$-\infty$になってしまうのを防ぐという流れで出てきたのですが、この部分が結局停留条件と同じものを与えています。

制約想定

最初に、スレーター条件の成立を想定してからKKT条件の説明をしましたが、このスレーター条件が成立しているという想定を、「制約想定」といいます。KKT条件が最適解の必要十分条件となるような想定がスレーター条件に限られるわけではどうもないようで、他にもいろんな制約想定があるようです(ここはまだ勉強中)。

まとめ

半正定値計画問題の標準形を主問題として、そのラグランジュ双対問題の導出、弱双対性、強双対性の十分条件としてのスレーター条件、スレーター条件の成立を想定したもとで最適解の必要十分条件としてのKKT条件を紹介しました。

補足

これまでは主問題がmaximizeの場合の手続きを踏んでいますが、主問題がminimizeの場合、ラグランジアンは

L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A):=
\begin{cases}
\mathrm{Tr}[J_\mathrm A X_\mathrm A]-\mathrm{Tr}[Y_\mathrm{B}\{K_\mathrm{B}-\Phi_{\mathrm{A}\to\mathrm{B}}(X_\mathrm A)\}]-\mathrm{Tr}[Z_\mathrm{A}X_\mathrm{A}]\quad &(Z_\mathrm A\succeq 0_\mathrm A)\\
-\infty\quad &(\text{otherwise}).
\end{cases}

と定義され

\sup_{Y_\mathrm B,Z_\mathrm A}L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)=
\begin{cases}
\mathrm{Tr}[J_\mathrm A X_\mathrm A]\quad &(\Phi_{\mathrm{A}\to\mathrm{B}}(X_\mathrm A)=K_\mathrm B,X_\mathrm A\succeq0_\mathrm A)\\
+\infty\quad &(\text{otherwise})
\end{cases}

となるので主問題は

\inf_{X_\mathrm{A}}\sup_{Y_\mathrm B,Z_\mathrm A}L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)

双対問題は

\sup_{Y_\mathrm B,Z_\mathrm A}\inf_{X_\mathrm{A}}L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)

となります。$Z_\mathrm{A}\succeq 0_\mathrm{A}$の場合のラグランジアンを

L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)=-\mathrm{Tr}[Y_\mathrm{B}K_\mathrm{B}]+\mathrm{Tr}[\{J_\mathrm{A}+\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm{B})-Z_\mathrm A\}X_\mathrm{A}]

と書き換えれば、

\inf_{X_\mathrm{A}}L(X_\mathrm A, Y_\mathrm B, Z_\mathrm A)=
\begin{cases}
-\mathrm{Tr}[Y_\mathrm{B}K_\mathrm{B}]\quad&(J_\mathrm{A}+\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm{B})-Z_\mathrm A=0_\mathrm{A})\\
-\infty\quad &(\text{otherwise})
\end{cases}

で、$Z_\mathrm{A}\succeq 0_\mathrm{A}$に注意すれば、制約付き双対問題が得られます。ただし$-Y_\mathrm{B}$を$Y_\mathrm{B}$と取り直すことで形がきれいになって、最終的に、与えられた$J_\mathrm{A}\in\mathcal L_\mathrm{Her}(\mathcal H_\mathrm{A}), K_\mathrm{B}\in\mathcal L_\mathrm{Her}(\mathcal H_\mathrm{A})$およびエルミート性保存写像$\Phi_{\mathrm{A}\to\mathrm{B}}\in\mathscr T(\mathrm{A}\to\mathrm{B})$に対して、

\begin{align}
\underset{Y_\mathrm{B}\in\mathcal L_{\mathrm{Her}}(\mathcal H_\mathrm{A})}{\text{Maximize}}\quad &\mathrm{Tr}[Y_\mathrm B K_\mathrm B]\\
\text{subject to}\quad &\Phi^\dagger_{\mathrm{A}\to\mathrm{B}}(Y_\mathrm{B})\preceq J_\mathrm{A}
\end{align}