新しい量子アルゴリズムの発見

20世紀半ば以前は、コンピューターは特定用途向けに組み立てられた、部屋サイズの真空管の集合体でした。これらは、集計や複雑な計算の実行など、明確に定義された問題を念頭に置いて設計されていました。しかし、その可能性を最大限に引き出すには、ハードウェアを改善するだけでは不十分でした。新しいアルゴリズムを考案する創造的な頭脳が必要だったのです。

量子コンピューティングも今日、同じような状況にあります。量子ハードウェアが徐々に成熟して萌芽期にある今日の量子システムは、問題解決ができるようになりつつあり、量子業界はシステムの小型化と拡張のための詳細な計画に取り組んでいます。化学シミュレーション、材料科学、最適化における問題の高速化を約束する量子アルゴリズムもありますが、量子アルゴリズムの研究者は、ハッシュや高速フーリエ変換などのアルゴリズムが以前の古典計算を革新したのとほぼ同じように、革新的な応用領域を持った新しい量子アルゴリズムを発見しようと目を光らせ続けています。

最近、IBM Researchの理論研究者は、最良の古典手法と比べて大幅な高速化を示す新しい量子アルゴリズムを発見しました。このアルゴリズムは、量子物理学と数学の深い関係を利用し、数学で長年未解決だった疑問に答えるための手がかりを提供します。また、発見されてから長い時間のたった古い量子アルゴリズムに新たな応用を与えます。

この新しいアルゴリズムがどこで実際に活用されるかはまだわかりません。今のところ、これはそれを利用して他の量子アルゴリズムを開発できる言わば量子高速化のテンプレートと見ることができますが、その潜在的な高速化の分析にはさらなる精査も必要です。いずれにせよ、これは量子を革新的なコンピューティング・パラダイムに変えるような創造性を示しています。

「この研究は、量子の高速化を探す道筋を確立します」と、新しいアルゴリズムの研究者の一人である Vojtěch Havlíčekは述べています。「それが新しい量子アルゴリズムの開発に役立つことを願っています。」

自然には構造があります。惑星、人、原子はすべて、その構造を支配する一連の数学的ルール、つまり言い換えれば、振る舞いの仕方、行くことが許される場所、持つことが許される特性、そして互いに相互作用する方法に従っています。

原子と原子核のスケールでは、その構造は量子力学と呼ばれる一連のルールによって支配されています。物理学に固有のルールは「対称性」です。これは変化に対して系が影響を受けない性質です。粒子の対称性は、対象の集合とそれらに対して行えるさまざまな操作を研究する数学の分野である群論によって説明することができます。量子粒子が群論で説明可能な構造を持っているがために、我々は粒子を洗練された方法で研究することができ、さらに重要なことに、量子コンピューターでデータを保存・操作する手法を得ることもできるのです。

群論それ自体は抽象的であるため、普通私たちは表現論というツールを使って研究します。表現論は、群を具体的な「表現」に変えます。たとえば表に編成された一連の数値と、それらに作用できる演算のようなものです。特に私たちの関心事について言えば、量子力学では、表現論は量子オブジェクトがどのように変化するか、つまり対称性群（symmetry group）に従って変化する様子を教えてくれます。そして、対称性群の構造に対して、粒子や原子を記述する数値、たとえば「スピン」「角運動量」「電荷」といった量子数などが特徴を与えます。

これらのことから、量子アルゴリズムの開発に取り組む際の自然な指針は、問題に隠された対称性を見つけることだと分かります。群の表現論は、これらの対称性を利用して目の前の問題を解決するための道具を提供します。より根本的には、対称性群は物理系の解空間に作用するため、群の対称性を理解することで、可能な解の特性について多くのことがわかります。これがどういうこと詳しく見てみましょう。

このような対称性群のひとつの例は、それぞれ違うカードで構成されたデッキのシャッフルを表す「置換群（symmetric group）」です。カードの初期順序をたとえば、Aが位置1、Bが位置2、Cが位置3にあるとして、この状態を簡単のためABCと書くことにします。

