4501
правка
Квантовый алгоритм проверки матричных тождеств: различия между версиями
Перейти к навигации
Перейти к поиску
Квантовый алгоритм проверки матричных тождеств (посмотреть исходный код)
Версия от 20:42, 22 ноября 2022
, 22 ноября 2022→Применение
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 59: | Строка 59: | ||
'''Теорема 3. Для любых матриц A и B размера n x n в целочисленной области матричное произведение C = AB может быть вычислено квантовым алгоритмом с полиномиально малой вероятностью ошибки за ожидаемое время | '''Теорема 3. Для любых матриц A и B размера n x n в целочисленной области матричное произведение C = AB может быть вычислено квантовым алгоритмом с полиномиально малой вероятностью ошибки за ожидаемое время''' | ||
<math>O(1) \cdot | |||
\begin{cases} | |||
n \; log \; n \cdot n^{2/3} w^{2/3}, 1 \le w \le \sqrt{n}; \\ | |||
n \; log \; n \cdot \sqrt{n} w, \sqrt{n} \le w \le n; \\ | |||
n \; log \; n \cdot n \sqrt{w}, n \le w \le n^2, \\ | |||
\end{cases}</math> | |||
где w – количество ненулевых элементов матрицы C.''' | '''где w – количество ненулевых элементов матрицы C.''' | ||
| Строка 74: | Строка 80: | ||
Поскольку произведения булевых матриц могут быть проверены быстрее, эти произведения могут быть вычислены за ожидаемое время O(n3/2w), где w – число элементов Г в произведении. | Поскольку произведения булевых матриц могут быть проверены быстрее, эти произведения могут быть вычислены за ожидаемое время O(n3/2w), где w – число элементов Г в произведении. | ||
Все упомянутые алгоритмы матричного произведения могут быть использованы и для умножения прямоугольных матриц с соответствующими модификациями. | Все упомянутые алгоритмы матричного произведения могут быть использованы и для умножения прямоугольных матриц с соответствующими модификациями. | ||
== См. также == | == См. также == | ||