私の完全な理解によると「Groverのアルゴリズム」とは、
全ての可能性 を 重ね合わせ た 量子状態
です。
はじめに
先日、会社のハッカソンイベントがありました。
今年は、Amazon Braketを使って量子コンピューティングに挑戦してみました。
当初のモチベーションとしては「触ったことのないAWSサービスを試したい」でした。本当はAWS Ground Stationを試したかったのですが、あまりにも難易度が高くてサービスを使うこと自体が無理ゲーだったので、Amazon Braketで量子コンピュータを使うに落ち着きました。
ちなみに去年は、AWS ParallelClusterを使ってバーチャル富岳を動かしました。
一昨年は、ラズパイで顔認証しました。これは、Amazon Rekognitionのお値段が結構高いから「全部ラズパイでやれば無料じゃね？」的なモチベだった記憶です。
Amazon Braket について
Amazon Braketは、量子コンピューティングを提供するマネージドサービスです。
手元に量子コンピュータがなくても、(量子コンピュータが動いていれば)従量課金で気軽に使うことができます。
また、安定して動いている安価なシミュレータが同じインターフェースで使えるので、「シミュレータである程度動作確認した後に、実機に切り替えて動かす。」ということが容易にできます。
「Braket」ってそもそも何？
「なんで量子コンピュータを提供するサービスの名前がブラケットなの？」と気になりませんか？
量子コンピューティングではこんな表記「
逆の表示である「
この2つが合体したのがAWSのサービス名にもなっている ブラケット「
ハッカソンやったこと
ここからは、実際にハッカソンでやったことを「ちょっと触ってみたい」という人向けのコメントを交えながら説明したいと思います。
事前準備
まず、こちらの動画を見ました。こちらとても分かりやすいです。これから入門する人はほぼ必須で見ることをお勧めします。
また、初心者向けの本を買いました。今回は2人でやったので1冊ずつ別の本を購入しました。
- みんなの量子コンピュータ
- 量子コンピュータの頭の中
2冊あることで、内容が重複している項目から重要な点を確認したり、複数の視点で物事を見ることができて良かったです。
ただ、どちらか片方だけを買うなら、圧倒的に後者の「量子コンピュータの頭の中」をお勧めします。
というのも「量子コンピュータの頭の中」の方は、Groverのアルゴリズムのサンプルコードが載っており、そのサンプルコードを理解する為に知識が書籍内に書いてあるからです。
Amazon Braketを活用すれば、実際にコードを書いて動かして、その挙動を見ながら学ぶことができます。書籍を選ぶ際は、概念的な説明や数式のみのものより実際に動くコードが記載されているものが良いと思います。
とりあえず、Amazon Braketを触ってみる
さて、Youtubeを見て、書籍を用意したところで実際にAmazon Braketを触ってみました。(書籍を読んだとは言っていない。Youtubeは見た。)
まずマネコンでAmazon Braketに繋いでみましょう。日本のリージョンでは使えないので、us-east-1 などで使いましょう。
Amazon Braketダッシュボードで開始方法を押して、必要なIAMロールの作成等をしましょう。
私は、これを無視したので、後で権限不足で困りました。
IAMロールを作成したらノートブックインスタンスを作って起動すればOKです。
なお、公式サンプルのGitHubレポジトリを使ってお試ししましたが、これは明示的に設定しなくても自動でimportしてくれるようです。
ノートブックを起動して、しばらく待つとサンプルのフォルダが表示されます。Braket algorithms/textbook/ の配下にある Grovers_Search.ipynb を開きましょう。
あとは、そのまま実行すればGroverのアルゴリズムが動くはずです。(デフォルトではシミュレータを使うようになっているので、コストはほぼかかりません)
ちなみに、デフォルトだと3bitで111を探すコードになっており、結果が以下のように出ます。
[0.03 0.029 0.027 0.032 0.032 0.046 0.032 0.772]
量子コンピューティングは確率で結果が出るので、毎回同じ結果にはなりませんが、今回は77.2%の確率で111を見つける事ができました。
精度悪いですね！
実はこのサンプル、Groverのアルゴリズムとして最適な動きをしていません。コードのこの部分に注目してみましょう。
circuit = grovers_search(oracle, n_qubits=n_qubits, n_reps=1)
Groverのアルゴリズムでは、ある操作を何回か繰り返すのですが、その回数がn_reps=1です。この繰り返し回数は最初に書いた通りn_reps=2にして再度動かしてみましょう。
[0.005 0.005 0.008 0.009 0.01 0.005 0.004 0.954]
正解率が95.4%まで上がりましたね。後の4.6%足りない分は、0.22144回不足しているからですね。
と、このように量子コンピュータによる計算は、特定の演算を繰り返すことで正解を得る確率を高めることにあります。確実に正解を得ることはできず、確率的な結果しか分からないのど、通常のコンピュータと比べて扱いが非常に難しいです。
実際の量子コンピュータを試してみよう
では、実際に本物の量子コンピュータを使ってみましょう。しかし、本物はいつでも自由に使えるわけではなく、使える曜日や時間が制限されています。
ハッカソンの時にその場で使えたのは Rigetti - Ankaa-3 だけでしたので、こちらを使ってみました。
ランダムと変わらん
Ankaa-3は比較的安価で高速に動き稼働率も安定していますが、ノイズが多い量子コンピュータでGroverのアルゴリズムのような、深い処理には向かないようです。
残念な結果になりましたが、実際に実機を使えたことで「実機で精度を出すのは難しい」という知見を得ることができました。
なお、このノイズを得るのにかかった費用は30ドルです。ふざけんな！
また、ハッカソンから数日が経ちましたが、未だに他のデバイスを使える気配がありません。
まだまだ、量子コンピュータの可用性には課題が大きいと思いました。
書籍を読んで、自力でコードを書いてみた
だいぶ記事が長くなったので、あとは簡潔に書きます。
Amazon Braket上のノートブック(実態はただのSageMaker)で感覚を掴んだので、書籍「量子コンピュータの頭の中」を参考に自分でコードを書いてみました。なお、最初はBraketのサンプルコードをベースに中身を理解しようと思ったのですが、ちょっとサンプルコードの量子回路が煩雑で素人が理解するのに難易度が高かったので、書籍のコードをベースに理解を深めることにしました。
書籍のコードはQiskitというライブラリを使っています。これを直接Amazon Braketで動かすことはできませんが、Qiskit provider for Amazon Braketを使うことで簡単に変換ができました。
ちなみに、書籍をそのまま再現すると3bitの回路を汲むのにCCXゲートを使っていたのですが、対称性がなくなるのでド素人が理解するにはちょっと悩みました。
┌───┐┌───┐ ┌───┐┌───┐┌───┐ ┌───┐┌───┐┌───┐ ┌───┐┌───┐┌───┐ ┌───┐┌───┐ ┌─┐
q_0: ┤ H ├┤ X ├──■──┤ X ├┤ H ├┤ X ├───────■──┤ X ├┤ H ├┤ X ├───────■──┤ X ├┤ H ├┤ X ├───────■──┤ X ├┤ H ├─────┤M├──────
├───┤└───┘ │ ├───┤├───┤└───┘ │ ├───┤├───┤└───┘ │ ├───┤├───┤└───┘ │ ├───┤├───┤ └╥┘┌─┐
q_1: ┤ H ├───────■──┤ H ├┤ X ├────────────■──┤ X ├┤ H ├────────────■──┤ H ├┤ X ├────────────■──┤ X ├┤ H ├──────╫─┤M├───
├───┤┌───┐ │ ├───┤├───┤┌───┐┌───┐┌─┴─┐├───┤├───┤┌───┐┌───┐ │ ├───┤├───┤┌───┐┌───┐┌─┴─┐├───┤├───┤┌───┐ ║ └╥┘┌─┐
q_2: ┤ H ├┤ X ├──■──┤ X ├┤ H ├┤ X ├┤ H ├┤ X ├┤ H ├┤ X ├┤ H ├┤ X ├──■──┤ X ├┤ H ├┤ X ├┤ H ├┤ X ├┤ H ├┤ X ├┤ H ├─╫──╫─┤M├
├───┤├───┤┌─┴─┐└───┘└───┘└───┘└───┘└───┘└───┘└───┘└───┘└───┘┌─┴─┐└┬─┬┘└───┘└───┘└───┘└───┘└───┘└───┘└───┘ ║ ║ └╥┘
q_3: ┤ X ├┤ H ├┤ X ├─────────────────────────────────────────────┤ X ├─┤M├─────────────────────────────────────╫──╫──╫─
└───┘└───┘└───┘ └───┘ └╥┘ ║ ║ ║
c: 4/═══════════════════════════════════════════════════════════════════╩══════════════════════════════════════╩══╩══╩═
3 0 1 2
最新のQiskitだとCCZゲートがあるので、そっちを使ったほうが理解しやすかったです。(もっともCCZはbit数増えると現時点では対応できませんでしたが。)
┌───┐┌───┐ ┌───┐┌───┐┌───┐ ┌───┐┌───┐┌───┐ ┌───┐┌───┐┌───┐ ┌───┐┌───┐┌─┐
q_0: ┤ H ├┤ X ├──■──┤ X ├┤ H ├┤ X ├─■─┤ X ├┤ H ├┤ X ├──■──┤ X ├┤ H ├┤ X ├─■─┤ X ├┤ H ├┤M├──────
├───┤└───┘ │ ├───┤├───┤└───┘ │ ├───┤├───┤└───┘ │ ├───┤├───┤└───┘ │ ├───┤├───┤└╥┘┌─┐
q_1: ┤ H ├───────■──┤ H ├┤ X ├──────■─┤ X ├┤ H ├───────■──┤ H ├┤ X ├──────■─┤ X ├┤ H ├─╫─┤M├───
├───┤┌───┐ │ ├───┤├───┤┌───┐ │ ├───┤├───┤┌───┐ │ ├───┤├───┤┌───┐ │ ├───┤├───┤ ║ └╥┘┌─┐
q_2: ┤ H ├┤ X ├──■──┤ X ├┤ H ├┤ X ├─■─┤ X ├┤ H ├┤ X ├──■──┤ X ├┤ H ├┤ X ├─■─┤ X ├┤ H ├─╫──╫─┤M├
├───┤├───┤┌─┴─┐└───┘└───┘└───┘ └───┘└───┘└───┘┌─┴─┐└┬─┬┘└───┘└───┘ └───┘└───┘ ║ ║ └╥┘
q_3: ┤ X ├┤ H ├┤ X ├─────────────────────────────────┤ X ├─┤M├─────────────────────────╫──╫──╫─
└───┘└───┘└───┘ └───┘ └╥┘ ║ ║ ║
c: 4/═══════════════════════════════════════════════════════╩══════════════════════════╩══╩══╩═
3 0 1 2
まとめ
量子コンピュータの基本
量子コンピュータは、既存のPCやスパコンの進化系ではありません。
- すべての状態を同時に計算しますが、結果として観測できるのは、確率的に1つの答えだけです。
- 「正解を見つける確率を何らかの方法で1に近づける」のが量子アルゴリズムの目的です。本質的には複雑な行列計算を行っています。
- 量子コンピュータが高速化できるのは、「正解の検証が簡単にできる」という最低条件を満たす課題に限られます。例えば、「循環セールスマン問題」などは現状では高速化できません。
Amazon Braketで本物の量子コンピュータを動かしてみて
シミュレータでは理論通りの結果が出ましたが、本物の量子コンピュータの利用には、大きな課題に直面しました。
- ノイズがひどい：常時動いている実機（Rigetti Ankaa-3）でGroverのアルゴリズムを試しましたが、物理的なノイズが多く、ランダムと変わらないレベルの精度しかでませんでした。
- 可用性が低い：使おうとした高性能な実機はオフラインでした。使えることになっている時間帯でも実際には使えませんでした。
- コストが高い：ノイズしか得られなかった実機を数回動かしただけで、30ドルもかかりました。
- シミュレータは使いまくったけど0ドル
将来的な可能性
現時点での課題は多いものの、量子コンピュータが成熟すれば、特定の課題を劇的に変える可能性があります。例えば今回触ってみた「Groverのアルゴリズム」は、膨大な選択肢からの探索や最適な組み合わせを見つけ出すタスクにおいて、探索時間を大幅に短縮できます。
思ったこと
現在の量子コンピュータでの開発は、既存のコンピュータで言えば AND や OR や NOT を組み合わせて回路を作ることが必要な状態と感じました。
今後、抽象度が高く分かりやすいプログラミング環境、つまり量子コンピュータ用のプログラミング言語やコンパイラが登場することで、もう少し分かりやすく使えるようになるんじゃないかなと期待します。
元の記事を確認する
