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

Пусть 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].

Амбайнис, Бурман, Хойер, Карпински и Курур [2] впервые изучили задачу проверки матричного произведения в квантовомеханической формулировке. Рекурсивно применяя алгоритм поиска Гровера [6], они представили алгоритм с временем выполнения <math>O(n^{7/4})</math>. Бурман и Шпалек улучшили это время, адаптировав алгоритмы поиска, основанные на квантовом блуждании, которые были незадолго до того разработаны Амбайнисом [1] и Шегеди [11].

Бурман и Шпалек излагают свои результаты в терминах сложности «черного ящика» или «сложности в запросах», где элементы входных матриц A, B, C предоставляются оракулом. В качестве меры сложности здесь используется количество вызовов оракула (запросов). Сложность в запросах их квантового алгоритма совпадает с временем работы в вышеприведенной теореме. Они также вывели нижнюю границу сложности в запросах для этой задачи.

Используя бинарный поиск вместе с алгоритмами из предыдущего раздела, можно найти положение неправильного элемента в матрице C (предположительно являющейся произведением матриц A и B) и затем исправить его. Бурман и Шпалек применяют этот подход в итеративном режиме для получения алгоритма умножения матриц, начиная с предположения C = 0. Когда произведение AB является разреженной матрицей, этот метод позволяет получить квантовую схему умножения матриц, которая для некоторых параметров работает быстрее, чем известные классические схемы.

'''Теорема 3. Для любых матриц A и B размера n x n над целочисленной областью матричное произведение C = AB может быть вычислено квантовым алгоритмом с полиномиально малой вероятностью ошибки за ожидаемое время'''

'''где w – количество ненулевых элементов матрицы C.'''

Последующий алгоритм квантового блуждания, который предложили Маньез, Наяк, Роланд и Санта [9], находит неправильный элемент за то же время, что и в Теореме 1, не требуя проведения бинарного поиска. Это немного улучшает время работы вышеописанного квантового алгоритма умножения матриц.

 

 

Поскольку произведения булевых матриц могут быть проверены быстрее, эти произведения могут быть вычислены за ожидаемое время <math>O(n^{3/2}w)</math>, где w – число элементов "1" в произведении.