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

Квантовый алгоритм проверки матричных тождеств (посмотреть исходный код)

62 байта добавлено , 22 ноября 2022

м

4551

правка

@@ Строка 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>.