中国科学院コンピューティング技術研究所の孫暁明氏：多項式レベルの加速の実現、量子探索アルゴリズムの利点と課題

4月20日、Syncedは「量子コンピューティング」に関するオンライン円卓会議イベントに、中国科学院コンピューティング技術研究所の研究者であり、量子コンピューティング研究所所長である孫暁明氏を招待しました。彼の講演のタイトルは「量子探索アルゴリズムと回路最適化」でした。報告では、探索アルゴリズムと回路最適化の開発と現在の課題について簡単に振り返り、これら 2 つの分野における彼のチームの作業の進捗状況の一部を紹介しました。

スピーチレビュービデオ（クリックすると元のテキストが読めます）: https://app6ca5octe2206.pc.xiaoe-tech.com/detail/p_62612f69e4b09dda125e441b/6?fromH5=true

Synced は、元の意味を変えずにスピーチの内容を編集しました。本日ご紹介したいのは、探索部分を中心に量子探索アルゴリズムと回路最適化についてです。ご存知のとおり、検索は古典的なコンピューターで最も広く使用されているアルゴリズムの 1 つです。検索エンジン、パス ナビゲーション、推奨システムなどに適用できます。今では新薬の開発にも応用でき、暗号解読を探索問題として捉えることもできるようになっています。

たとえば、ハッシュ関数を解読したい場合、それはハッシュ後に最初の 32 ビットがすべて 0 であるなど、特定の特性を満たす文字列を検索するのと同じです。コンピュータ アルゴリズムの分野ではバイブルとみなされている一連の書籍があることは周知の事実です。それは、Knuth 著の「The Art of Computer Programming」です。その第 3 巻全体はソートと検索について説明しており、検索の重要性を示しています。

量子探索アルゴリズム

量子コンピューティングが 1990 年代に突然普及したのも知られています。その重要な理由の 1 つは、ショアのアルゴリズムとグローバーのアルゴリズムという 2 つの重要なアルゴリズムが導入されたことです。グローバーのアルゴリズムは、順序付けされていないデータベース内の特定の要素を検索するために使用できます。たとえば、データベース内の特定の IP アドレスを検索したり、ハッシュ関数の原像を見つけたり、チェス ゲームの最適な戦略を見つけたりする場合、これらはすべて検索タスクと見なすことができます。

従来のアルゴリズムでは、インデックスのないデータベースでは、データベースのサイズが n の場合、必ず n に比例した時間がかかります。量子アルゴリズムは、平方根程度の加速を実現できます。ショアのアルゴリズムのように指数関数的な加速は実現できませんが、平方根は実際には多くの場合非常に意味があります。たとえば、ビッグデータ処理では、処理するデータが 1 億個ありますが、Grover アルゴリズムではそのうちの数万個を処理できます。たとえば、暗号解読では、元のブルートフォース列挙アルゴリズムは 2 の 90 乗でしたが、これを 2 の 45 乗程度に減らすことができます。現在のスーパーコンピュータでは、2 の 45 乗のスケールが許容されます。

Grover 検索では、非常に重要なモジュールである Oracle を使用します。量子ビットが 50 個あれば 2 の 50 乗の並列加速が実現できる、といった記述をよく見かけますが、基本的にはその通りです。彼が実際に言っていたのは、例えば n を logN とすると、n ビットの重ね合わせ状態を準備できれば、n 個のゼロ状態を事前に準備してハードマード変換を実行することで、1 から N (または 0 から N-1 = 2 の n 乗マイナス 1) までのすべての計算基数の重ね合わせ状態を生成できるということでした。そして、線形性に従って、Oracle を通過した後、すべての f(x) (x=1~N) を計算し、次のような状態を取得します (図には青い重ね合わせ状態が含まれています)。

