Help us understand the problem. What is going on with this article?

RigettiのQAOA論文をざっくりみてみる

More than 1 year has passed since last update.

はじめに

量子アニーリングマシンを使って日々最適化問題を実装をしています。キメラグラフと呼ばれる接続数の多いグラフ形状や、最近ではペガサスグラフという新しいグラフトポロジーも出てきました。

一方、量子ゲートマシンは超電導量子ビットのトランズモンを中心に開発が進んでいますが、なかなか実装に苦労をしているというのが現実かと思います。かつ、ゲートの量子ビットトポロジーも量子アニーリングのように複雑とはいかず、二次元格子のシンプルなものになっています。

ただ、量子ゲート方式は任意の量子状態を作り出すことができるという点においてやはり夢があります。どうせ量子コンピュータは古典状態からスタートして、古典状態で終わり、実現できる量子状態は計算過程のみなので、どのような計算が実現できるのかあまり常識的にとらわれずこれから起こることを楽しみに調べ物をしていきたいと思います。

量子アニーリングから一歩発展させて途中の量子状態の任意変化をプログラミングで実現できればとても面白いことができるきがします。

まずはQAOAをしっかり少しずつ学んでみて、実用的な問題が1つでも多く解けるように頑張りたいと思います。

参考資料

"Unsupervised Machine Learning on a Hybrid Quantum Computer"
https://arxiv.org/pdf/1712.05771.pdf

多分以前にも紹介した気がしますが、こちらをみてみたいと思います。内容はシンプルですのでざっくりと確認します。

マシン

使用したのはRigettiの量子コンピュータですが、19量子ビットのマシン(今は壊れたらしい)です。こちらを既存の計算機とつなげてハイブリッド計算します。

スクリーンショット 2019-03-04 2.31.54.png
引用:https://arxiv.org/pdf/1712.05771.pdf

QAOA

QAOAは量子ゲート方式の量子コンピュータで組合せ最適化問題を解くためのアルゴリズムです。組合せ最適化問題は問題自体には量子性がないのですが、解く過程のアルゴリズムに量子断熱計算を導入することで、量子性を使って組合せ最適化を解くという道筋をつけています。

実際には量子状態$\mid\psi\rangle$の状態からスタートして最終状態へシミュレーションを行います。

スクリーンショット 2019-03-04 2.31.37.png
引用:https://arxiv.org/pdf/1712.05771.pdf

ハイブリッド方式

量子コンピュータはまだ開発途中です。誤り訂正機能がないため、量子変分アルゴリズムと呼ばれるハイブリッド式が採用されます。

スクリーンショット 2019-03-04 2.30.19.png
引用:https://arxiv.org/pdf/1712.05771.pdf

ある量子状態からスタートして、最終的にベータとガンマのパラメータを導入したシミュレーションを通じて答えを取り出します。その答えを評価した上で、最終的に新しいパラメータを割り振り次の計算を行います。

今回解いた問題

今回解いたのはmaxcutと呼ばれる2グループに分類するとても簡単な問題です。コスト関数やハミルトニアンと呼ばれるコストが低くなると正解に近くなるという数式を準備してそれを解かせるようにします。数式自体はイジングモデルと呼ばれる物理モデルで構成されており、-1と+1が量子ビットの値にセットされます。

スクリーンショット 2019-03-04 2.29.43.png

こちらがハミルトニアンです。量子断熱計算では、上記のハミルトニアンの他にもう1つハミルトニアンを準備します。

スクリーンショット 2019-03-04 2.29.58.png

こちらは初期状態を表すハミルトニアンで、$\mid + \rangle$に準備されています。こちらのドライバーハミルトニアンと呼ばれているものを操作して、先ほどのコストハミルトニアンと割合を少しずつ入れ替えながら、このハミルトニアンからスタートし、上記のコストハミルトニアンへと移行して計算をしてみます。

この辺りは量子アニーリングと似ています。

最適化

最適化すべきものは両方のハミルトニアンに導入されたパラメータのベータとガンマです。この論文ではそれらのパラメータをベイズ最適化を使って最適化しています。ベイズ最適化は上記の角度パラメータの全体最適化を行えるように、ステップごとに取りうるあたいの範囲を少しずつ推定して絞りながら次の点を探索していきます。

角度パラメータを最適化するのに古典計算機をフル活用しているのが特徴です。

スクリーンショット 2019-03-04 2.30.48.png

結果

結果はあまり面白いものではなくて、ランダムでやるよりは早いというものになっています。実際10分程度かかっていますが、実際のPCなどでしたら一瞬で終わるような計算でしょう。

しかし今後このような組合せ最適化問題がどの程度量子断熱計算の特徴を捉えて量子プログラミングで改善されていくのはかは、NISQと呼ばれるここ数年全世界で取り掛かっている量子ゲート方式の量子コンピュータの行く末を占うものと思います。

今後はより理論に踏み込みながら、古典最適化計算もいいものを選びながら実装を進めてみたいと思います。以上です。

YuichiroMinato
最近はblueqat.comの方でもブログを書いてます。
https://blueqat.com/
mdrft
量子コンピュータのアプリケーション、ミドルウェア、ハードウェアをフルスタックで開発
https://blueqat.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away