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

Пусть 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 может быть вычислено квантовым алгоритмом с полиномиально малой вероятностью ошибки за ожидаемое время'''