微分可能な量子回路探索

概要

量子回路の探索という離散的な問題（組み合わせ最適化問題）を、確率モデルを用いて連続的な問題として最適化する手法の提案です[1]

タイトル
Differentiable Quantum Architecture Search
著者
S.-X. Zhang, C.-Y. Hsieh, S. Zhang, H. Yao
リンク
http://arxiv.org/abs/2010.08561

背景

VQEやQAOAなどのNISQ向けアルゴリズムを実機で実行し有用な結果を得るためには、より少ない量子ゲート（演算子）数で所望の結果（エネルギーなど）が得られるように量子回路を最適化することが重要です。量子回路の最適化は回路のどの位置にどのゲートを当てはめるかという離散的な問題（組み合わせ最適化問題）です。従来の手法では貪欲法[2]や遺伝アルゴリズム[3]が使われますが、最適化に利用できるゲートが限られていたり、利用できるアルゴリズムが限られるために計算コストが高かったりします。

そこで本研究では量子回路のゲート選択を確率モデル（例：ボルツマンマシン、カテゴリカル分布）を用いて行うことで、回路探索という離散的な問題を確率モデルのパラメーター選択という連続的な問題に置き換えます。つまりパラメーターの変更により選択される回路が変わり、それに応じて対象とする目的関数の値が変化するため、目的関数の微分が可能となります。また本手法は、演算子の種類や目的関数の種類は目的に応じて自由に選択できるため、幅広いタスクへの応用が可能です。以下では、本手法の説明後、適用例としてMAXCUTの結果を示します。

手法

以下で本手法の説明を行います。初めに本手法の流れを示し、次に本手法のポイントである微分可能な回路最適化について説明します。そして具体的な回路生成の例を確率分布からのサンプリングの詳細を交えて説明し、最後に手法の各ステップと後処理について補足します。

本手法の流れは以下の4ステップです。また図1に流れの概要を示します。各ステップの英字と図1の赤英字は対応させてあります。

A) 演算子（ゲート）のプールを用意。
B) 確率モデルP({\bf k},{\bf \alpha})を用いて、プールから取り出す演算子の種類と順番を決定。
C) 目的関数Lを計算。各演算子のパラメーターは演算子の種類と順番を基にパラメータープール\bf{\theta}から取得。
D) Lの微分値を計算し、微分値を基に{\bf \alpha}と\bf{\theta}更新。Bに戻る。
以上を終了条件を満たすまで繰り返す。

{\bf k}と{\bf \alpha}はそれぞれ、回路の構造を決定する変数（数字列）と確率モデルのパラメーターです。

図1 提案手法の流れ（[1]を基に作成）

本手法のポイントは、ステップBで確率モデルを用いて回路構成を決定していることです。通常の回路最適化では、演算子の種類・位置は例えば「アダマールゲートを2bit目の1番初めに置く」のように離散的（組み合わせ的）に決定されます。しかし本手法では演算子の種類・位置を直接決めるのではなく、連続的なパラメーター{\bf \alpha}を持つ確率モデルP({\bf k},{\bf \alpha})を基に決定されます。具体的にはステップAで回路に入れたい演算子に番号を振っておき（図1だとe^{i\theta\sum X}は1番、e^{i\theta\sum Z}は2番、e^{i\theta\sum ZZ}は3番など）、ステップBで確率モデルから生成される数字列{\bf k}に応じて回路を決定します。ここで\sumはビットやビットの組み合わせに対する和です。例えば確率モデルから{\bf k}=(1,3,1)が得られたとすると、図1の設定だとU=e^{i\theta\sum X}e^{i\theta\sum ZZ}e^{i\theta\sum X}のようなユニタリ演算子Uを持つ回路が生成されます。イメージとしては回路の空きスロットに選択された演算子を入れていく感じです。そして回路Uが得られればで目的関数L（例：L=\langle 0|U^{\dagger}HU|0\rangle、Hはハミルトニアン）が取得できます（ステップC）。またパラメータ{\bf \alpha}（及び\bf{\theta}）は連続的に変化可能なので、Lの微分値\nabla_{{\bf \alpha}}L(及び\nabla_{\bf{\theta}}L)も計算できます（ステップD）。なお上記の説明ではP({\bf k},{\bf \alpha})から取得する回路は1つとして書きましたが、実際にはバッチ学習を行う関係でP({\bf k},{\bf \alpha})から多数の回路変数{\bf k}_i(i=1,2,...K)及び回路U_iを取得します（Kはバッチ数）。結局本手法では、連続的なパラメーター{\bf \alpha}を引数とする確率モデルP({\bf k},{\bf \alpha})によって回路構成が決まるため、回路最適化が連続的なパラメーター最適化の問題、つまり微分可能な問題として扱えるわけです。

ここで確率モデルP({\bf k},{\bf \alpha})からのサンプルを用いた回路生成について具体例を交えて説明します。まずP({\bf k},{\bf \alpha})はパラメーター{\bf \alpha}が決まると多数の回路構成{\bf k}_i(i=1,2,...K)を確率的に生成するものとみなせます。そして回路生成の具体例として演算子を入れるスロットが2種類、プール内の演算子が3種類の場合を考えます。この場合取りうる{\bf k}は(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)の9種類です。仮にある\bf{\alpha_0}では
$$
P({\bf k}=(1,1),{\bf\alpha_0})=0.9
$$
$$
P({\bf k}=(2,1),{\bf\alpha_0})=0.1　
$$
で残りのkでは全て確率0とします。ここで、この確率モデル(分布)に対してK=100個サンプルをとり、その結果を{\bf k}_i(i=1,2,...100)とします。すると{\bf k}_iのうち約90個は(1,1)、約10個は(2,1)となり、これで100個の回路構成が決定されました。あとはそれぞれの{\bf k}に対応する回路を作成すれば目的関数の値が求まります（値はサンプル平均します）。またパラメーターを\bf{\alpha_0}\rightarrow\bf{\alpha_1}と（連続的に）変更すれば別の確率分布が出て目的関数の値も変わります。このことからも、問題が微分可能であることが分かります。

