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

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

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

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