既存の量子コンピューターでも指数関数的な量子高速化を実現する接合木アルゴリズム

接合木アルゴリズムの実装は、Classiqのライブラリやドキュメントからご確認いただけます。接合木問題について詳しく知りたい方は、接合木のウェブサイトをご覧ください。

現在の量子コンピューティング分野における最大の課題の1つは、利用できるハードウェアが比較的初期段階であることです。量子ハードウェアはここ数年で大幅に進化したものの、多くの量子アルゴリズムは量子優位性を明らかにする規模での実行は依然として困難です。

それでも、現在の量子コンピュータ上で効果的に実行できるアルゴリズムも存在します。その一つが、2本のバイナリツリーを 「接合 」し、一方のツリーの端にある各ノードが、もう一方のバイナリツリーのランダムな2つのノードに接続されるようにすることで、指数関数的な量子高速化を実現するアルゴリズムです。

仮に各ノードが秘密鍵を持っていて、その鍵を入力すると隣接するノードの鍵を返す機械（オラクル）があるとします。この接合木問題の中心的な問いは、入口ノードの鍵を与えられた時、出口ノードの鍵をどれだけ効率的に見つけることができるかです。

ここでの最大の問題点であり、古典コンピュータが効率的に解くことができない理由は、どの鍵がどのノードに属しているかが実際にはわからないことです。ランダムな接続網に入った後、出口ノードに向かっているのか、それとも遠ざかっているのかは、実際に出口に到達するまで判断できません。そのため古典コンピュータでは、最悪の場合、接合木内のすべてのノードを調べる必要があります。

この記事では、接合木問題を解くための量子アプローチを概説し、Classiqを使い実装する方法や、現在の量子コンピュータでも接合木問題が解決可能なことをご紹介します。また、接合木アルゴリズムや同様のアルゴリズムが今後どのように進展するかについても考察します。

なお、接合木問題は、2002年10月にChilds氏らによって発表された論文「Exponential algorithmic speedup by a quantum walk」で初めて提起されましたが、この記事では、2023年12月にBabbush氏らによる論文「Exponential Quantum Speedup in Simulating Coupled Classical Oscillators」で提案されたアルゴリズムを取り上げます。

接合木アルゴリズムの仕組みとは？

一見すると接合木問題はコンピュータサイエンスや数学のグラフ問題を彷彿させますが、実は効率的なアルゴリズムの実装に役立つのはニュートン力学です。接合木構造を、ノードが球、エッジがバネであるシステムだと考えてみましょう。入口ノードに対応する球を押し出すと、その動きが伝播し、最終的に出口ノードに影響を与えます。

この球とバネのシステムは、順序がランダムなノードの隣接行列として表現できます。そして、この行列からブロックハミルトニアンを作成し、ハミルトニアンシミュレーションを使って、各振動子の変位と速度をモデル化した量子状態を生成します。

次に、入口ノードに対応する振動子を押し出すように量子状態を設定します。この押し出しは接合木システムの列ごとに伝播し、1本のツリーの列数がNの場合、時間2Nで出口ノードの速度は急上昇します。量子コンピュータを使ってこの原理を利用すれば、アルゴリズムの時間複雑性を指数関数時間から線形時間へと高速化することができます。秘密鍵がビット列の値であると仮定すると、時間2Nで急上昇が観察されるビット列を特定することで、効率的に出口ノードの秘密鍵を見つけることができます。

接合木アルゴリズムの実装方法

接合木アルゴリズムは、Classiqを使用することで非常に効率的に実装できます。接合木構造を表すブロックハミルトニアン（NumPyなどの外部ライブラリを使用して生成）を保持した後、Classiqの組み込み関数の一つを使用してパウリ分解を行い、パウリリストを取得します。このステップは、Classiqのハミルトニアンシミュレーション関数がパウリリスト形式を受け入れるために必要となります。その後、Classiqのハミルトニアンシミュレーション機能を使用して、指定した時間における量子状態の測定を行います。

私の実装では、出口ノードを表す量子状態のスパイクが明確に観測できるように、2Nの周りに異なる時間を表す複数の異なる量子回路を組み立てています。デモ向けにノードの順序を線形にすることで、出口ノードがどこにあるかを明確にし、その特定の状態のスパイクを観測できるようにしていますが、このアルゴリズムはClassiqの組み込みSDKやIDEの機能を使うことで、どのようなノードの順序でも実装することができます。

既存の量子ハードウェアでは、どのように解決できるのか？

このアプローチの主な問題点は、量子ビット数の大きい接合木構造では、パウリリストが非常に大きくなってしまう可能性があることです。この問題に対する私の解決策は、アドホックなパウリ行列の切り出しと近似アルゴリズムを作成することでした。これにより、非常に大きくなる可能性があるパウリ行列を、データに含まれる重要な情報を保持しつつ、管理しやすいサイズに縮小しました。また、より小さな量子ビット数のパウリ行列に基づいた近似を使用することで、高い量子ビット数に対応するパウリ行列の生成を避けることができました。

より優れた量子ハードウェアが開発されるにつれて、量子コンピュータは深い回路を処理できるようになり、より大きなパウリ行列の入力にも対応できるようになります。現在の量子ハードウェアで接合木アルゴリズムを実行するには大幅に切り詰めたパウリ行列を使用する必要がありますが、将来の量子コンピュータでは削除するデータが少なくなるため、アルゴリズムをより正確に実行できるようになるでしょう。

接合木アルゴリズムは何の役に立つのか？

現在のところ、接合木アルゴリズムには知られた応用例はありません。このアルゴリズムは設定が比較的簡単なためデモンストレーションに適しており、錬成調和振動子のシミュレーションアプローチを使用した指数関数的な量子高速化を示すための「練習用の問題」として使われています。 

接合木問題は、錬成調和振動子のシステムに変換でき、量子コンピュータ上で効率的にシミュレーションできるグラフ問題の一例に過ぎません。将来的には、現実世界で強い応用可能性を持つ、より興味深い例が発見されるかもしれません。いずれにせよ、接合木アルゴリズムは、グラフ問題、ニュートン力学、量子コンピュータが一体となり、今日の量子コンピューターでも指数関数的な量子高速化を可能にするという、ユニークで興味深い事例であることに変わりはありません。

接合木アルゴリズムの実装は、Classiqのライブラリやドキュメントからご確認いただけます。接合木問題について詳しく知りたい方は、接合木のウェブサイトをご覧ください。