• 「何もしない」や「位置1と位置2のカードを交換する」などの並べ替え操作は、群の要素（元）と呼ばれます。
• 「1と2のカードを入れ替える」や「12、23、31へと入れ替える」と書く代わりに、(12)や(123) と書くことでスペースを節約します。そのように記述した場合、ABCに(12)を適用するとBACに、また (123)ABC = CABとなります。
• 任意の二つの元を合成して 3番目の元を構成できます。例えば、(12)(23)は(132)と同じです。ここで順序には意味があり、(23)(12) = (123) である一方で (12)(23) = (132) で合成結果が異なります。
• 「何もしない」スワップ() もあり、もちろん各シャッフルは元に戻すことができます。例えば (123)(132) = () です。
• 最後に、シャッフルは結合的（associative）で、たとえば (12)[(23)(12)] = [(12)(23)](12) と記述できます。ここで [ ]はその内部の合成を先に行うことを表します。つまり、各ステップでどのように置換を合成するかについては自由度があるということです。

数学者は、シャッフルを表現するのにさまざまな種類の方法を用います。彼らは、カードの代わりに行列を使用して群作用を表現する方法として表現論を発明しました。行列は数値の2次元配列であり、行列の乗算で他の行列と組み合わせることができます。表現行列の行と列の数は同じで、 ab=cの関係を持っている任意の元について、それらの行列バージョンである M(a)、M(b)、M(c) は M(a)M(b) = M(c) を満たす必要があります。

この条件を満たす限り、群のさまざまな表現を作成できます。直和やテンソル積といった複合表現を作成することもできます。

一つの群の三つの異なる表現 R₁、R₂、R₃がありそれぞれに独自の行列集合があるとします。これらは同じ群を表すため、同じ数の行列を持ちます。この時に、次のような方法で第四の表現を作ることができますが、ここではシンプルに Rと呼びます。すなわちその方法とは群の元それぞれについて、R₁を左上に置きその右や下はすべて0にします。次にその右下、対角線の方向にR₂を配置し、その右や下も0にします。そして最後にさらにその右下、対角線の方向にR₃を配置します。

（原文ブログにはこれらの行列表現の図があります）

「基底の変換」を使用してこのブロック対角形式に変換できる表現は、可約表現と呼ばれます。この方法で単純化できない表現は、既約表現と呼ばれます。

既約表現は、可約表現の内部に複数回出現する可能性があります。既約表現が現れる回数を、その重複度（あるいは多重度）と呼びます。もし既約表現R₁、R₂、R₃から可約表現を作った場合、R₁の重複度は2で、R₃の重複度は1になります。この図の3次元表現は二つの既約表現を持っていて、それぞれ重複度は1です。

置換群表現については、多くの問いを立てることができます。最も注目すべきものの中には、クロネッカー係数があります。置換群の二つの既約表現を取り、それらのテンソル積を計算すれば、これも表現を組み合わせる一つの方法です。これにより、再び既約表現に分解される新しい表現が得られ、それらの規約表現の重複度がクロネッカー係数です。

クロネッカー係数の計算は、古典コンピューターでは非常に、非常に、非常に困難ですが、そのような難しい古典問題は、量子加速を求めるのにうってつけの問題となります。

表面的には、この問題は理解するのが難しいという事実を除けば、量子と共通するものは何もないように見えるかもしれません。しかし、量子系もまた、正方ユニタリ行列で記述できる方法で時間発展します。そして、量子力学も表現論を通じて理解することができます。実際、Herman Weyl、Werner Heisenberg、Eugene Wignerなどの影響力のある物理学者による量子論の多くの重要な発展は、表現論に大きく基づいています。

2022年に理論物理学者のAnirban Chowdhury、David Gosset、Pawel Wocjan、主任研究者のSergey Bravyiは、量子における最も基本的な問題の一つを探求していました。彼らは、熱平衡状態にある粒子の基本的な特性を推定するのがどれほど困難かという問いを立てました。熱平衡状態は、平均値で見れば熱が系を出入りせず、粒子間に熱が伝達されない状態です。それは基本的に安定した系です。

彼らはまず、最も単純な「2-local」の場合、すなわち隣接する粒子ペアで生じる反応のみで系を表すことができるケースを調査することから始めました。彼らの証明は、この系の有効自由エネルギー （本質的には、何かの変化を起こすために残ったエネルギー）の計算がQMA困難であることを示しました。

QMA問題クラスにあるということは、誰かが量子の「証明」、つまり問題の解の証拠となる量子状態、とともに自由エネルギーの推定値を提示した時に、証明書と量子コンピューターを使用して、答えが正しいかどうかを効率的に検証することが可能であることを意味します。QMA困難であるということは、これがQMA問題の中でも最も難しい問題クラスであることを意味しており、そもそも答えを見つける効率的な量子アルゴリズムが存在する可能性は低いということです。

