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

Бурман и Спалек рассматривали сложность проверки матричных произведений на квантовом компьютере.

Теорема 1. Рассмотрим задачу 1. Существует квантовый алгоритм, который всегда возвращает значение EQUAL, если C = AB, возвращает NOT EQUAL с вероятностью не менее 2/3, если С 6AB, и имеет наихудшее время выполнения O(n5/3), ожидаемое время выполнения O(n2/3/q(W)1/3) и пространственную сложность O(n5/3).

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

Используя бинарный поиск вместе с алгоритмами из предыдущего раздела, можно найти и затем исправить положение неправильного элемента в матрице C (предположительно являющейся произведением матриц A и B). Бурман и Спалек применяют этот подход в итеративном режиме для получения алгоритма умножения матриц, начиная с предположения C = 0. Когда произведение AB является разреженной матрицей, этот метод позволяет получить квантовую схему умножения матриц, которая для некоторых параметров работает быстрее, чем известные классические схемы.