この記事の概要
2020年4月にGoogle AI Quantum and CollaboratorsがarXivに投稿した論文 "Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor" を読んだので、その理解を深めるためにアウトプットをしたものです。
序章: Sycamoreプロセッサ
Googleが開発した量子プロセッサです。超伝導量子ビットが54個搭載されています。

2019年10月23日にNatureから出版された論文"Quantum supremacy using a programmable superconducting processor"で、量子超越(Quantum supremacy)を達成したことが報告されました。その当時、世界最先端を行く古典スーパーコンピュータでおよそ10000年かかる計算を200秒ほどで完了させた、という驚きの成果を出したのがこのSycamoreプロセッサです。
序章: QAOA (Quantum Approximate Optimization Algorithms, 量子近似最適化アルゴリズム)
ここではQunaSysさんのQuantum Native Dojo, 5-3を元に、QAOAの概要を復習しましょう。
QAOA概要
量子アニーリングと同様に、組み合わせ最適化問題の解を求めるためのアルゴリズムです。NISQ上で実行できるとして、期待が寄せられています。
問題設定
QAOAではというn桁のビット列zに関して、コスト関数
が最小になるようなzを探す問題を考えます。
はビット列zを引数にとる何らかの関数で、ここでは特にイジングモデル的な
というような項を考えれば良いでしょう。
この最小化問題を解くためにn qubitの量子系を用います。そして、
をパラメータとして、次のような量子状態を考えましょう。
ここではX演算子の固有状態
であり
C(Z)というのはビット列を引数にとる関数C(z)の入力にパウリ演算子と代入したものです。そして
を最小にするような
を探索することで、元々の最適化問題の答えを探そうとするのが、QAOAになります。
QAOAの手順
具体的なQAOAの定順は以下のようになります。
- 量子コンピュータ上で重ね合わせ状態
を作成します。
- パラメータ
に応じて、量子状態に
を作用させていき、状態
を得ます。
- 量子コンピュータを用いて
を測定します。
- 古典コンピュータで
がより小さくなるようにパラメータ
をアップデートします。
- 1~4を繰り返し、最適な
を獲得します。
- 状態
に対して、z方向の射影測定を複数回実行し、得られた(良さそうな)測定結果
を元々の最適化問題の解として採用します(注意: 測定結果
は古典ビットのことです)。
数値実験に用いた問題
コスト関数と対応する演算子
この論文では3つのグラフ問題を解いています。その全ての問題で、コスト関数に
を採用しています。はエッジの重みを表すもので、
ならば点
と
が繋がっていないことを表しています。
これに対応する演算子として、ビット列をパウリ
に置き換えた
を用います。は
番目の量子ビットにかかるパウリ
です。
数値実験に用いたグラフ
Hardware Grid with a graph matching

上図のような2次元正方格子において、最大で23量子ビットを用いてグラフマッチング問題を解きます。
Three-Regular Maxcut

1つの点から3つに枝分かれするような、上図のグラフでMaxcut問題を解きます。用いているのは最大で22量子ビットです。
Sherrington-Kirkpatrick (SK) model

上図のような全結合グラフにおいて、SKモデルと呼ばれるスピングラスの理論モデルを解きます。最大で17量子ビットを用います。
コンパイルについて
今回の問題のコスト関数、もといそこから生まれるQAOAのためのユニタリ演算子$`U_C`$は
となります。この演算を実装するために、この論文では以下のような量子回路を組んでいます。

上図aは17量子ビットを用いてSKモデルを解くのに用いた量子回路図です。図のように演算を配置することで、
を満たす全ての組み合わせを再現しています。
さらにを上図bのように、黄色の
に依存した1量子ビットの回転と緑色のSYCゲートで表現します。SYCゲートの定義は以下のようなものです。
エネルギーランドスケープと最適化されていく様子
以下ににおけるエネルギーランドスケープと、QAOAのイテレーションによりエネルギーが遷移していく様子を示します。

右列がシミュレーションによるエネルギーランドスケープで、図中の青星印は局所最適解の場所を示しています。右図はSycamoreの実験による量子回路の深さ(を作用させる回数)が
のときのエネルギーランドスケープで、赤四角から始まる折れ線はQAOAによる最適解探索の様子を示しています。カラーコントアはコストを表しており、黄色がコストの低い部分、黒色がコストが高い部分に対応します。Hardware gridは23量子ビット、3-regular graphは14量子ビット、そしてSKモデルは11量子ビットのときの様子を示しています。
Sycamoreによる数値実験では、青星印の最適解に向かって状態が遷移していく様子がわかります。
QAOAにおけるSycamoreの性能

上図はのとき、横軸を量子ビット数、縦軸をコストの小ささ(1は最適解、0はランダムな解)を表しています。実線がSycamoreの数値実験の結果です。Hardware grid問題は量子ビットの数に依存せず一定に落ち着いています。一方でMaxCutとSK Modelでは量子ビット数が増加するほど、ハードウェアのノイズによる影響を大きく受けています。

そして次の図は横軸を、縦軸をHardware grid問題を解いたときの性能としたときのものです。緑線のシミュレーションは
を増やすごとに最適化されていきますが、Sycamoreによる数値実験ではむしろ精度が落ちています。下の棒グラフは各
のとき、どのくらいのパーセンテージ最高のパフォーマンスを発揮できたかを表しています。
が最高パフォーマンスを記録していることがわかります。
結言
Googleの量子プロセッサSycamoreによる数値実験の論文をご紹介しました。QAOAを実際に行った結果、現在のNISQデバイスではくらいの量子回路の深さが最良の結果を示しました。しかし今後のノイズ抑制技術次第では、この結果も大いに変わってくることでしょう。
参考文献
- [1] Google AI Quantum and collaborators, 2019, "Quantum supremacy using a programmable superconducting processor"
- [2] Google AI Quantum and collaborators, 2019, "Supplementary information for "Quantum supremacy using a programmable superconducting processor""
- [3] Quantum Native Dojo, 5-3, QAOA
- [4] Google AI Quantum and Collaborators, 2020, "Quantum Approximate Optimization of Non-Planar Graph Problems on a Planner Superconducting Processor"