重要なことは、この問題の一般化バージョンでは、量子証明として機能する線形独立状態の数を概算する必要があることを彼らが発見したことです。彼らは、この種の問題に新しい名前、つまり QXC（quantum approximate counting）問題という名前を与えました。ある問題の解がQMA問題に対する解の個数の概算である場合、その問題はQXCであると言えます。

さて、QXCが説明されたことで、彼ら理論家たちは、これらのQXC問題は困難ではあるが、古典コンピューターが潜在的な解の数を数えることができる（ただし必ずしも計算できるとは限らない）種類の最も難しい問題ほどには難しくはないと直感しました。あとはそのような問題の具体例を見つけるだけでした。その際に、量子粒子の数学的記述との深い相乗効果を考えれば、彼らが表現論に注目するのは自然でした。

2024年の論文でBravyiのチームは、クロネッカー係数やその他の置換群の多重度を数える問題が QXC複雑性クラスになることもあることを発見しました。そのBravyiのチームには現在、同じ IBMの Anirban Chowdhuryと Guanyu Zhuに加えて Havlíčekもメンバーとして含まれています。量子コンピューターが、多重度を計算するという方法は用いないにしても少なくともその数を概算することによって、この問題に対してある程度有効だろうと考え、Havlíčekと彼の共同研究者であるロスアラモス国立研究所のMartin Laroccaは、それらを計算するための量子アルゴリズムを考案し始めました。(HavlíčekはBravyiのチーム・メンバーとしてこの分野での仕事を続けて、今年初めにPRX Quantumに掲載されたフォローアップ論文がこちらです。)

Havlíček と Larocca は、古典コンピューターよりも量子コンピューターの方が効率的に計算できるひとつの問題を特定したのではないかという直感を持ちました。そこで、それを実際に解くアルゴリズムを設計する必要が生じた彼らは、量子フーリエ変換（QFT）に目を向けました。

フーリエ変換は、信号を、重みがついた基本周波数に分解する手法で、自然が白色光を虹の色に分解するのとほとんど同じことをします。

同様に、量子フーリエ変換 (QFT) は、量子状態を、well-definedな対称性を持つ単純な状態に分解します。これは、古典コンピューターよりも指数関数的に速く素因数分解をすることができるShorのアルゴリズムでも使われている数学的ルーチンです。また、分子のエネルギーをモデル化するための有望なツールである位相推定もQFTを使います。

しかし、ここに問題があります。物理学者は、加算や乗算などの「可換な」数学構造上の位相推定アルゴリズムに精通しています。そこでは数学演算の順序の違いは結果に影響を及ぼしません。しかし、カードの例で見たように、置換群には同じことが当てはまりません。QFTには非可換群への自然な一般化拡張があります。それは、状態を個々の既約表現が張る成分に分解する変換です。置換群に対して効率的に動く量子アルゴリズムも知られています。

ただし、非可換群に対する位相推定（一般化位相推定とも呼ばれる)の適用は、しばしば失望につながってきました。

「これは可換群の場合に成功したことが証明された理論の、非常に自然な延長線上にありますが、これまで非可換群で同様の成果は得られていません」とIBM量子アルゴリズム理論グループの責任者であるKristan Temmeは言います。「多くの人がこの理論発展に非常に大きな期待と願望を持っていましたが、これまでのところこの期待に沿った成果は得られていないのです。」

それでも、この問題に頭を悩ましたHavlíčekは、これが非可換な置換群の位相推定を使用するアルゴリズム、つまり量子コンピューター上で多重度、さらにはクロネッカー係数を計算できるアルゴリズムであることに気づきました。そして、このアルゴリズムは一部の入力について特に効率的でした。

Havlíčekが文献を検索してみると、この量子アルゴリズムと同等以上に効率的な古典アルゴリズムは見つけることができませんでした。彼は、このアルゴリズムが最良の古典手法と比較して多項式加速を超える高速化を示しているという予想を立てました。この高速化は、古典計算が一般的な自家用車ならば量子計算はレースカーぐらい速い、という話ではなく、古典が自動車なら量子はロケット宇宙船だというレベルの比較だと言えます。

