행렬곱 검산

• 영어 명칭: Verifying Matrix Products
• 속도 향상: 다항적
• 구현 코드: ∅

세 $n\times n$ 행렬 $A$, $B$, $C$가 주어져 있을 때, 행렬 곱 검산 문제는 $AB=C$의 성립 여부를 판정한다. 알려진 고전 알고리즘 중에서 가장 빠른 행렬곱 계산 알고리즘은 $O(n^{2.373})$ 시간에 계산해 내지만, (무작위) 행렬 곱검산 알고리즘은 $O(n^2)$ 시간에 이를 판정한다. 암바이니스(Ambainis)와 그 외 연구진들은 $O(n^{7/4})$ 시간에 해결하는 양자 알고리즘을 발견했다 [6]. 이어서 버먼(Buhrman)과 슈팔렉(Špalek)은 이 알고리즘에서 발전된 형태인 $O(n^{5/3})$ 시간에 해결하는 양자 알고리즘을 발견했다 [19]. 후자의 알고리즘은 [85]에서 증명된 양자 확률보행에 기초한다.