Квантовый поиск в словаре на основе функции отпечатков
https://doi.org/10.26907/2541-7746.2025.1.115-124
Аннотация
Рассмотрена задача поиска элемента в словаре. В последние десятилетия были предложены различные подходы к решению этой проблемы, в том числе классические и квантовые алгоритмы. Метод квантового усиления амплитуды, который лежит в основе хорошо известного алгоритма Гровера, квадратично ускоряет процесс поиска. Мыпредставляем новый подход к поиску элемента w длиной m в словаре V размером n, основанный на квантовой функции отпечатков. Наш алгоритм имеет запросную сложность O(√n) и использует O(logn + logm) кубитов, тогда как алгоритмы, представленные в работах других авторов, используют O(logn +m) кубитов.
Об авторе
Н. М. Салихова
Казанский (Приволжский) федеральный университет
Россия
Россия
Наиля Маратовна Салихова, аспирант
г. Казань,
Список литературы
1. Grover L.K. A fast quantum mechanical algorithm for database search // STOC’96: Proc. 28th Annu. ACM Symp. on Theory of Computing. Philadelphia, PA: ACM. 1996. P. 212–219. https://doi.org/10.1145/237814.237866.
2. Brassard G., Høyer P., Mosca M., Tapp A. Quantum amplitude amplification and estimation // Quantum Computation and Information. Ser.: Contemporary Mathematics. Providence, RI: Am. Math. Soc., 2002. V. 305. P. 53–74. http://dx.doi.org/10.1090/conm/305/05215.
3. Kaye P., Laflamme R., Mosca M. An Introduction to Quantum Computing. New York, NY: Oxford Univ. Press, 2007. 274 p.
4. Ablayev F., Ablayev M., Huang J.Z., Khadiev K., Salikhova N., Wu D. On quantum methods for machine learning problems. Part I: Quantum tools // Big Data Min. Anal. 2020. V. 3, No 1. P. 41–55. https://doi.org/10.26599/BDMA.2019.9020016.
5. Ablayev F., Ablayev M., Huang J.Z., Khadiev K., Salikhova N., Wu D. On quantum methods for machine learning problems. Part II: Quantum classification algorithms // Big Data Min. Anal. 2020. V. 3, No 1. P. 56–67. https://doi.org/10.26599/BDMA.2019.9020018.
6. Ablayev F., Salikhova N., Ablayev M. Hybrid classical–quantum text search based on hashing // Mathematics. 2024. V. 12, No 12. Art. 1858. https://doi.org/10.3390/math12121858.
7. Buhrman H., Cleve R., Watrous J., de Wolf R. Quantum fingerprinting // Phys. Rev. Lett. 2001. V. 87, No 16. Art. 167902. https://doi.org/10.1103/PhysRevLett.87.167902.
Рецензия
Для цитирования:
Салихова Н.М. Квантовый поиск в словаре на основе функции отпечатков. Ученые записки Казанского университета. Серия Физико-математические науки. 2025;167(1):115-124. https://doi.org/10.26907/2541-7746.2025.1.115-124
For citation:
Salikhova N.M. Quantum search in a dictionary using fingerprinting function. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki. 2025;167(1):115-124. (In Russ.) https://doi.org/10.26907/2541-7746.2025.1.115-124
Просмотров:
101
Послать статью по эл. почте 