Квантовый алгоритм проверки матричных тождеств: различия между версиями

Пусть A, B, C – три заданные матрицы размерности n x n над полем, где C – матричное произведение AB. Прямолинейный метод проверки того, что С = AB, заключается в перемножении матриц A и B и поэлементном сравнении полученного результата с C. Это занимает время <math>O(n^{\omega})</math>, где <math>\omega</math> – «экспонента матричного умножения». Из определения операции умножения матриц следует, что <math>2 \le \omega \le 3</math>. Наилучшая известная нижняя граница <math>\omega</math> составляет 2,376 [4].