最後に各ステップと計算の後処理について注意点を書きます。
ステップAではプールに入れられるユニタリ演算子にはパラメーターがなくても構いません。図1ではアダマールゲートもプールに入っています。これは例えばADAPT-VQE[2]ではパラメーター付き演算子のみしか演算子プールに入れられないのとは対称的で、本研究の大きなメリットです。
ステップBではバッチ学習を行う関係でP({\bf k},{\bf \alpha})から複数の{\bf k}_i(i=1,2,...K)を取得し、バッチサイズは数十から数百程度です。
ステップCでは演算子に当てはめるパラメーターの値は演算子の種類とスロット位置によって決定されます。具体的にはまずスロット数をp、演算子の総種類をc、演算子プールにおける各演算子のパラメーターの最大数をlとしてp\times c\times lサイズのパラメータープール\bf{\theta}を保持しておきます。そして演算子に当てはめる際には、\bf{\theta}から演算子の種類とスロット位置に対応する成分（最大要素数lのベクトル）を取り出して使用します。
ステップDは特筆すべきことはありませんが、解析微分や自動微分などを組み合わせれば計算が速くなります。
計算の後処理としては、終了条件を満たしたら最後にP({\bf k},{\bf \alpha})が最も高くなる{\bf k}を取り出し、必要に応じて\bf{\theta}を調整します。

結果

本手法をQAOAの回路が解となるMAXCUT問題へ適用し、生成される回路がQAOAの回路を再現するか確認しています。問題は8 node、3 degreeの制限グラフアンサンブルの学習です。目的関数はMAXCUTハミルトニアンの期待値です。スロット数pは5です。演算子プールは\bigotimes^n H,e^{i\theta\sum X}, e^{i\theta\sum Y}, e^{i\theta\sum Z}, e^{i\theta\sum ZZ}であり、以降それぞれH、rx、ry、rz、zzと書きます（nはビット数。lとcの値は論文中に書いてませんが演算子プールで決まります）。計算は約2000エポック行っています。選択した確率モデルP({\bf k},{\bf \alpha})は独立カテゴリカル確率モデルで、ソフトマックス関数から作成されます。
$$
P({\bf k},{\bf \alpha})=\prod_i^p{p(k_i,{\bf \alpha}i)}
$$
$$
p(k_i=j,{\bf \alpha}i)=\frac{e^{\alpha{ij}}}{\sum_k e^{\alpha{ik}}}
$$
{\bf \alpha}はモデルのパラメーター、k_i=jはi番目のスロットに演算子プールj番目の演算子を入れるという意味です。{\bf \alpha}の初期値は全て0、{\bf \alpha}の初期値は平均0標準偏差0.2のガウス分布から取得、オプティマイザは学習率0.1のAdamです。バッチサイズは64から512程度です。

図2 各トレーニングエポックにおける損失関数とQAOAレイアウトに対する確率（[1]を基に作成）

結果は図2の通りです。上図では学習が進むほど目的関数が解である-8.8に近づいています。最終的には確率モデルから解のQAOAと同じH、zz、rx、zz、rxのレイアウトを持つ回路が多く生成されました（バッチ学習のため一つの確率モデルから多数の回路が生成されます）。下図は確率モデルから上記のQAOAのレイアウトが生成される確率を表しており、最終的に1.0に近い値となりました。つまり生成されるレイアウトは殆どが解と同じレイアウトとなりました。よって本手法により、回路探索を連続的な問題に置き換えて最適化することが可能であることが示されました。

また今回紹介しきれませんでしたがMAXCUTの他にも、目的関数を忠実度とし回路のゲート間に演算子プールから選んだ1量子ゲートを挟むことでエラー緩和するよう最適化する、ということも論文中でなされていました。このように本手法はエネルギー最適化以外の様々な問題にも適用できることも重要な特徴です。

まとめ

本研究では確率モデルを用いることで回路探索という離散的な問題を連続的なパラメーターの問題に置き換えて回路最適化するアルゴリズムを提案しました。本手法は目的関数やゲートに関する制限はないため、様々な問題に適用することができます。例としてMAXCUT問題へ適用し（勾配に基づいた方法で最適化）、結果としてQAOAと同様な回路が得られました。この手法により連続的な問題向けのアルゴリズムと組み合わせた回路探索ができるようになるため、探索に使用できるアルゴリズムが一気に広がります。

参考文献

[1]: S.-X. Zhang, C.-Y. Hsieh, S. Zhang, and H. Yao, Differentiable Quantum Architecture Search, http://arxiv.org/abs/2010.08561.

[2]: H. R. Grimsley, S. E. Economou, E. Barnes, and N. J. Mayhall, An Adaptive Variational Algorithm for Exact Molecular Simulations on a Quantum Computer, Nat. Commun. 10, 3007 (2019).

[3]: D. Chivilikhin, A. Samarin, V. Ulyantsev, I. Iorsh, A. R. Oganov, and O. Kyriienko, MoG-VQE: Multiobjective Genetic Variational Quantum Eigensolver, http://arxiv.org/abs/2007.04424.