4511
правок
Квантовый алгоритм проверки матричных тождеств: различия между версиями
Материал из WEGA
Квантовый алгоритм проверки матричных тождеств (посмотреть исходный код)
Версия от 19:56, 13 января 2023
, 13 января 2023→Постановка задачи
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть A, B, C – три заданные матрицы размерности n x n над полем, где C – матричное произведение AB. Прямолинейный метод проверки того, что С = AB, заключается в перемножении матриц A и B и поэлементном сравнении полученного результата с C. Это занимает время <math>O(n^{\omega})</math>, где <math>\omega</math> – | Пусть 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]. | ||
