4×4 複素行列の積：AlphaEvolve が乗算 48 回のアルゴリズムを発見

問題

1969 年、Strassen は 2 つの $2 \times 2$ 行列の積が、素朴な 8 回ではなく 7 回のスカラー乗算で計算できることを発見した。この方法を $4 \times 4$ 行列に再帰的に適用すると、$7^2 = 49$ 回の乗算が必要になる。複素行列については、それより少ない方法が半世紀以上見つかっていなかった。

AI が行ったこと

AlphaEvolve では、大規模言語モデルが探索アルゴリズムのコードを繰り返し提案・書き換えし、自動評価器が正しさと乗算回数を検査する。こうして $4 \times 4$ 複素行列の積を 48 回のスカラー乗算で計算するアルゴリズムを見つけた。

検証の方法

アルゴリズムは線形結合と積の明示的な列である。記号的な行列を代入すれば、結果が行列の積に等しいことを項ごとに確かめられる。

限界

改良されたのは上界であり、48 回が最小かどうかはまだ分からない。結果は複素数体に限ったものであり、この程度の定数倍の改善が実際の計算速度に与える影響は限られる。

∎