行列積の計算は線形代数の最も基本的な演算であり, 機械学習など様々な場面で登場する実用的に高速なアルゴリズムの設計は非常に重要である. 漸近的には高速なアルゴリズムはStrassen(1969)以降多く提案されているが, これらはオーダー記法に隠れた定数倍部分が大きいために実用性に欠けるという問題点がある. 実用的に高速な行列積アルゴリズムの設計は従来の計算機のみならず, GPUといった並列計算機に基づく設計や, 光デバイスや熱力学系といった物理学的な系を利用したものまで提案されている. 特に物理学的な系に基づく計算機はその系のノイズにアルゴリズムの実行結果が左右されることがあるため, 必ずしも厳密に正しい答えが得られるとは限らない.
そこで本発表では「高速だが必ずしも行列積の全ての成分を正しく計算できるとは限らないアルゴリズムが与えられたとき, 行列積を計算するアルゴリズムを設計できるか？」という問いを考える. 例えば, 90％の成分に対して正しく行列積を計算するアルゴリズムを使って行列積の全成分を正しく計算できるだろうか? 本発表では, 有限体上の行列積に対してこれが可能であることを示す. 具体的には有限体の要素数が q であるとき, 任意の定数 c > 0 に対して行列積の 1/q + c の割合の成分を計算するアルゴリズムが存在するならば, それを polylog(n) 回呼び出すことで全成分を正しく計算する行列積アルゴリズムが設計できることを示す.
本発表の内容は Symposium on Theory of Computing (STOC2025) および International Colloquium on Automata, Languages, and Programming (ICALP2025) に採択された平原秀一氏 (国立情報学研究所) との二つの共同研究に基づく.