実際には、ここには 2 つの問題があり、これについてはレポートの残りの部分でも説明しますが、QRAM によって何を達成できるかという観点に基づいた Oracle の準備に関する問題です。しかし、多くの問題では、この Oracle には特定の意味があります。たとえば、先ほど紹介したように、下の図の左上にあるハッシュ関数であったり、SAT 式などの NP 完全問題であったりします。そのような神託をどのように準備するのでしょうか?実際、可逆関数である限り、量子的な方法で実現できることは、かなり以前から定性的にわかっていました（たとえば、ニールセンとチュアンの著書「量子計算と量子情報」）。最近、私たちはオラクルの量的な実装に関するそのような作業を行い、それを arxiv にアップロードしました。私たちは、CNF または SAT オラクルの作成という関数のクラスをターゲットにしています。論文アドレス: https://arxiv.org/pdf/2101.05430.pdf

もう一つの疑問は、計算結果をどのように読み取るかということです。量子不確定性原理はご存じのとおりです。2^n 個の結果すべてを一度に読み出すことは不可能です。毎回読み出す確率は、実際には 1/2^n しかありません。つまり、50 ビットある場合、毎回結果が表示される確率は 1/2^50 しかないということです。特定の計算結果を得たい場合、測定を繰り返すのに 2^50 回を費やす必要があるため、ここでは量子加速は行われません。

しかし、Grover アルゴリズムは、複数の対称性と反転を処理するように巧妙に設計されており、高い確率で目的の結果を得るのに N の平方根の時間しかかかりません。

振幅増幅アルゴリズム

グローバーの後、理論研究者は振幅増幅と呼ばれるアルゴリズムを提案しました。これは、現在ランダム検索アルゴリズムが存在する場合、その成功率は 10,000 分の 1 など、比較的低い可能性があるというシナリオを解決することを目的としています。このアルゴリズムを呼び出すことで、高い成功確率が得られることを期待しています。

昔の人はよく「三人の靴屋は一人の諸葛亮より優れている」と言った。各アルゴリズムの成功確率が 10,000 分の 1 の場合、平均して 10,000 回繰り返す必要があります。しかし、振幅増幅アルゴリズム（Grover のアルゴリズムに非常に似ています）の考え方を使用すると平方根計算を実行できます。つまり、10,000 回かかる計算が、実際には約 100 回で実行できることになります。

もちろん、このような加速を実現するには、事前にアルゴリズムを量子アルゴリズムに変換する必要があります。例えば、先ほど述べた NP 完全問題や SAT 問題に当てはめると、ランダムに解を選択した場合、成功確率は 1/2^n になります。したがって、グローバーのアルゴリズムを単純に使用すれば、2 の n 乗の平方根、つまり 1.414^n を得ることができます。

ただし、アルゴリズム設計テクニックをいくつか追加することもできます。これは、アルゴリズム テクノロジーを一切使用せずに、単に Grover アルゴリズムを呼び出しているからです。より優れたアルゴリズム設計を行い、より優れた SAT 解決アルゴリズムを使用すれば、複雑さは実際に以前よりもはるかに小さくすることができます。

他にもいくつか問題があります。たとえば、ビッグデータでは、三角形のような最も単純なサブクラスターであっても、コミュニティ内のサブクラスターを見つけたいことがよくあります。実際のところ、最良の量子アルゴリズムがこの問題をどの程度まで解決できるかはまだわかっていません。

単純に Grover のアルゴリズムを使用すると、三角形の合計数が最大で n^3 であるため、Grover は n^1.5 アルゴリズムを作成できます。その後、Szegedy は n^10/7 を達成でき、現在は n^5/4 を達成できます。しかし、これより優れたものがあるかどうかは、まだわかりません。

これは実際に私たちにインスピレーションを与えてくれます。それは、多くの人が尋ねていることです。なぜ量子アルゴリズムの設計が難しいのか。私の考えでは、その理由の 1 つは、量子が確かに少し直感に反するということです。量子は私たちの古典的な世界のように目に見えず、触れることもできないため、設計するのは非常に困難です。一方、この方向の研究に従事する人はまだ十分ではありません。ニューヨークタイムズ紙の報道によると、量子コンピューティングに携わる専門家は世界中に1000人未満だそうです。

