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

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

Бурман и Спалек рассматривали сложность проверки матричных произведений на квантовом компьютере.

Эти же авторы изучали задачу проверки над булевой алгеброй f0; 1g с операциями f_; л}, где техника снятия отпечатков пальцев неприменима.

Задача 2 (умножение матриц)

Дано: матрицы A, B, C размерности n х n над целочисленной областью или булевой алгеброй {0, 1}.

Требуется: найти матричное произведение C = AB над целочисленной областью или булевой алгеброй.

Амбайнис, Бурман, Хойер, Карпински и Курур [2] впервые изучили задачу проверки матричного произведения в квантовомеханической формулировке. Рекурсивно применяя алгоритм поиска Гровера [ ], они представили алгоритм с временем выполнения O(n7/4). Бурман и Спалек улучшили это время, адаптировав алгоритмы поиска, основанные на квантовом блуждании, которые были недавно разработаны Амбайнисом [ ] и Шегеди [11].

Обозначим за W = f(i;j)j(AB - C)jtj /0} множество координат, где C не совпадает с произведением AB, и за W0 – наибольшее независимое подмножество W. (Набор координат считается независимым, если ни одна строка или столбец не встречается в нем более одного раза). Определим q(W) =

Теорема 1. Рассмотрим задачу 1. Существует квантовый алгоритм, который всегда возвращает значение EQUAL, если C = AB, возвращает NOT EQUAL с вероятностью не менее 2/3, если С 6AB, и имеет наихудшее время выполнения O(n5/3), ожидаемое время выполнения O(n2/3/q(W)1/3) и пространственную сложность O(n5/3).

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

Теорема 2. Любой квантовый алгоритм с ограниченной ошибкой для задачи 1 имеет сложность в запросах Q(n312).

Когда матрицы A, B, C являются булевыми, а произведение определено над операциями f_; л}, оптимальный алгоритм с временной сложностью / сложностью в запросах O(n3/2) может быть получен из алгоритма для деревьев AND-OR [ ]. Пространственная сложность этого алгоритма составляет O((log n)3).

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

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

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