Googleの最新SycamoreプロセッサでのQAOA組合せ最適化問題の論文の解説

勉強会で読んだのですが、比較的面白かったのと、現在の技術の限界が見れますのでお勧めです。中身を読み解いてみたいと思います。

量子の性質を利用したコンピュータです。これまでは実機がありませんでしたが、2015年前後から一般に公開され使われるようになってきました。

現在の量子コンピュータではそんなにたくさんは動くソフトウェアが発見されていません。

1985年以降ハードウェア不在のまま開発が進んだ量子アルゴリズムのうち、量子位相推定アルゴリズムが2015年以降のgoogle/IBMの実機マシンでのNISQアルゴリズムのVQEとして発展しています。VQEは量子古典ハイブリッドシステムで、量子コンピュータと古典コンピュータを直列でつなぎます。

今回のGoogleのQAOA論文は、2012年以降のカナダのD-Wave社というベンチャー企業の専用機から発展した、組合せ最適化問題をGoogle/IBMマシンで動かすというものの集大成のようなものです。

この最新論文を読むと2020年現在の科学技術の最先端がわかります。

量子断熱計算というアルゴリズムのうちで、Transverse-field Ising Modelを使ったものです。D-Wave社のマシンではアナログ実装されていましたが、今回のGoogleマシンではこのステップがデジタル実装されています。

初期ハミルトニアンからスタートし、求めたい問題のハミルトニアンに入れ替えていきます。

初期状態は初期ハミルトニアンXの固有状態である|+>状態を選択します。勉強会で質問がありましたが、$\otimes$はテンソル積なので、Xハミルトニアンが量子ビット個別に適用されています。

今回は最終のハミルトニアンの固有値、固有状態を求めますが、量子古典ハイブリッド計算では、変分原理を利用します。固有値を求める際に、ハミルトニアンの期待値は固有値を下回らないということで、ランダムに生成した状態ベクトルを勾配計算で最適化し、大域最適解を求めていきます。

問題を効率的に解くためのAnsatzと呼ばれる量子回路を準備し、その計算結果から行列の期待値を計算します。その後、期待値を小さくするために最適化計算を利用し、量子回路内部の角度パラメータを最適化します。

これを繰り返し、ある程度期待値が小さくなるまで続けます。

近代のエラーの多いマシンをNISQと言います。課題はエラーが多いので長い回路の実行が難しいところです。

VQEでは、ハミルトニアンのエルミート行列をトロッタ展開ではなく、ユニタリ行列に分けて個別に計算し、集計することで回路が長くなることを避けています。

量子断熱計算はスタートからゴールまで時間発展と呼ばれる手法を用いて、シミュレーションされます。

量子状態を時間変化させるには、ハミルトニアンを指数の肩に導入した時間発展演算子を利用します。

ハミルトニアンにはパウリ行列が利用されます。初期ハミルトニアンはXだったので、全てX演算子が量子ビットに個別に適用されます。また、最終ハミルトニアンは古典の問題になるので、ZとZZで記述されます。

このハミルトニアンは前述の時間発展演算子に適用される際には、対角化された結果、任意回転ゲートに時間を導入した角度での回転操作に変換されます。

本来時間発展演算子を利用する際には、回転角度は時間のスケジュールで決まるはずですが、変分原理を利用した量子古典ハイブリッド計算では、この角度パラメータは全て変分パラメータとして丸めて最適化してしまいます。初期は大体ランダムで決まります。

これらの知識を統合し、Ansatzは量子断熱計算の時間発展を変分化した回路として作ることができます。

今回は初期状態が|+>なので、すべての量子ビットにHゲートをかけて重ね合わせ状態を実現しています。ミキサーはXの時間発展でRXを変分かします。最終ハミルトニアンは問題に合わせてZやZZの時間発展&変分化します。RZとRZZで書かれます。

これで準備はすべて終わりです。早速論文を見てみましょう。

こちらは、2020年4月のものです。

https://arxiv.org/pdf/2004.04197.pdf

Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor Google AI Quantum and Collaborators∗ (Dated: April 10, 2020)

概要はとてもシンプルです。Googleのマシンで最大23量子ビットのQAOAを実行しましたということです。

量子コンピュータの接続方法が限られているので、組合せ最適化問題のグラフ接続によって計算結果が変わってきますので、その辺りのリアルな結果が見れます。

主に計算された離散最適化は、ハードウェアの二次元格子モデル、3-regularのmaxcut、そして、Sherrington-Kirkpatrickモデル（SKモデル）と呼ばれるものでした。

引用：https://arxiv.org/pdf/2004.04197.pdf

aのハードウェアグリッドは二次元格子状。maxcutはネットワークは1ノードから最大3つのエッジが接続されています。SKモデルは全結合になっています。

一番右のdのグラフはQAOAのansatzを示していて、青がコスト関数。垢が横磁場のシミュレーションになっています。pは断熱過程のステップ数で、p=1以上で何回繰り返すかが示されています。初期状態は|+>が想定されていて、初期のHゲートの適用などは省略されています。

コスト関数は局所磁場なしの、

とZを使ってイジングで示されます。

コスト関数の時間発展は、下記の通りに変形されます。

また、初期ハミルトニアンはXなのでこちらも、

最終的には変分化された時間発展が初期状態の|+>状態からスタートして計算されます。これらは前述の説明と同じです。

グラフ問題を二次元格子のハードウェアで解くためには、ハードウェアの量子ビットをswapゲートを使って入れ替える必要があります。

googleマシンでは、特殊な方法でswap networkを実現しているようです。

引用：https://arxiv.org/pdf/2004.04197.pdf

1量子ビットの任意回転とSYCゲートを使ってswapネットワークを実現しているようですが、これは別の記事でやってみようと思います。

勾配を使って最適化をすることで、問題の最適解・局所解を見つけるというグラフが示されています。

Model Gradient Descentと呼ばれる手法が使われているそうです。赤い四角からスタートして、左側の理想的なシミュレーションの最適解へと勾配計算でいく様子が書いてあります。

引用：https://arxiv.org/pdf/2004.04197.pdf

ノイズなしの理想的なシミュレーション結果と実機の比較をしています。

丸が実験値です。SKモデルは全結合なので当然ですが精度がかなり下がっています。n=17でほぼランダムに。二次元格子ならなんとか計算結果を保っています。/Cminで最小値が分かっているので、それを元に計算結果を出しています。

研究としてはかなりの進展があったのではないでしょうか。逆にビジネスとしては、17-23量子ビットのグラフ問題はほぼ何も出来ていないのと同じなので実用化はかなり遠そうです。

pは断熱ステップでした。アニーラーではアナログ実装されている過程をデジタル実装するということで、p=2以上のパフォーマンスが考察されています。

n>10で二次元格子の時のQAOAで、シミュレーションはステップを増やすと精度が増えていいますが、実機はp=2,3くらいの時に最大になって、p=4以上だとエラーの影響で精度が下がっています。

断熱ステップを細かくするほど精度を上げる必要がある問題もあるので、これもやはり実用化へはまだまだ遠そうです。

実機でここまでできるというのはものすごい研究と思いました。大学や研究所の人は注目すべき結果で、やりがいがあるのではないでしょうか。一方ビジネスを見込んでいた人からすると、グラフ問題がほぼ解けないという結果なので、まだまだ実用化へは数十年かかるかもしれません。

研究とビジネスは全く違うのだなと思いました。

以上です。