Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Материал конференции: "XIV международный научный семинар "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (20-25 июня 2022 г., Москва)"
Авторы: Хадиев К.Р., Ремидовский В.С.
Квантовый алгоритм для поиска квадрата наибольшего размера на двухмерной карте
Аннотация:
В рамках данной работы рассматривается задача поиска самого большого квадрата в 0-1-матрице состоящая из единиц. Задача рассматривается с точки зрения квантовых алгоритмов. Для задачи поиска квадрата наибольшего размера на двухмерной карте существует квантовый алгоритм со временем работы O(n1.5log n) и вероятностью ошибки не более 0.1. В тоже время любой классический алгоритм (вероятностный или детерминированный) имеет нижнюю оценку на время работы Omega(n2).
Ключевые слова:
квантовые вычисления
Язык публикации: русский,  страниц: 3 (с. 101-103)
Полный текст на русском языке:
Экспорт ссылки на публикацию в формате:   RIS    BibTeX
Сведения об авторах:
  • Хадиев Камиль Равилевич,  orcid.org/0000-0002-5151-9908Казанский университет
  • Ремидовский Владислав Сергеевич,  Казанский университет