Квантовый алгоритм проверки матричных тождеств
Ключевые слова и синонимы
Проверка матричного произведения
Постановка задачи
Пусть A, B, C – три заданные матрицы размерности n x n над полем, где C – матричное произведение AB. Прямолинейный метод проверки того, что С = AB, заключается в перемножении матриц A и B и поэлементном сравнении полученного результата с C. Это занимает время [math]\displaystyle{ O(n^{\omega}) }[/math], где [math]\displaystyle{ \omega }[/math] – «экспонента матричного умножения». Из определения операции умножения матриц следует, что [math]\displaystyle{ 2 \le \omega \le 3 }[/math]. Наилучшая известная нижняя граница [math]\displaystyle{ \omega }[/math] составляет 2,376 [4].
Здесь и в дальнейшем под «временем» понимается количество арифметических операций над полем (или другой алгебраической структурой, которой принадлежат элементы матрицы). Аналогично, при определении пространственной сложности мультипликативный коэффициент, соответствующий объему памяти, необходимому для представления элементов алгебраической структуры, опускается.
Удивительно, но без умножения матриц можно обойтись, если использовать рандомизированный метод «снятия отпечатков пальцев», предложенный Фрейвальдсом [5], и произведение матриц можно проверить за время [math]\displaystyle{ O(n^2) }[/math] с ограниченной вероятностью односторонней ошибки. Этот алгоритм фактически распространяется на матрицы над любой целочисленной областью [3], а количество используемых случайных бит может быть уменьшено до [math]\displaystyle{ log \frac{n}{\epsilon} + O(1) }[/math] для алгоритма с односторонней вероятностной ошибкой не более [math]\displaystyle{ \epsilon }[/math] [8]. (Все логарифмы в данной статье приведены к основанию 2). Техника «снятия отпечатков пальцев» нашла множество других применений в теоретической информатике (см., например, [10]).
Бурман и Шпалек рассматривали сложность проверки матричных произведений на квантовом компьютере.
Задача 1 (проверка матричного произведения)
Дано: матрицы A, B, C размерности n х n над целочисленной областью.
Требуется: выдать EQUAL, если C = AB, и NOT EQUAL в противном случае.
Эти же авторы изучали задачу проверки над булевой алгеброй {0, 1} с операциями [math]\displaystyle{ \{ \vee, \wedge \} }[/math], где техника снятия отпечатков пальцев неприменима.
В качестве приложения своих алгоритмов проверки они рассматривали умножение разреженных матриц.
Задача 2 (умножение матриц)
Дано: матрицы A, B, C размерности n х n над целочисленной областью или булевой алгеброй {0, 1}.
Требуется: найти матричное произведение C = AB над целочисленной областью или булевой алгеброй.
Основные результаты
Амбайнис, Бурман, Хойер, Карпински и Курур [2] впервые изучили задачу проверки матричного произведения в квантовомеханической формулировке. Рекурсивно применяя алгоритм поиска Гровера [6], они представили алгоритм с временем выполнения [math]\displaystyle{ O(n^{7/4}) }[/math]. Бурман и Шпалек улучшили это время, адаптировав алгоритмы поиска, основанные на квантовом блуждании, которые были недавно разработаны Амбайнисом [1] и Шегеди [11].
Обозначим за [math]\displaystyle{ W = \{ (i,j) |(AB - C)_{i, j} \ne 0 \} }[/math] множество координат, где C не совпадает с произведением AB, и за W' – наибольшее независимое подмножество W. (Набор координат считается независимым, если ни одна строка или столбец не встречается в нем более одного раза). Определим [math]\displaystyle{ q(W) = max \{ |W'|, min \{ |W|, \sqrt{n} \} \} }[/math].
Теорема 1. Рассмотрим задачу 1. Существует квантовый алгоритм, который всегда возвращает значение EQUAL, если C = AB, возвращает NOT EQUAL с вероятностью не менее 2/3, если С [math]\displaystyle{ \ne }[/math] AB, и имеет наихудшее время выполнения [math]\displaystyle{ O(n^{5/3}) }[/math], ожидаемое время выполнения [math]\displaystyle{ O(n^{2/3}/q(W)^{1/3}) }[/math] и пространственную сложность [math]\displaystyle{ O(n^{5/3}) }[/math].
Бурман и Шпалек излагают свои результаты в терминах сложности «черного ящика» или «числа запросов», где элементы входных матриц A, B, C предоставляются оракулом. В качестве меры сложности здесь является количество вызовов оракула (запросов). Сложность в запросах их квантового алгоритма совпадает с временем работы в вышеприведенной теореме. Они также вывели нижнюю границу сложности в запросах для этой задачи.
Теорема 2. Любой квантовый алгоритм с ограниченной ошибкой для задачи 1 имеет сложность в запросах [math]\displaystyle{ \Omega(n^{3/2}) }[/math].
Когда матрицы A, B, C являются булевыми, а произведение определено над операциями [math]\displaystyle{ \{ \vee, \wedge \} }[/math], оптимальный алгоритм с временной сложностью / сложностью в запросах [math]\displaystyle{ O(n^{3/2}) }[/math] может быть получен из алгоритма для деревьев AND-OR [7]. Пространственная сложность этого алгоритма составляет [math]\displaystyle{ O((log \; n)^3) }[/math].
Все квантовые алгоритмы могут быть обобщены для проверки произведения прямоугольных матриц с соответствующей модификацией временной и пространственной сложности.
Применение
Используя бинарный поиск вместе с алгоритмами из предыдущего раздела, можно найти и затем исправить положение неправильного элемента в матрице C (предположительно являющейся произведением матриц A и B). Бурман и Шпалек применяют этот подход в итеративном режиме для получения алгоритма умножения матриц, начиная с предположения C = 0. Когда произведение AB является разреженной матрицей, этот метод позволяет получить квантовую схему умножения матриц, которая для некоторых параметров работает быстрее, чем известные классические схемы.
Теорема 3. Для любых матриц A и B размера n x n в целочисленной области матричное произведение C = AB может быть вычислено квантовым алгоритмом с полиномиально малой вероятностью ошибки за ожидаемое время
[math]\displaystyle{ 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.
Детальное сравнение этого квантового алгоритма с классическим можно найти в [3].
Последующий алгоритм квантового блуждания, который предложили Маньез, Наяк, Роланд и Санта [ ], находит неправильный элемент за то же время, что и в Теореме 1, не требуя проведения бинарного поиска. Это немного улучшает время работы вышеописанного квантового алгоритма умножения матриц.
Поскольку произведения булевых матриц могут быть проверены быстрее, эти произведения могут быть вычислены за ожидаемое время O(n3/2w), где w – число элементов Г в произведении.
Все упомянутые алгоритмы матричного произведения могут быть использованы и для умножения прямоугольных матриц с соответствующими модификациями.
См. также
Литература
1. Ambainis, A.: Quantum walk algorithm for Element Distinctness. In: Proceedings of the 45th Symposium on Foundations of Computer Science, pp. 22-31, Rome, Italy, 17-19 October 2004
2. Ambainis, A., Buhrman, H., Hayer, P., Karpinski, M., Kurur, P.: Quantum matrix verification. Unpublished manuscript (2002)
3. Buhrman, H., Spalek, R.: Quantum verification of matrix products. In: Proceedings of 17th ACM-SIAM Symposium on Discrete Algorithms, pp. 880-889, Miami, FL, USA, 22-26 January 2006
4. Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3), 251-280 (1990)
5. Freivalds, R.: Fast probabilistic algorithms. In: Proceedings of the 8th Symposium on Mathematical Foundations of Computer Science, pp. 57-69, Olomouc, Czechoslovakia, 3-7 September 1979
6. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th ACM Symposium on the Theory of Computing, pp. 212-219, Philadelphia, PA, USA, 22-24 May 1996
7. Hayer, P., Mosca, M., de Wolf, R.: Quantum search on bounded-error inputs. In: Proceedings of the 30th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 2719, pp. 291-299, Eindhoven, The Netherlands, 30 June - 4 July 2003
8. Kimbrel, T., Sinha, R.K.: A probabilistic algorithm for verifying matrix products using O(n2) time and log2n + O(1) random bits. Inf. Proc. Lett. 45(2), 107-110 (1993)
9. Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. In: Proceeding of the 39th ACM Symposium on Theory of Computing, pp. 575-584, San Diego, CA, USA, 11-13 June 2007 (2007)
10. Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
11. Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 32-41, Rome, Italy, 17-19 October 2004 (2004)