|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Квантовый поиск заданной подстроки в тексте на основе техники хеширования
М. Ф. Аблаевab, Н. М. Салиховаb a Казанский физико-технический институт им. Е.К. Завойского, ФИЦ Казанский научный центр РАН, г. Казань, 420029, Россия
b Казанский (Приволжский) федеральный университет, г. Казань, 420008, Россия
Аннотация:
Рассмотрена задача поиска в тексте заданной подстроки. Известно, что классические алгоритмы решают эту задачу за линейное от длины текста и заданного шаблона время. Квантовые алгоритмы позволяют ускорить поиск в «корень квадратный раз».
В работе предложен квантовый алгоритм, решающий задачу поиска а) с высокой вероятностью получения правильного результата, б) с таким же ускорением («корень квадратный раз») по сравнению с классическим, но в) гораздо более экономный по памяти (по числу используемых кубит) по сравнению с ранее известными квантовыми алгоритмами.
Продемонстрировано применение универсального хеширования и техники квантового хеширования для задачи поиска в тексте заданной подстроки.
Ключевые слова:
квантовые алгоритмы, поиск строки, квантовый поиск.
Поступила в редакцию: 23.07.2020
Образец цитирования:
М. Ф. Аблаев, Н. М. Салихова, “Квантовый поиск заданной подстроки в тексте на основе техники хеширования”, Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 162, № 3, Изд-во Казанского ун-та, Казань, 2020, 241–258
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/uzku1558 https://www.mathnet.ru/rus/uzku/v162/i3/p241
|
Статистика просмотров: |
Страница аннотации: | 184 | PDF полного текста: | 109 | Список литературы: | 13 |
|