4430
правок
Квантовый алгоритм проверки матричных тождеств: различия между версиями
Перейти к навигации
Перейти к поиску
м
Квантовый алгоритм проверки матричных тождеств (посмотреть исходный код)
Версия от 17:56, 21 ноября 2022
, 21 ноября 2022→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 35: | Строка 35: | ||
== Основные результаты == | == Основные результаты == | ||
Амбайнис, Бурман, Хойер, Карпински и Курур [2] впервые изучили задачу проверки матричного произведения в квантовомеханической формулировке. Рекурсивно применяя алгоритм поиска Гровера [ ], они представили алгоритм с временем выполнения O( | Амбайнис, Бурман, Хойер, Карпински и Курур [2] впервые изучили задачу проверки матричного произведения в квантовомеханической формулировке. Рекурсивно применяя алгоритм поиска Гровера [6], они представили алгоритм с временем выполнения <math>O(n^{7/4})</math>. Бурман и Шпалек улучшили это время, адаптировав алгоритмы поиска, основанные на квантовом блуждании, которые были недавно разработаны Амбайнисом [1] и Шегеди [11]. | ||
Обозначим за W = | Обозначим за <math>W = \{ (i,j) |(AB - C)_{i, j} \ne 0 \}</math> множество координат, где C не совпадает с произведением AB, и за W' – наибольшее независимое подмножество W. (Набор координат считается ''независимым'', если ни одна строка или столбец не встречается в нем более одного раза). Определим <math>q(W) = max \{ |W'|, min \{ |W|, \sqrt{n} \} \}</math>. | ||
| Строка 52: | Строка 52: | ||
Все квантовые алгоритмы могут быть обобщены для проверки произведения прямоугольных матриц с соответствующей модификацией временной и пространственной сложности. | Все квантовые алгоритмы могут быть обобщены для проверки произведения прямоугольных матриц с соответствующей модификацией временной и пространственной сложности. | ||
== Применение == | == Применение == | ||