量子技術を活用したデータベース検索の高速化研究　Grover searchアルゴリズムの改良で問題を解決する

自己紹介

手塚宙之氏（以下、手塚）：ソニーグループ株式会社R&Dセンター先端研究部の手塚です。（スライドを示して）本日は、ゲート型量子コンピュータの活用事例として、このようなタイトルでお話しします。かなりスペシフィックな内容になっているので、少々わかりづらいところがあるかと思いますが、全体の流れと大まかな概念を伝えられればと考えています。

現在は、慶応義塾大学の量子コンピューティングセンターで共同研究員を務めています。本日の話は、そちらでの成果の一部となっています。

まず私の所属する組織について簡単に紹介します。（スライドを示して）こちらが弊社R&Dセンターの技術ポートフォリオです。領域は非常に多岐にわたっていて、画像関係、AI関係、ロボティクス、センシングと、非常に幅広い分野を担当しています。

これらを用いて弊社内の幅広い事業を支えるとともに、新たな技術・製品、サービスを創出することをミッションに活動をしています。私の所属する先端研究部は、これらの中でも特に先端、長期的視点が必要なもの、かつ不確実性の高い領域を分野横断的に担当している部署です。このような趣旨にも、量子コンピューティングは非常に親和性が高いということで、研究をしています。

研究の最終的なゴール

ここから本題に入ります。はじめに、本研究の最終的なゴールを共有しておきます。本研究では、量子技術を用いてデータベース検索を高速化しました。

昨今の我々の生活では、あるデータがあった時に、「これと最もよく似たデータは、このデータベースの中のどこにあるのか」というデータベース検索が、いたるところで行われているかと思います。

古典技術を使う場合、基本的にはこれらのデータを一致しているかどうかを逐一見ていきます。量子技術を使うことにより、データベースの重ね合わせ状態を作れて、より少ない手数で結果が求められるの（ではないかということ）が研究の方向性になります。

ここまで話を聞いて、「なにを今さら」と感じる方がいるかと思います。それもそのはずで、量子コンピューティングの得意なことが何かという質問に対しては、長い間、素因数分解やデータベース検索が速くなる（こと）と言われてきました。

ただ一方で、こういった問題設定を実際に量子技術を使って解いてみることは、あまり真面目にやられていないというのが実情です。実際やろうとするとどうなるかという問題点についても、この後に話していきたいと思います。

（スライドを示して）こちらがこの後の話の全体像です。前半部分でタイトルにあるとおりGrover searchを簡単に紹介します。後半で、今回モチーフとして用いた量子画像について紹介したいと思います。

Grover searchについて詳しく調べる

ここで導入です。（スライドを示して）昨今、量子コンピュータへの期待が非常に高まっていて、日々さまざまなアルゴリズムが提案されてきています。しかしながら、これらすべてに量子加速の理論的な裏づけがあるわけではありません。まだまだヒューリスティックなものもたくさんあります。

その中でもしっかりとした理論に裏付けされたアルゴリズムももちろんあり、その代表例がこういったものです。特にこの中でも比較的汎用的で、いろいろなところで用いられているGrover searchという重要なアルゴリズムがあります。今回は、これについて詳しく調べてみたというのが研究のスタートポイントです。

Groverアルゴリズムですが、はじめに提案されたのは25年ほど前です。（スライドを示して）このようなタイトルの論文の中で、Groverさんがこのアルゴリズムの提案をしました。

その後、もうほとんどすべてと言っていいと思うのですが、量子計算の教科書や解説の記事、さらには学術ジャーナルの中でも、こういった図を使ってアルゴリズムの紹介がされています。

（アルゴリズムを）簡単に説明すると、まず初期化された量子状態を準備します。これに対して、アダマールゲートという演算、操作を行うと、すべての量子状態が均等に重ね合わされた量子状態が生成されます。

この状態をデータベース状態と見ることができます。続いて、ユーザーが検索したいデータを“クエリ”と呼びますが、ここでは例として「|q>」と書いています。これを使って、オラクル演算子を構成します。

その後に拡散演算を行うと、振幅増幅という現象が起ります。この状態を観測すると、ユーザーが設定したクエリの量子状態が高確率で得られるアルゴリズムになっています。

問題を解こうとしたときに生じる問題点

実際にこの処方箋に従って回路を組んでシミュレーションや実機の量子コンピュータで回すと、確かによく動くのですが、ここでふと思うわけです。「そもそもこれって、我々がやりたかったデータベース検索になっていますか？」と。これを使って実際の問題を解こうと思うと、いくつか問題点が出てきます。