研究結果の紹介ローカル検索 以下は、Shengyu と私が以前一緒に行った研究の紹介です。 グローバー検索は、グローバル極値を解くために使用できます。つまり、グローバル最大値または最小値を見つけるには、n の平方根時間がかかります。たとえば、局所的な極値を見つけるだけであれば、機械学習には多くのアプリケーションがあり、多くの場合、局所的な極値を見つけるだけで十分です。アーロンソンはこの問題を最初に研究し、基本的に立方根を求めることができるアルゴリズムを提示しました。聖宇、姚先生、そして私は、この三次加速が最良であることを一緒に証明しました。

重量測定

私たちが最近取り組んだ「重み決定問題」と呼ばれる小さな作業についてお話しします。 2 つの状況、つまり、解の数が k または l のいずれかである状況を区別する必要があります。ここで、k と l は事前に与えられた 2 つの数値です。他の状況は関係ありません。これら 2 つの重みを区別できれば十分です。

k が 0、l が n/2 に等しい、つまり解がちょうど半分あるか、解がまったくないなどの特殊なケースも見られます。これが、最初に提案された量子アルゴリズムである Deustch-Josza アルゴリズムが行うことです。たとえば、k が 0 で l が 1 の場合、少なくとも 1 つの解が存在するかどうかを区別するのが Grover のアルゴリズムです。

実際、私たちより前に、中山大学の邱道文教授とその同僚がいくつかの研究を行っており、他の研究者もいくつかの研究を行っていましたが、ここでは詳しくは触れません。

主な結果 次に、結論についてお話ししましょう。下限と上限を示します。ここでは、上限と下限がどのように見えるかを画像を使用して説明します。右上の図は量子アルゴリズムである上限を示しています。異なるパラメータ d に対して、まずポイントのバッチを生成できます。たとえば、前の作業では、緑、赤、およびこれらのポイントのみを処理できます (中央の図)。基本的にすべての領域を解決しました。たとえば、d=2 の場合、2 つのポイントがあります (右上の図)。これらのポイントは両方とも、緑色のポイント (左の図) と同様に、左上の 1 つの量子クエリのみを必要とします。

次のケースには 5 つのポイントがあり、下の右上の図の 4 つの赤いポイントと 1 つの青いポイントです。左上隅の水色の領域は、量子によってわずか 2 ステップで解決でき、以前の結論の一部を完全にカバーします。同時に、これら 5 つのポイントの右下側は、右下の写真の薄い黄色の領域です。 2 つの量子ステップでは解決できないことは証明できますが、少なくとも 3 つのステップが必要です。次に、別のポイントのバッチを持つセット S_3 をさらに定義します。左上には 3 ステップで実行できるアルゴリズムがありますが、右下のアルゴリズムは完了するのに少なくとも 4 ステップが必要です。同様の結果は、任意の d に拡張できます。先ほどの Shengyu さんの論文には、私の元博士課程の学生である Yuan Pei さんについても触れられています。この研究は、Yuan Pei 博士、現在博士課程に在籍している He Xiaoyu さん、そして私の元同僚である Yang Guang さんと共同で行いました。

また、量子計算の複雑さの下限も設定しました。つまり、量子では特にうまく処理できない領域がいくつかあることを証明できます。最も重要な定理の 1 つは、2001 年に Beals らによって証明された結論であり、正確な量子アルゴリズムの場合、関数を多項式として記述し、その次数を 2 で割ることで、その複雑性を下限に抑えることができるというものです。したがって、この問題を多項式表現の多項式次数を考慮する問題に変換することができます。

多項式の次数を調べるには、いくつかのツールが必要です。チェビシェフ多項式と呼ばれる非常に有名な多項式があります。これは、cos mθ (m は整数) が cos θ の多項式として表されることを意味します。たとえば、2 倍角の公式によれば、cos 3θ は次のように表すことができます。

グローバーの探求の鍵は、実はこのようなチェビシェフ多項式なのです。この研究でもこれを使います。最も重要な点は、チェビシェフ多項式が多項式空間の基底を構成するということです。次に、任意の多項式をこの基数集合に展開し、チェビシェフ多項式のいくつかの特性を使用して下限を証明します。

事前知識を用いた量子探索 次に、私たちが最近行ったもう 1 つの研究である「事前知識を用いた量子探索」を紹介します。グローバー探索では、見つけたい解決策については何もわからないため、解決策がどれか 1 つである確率は等しいことになります。しかし、α-β 剪定などの一部の検索問題では、特定の確率分布、つまりどのパスが選択される確率が高いかが事前にわかっています。

