はじめに
前回は、量子回路について整理しました。
今回は第4回として、量子アルゴリズムを見ていきます。
量子回路が少しわかってくると、次に出てくるのが Shor、Grover、量子フーリエ変換、量子シミュレーション、NISQ 時代のアルゴリズムあたりです。
ここでまた迷子になります。
さらに、「量子優位性」みたいな言葉も出てきます。強そうな言葉ですが、何の問題で、何と比べて、何が有利なのかを分けて見ないと、期待値だけが先に走りがちです。
量子回路は、状態ベクトルにゲート行列をかけて、最後に測定するものとして見られました。一方、量子アルゴリズムは「その回路を使って、解きたい問題の構造を見つけてどう計算するか」の話です。
古典コンピュータでも、AND/OR の回路がわかることと、ソートや暗号や機械学習のアルゴリズムがわかることは別でした。量子でも同じです。
この記事では、Shor や Grover の中身を数式で追うのではなく、量子アルゴリズムを読むときに迷子にならないための見取り図を整理します。
量子アルゴリズムは「全部を並列に試す」ではない
いろんなところで言われてはいますし、前回までの記事でも書きましたが、最初に避けたい誤解はこれです。
量子コンピュータ = 全パターンを同時に試せる = 何でも一瞬
並列に試すという説明は入口としては便利ですが、そのまま理解すると勉強していくうちに、混乱します。また、他の人と話すときにもわかってない人扱いされます（たぶん）。というか、並列にやるから早いって説明を聞くと、「え、ちゃうやろ？この人わかってんのかな？」となります。自分のことは棚に上げつつ。
n qubit の状態は 2^n 個の基底状態に対する振幅を持てます。ただし、測定して取り出せるのは基本的に1つのビット列です。
つまり、全部の答えをリストとして取り出せるわけではありません。
量子アルゴリズムで重要なのは、たくさんの状態を持つこと自体ではなく、欲しい答えの振幅が大きくなるように干渉を設計することです。
状態を広げる
↓
問題の構造を位相や振幅に入れる
↓
干渉で欲しい答えの確率を上げる
↓
測定する
この見方を持っておくと、「全パターン並列」という雑な理解から少し抜け出せる気がします。
量子優位性は条件つきで見る
量子アルゴリズムの話をしていると、「量子優位性」という言葉も出てきます。
これはざっくり言うと、古典コンピュータでは難しい計算を、量子コンピュータが有利に実行できることです。ただし、「有利」の意味はかなり文脈依存です。
理論的に計算量がよいのか、特定のベンチマークで勝ったのか、実用上のコストまで含めて意味があるのかで、話が変わります。
なので「量子優位性がある」と聞いたときは、何の問題で、どの古典手法と比べて、何を指標にしているのかを見る必要があります。ここを飛ばすと、かなり話が盛られて見えます。それがむちゃくちゃ難しいんだとは思いますが。。。
量子アルゴリズムには構造が必要
量子アルゴリズムが効くには、問題側に何らかの構造が必要です。ということらしいです。
雑に言うと、量子コンピュータは「候補が多い問題」すべてに強いわけではありません。候補の中にある規則性、周期性、対称性、振幅を増幅できる条件などを使います。
古典アルゴリズムでも同じです。配列の中から目的のデータを探す場合、ソート済みなら二分探索を使えますが、何の構造もない配列では一つずつ確認するしかありません。
量子でも、構造があるから干渉を設計できます。構造がなければ、量子でも魔法のように答えが出るわけではありません。
Shor は「因数分解を総当たりする」わけではない
量子アルゴリズムで有名なのが Shor のアルゴリズムです。
よく「量子コンピュータができると RSA が破られる」と言われます。これは Shor のアルゴリズムが大きな整数の素因数分解に効くからです。
ただし、Shor は因数分解を直接総当たりしているわけではありません。
ざっくり言うと、因数分解の問題を周期を見つける問題に変換します。そして、その周期を量子フーリエ変換のような道具で見つけます。
因数分解
↓
周期発見の問題に変換
↓
量子回路で周期に関係する情報を振幅に出す
↓
測定して古典計算で後処理
ここで大事なのは、量子部分だけで全部が完結しているわけではないことです。
量子回路で情報を取り出しやすい形にして、測定し、その結果を古典コンピュータで後処理します。
量子アルゴリズムは、量子だけでなく古典計算とのハイブリッドとして見るほうが自然です。
Grover は「探す」けれど万能検索ではない
もう1つ有名なのが Grover のアルゴリズムです。
Grover は、ざっくり言うと、条件を満たす答えの振幅を増幅するアルゴリズムです。
候補全体の重ね合わせを作る
↓
正解に印をつける
↓
正解の振幅を増幅する
↓
測定する
この「正解に印をつける」部分は oracle と呼ばれます。
oracle は、雑に言うと「この候補は正解か？」を判定する回路です。
ただし量子回路では、途中で情報を捨てるような普通の比較回路をそのまま置くわけにはいきません。X ゲートや制御ゲートを組み合わせて、量子回路として「一致した候補に印をつける」形にします。イメージとしては、古典の == 判定を量子回路に埋め込む感じです。
ここも誤解しやすいです。Grover は、何も知らない状態で勝手に答えを見つけてくれる魔法ではありません。
「この候補は正解か」を判定する仕組みは必要です。その判定を量子回路として用意できるときに、振幅増幅で探索回数を減らせます。
古典的には N 個を見る必要がある探索を、理想的にはだいたい √N 回くらいにできます。ただし、指数的に速くなるわけではありません。
量子シミュレーションは少し別の本命感がある
Shor や Grover は「古典の問題を量子で速く解く」雰囲気があります。
一方で、量子シミュレーションは少し見方が違います。
量子化学や材料の問題は、そもそも対象が量子的です。分子や電子の振る舞いを古典コンピュータで正確に扱おうとすると、状態空間が爆発します。
この発想でよく名前が出てくるのがファインマンです。物理学科卒はみんな知っているであろう『ご冗談でしょう、ファインマンさん』で有名な、あのファインマンです。ファインマンさんは、自然界の量子系を古典コンピュータで無理やりシミュレーションするより、量子力学に従う機械でシミュレーションするほうが自然ではないか、という方向の問題提起をしました。
量子系を量子コンピュータでシミュレーションする。
実用には誤り訂正やスケールの問題がありますが、「量子コンピュータが本質的に得意そうな領域」としては、量子シミュレーションはかなり納得感があります。
NISQ 時代の量子アルゴリズム
現在の量子コンピュータは、ノイズがあり、qubit 数も限られています。いわゆる NISQ と呼ばれる時代です。NISQ は Noisy Intermediate-Scale Quantum の略で、ざっくり言うと「ノイズあり・中規模の量子コンピュータ」です。
この文脈では、量子回路を何度も試して、その結果を見ながら古典コンピュータ側でつまみを調整するタイプのアルゴリズムがあるようです。今の機械で試しやすい一方で、すぐに古典計算を圧倒するとは限らない、くらいの温度感です。
アニーリングや量子インスパイアードもある
ここまでの話は、主にゲート型量子コンピュータを前提にしています。一方で、組合せ最適化の文脈では量子アニーリングも出てきます。これは Shor や Grover を動かす万能なゲート型とは別の見方が必要です。
また、量子インスパイアードという言葉もあります。これは量子コンピュータそのものを使うというより、量子計算やアニーリングの考え方にヒントを得て、古典コンピュータ上で高速な最適化を狙うアプローチです。「量子」と名前がついていても、実際に量子ハードウェアを使っていない手法があります。量子コンピュータだけで優位性を言ってるのかもポイントかと思います。
量子アルゴリズムを見るときの整理表
量子アルゴリズムは次のように分類すると見やすくなります。
| 種類 | 代表例 | 見るポイント |
|---|---|---|
| 構造利用・振幅操作系 | Shor、Grover | 構造や正解候補をどう取り出すか |
| 量子シミュレーション系 | 量子化学、材料 | 量子系を量子系として扱えるか |
| NISQ 時代のアルゴリズム | 現在の量子コンピュータで試す手法 | 量子と古典のループをどう回すか |
| アニーリング/インスパイアード | 最適化向けの別アプローチ | ゲート型と分けて見る |
どれも「全パターンを並列に試して読む」ではありません。
問題の構造をどう量子状態に埋め込み、干渉や測定でどう取り出すか、という話です。
おわりに
今回は、量子アルゴリズムをざっくり整理しました。自分の中では、次のように見ると迷子になりにくいです。
- 全パターンを並列に試して全部読むわけではない
- 量子優位性は、何と比べて何が有利なのかを見る
- 問題の構造や正解候補を振幅・位相に写して取り出す
- 量子シミュレーションは、量子系を量子系として扱う発想
量子アルゴリズムをさらに理解するには、ここからさらに実装に入る必要があります。道のりが長い。。。
次は、ソフトウェア編として、Qiskit などのスタックで量子回路や量子アルゴリズムをどう動かすのかを整理する予定です。
まだ自分も整理中なので、間違いや違和感があれば教えてもらえるとうれしいです。