さらに、この理論は、別の分野である代数的組み合わせ論で何十年にもわたって未解決だった数学的問題を研究する新しい方法を世界にもたらしました。この数学領域は、簡単に言えば、離散的かつ有限な対象(たとえば、ヤング図形と呼ばれる、数値が書かれたテトリス・ブロックのような表) を扱うときに、さまざまな種類の代数構造とその作用を分析する数学の分野です。

代数的組み合わせ論が存在するのは、これらの図形が置換群の特性やその他の重要な数学的構造を単純に記述できるためです。クロネッカー係数がこの分野で意味を持つかどうか、つまり特定の特性を共有する形状がある程度存在するかどうかに答えることは、未解決の重要な問題です。

Havlíčekは、古典計算の専門家の目を引くために意図的に大胆な主張を行いました。そしてその狙いは的中し、この論文はすぐにロサンゼルスの南カリフォルニア大学の数学教授であり、クロネッカー係数の第一人者である熟練した数学者Greta Panovaの目を惹きました。

Panovaは arXivプレプリントでこの問題を詳しく調べ、Havlíčekと Laroccaが行った多項式加速を超える高速化の予想を、既存の最先端のアルゴリズムに重要な改良を加えることで事実上反証しました。しかし、その反証があっても、特定の多項式高速化は残りました。調整可能なパラメーター に基づいて問題を実行する時間のオーダーが古典手法では であるのに対して、量子では で済むのです。

が2であるとき、量子の計算量は 、古典は になります。を3にすると、量子は漸近的に となりますが、古典は へと増えるという具合に、このギャップは が増加するにつれて急速に拡大します。つまり、古典が自家用車なら量子はレースカーというぐらいの差がまだあると言えます。さらに、もしたとえこのスピードアップすらも新しい研究によって反証されたとしても、この研究はこの分野にとって象徴的な重要性を持っていると言えます。

「大きな未解決の問題に対して、その数式をどう捉えるべきかいくつかの考え方がこの分野にはありました」とPanovaは言います。「そこに突然、量子アルゴリズムのフーリエ変換が飛び込んできました。それによって、私たちがこれらの量を理解するための新しい構造と新しい方法が開かれました」。実際には、このような進歩は急激には起こらないかもしれません。量子は、抽象代数というPanovaの専門分野で働いている数学者にとってまったく新しい分野です。しかし、原則的には、数学者たちは量子計算の概念を探究することで、長年未解決だった問題に答える手がかりを得ることができるようになってきています。

Havlíčekは彼の新しいアルゴリズムについて慎重ながらも楽観的な見方を持ち続けていて、古典計算に対するその高速化が維持されることを望んでいます。今のところ、彼はこの仕事をコミュニティーへの挑戦だと考えています。「もしこれが量子アルゴリズムでうまくいかないなら、他に何がうまくいくんだ？という気持ちです」とHavlíčekは言います。「私たちのアルゴリズムは非常に一般的であるため、ここで量子高速化の存在が反証されると、他の量子アルゴリズムにも影響を及ぼしえます。これは私にとって重要なポイントであり、私がこの予想を明確に示した理由です。」

Havlíčekは、量子計算と理論数学の間を繋ぐ新しい架け橋としてのこの理論と、数学者がその結果を真剣に受け止めているという事実に非常に興奮しています。彼は数学会議に招待され、Panovaと共同で結果について講演しました。

さらに、この研究は、IBM Researchの中核的な使命、つまり最高の古典手法を上回る新しいアルゴリズム的ツールを発見することを具現化しています。今回の成果は、理論数学の領域にしっかりと根ざしているものの、一般化位相推定が古典的手法に対して大きな高速化をもたらす領域を特定することは、量子コンピューティングから大きな価値を引き出せる、より応用的なユースケースへの道しるべとなります。このような研究は、ハッシュや高速フーリエ変換が古典計算で行ったように、まったく新しいアプリケーションや研究分野を切り開く可能性さえあるのです。

「この研究は、一歩引いて見ることが目的でした」とHavlíčekは言います。「私たちは、計算パフォーマンスを大幅に向上させる方法だけでなく、計算能力の観点からこれまで不可能だったことを可能にするような方法をも作り上げる基礎理論をより深く探求しています。」

この記事は英語版IBM Researchブログ「Discovering a new quantum algorithm」（2025年10月29日公開、Ryan Mandelbaum, Vojtěch Havlíček著）を翻訳し一部更新したものです。