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

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

'''Теорема 3. Для любых матриц A и B размера n x n над целочисленной областью матричное произведение C = AB может быть вычислено квантовым алгоритмом с полиномиально малой вероятностью ошибки за ожидаемое время'''