これを p = (p_1, p_2, …, p_N) の形式でモデル化すると、1 が解である確率は p_1、2 が解である確率は p_2、N が解である確率は p_N であることがわかります。このような状況で検索を行う最善の方法は何でしょうか?私たちは最近この問題を研究しましたが、その核となる結論は、特別な初期状態を準備する必要があるというものでした。これは、初期状態の準備の問題について Shengyu と後に議論する際の出発点の 1 つでもありました。この特別な初期状態を準備した後のアルゴリズムのステップ (対称性、反転など) は、Grover アルゴリズムと非常に似ています。漸近的に見ると、これはほぼ最適であることが分かります。

回路の最適化次に、量子回路の最適化に関する私の研究について簡単に紹介します。最近、量子ハードウェアが急速に発展しています。ジョン・プレスキル教授は2018年にNISQ（Noisy Intermediate-Scale Quantum System）と呼ばれる概念を提唱しました。盛宇氏はIBMがロードマップを持っていると述べ、来年には1,000ビット以上を達成できるだろうと語った。ただし、ノイズが多いのが特徴なので、回路の深さを圧縮する必要があります。

以前、CNOT 回路の行の深さについて議論する作業を行いました。ご存知のとおり、CNOT とシングルビット ゲートの組み合わせは汎用性が高く、あらゆる量子回路を生成できます。したがって、CNOT 回路は非常に重要です。

以下は、CNOT 回路を等価回路に変換する方法を示した例です。元の深さは 7 でしたが、現在の深さは 5 です。重要な点は、CNOT 回路は基本的にこれらの変数の線形結合として記述できることです。

CNOT 回路の簡略化は、実際には F_2 上の可逆行列分解と密接に関係しています。実際、各レイヤーに複数の CNOT ゲートを配置できます。たとえば、下の図の左下の最初のレイヤーには 2 つの CNOT ゲートがあり、これは右下図の 2 番目のマトリックスに対応しています。線形代数の観点から見ると、これは行消去、つまり 1 行目を 2 行目に、3 行目を 4 行目に加算する操作として考えることができます。

したがって、CNOT 回路の簡略化は数学的な問題に変換できます。並列ガウス消去法が許可されている場合、可逆行列を単位行列に変換するにはいくつのステップが必要ですか?各ステップは並行して実行できることに注意してください。

結果の概要 私たちは以下の結果を得ました。その主な内容は、補助ビットと回路の深さの関係について議論することです。これは前回の結果です。補助ビットがn^2に達したときの結果もありますし、補助ビットが0のときの結果もいくつかあります。両側の結果を改善でき、より一般的な結果が得られます。つまり、補助ビットが m 個ある場合、回路の深さを厳密な境界に最適化できます。これは、下の図の右下隅の式です。特に、m が 0 で、m が n^2 の場合、私たちの結果はそれぞれ 2 つの元の境界を最適化できます。

チームと著書の紹介下の写真は、先ほどの論文で触れた張家林教授、田国晶教授、袁培博士、江嘉青、何暁宇、楊帥を含む、中国科学院計算技術研究所の量子コンピューティングおよびアルゴリズム理論研究室チームのメンバーの一部です。

このイベントには2つの出版社から強力なサポートをいただきました。私たちは、尚雲教授、李盧州教授、尹章奇教授、魏兆輝博士、田国晶博士とともに、マイケル・A・ニールセン氏とアイザック・L・チュアン氏が共著した、総ページ数570ページを超える量子コンピューティング分野の最も古典的な教科書『量子コンピューティングと量子情報 10周年記念版』を3年かけて翻訳しました。現代の観点から見ても優れた教科書であると考えます。もちろん、この本には最近の内容（たとえば、ハードウェアの実装など）が欠けています。しかし、入門書としては非常に読みやすく、特にコンピューター分野出身で量子コンピューティングを学びたい人にとっては、線形代数の最も基本的な知識を習得するだけで、この本を読むのに問題はありません。