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

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




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




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