量子コンピューターの特徴を活かすアルゴリズムの開発

量子コンピューターの適用分野はアルゴリズム次第

量子コンピューターに期待される適用分野は多岐にわたります。その代表例には、同じ「量子」という言葉を冠する量子化学シミュレーションや、一見すると量子コンピューターとは何の関連性もなさそうな機械学習・AIなどがあります。これらの適用分野において共通することは、量子コンピューターの特徴を巧みに活かす最適なアルゴリズム（量子アルゴリズム）が必要だということです。近年は、そうした量子アルゴリズムの開発が加速するほか、量子アルゴリズムを実装するためのソフトウエア開発キット（SDK）も提供され始めています。

本コラムでは、典型的な量子アルゴリズムの一つであるGroverの探索アルゴリズムを解説することで、量子アルゴリズムのエッセンスをお伝えしたいと思います。

そもそも量子コンピューターで問題を解くとは？

そもそも量子コンピューターで問題を解くとはどういうことか、量子コンピューターと古典コンピューターを比較しながら確認しましょう。

量子コンピューターは「量子ビット」を用いて計算を行います。量子ビットを使うと、量子力学の「重ね合わせの原理」を利用することで、「0」「1」の「どちらの状態も」取りながら計算を行うことができます。古典コンピューターは「ビット」の値（「0」または「1」）を書き換えながら計算を行いますが、量子コンピューターでは「量子ビットの値」（「0」「1」の重ね合わせ状態）を書き換えながら計算を行うのです。原理的には、古典コンピューター（ビット）で計算できることはすべて、量子コンピューター（量子ビット）で計算できるとされています。

では、どのような問題を量子コンピューターに解かせたらよいでしょうか。例えば「1+1=2」のような単純な計算は、量子ビットが4つあれば実現可能です。しかし直感的にも、この計算のために量子コンピューターを使うのは「もったいない」ことは自明です。古典コンピューターのアルゴリズムとは異なる、量子ビットならではの性質を活かしたアルゴリズム（量子アルゴリズム）に対応した問題において、量子コンピューターは威力を発揮するのです。

量子ビットの特性

ここで、量子ビットの特性を説明しておきましょう。量子ビットは、「0が観測される確率」、「1が観測される確率」、「位相」の情報をもちます。量子ビットは波の性質をもっており、0の状態の波と1の状態の波の両方を備えています。位相とは、その0の状態の波と1の状態の波のずれのようなものです。量子ビットのもつ情報は、ブロッホ球の表面上の任意の点として表現できます（図1にブロッホ球上のいくつかの点について、対応する量子ビットの意味合いを記載）。古典的なビットが0または1しか取り得ないのとは大きな違いです。

量子アルゴリズムは正解を浮き上がらせる

量子コンピューターは量子ビットならではの性質を活かしたアルゴリズム（量子アルゴリズム）に対応した問題で威力を発揮すると述べてきました。その一例として、古典コンピューターよりも速く問題を解くことができる量子アルゴリズム「Groverの探索アルゴリズム」がありますので、簡易な例を用いてエッセンスをお伝えしましょう。

この例は、フルーツ名の日本語と英語の対応表（図2左）から「マンゴー」の英語名称を検索せよ、という問題設定です。フルーツテーブルを見れば答えは一目瞭然「Mango」ですが、古典コンピューターで検索した場合のイメージは図2中央のようなものになります。検索の手順を考えると、フルーツテーブルの中身に順序性はないとすると、上から順番に１件ずつチェックしていき、4回目に目当ての値を見つけて終了します（図2右）。この手順では、最大で8回のチェックが必要となります。

次に、量子アルゴリズムであるGroverの探索アルゴリズムでこの問題を解いてみましょう。Groverの探索アルゴリズムでこの問題を解くには、3個の量子ビットを必要とします（検索対象のデータ数が23であるためで、対象が2Nの場合はN個の量子ビットが必要となる）。ここで、IDを二進数表記の000から111としているのは、3つの量子ビットとの対応をわかりやすくするためです（図3）。

図3に示した、Groverの探索アルゴリズムの各ステップは、次の通りです。

この探索アルゴリズムでポイントとなるのはステップ2です。ステップ２を実行すると状態011が求める正解であることがわかります。しかしここで量子ビットに何も操作を加えなければ、3つの量子ビットを観測しても、000～111の状態がランダムに観測されるだけで、正解は得られません。そこで011の状態が正解であるしるしとして、「位相を反転」させるのです。あとはステップ3以降で、「位相が反転」している場合には観測される確率を上げる操作を行っていきます。

かなり荒っぽい説明ですが、これが正解を浮き上がらせるGroverの探索アルゴリズムのエッセンスです。量子コンピューターで問題を解くとはどういうことか、その一端が少しでもイメージいただければ幸いです。

これからの量子アルゴリズムと適用分野への期待

Groverの探索アルゴリズムは、エラー耐性量子コンピューター（FTQC, Fault-Tolerant Quantum Computation）向けの量子アルゴリズムです。実用的なFTQCのハードウエア開発にはまだ多くの時間が必要であり、すぐに実用化に結びつくものではありません。一方、エラー耐性のない量子コンピューター（NISQ, Noisy Intermediate-Scale Quantum Computer）は、比較的早い段階で実用化されることが期待できます。実際に現在では、組合せ最適化問題に関するアルゴリズム開発が活発に行われており、量子化学シミュレーションや機械学習、物流の最適経路探索などへの応用が期待されています。

今後も量子コンピューターのハードウエア開発に加えて、量子アルゴリズムの発展にも期待したいと思います。