55 Additions Suffice for 3x3 Matrix Multiplication at Rank 23

あなたは、巨大で複雑なケーキを焼こうとしている熟練のシェフだと想像してください。そのレシピには、数十種類の材料を非常に特定の方法で混ぜ合わせることが求められます。コンピュータの世界では、「混ぜる」ことは数字を掛け合わせることに相当し、「ケーキを焼く」ことは2つの数字のグリッド（行列）を掛け合わせて新しい結果を得ることに相当します。長い間、数学者たちは、標準的で低速なレシピに従う以外に方法はないと考えてきました。つまり、すべての数字を一つずつ掛け合わせ、それらを足し合わせるという方法です。しかし、1960年代、シュトラッセンという天才が魔法のようなトリックを発見しました。彼は、混ぜる順番を変えることで、重労働をスキップできることに気づいたのです。これにより、最もコストがかかり、時間がかかるステップである「掛け算」の回数を減らして、同じ美味しいケーキを作ることができるようになりました。

しかし、落とし穴があります。掛け算の回数を減らせる一方で、材料を準備するために「足し算」（混ぜるボウル）の回数が増えてしまうことがよくあります。これを次のように考えてみてください。単に小麦粉をボウルに注ぐ代わりに、それらを組み合わせる前に、特定のダンスのように、刻んだり、かき混ぜたり、折り込んだりする工程が必要になるのです。目標は、可能な限り少ないステップ数で済む、完璧なダンスのルーチンを見つけることでした。あなたがこれから読む論文は、この特定の種類のケーキ、すなわち3x3行列に対して、より効率的なダンスを見つけたチームについてのものです。彼らは「重いリフト（掛け算）」の回数は変えませんでしたが、「混ぜるステップ（足し算）」の数を1つ削り、作業量をわずかに、しかし確実に軽減しました。

新たな記録を打ち立てたダンス

Logical AIのSamurdhi KarunaratneとAnushka Idamekoralaによるこの論文は、2つの3x3の数字のグリッドを掛け合わせるための新たな記録を発表しています。彼らは、わずか55回の足し算と23回の掛け算でこれを行う方法を見つけ出しました。

なぜこれが大きなニュースなのかを理解するために、以前の最高記録のレシピを思い浮かべてみてください。Sunという研究者が作った現在のチャンピオンは、56回の足し算を必要としていました。本論文の著者たちは、全く新しい行列の掛け算の方法を発明したわけではありません。代わりに、彼らはPerminovによって作成された、58回の足し算（および初期バージョンの59回の足し算）を使用する既存の公開レシピを取り上げ、その「準備」ステップを最適化しました。彼らは、材料を事前に混ぜ合わせる方法を再構成することで、合計の足し算ステップを55回まで減らせることに気づいたのです。

彼らの新しい「キッチン」の仕組みを、3つのシンプルなステージに分けて説明します：

1. 左側の材料の準備： 混ぜ合わせる前に、彼らは最初の数字のグリッド（「左」のグリッドと呼びましょう）を取り、13回の単純な足し算または引き算のステップを行い、23の特別な混合物を作成します。
2. 右側の材料の準備： 彼らは2つ目のグリッド（「右」のグリッド）に対しても同様に、23の特別な混合物を作るために14回のステップを行います。
3. 大きな混合と最終組み立て： 彼らは、左のグリッドと右のグリッドから対応する混合物を掛け合わせます（計23回の掛け算）。その後、それら23の結果を取り、最終的な3x3の結果を組み立てるために、さらに28回の足し算ステップを行います。

準備作業（13 + 14）と最終組み立て（28）を合計すると、ちょうど55回の足し算になります。これは以前の最高記録よりも1回少なく、この特定の計算タイプにおいて知られている中で最も効率的な方法です。

なぜこれが重要なのか（そして、何が重要ではないのか）

「これが絶対的な最善の方法なのでしょうか？」と疑問に思うかもしれません。著者たちは慎重にこう述べています。「必ずしもそうではありません」。彼らは、自分たちが選んだこの特定の材料の配置においては、55がベストであることを証明しました。彼らは厳格な数学的探索を用い、この特定のレシピにおいては、これ以上ステップを減らすことはできないことを証明しました。しかし、彼らは、全く異なるレシピ（異なる材料の配置）があれば、さらに高速になる可能性があることも認めています。彼らはまだそれを見つけておらず、行列の掛け算に関する謎すべてを解いたと主張しているわけでもありません。

また、これは単なる偶然の勘や、間違いの可能性があるコンピュータ・シミュレーションではないことも明確にしています。彼らは「真実の証明書」を提供しました。彼らはステップ・バイ・ステップのレシピ（「直線プログラム」と呼ばれます）を書き出し、すべての729個の数学的ルールが成立しなければならないことを、複数の独立したコンピュータプログラム（PythonおよびNode.jsで記述）を実行してチェックしました。すべてのチェックをパスしました。これは、数学が堅実であり、掛け算の順序が重要となる特殊な数体系であっても、このレシピが完璧に機能することを意味しています。

カーテンの裏にいるAI

この物語には興味深い展開があります。どのようにしてレシピが見つかったのかという点です。著者たちは、人間による研究者がAIシステム（具体的には、OpenAIのGPT-5.6 Solを使用するエージェント）を導いて、このレシピを発見したことを明らかにしています。人間は、「56回の足し算の記録を破る方法を見つけろ」という目標を設定しました。AIは既存のレシピの風景を探索し、Perminovの古い58回の足し算バージョンを見つけ出し、準備ステップを微調整することで、3つのステップを削れることに気づきました。その後、AIは自分の仕事をダブルチェックし、コードを書き、数学を検証しました。これは、人間と機械が協力し合う完璧な例です。人間は方向性と「なぜ」を提供し、AIは「どのように」を見つけるために、何百万もの可能性の中から探索するという重労働を担いました。

結局のところ、この論文は小さくも精密な勝利です。それは、行列の掛け算という古くからの分野においてさえ、注意深く観察すれば、まだ発見されるのを待っている、小さく隠れた効率性が存在することを示しています。それは、慣れ親しんだ森の中で、わずかに短い新しい道を見つけるようなものです。目的地には同じ場所に着きますが、そこに至るまでの歩数が一つだけ減っているのです。