Ученые записки Казанского университета. Серия Физико-математические науки
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Ученые записки Казанского университета. Серия Физико-математические науки, 2020, том 162, книга 3, страницы 241–258
DOI: https://doi.org/10.26907/2541-7746.2020.3.241-258 (Mi uzku1558) 		 
Эта публикация цитируется в 1 научной статье (всего в 1 статье)

Квантовый поиск заданной подстроки в тексте на основе техники хеширования

М. Ф. Аблаевab, Н. М. Салиховаb

a Казанский физико-технический институт им. Е.К. Завойского, ФИЦ Казанский научный центр РАН, г. Казань, 420029, Россия
b Казанский (Приволжский) федеральный университет, г. Казань, 420008, Россия
PDF полного текста (307 kB) Список цитирования (1)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.26907/2541-7746.2020.3.241-258
Аннотация: Рассмотрена задача поиска в тексте заданной подстроки. Известно, что классические алгоритмы решают эту задачу за линейное от длины текста и заданного шаблона время. Квантовые алгоритмы позволяют ускорить поиск в «корень квадратный раз».
В работе предложен квантовый алгоритм, решающий задачу поиска а) с высокой вероятностью получения правильного результата, б) с таким же ускорением («корень квадратный раз») по сравнению с классическим, но в) гораздо более экономный по памяти (по числу используемых кубит) по сравнению с ранее известными квантовыми алгоритмами.
Продемонстрировано применение универсального хеширования и техники квантового хеширования для задачи поиска в тексте заданной подстроки.
Ключевые слова: квантовые алгоритмы, поиск строки, квантовый поиск.
Финансовая поддержка Номер гранта
Российский научный фонд 19-19-00656
Исследование выполнено за счет гранта Российского научного фонда (проект № 19-19-00656).
Поступила в редакцию: 23.07.2020
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.7
Образец цитирования: М. Ф. Аблаев, Н. М. Салихова, “Квантовый поиск заданной подстроки в тексте на основе техники хеширования”, Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 162, № 3, Изд-во Казанского ун-та, Казань, 2020, 241–258
Цитирование в формате AMSBIB
\RBibitem{AblSal20}
\by М.~Ф.~Аблаев, Н.~М.~Салихова
\paper Квантовый поиск заданной подстроки в~тексте на основе техники хеширования
\serial Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки
\yr 2020
\vol 162
\issue 3
\pages 241--258
\publ Изд-во Казанского ун-та
\publaddr Казань
\mathnet{http://mi.mathnet.ru/uzku1558}
\crossref{https://doi.org/10.26907/2541-7746.2020.3.241-258}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/uzku1558
  • https://www.mathnet.ru/rus/uzku/v162/i3/p241
    • Эта публикация цитируется в следующих 1 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Ученые записки Казанского университета. Серия Физико-математические науки
    Статистика просмотров:
    Страница аннотации:184
    PDF полного текста:109
    Список литературы:13
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024