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

Амбайнис, Бурман, Хойер, Карпински и Курур [2] впервые изучили задачу проверки матричного произведения в квантовомеханической формулировке. Рекурсивно применяя алгоритм поиска Гровера [6], они представили алгоритм с временем выполнения <math>O(n^{7/4})</math>. Бурман и Шпалек улучшили это время, адаптировав алгоритмы поиска, основанные на квантовом блуждании, которые были недавно разработаны Амбайнисом [1] и Шегеди [11].

Бурман и Шпалек излагают свои результаты в терминах сложности «черного ящика» или «числа запросов», где элементы входных матриц A, B, C предоставляются оракулом. В качестве меры сложности здесь является количество вызовов оракула (запросов). Сложность в запросах их квантового алгоритма совпадает с временем работы в вышеприведенной теореме. Они также вывели нижнюю границу сложности в запросах для этой задачи.