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

Пусть A, B, C – три заданные матрицы размерности n x n над полем, где C – матричное произведение AB. Прямолинейный метод проверки того, что С = AB, заключается в перемножении матриц A и B и поэлементном сравнении полученного результата с C. Это занимает время O(n!), где ! – «экспонента матричного умножения». Из определения операции умножения матриц следует, что 2 < ! < 3. Наилучшая известная нижняя граница ! составляет 2,376 [4].

Удивительно, но без умножения матриц можно обойтись, если использовать рандомизированный метод «снятия отпечатков пальцев», предложенный Фрейвальдсом [ ], и произведение матриц можно проверить за время O(n2) с ограниченной вероятностью односторонней ошибки. Этот алгоритм фактически распространяется на матрицы над любой целочисленной областью [ ], а количество используемых случайных бит может быть уменьшено до log ^- + O(1) для алгоритма с односторонней вероятностной ошибкой не более e [ ]. (Все логарифмы в данной статье приведены к основанию 2). Техника «снятия отпечатков пальцев» нашла множество других применений в теоретической информатике (см., например, [10]).

Задача 1 (проверка матричного произведения)

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

Требуется: выдать EQUAL, если C = AB, и NOT EQUAL в противном случае.