（スライドを示して）一番わかりやすいものは、このオラクル演算子です。このオラクル演算子を作る時に、欲しい量子状態「|q>」を使って組むと言いましたが、そもそも量子状態の|q>が欲しいからこのアルゴリズムを使っているわけで、完全にニワトリと卵の問題になってしまっているというのが、1点目です。

さらに、データベースステートの量子状態を見てみると、すべての量子状態が均等に重ね合わされた状態という、非常に特殊な状態を想定してしまっています。

ここで「データベースをもう少し複雑化すればいいだろう」と考えるわけですが、任意の量子状態を生成するには、一般に2の指数回の計算ステップが必要であることが知られています。したがって、こういうことを考えると、後半で期待されている2乗加速のよさが消されてしまいます。

このように、既存のアルゴリズムでは、いわゆる我々が想像するようなデータベース検索問題には、そのままでは適用できない状況でした。そこで本研究では、これらの問題点を解決するスキームを考えた次第です。

データベース検索問題の定義

その具体的なスキームの話をする前に、今一度、データベース検索問題を定義したいと思います。一番シンプルなデータベースとして、電話帳があるかと思います。

（スライドを示して）電話帳は、電話番号とそれが誰のものかという情報です。データと、それにひもづくインデックスが束になったデータセットが手元にあります。こういう状態で、外から電話がかかってきた時に、電話番号をもとに「これは誰のものか」というインデックスの情報を求めます。これが一番シンプルなデータベース検索といえます。

この概念を拡張すると、データ分類が可能になります。同様に、データベースがあって、新たなクエリというデータが入ってきた時に、このクエリとデータの類似度を計算することで、「このクエリはどの属性に属するのか」が求められるようになります。

（スライドを示して）本研究で採用した問題設定も、真ん中の問題設定のアナロジーとなっていて、量子データベース検索問題でこのような問題設定を考えました。

真ん中と同様に、データの部分にはさまざまな量子状態を準備します。これとインデックスキュービットがエンタングルした状態が重ね合わされた状態をデータベースステートとして準備します。

今度はクエリデータです。クエリとデータの類似度を計算して、それが最も高くなるインデックスはどれかを求める問題を考えました。

（スライドを示して）実際に解く提案手法がこちらです。けっこう込み入っているので、技術的な内容に興味がある方は、ぜひアーカイブ論文をご参照ください。

ポイントは大きく2点あります。1点目のデータを作るところに関して、先ほど一般には2の指数回の計算ステップが必要という話をしましたが、量子機械学習の手法をうまく応用することによって、2の指数回ではなくて、Qubit数の多項式回程度の浅い回路で状態が生成できるスキームを考えました。

さらにデータとクエリの類似度を計算すると言いましたが、Inversion testという手法を使うことによって、オラクル演算子がクエリに非依存になるフレームワークを考案しました。

こうすることで、先ほど言った問題設定のとおり、クエリの類似度がインデックスごとに観測確率として出てきて、|q>という量子状態はインデックス|011>にきちんと対応することが求められるアルゴリズムを再構築しました。

量子画像に適用した結果

今回は、これを量子画像に適用しました。量子画像について簡単に紹介します。一言で言ってしまうと、ふだん我々が目にする画像データを、量子状態としてマッピングするものです。

（スライドを示して）例えば、弊社のフラグシップの一眼レフカメラで1枚パシャッと写真を撮ると、こういった規模のデータがアウトプットされます。ビット数で見るとかなり大きいですが、量子画像として扱うと、わずか30qubitで済むというインパクトのある概念になります。

もう少し具体的に言うと、画像はピクセル位置とそれに対応した輝度情報で表されるので、それの重ね合わせ状態で量子画像を作ります。これをデータの部分に埋め込むことで、先ほどのアルゴリズムが動く算段です。

（スライドを示して）それを使って行ったデモンストレーションの結果がこちらです。こちらではトイモデルとして非常に小さい問題設定を使っていますが、4ピクセルで8枚のデータベースが重ね合わされたものを使っています。

これに対して、例えば0hという真っ黒な画像を検索にかける、「この0hはどのインデックスにあるか」というと、000というところで000が最も高い確率できちんと求められます。クエリを変えるとこれが動いていくので、きちんと動いていることがわかります。

グラフの上段と下段の2段が何かというと、今回提案したアルゴリズムは、Groverオペレーターを使って確率増幅をする前に、類似度計算をしています。上段が確率増幅前で、下がGrover演算子を使った後になっています。相対関係がきちんと維持されたまま振幅増幅しているので、やはりきちんと動作していることが確認できます。