4501
правка
Квантовый алгоритм проверки матричных тождеств: различия между версиями
Перейти к навигации
Перейти к поиску
м
Квантовый алгоритм проверки матричных тождеств (посмотреть исходный код)
Версия от 20:43, 22 ноября 2022
, 22 ноября 2022→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 75: | Строка 75: | ||
Последующий алгоритм квантового блуждания, который предложили Маньез, Наяк, Роланд и Санта [ ], находит неправильный элемент за то же время, что и в Теореме 1, не требуя проведения бинарного поиска. Это немного улучшает время работы вышеописанного квантового алгоритма умножения матриц. | Последующий алгоритм квантового блуждания, который предложили Маньез, Наяк, Роланд и Санта [9], находит неправильный элемент за то же время, что и в Теореме 1, не требуя проведения бинарного поиска. Это немного улучшает время работы вышеописанного квантового алгоритма умножения матриц. | ||
Поскольку произведения булевых матриц могут быть проверены быстрее, эти произведения могут быть вычислены за ожидаемое время <math>O(n^{3/2}w)</math>, где w – число элементов "1" в произведении. | |||
Все упомянутые алгоритмы матричного произведения могут быть использованы и для умножения прямоугольных матриц с соответствующими модификациями. | Все упомянутые алгоритмы матричного произведения могут быть использованы и для умножения прямоугольных матриц с соответствующими модификациями. | ||