Квантовый алгоритм для поиска квадрата наибольшего размера на двухмерной карте
Аннотация:
В рамках данной работы рассматривается задача поиска самого большого квадрата в 0-1-матрице состоящая из единиц. Задача рассматривается с точки зрения квантовых алгоритмов. Для задачи поиска квадрата наибольшего размера на двухмерной карте существует квантовый алгоритм со временем работы O(n1.5log n) и вероятностью ошибки не более 0.1. В тоже время любой классический алгоритм (вероятностный или детерминированный) имеет нижнюю оценку на время работы Omega(n2).
