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

Перейти к навигации Перейти к поиску
мНет описания правки
Строка 50: Строка 50:




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




Строка 59: Строка 59:




Теорема 3. Для любых матриц A и B размера n x n в целочисленной области матричное произведение C = AB может быть вычислено квантовым алгоритмом с полиномиально малой вероятностью ошибки за ожидаемое время
'''Теорема 3. Для любых матриц A и B размера n x n в целочисленной области матричное произведение C = AB может быть вычислено квантовым алгоритмом с полиномиально малой вероятностью ошибки за ожидаемое время
I n log n • n2/3w2/3    when 1 < w < pn ; n log n • pn w        when pn < w < n ; and nlog n • npw        when n < w < n2 ;
 
где w – количество ненулевых элементов матрицы C.
 
 
где w – количество ненулевых элементов матрицы C.'''




Источник — http://pco.iis.nsk.su/wega/index.php/Квантовый_алгоритм_проверки_матричных_тождеств