【まとめ2019/3】量子コンピュータと量子アニーリングの現時点まとめ
はじめに
（注）2019年の記事です。
量子コンピュータは難しそうとか、難しいことをやってそうとか思いますが、現在のマシンはそこまででもありません。情報が錯綜しているので、一回量子アニーリングや量子ゲートのアルゴリズムに関してまとめてみます。量子ゲート方式の量子コンピュータがどうとか、量子アニーリングがどうとかいう議論もありますが、僕は両方やっているのでその辺りも包括的にまとめてみたいと思います。
個人的な見解も多少入ってますが、読めば最新動向がある程度理解できるとは思います。2019年3月時点でのまとめです。適宜読み飛ばしながら見てもらえればと思います。
まずは簡単な概要とそれから量子ゲートの変分回路におけるNISQアルゴリズムの概要を把握して、今後の量子コンピュータの展開を予測するのが最終的な目標です。
量子コンピュータの二方式？
量子コンピュータには量子アニーリングマシンと量子ゲートマシンがあるという説明がありますが、少し混乱しそうなので補足します。
そもそも多分量子アニーリングは計算原理ではなくてアルゴリズムのことで、特定のアルゴリズムを実機で再現した専用マシンであると思います。最適化計算にはたくさんの手法があり、その中で実現しやすい量子アニーリングが選ばれて実機搭載されたというものであると思います。
そのため、最適化アルゴリズムのさらにその上で動く問題に対して適用するものなので、量子アニーリングでなくても問題が解けるのでデジタルアニーラやCMOSアニーラやCIMのような様々な最適化アルゴリズムを適用した専用マシンがたくさんあるのだと思います。実際D-WaveとNEC以外は量子アニーリングを使っていません。世の中には様々な最適化アルゴリズムがあって、その中でどれを選んで実機にするのかという問題かと思います。
量子アニーリングは使っている量子効果が限定的なので、古典計算機で効率的にシミュレーションできてしまう（古典計算機のモンテカルロで効率的にシミュレートできる）ので応用範囲が狭いと言われがちですが、組合せ最適化問題は大きな課題であってゲートマシンでも解けるかどうかはよくわからないので、量子アニーリングマシンは量子ゲートマシンとは異なる用途で活躍するのではないでしょうか。
海外でも結構トライされていて結果として横磁場を導入した組合せ最適化向け量子マシンくらいの認識で良い思います。D-Waveのマシンがしっかり量子効果を活用して問題を解いたからこそ量子コンピュータに火がついたというのは紛れもない事実だと思いますので。
量子アニーリングアルゴリズムの作り方
上記を踏まえると、量子アニーリングはイジングモデルと呼ばれる物理モデルに特化した最適化アルゴリズムをハードウェアに起こした専用マシンですので、イジングモデルと呼ばれる物理モデルに特化した形で問題を設定します。アルゴリズムの上にアルゴリズムを作る感じです。
イジングモデルのアルゴリズムを作る上で設定できるのは、
１、局所磁場と呼ばれる量子ビット自体にかかる値
２、相互作用と呼ばれる量子ビット間にかかる値
です。この２つを設定して操作することで、問題を解きます。D-Waveが採用した量子アニーリングマシンはこのイジングモデルを採用していますので、他の最適化マシンもイジングモデルを採用して競争しています。
デジタルアニーラやCIMはイジングモデルとしては一番良い形で上記の２番の相互作用がそれぞれの量子ビットに対して全結合の形になっているものを採用しています。一方CMOSアニーラやD-Waveは結合に制限があるため、キメラグラフとかキングスグラフとかペガサスグラフとか接続が制限された形でどのように問題を解いていけばいいのかを考える必要がありますが問題の本質的なところとは少し異なる企業ごとのチップの製造などの事情になります。
こんな感じで問題を解くための接続を考慮する必要があります。量子ゲートはこんな複雑な接続は実現できていないので、独自発展して組合せ最適化をどれだけ解くかに特化していると思います。量子アニーリングや他のイジングも量子ゲートとは異なる形で独自発展をしていて興味深いです。多少世界から見たらカナダと日本はガラパゴスですが、仕方ないとも思います。
量子ゲート
量子アニーリングが横磁場という限定的な形で量子効果を導入して計算に応用した一方で、その量子効果をよりきちんと操作して様々な量子効果を活用できるように開発されているのが量子ゲート方式です。
量子ゲート方式の場合には量子計算と呼ばれる計算原理が確立されていますので、そのルールに則った形で計算を行います。量子計算は非常によく出来上がった理論ですので、その上で計算が動くというのはとてもすごいことだと感じました。
量子ゲート方式の量子コンピュータが従来の私たちが今使っているコンピュータと違うところを簡単に確認したいと思います。
量子の世界
量子とはとても小さい単位で、物質やエネルギーの最小単位でそれ以上分割できないという単位です。量子の世界は今の半導体の技術の世界とは異なっていて、粒子と波の性質を同時に兼ね備えていると言われています。
サイズが小さくなると粒子はこれまで持っていなかった波の性質を持つようになり、その波は状態を表し重ね合わせなど今まで活用できなかった原理を活用できるようになります。
現在の半導体チップは微細化が進みすぎてこれ以上性能向上が厳しいという背景には、量子の世界では物理法則がかわり、半導体のPCの原理となっている計算原理が量子の世界ではそのまま適用は難しいという事情もあります。
量子ビット
上記量子の世界では今の世界よりもサイズが小さく他の原理が応用できるとありました。それが物質波で、物質と波の両方の性質を持ちます。その両方の性質を使い分けられるように設計されたのが「量子ビット」です。量子ビットは様々な量子の種類を使って実現されますが、重ね合わせや量子もつれのような不思議な機能を持ちます。
閉鎖系
現在主流の量子コンピュータは超電導回路のようなものでは閉鎖系と呼ばれ、密閉されて絶対零度近くに冷やされて系全体のエネルギーが保存されて変わらないような状態を作ります。これにより、系の中での量子ゲートの計算ができるようになります。量子力学では時間非依存型のシュレディンガー方程式が使われ、時間によって系が変化しないということがとても大事になります。
量子回路
量子ゲート方式は量子回路と呼ばれる時間で変化する音符のような回路を活用して問題をプログラミングします。
量子ゲート方式は汎用計算機と呼ばれ、現在の私たちの使っているコンピュータの計算回路を再現できる汎用性（と互換性？）があります。量子回路は量子ビットの初期化と量子ゲート操作や演算、そして測定からなります。
初期化は普段は量子ビットは0に初期化されます。次に量子ゲート操作をおこなうことによって量子状態と呼ばれる特殊な状態を操作することができます。その量子状態は私たちの目に見える世界以上に複雑なデータの持ち方をすることができ、それを活用することで今のコンピュータにできない計算をします。そして最後に測定をするとその量子状態は壊れて私たちに見える形で計算結果が戻ります。
量子状態
量子状態は特殊なデータの持ち方を実現します。通常私たちのコンピュータはビットと呼ばれる0と1の計算をします。量子コンピュータではこの0と1以外のデータの状態を実現できます。
実際には三次元を取りますのでより複雑になりますが、まずは段階的に二次元を見てみます。
私たちのコンピュータは0と1だけを取りますが、量子コンピュータは0と1以外に+や-という中間表現を取ることができます。+や-は0と1が50%ずつ重なっているという表現をしますが、そのような中間表現を量子ゲートと呼ばれるものを使って切り替えていきます。H（アダマール）ゲートを使って軸を切り替えながら、XやZをつかってビットを切り替えます。
これをさらに三次元に展開して波の性質をふんだんに活用できます。通常この01以外のデータを三次元の球で持てて、その三次元のデータを表現した球のことをブロッホ球と呼びます。
参考：https://ja.wikipedia.org/wiki/ブロッホ球
この量子状態におけるデータの持ち方を状態ベクトルと呼びますがそれをみてみたいと思います。
状態ベクトル
このデータの持ち方を状態ベクトルというベクトルで表現します。状態ベクトルは１つの量子ビットに対してはシンプルなベクトルで与えられます。
ブロッホ球の上を0、下を1として、縦ベクトルで[1,0]で0を[0,1]で1を表現します。量子状態であるということがわかりやすいようにディラック記法というもので、0と1は
のように表記されます。
上記でしめた通り、0でも1でもない中間表現が取れます。どれだけ0に近いか1に近いかを含めて、状態ベクトルは、
のように
というルールが成り立ちます。
複数量子ビットの状態ベクトル
複数量子ビットの状態ベクトルは量子回路においては組み合わせもしくは重ね合わせのビット配列で表現され、状態ベクトルの表現に影響します。
２量子ビットの場合にはそれぞれの量子ビットは
の４種類あります。ディラック記法で状態ベクトルを表現する際には、
のように確率振幅で表現することもあります。実際の量子コンピュータのアプリケーション現場ではpythonが使用されていて、プログラムで書く必要があり、量子状態は普段は状態ベクトルの形でベクトル表記を取り扱います。
複数量子ビットの状態ベクトルは01の表記を2進数で扱い、
の配列の順番でそれぞれの確率振幅を入れます。
こちらを数学的に表現するには、テンソル積を使い、１量子ビットずつの状態ベクトルのテンソル積というものを計算することで実現できます。
テンソル積は単純に前のベクトル要素に次のベクトル要素をかけます。
３量子ビット以上でも同様で、
のように計算し、順番に計算することでできます。N量子ビットの場合には状態ベクトルのサイズは
##初期化
初期化は簡単です。最初の
でしたので、２量子ビットの初期化された状態ベクトルは、
のようになります。増えるごとに、テンソル積の計算が大きくなります。
このサイズが指数で増えるので量子計算は膨大な処理ができると言われています。
ゲート演算
次にゲート演算です。準備されて初期化された量子ビットにゲートと呼ばれる演算回路を適用して計算を行います。
量子ゲートは数学的な形は行列で表現され、ブロッホ球においては
ゲートには様々な種類があります。まずは代表的なものとして、ブロッホ球の各軸周りに180度回転するXYZゲート。こちらはパウリゲートと呼ばれます。
また、ZXを相互変換するHゲート。アダマールゲート。
そしてZ軸周りを任意回転する位相回転ゲートRz
また、２量子ビット間の関係性を決めるCX(CNOT)ゲート
これらを使って演算をします。これらゲート演算を表現する行列はユニタリー行列と呼ばれるもので、エルミート性がありユニタリーです。
量子回路
量子回路は上記の量子ゲートを並べて演算として利用します。
左から右へと時間が経るごとに順番に配置された量子ゲートに対応された行列変換が行われます。量子ゲートの演算が進むごとに初期で準備された状態ベクトルが変化をしていきます。最終的に測定の手前までは量子状態が保たれて複雑なデータの保持が維持されます。
実際の演算は量子ビットの状態ベクトルに順番に量子ゲートの行列演算を適用します。下記はたとえばXゲートはNOTゲートとも呼ばれ、ビットを反転させます。
このようにできます。また、複数量子ビットには前に確認したテンソル積を使った状態ベクトルに、同じようにテンソル積を使った量子ゲート操作を適用して状態ベクトルを確定していきます。
ゲートは回路は時間ごとに分解され、じゅばんに演算を行なって状態ベクトルを更新していきます。
|0> ----X----
例えば、上記のような回路にXを導入すると、得られる状態ベクトルは、
のようになりました。Hゲートを適用すると、
|0> ----H----
こちらは、
このようになって、状態ベクトルが01の重ね合わせ状態になりました。
複数量子ビットの際には、
|0> ----*----
|0> ----X----
たとえば、これは*をコントロールビット、XをターゲットビットとしたCX回路として、２量子ビットのテンソル積で準備された状態ベクトルにCX回路を適用すると、
変化なしでした。先に0番目（上から0から数える）の量子ビットにXゲートを適用してからCXゲートを適用すると、
|0> --X--*----
|0> -----X----
こちらを計算します。まずは左から順番に計算しますが、Xゲートの方は１番目の量子ビットに対して演算がありませんが、こちらは単位行列Iを補完します。
|0> --X--*----
|0> --I--X----
まずは
|0> --X--
|0> --I--
の計算は、
となります。
|0> --X--*----
|0> --I--X----
その後にCXを適用して、
このように答えが出ます。より複雑で多い量子ビットで全く同様に計算ができます。
実際にはSDKのようなツールを使って、
from blueqat import Circuit
Circuit().x[0].cx[0,1].run()
#=>
array([0.+0.j, 0.+0.j, 0.+0.j, 1.+0.j])
このように簡単に計算できます。
測定
測定は上記で求めた状態ベクトルを古典ビットの01に戻します。状態ベクトルは2進数表記された量子ビットの出現確率が確率振幅という形で情報が格納されており、それを使って確率的に状態を確定させます。
は状態ベクトルの値である確率振幅を二乗した
また、
これは、一番下は
のようなものは
Circuit(2).h[:].run()
#=>
array([0.5+0.j, 0.5+0.j, 0.5+0.j, 0.5+0.j])
ですが、古典ビットに都度サンプルを取ってみると、
Circuit(2).h[:].m[:].run(shots=100)
#=>
Counter({'10': 22, '11': 27, '01': 26, '00': 25})
このようにだいたい1/4になります。シミュレーションではサイコロを振ります。
シミュレータ
量子ゲートのシミュレータは上記の行列計算をします。状態ベクトルは量子状態なので実機マシンではみることができませんが、少ない量子ビットの範囲であればシミュレータでは確認することができます。
ちなみに量子アニーリングもシミュレータがあり、そちらは通常は量子モンテカルロと呼ばれる乱数をふりながら解を評価するという方法が使われます。
量子ゲート回路は計算の最後にサイコロを振りますが、量子アニーリングでは計算過程でサイコロを振るのがシミュレータの違いになります。
##万能量子計算とNISQ
上記量子ゲート方式は状態ベクトルを複素数で持つことができます。そのため、とてもデータ保持の範囲が広くなります。また、重ね合わせによって組み合わせの数だけデータを持てますので、少ない量子ビットでデータを表現できます。
万能量子計算はこの空間の広さを利用して様々なこれまでの計算機でできない計算を実現しようとしています。たとえば、グローバーのアルゴリズムや量子ニューロンなどは、状態ベクトルを最大限活用して、２量子ビットで16パターンの実装例などがあります。
状態ベクトルを活用する例として、２量子ビット両方にHゲートを適用すると、
状態ベクトルはこのようになります。またこの状態ベクトルはZゲートやCZゲートを使うことによって、任意の状態ベクトルを操作することができ、
のように1を-1に操作して、２量子ビットだけで量子ゲート操作を使い、全部で
また、CCX回路のような従来計算機におけるXORゲートなど基本的な汎用ゲートも揃っているので、上記の状態ベクトルを利用した計算と、従来の汎用ゲート計算を組み合わせることで現在の計算機の機能を拡張することができます。
ただ、現在の量子ゲートマシンには上記の万能量子計算を十分に実行できるような誤り訂正機能がありません。そのため、現在のここ数年の量子ゲートマシンはNISQとよばれるエラーがあった状態での計算をしいられます。
NISQ
NISQはNoisy Intermediate-Scale Quantumの略で、エラーありの中規模マシンで100量子ビット前後でエラーありのマシンになっています。そのため従来考えられていたグローバーやshor、位相推定や量子フーリエ変換のようなアルゴリズムの実行が実質的に厳しくなっています。
そのため、NISQマシンでは上記のアルゴリズムの代替として現在量子変分回路と呼ばれる量子古典ハイブリッド方式のアルゴリズムが利用されます。
時間発展シミュレーション
量子ゲート方式には量子シミュレーションと呼ばれる量子効果を使ったシミュレーション手段があります。従来は位相推定などのアルゴリズムを使って結果を取り出す予定でしたがそれが実行できないため、他の手段で結果を取り出すこととなりました。
時間発展シミュレーションは、閉鎖系の超電導での時間非依存型のシュレディンガー方程式から、断続的にユニタリー変換を行い、量子状態を変化させる手段です。
その際に適用するオペレーションとしてハミルトニアンの時間発展を考えます。ハミルトニアンは基本的なパウリ演算の積和で表現され、エルミート行列をなし、固有値が実数で求まります。この演算を時間発展させることで、ハミルトニアンの固有値の期待値を求めることができます。
この
時間発展シミュレーションの量子回路への落とし込み
量子回路へは指数の肩のハミルトニアンを量子回路に落とします。手順としては、
１、指数の肩のハミルトニアンをユニタリ行列の積に分解する
２、対角化する
３、対角化するとそのまま累乗できる。
ハミルトニアンはエルミート行列ですが、ユニタリ行列とは限らないので、パウリ演算の積に分解します。パウリ演算の積の形になるとユニタリ行列になりますので、それを時間発展でとけます。
pauliZのように対角行列の場合には、そのまま指数の肩からおろせます。
一方でXやYのように対角行列でない場合には、
また、YYを対角化するには、
とすることで
演算子をとにかく回転を使ってZ軸に変換できれば対角化できますので、それを利用して指数の肩からおろします。そして、そのまま量子回路に入れます。
量子変分回路と量子古典ハイブリッド
ここまできたらあとはほとんどゴールに近いです。現在上記の作成した量子状態を取り出す手段がありません。NISQでは位相推定や逆量子フーリエ変換の実行が厳しいので、他の手段を考える必要があります。それが量子変分回路です。
量子変分回路は量子変分原理を利用して、位相推定の代わりにハミルトニアンの固有値を求めるための量子古典ハイブリッドアルゴリズムです。
量子変分原理
変分原理は、
「適当な境界条件を持つ任意の状態|Ψ⟩に対するハミルトニアンĤの期待値Eは、基底状態のエネルギーE0よりも常に大きいか等しい。」
これを利用することによって、ハミルトニアンを変えずに量子状態を変えてハミルトニアンの固有値の下限値に近づけていきます。
角度の導入
ハミルトニアンは変えられないので、実際には量子状態の方を色々変えてみればよく、量子状態は角度を変数にして変更できます。量子回路において角度を変数にできるのは基本的にはZ軸周りの任意回転なので、その角度θを導入すればよく、
となり、これはあるハミルトニアンの時間発展回路を任意の角度を導入した量子状態において測定をした期待値を求めればよいことになります。
変分回路
上記の変分原理を用いてハミルトニアンの固有値を求めることで様々な問題が解けます。実際の変分回路に関して構築の方法がいくつかあるようですが、下記のようにZゲートに角度を導入してRzにして計算するなどの方法があります。
|0> --*-------------------*--
|0> --X--*-------------*--X--
|0> -----X--Rz(theta)--X-----
変分回路の統合とハミルトニアンの固有値と量子古典ハイブリッド計算
上記の角度を導入した変分回路はユニタリー演算を解きますので、実際にはエルミート行列を分解してユニタリー行列に直した上で変分回路を使って期待値を求めます。そして、独立して求めたユニタリー行列の期待値を足し合わせることでハミルトニアンの固有値の期待値を求めて、それを繰り返すことによって固有値の探索を行います。
１、独立したユニタリー回路に角度の変数を導入した回路の期待値を求めるために繰り返し計算。
２、ユニタリー回路の計算結果を統合してハミルトニアンの固有値の期待値を求めて、角度を変えて探索を続ける。
上記のようにユニタリ回路の期待値を統合して係数をかけてハミルトニアンの期待値を算出することを古典計算機で行います。最初の角度は適当もしくは一定の理論に基づいて準備（量子化学計算ならUCC理論とか）して、それを変分回路でブンブン回します。次の角度の推定には古典最適化を使います。
古典最適化
量子変分回路では角度が変数となりますが、その角度の変数は古典最適化計算されるのが一般的です。古典最適化計算はベイズ最適化やPowell法など既存の有名な最適化手法を使って全体最適化もしくは局所最適化されて変分原理のあたいの精度を追い込んでいきます。
こちらの論文ではRigetti社はベイズ最適化を使って全体最適から変分回路の角度パラメータを推定しています。
これが一般的にいわれているVQE(Variational Quantum Eigensolver)です。
量子化学計算や組合せ最適化問題に応用
上記の量子古典ハイブリッド計算を利用することで、様々なゲートアルゴリズムを開発できます。有名なのは量子化学計算のような、上記のハミルトニアンに量子化学の分子軌道エネルギー計算を利用したようなものや、量子断熱計算と呼ばれるような、量子アニーリングのような量子効果をプログラミングで実装したアルゴリズムがあります。
QAOA
QAOAはQuantum Approximate Optimization Algorithmと呼ばれ、上記量子変分回路を使って、量子断熱計算と呼ばれる量子アニーリングに近い回路を実行しています。実際にはパラメータとして角度とアニーリングステップ数を設定し、横磁場を設定した|+>状態からスタートして最終的なハミルトニアンHを計算します。イジングモデルを使い、ハミルトニアンは量子アニーリングでつかわれる量子ビットのあたいにpauliZを使って表現します。
QAOAは量子アニーリングのような横磁場を量子シミュレーションとして扱って計算するので、より量子アニーリングも量子ゲートから入った方が理解がしやすいと思います。Hゲートを適用して全ての量子ビットをXに倒してからスタートするので横磁場の考え方もスムーズに進む気がしますし、解ける問題も同じです。
このように、量子ゲートは量子アニーリングを従来計算機の量子モンテカルロではなく直接量子シミュレーションできるところに意味がある気がします。
実際の最適化は現在の量子変分回路では古典最適化をしますので、基底状態探索にはベイズ最適化やPowell法など問題に合わせた形で古典最適化アルゴリズムが利用されるので、しっくりこない人もいるとおもいますが、現状では仕方がないとおもわれます。
今後
しばらく数年はこの量子古典ハイブリッド計算がつづき、ハミルトニアンの固有値を従来とは異なる形で表現できるので、それに対してのアルゴリズムが量産されると思います。
量子ゲートにとって組合せ最適化問題はあくまで量子シミュレーションでのアルゴリズムの１つなので、選択肢が広いです。量子ビット数が少ないですが、開発の速度は急激に上がってきているので、数百量子ビットの計算ができるのも間近なのではと感じることもあります。
今後はこれまでの量子アニーリングの知識から拡張し、量子ゲートの最適化や機械学習、量子化学計算などに応用分野が急激に増えていくのが今年の夏までの世界情勢と思います。