Направо към съдържанието

Алгоритъм на Гроувър

от Уикипедия, свободната енциклопедия

Алгоритъмът на Гроувър, известен също като алгоритъм за квантово търсене в квантовите изчисления е алгоритъм за неструктурирано търсене, който намира с голяма вероятност уникалния вход на функция "черна кутия", която произвежда определена изходна стойност със сложност , където е размерът на областта на определение (домейна) на функцията. Той е създаден от Lov Grover през 1996 г. [1]

Аналогичният проблем в областта на класическите изчисления не може да бъде решен от алгоритъм със сложност по-малка от (тъй като средно човек трябва да провери половината от домейна, за да има 50% шанс да намери правилния вход). Чарлз Х. Бенет, Итън Бърнстейн, Жил Брасар и Умеш Вазирани доказват, че всяко квантово решение на проблема трябва да оцени функцията пъти, така че алгоритъмът на Гроувър е асимптотично оптимален . [2] Тъй като класическите алгоритми за NP-пълни проблеми изискват експоненциално много стъпки, а алгоритъмът на Гроувър осигурява най-много квадратично ускорение спрямо класическото решение, това предполага, че алгоритъмът на Гроувър сам по себе си няма да предостави решения за полиномиално време на NP проблеми ( тъй като квадратният корен на експоненциална функция е експоненциална, а не полиномиална функция). [3]

Въпреки това, когато N е голям, квадратичното ускорение е значително и алгоритъмът на Гровър може да бъде приложен, за да ускори широк набор от алгоритми. [3] Алгоритъмът може да форсира 128-битов симетричен криптографски ключ за приблизително 2 64 итерации или 256-битов ключ за приблизително 2 128 итерации. Възможно е обаче алгоритъмът на Гроувър да не представлява значително по-голям риск за криптирането в сравнение със съществуващите класически алгоритми. [4]

Приложения и ограничения

[редактиране | редактиране на кода]

Алгоритъмът на Гроувър, заедно с варианти като амплитудно усилване, може да се използват за ускоряване на широк набор от алгоритми. [5] [6] [7]Например, алгоритми за NP проблеми, които използват изчерпателно търсене като подпрограма, могат да се възползват от ускорението на Гроувър. [6] Един пример е най-добрият теоретичен алгоритъм (спрямо сложността в най-лошия случай) за 3SAT. Общи задачи за удовлетворяване на ограничения също постигат квадратично ускорение чрез Гроувър. [8] Тези алгоритми не изискват входът да бъде даден под формата на оракул, тъй като алгоритъмът на Гроувър се прилага с изрична функция, например функцията, проверяваща дали набор от битове удовлетворява 3SAT инстанция. Не е ясно обаче дали алгоритъмът на Grover може да ускори най-добрите практически алгоритми за тези проблеми.

Алгоритъмът на Гроувър може също така да даде доказуеми ускорения за проблеми с черната кутия със сложността на квантовата заявка, включително разграничаване на елемента [9] и Collision problem [10] (решен с алгоритъма на Brassard–Høyer–Tapp ). При тези видове проблеми човек третира функцията на оракул f като база данни и целта е да се използва квантовата заявка към тази функция възможно най-малко пъти.

Криптография

[редактиране | редактиране на кода]

Алгоритъмът на Гроувър решава задачата за обръщане на функции. Казано просто, ако разполагаме с функция y=f(x), която може да бъде изчислена на квантов компютър, алгоритъмът на Гроувър позволява да намерим x, когато y е дадено. Благодарение на това, алгоритъмът осигурява значителни асимптотични ускорения за много видове атаки чрез изчерпателно търсене в симетричната криптография, включително атаки за колизии и предобрази. [11] Въпреки това, алгоритъмът на Гроувър не винаги е най-ефективният метод. Например, паралелният алгоритъм „rho“ намира колизии в SHA2 по-ефективно от алгоритъма на Гроувър. [12]

Ограничения

[редактиране | редактиране на кода]

Оригиналната статия на Гроувър описва алгоритъма като алгоритъм за търсене в база данни и това описание все още е често срещано. Базата данни в тази аналогия е таблица на всички изходи на функцията, индексирани от съответния вход. Тази база данни обаче не е представена изрично. Вместо това се извиква оракул, за да оцени даден елемент по неговия индекс. Четенето на пълна база данни елемент по елемент и преобразуването му в такова представяне може да отнеме много повече време от търсенето на Гроувър. За да се отчетат такива ефекти, алгоритъмът на Гроувър може да се разглежда като решаване на уравнение или удовлетворяване на ограничение . В такива приложения оракулът е начин за проверка на ограничението и не е свързан с алгоритъма за търсене. Това разделяне обикновено предотвратява алгоритмичните оптимизации, докато конвенционалните алгоритми за търсене често разчитат на такива оптимизации и избягват изчерпателно търсене. [13]

Това разделение обикновено пречи на алгоритмични оптимизации, докато традиционните методи за търсене често се възползват от такива оптимизации, избягвайки изчерпателно търсене. За щастие, бързи реализации на оракули за алгоритъма на Гроувър са възможни за много задачи за удовлетворяване на ограничения и оптимизация.[14]

Основната пречка за постигане на ускорение с алгоритъма на Гроувър е, че квадратичното ускорение не е достатъчно, за да компенсира големите изчислителни разходи на квантовите компютри от близко бъдеще. Въпреки това, бъдещи поколения на устойчиви на грешки квантови компютри с по-добра хардуерна производителност може да реализират тези ускорения при практически задачи.

Източници

[редактиране | редактиране на кода]
  1. ↑ Grover, Lov K. A fast quantum mechanical algorithm for database search // Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96. Philadelphia, Pennsylvania, USA, Association for Computing Machinery, 1996-07-01. ISBN 978-0-89791-785-8. DOI:10.1145/237814.237866. с. 212–219.
  2. ↑ Bennett C.H. и др. The strengths and weaknesses of quantum computation // SIAM Journal on Computing 26 (5). 1997. DOI:10.1137/s0097539796300933. с. 1510–1523.
  3. ↑ а б Nielsen, Michael A. Quantum computation and quantum information. Cambridge, Cambridge University Press, 2010. ISBN 978-1-107-00217-3. OCLC 665137861. с. 276–305.
  4. ↑ Bernstein, Daniel J. Post-Quantum Cryptography, Third International Workshop, PQCrypto 2010, Darmstadt, Germany, May 25-28, 2010. Proceedings // {{{conference}}}. Т. 6061. Springer, 2010, 73–80 с. DOI:10.1007/978-3-642-12929-2_6.
  5. ↑ Grover, Lov K. Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23–26, 1998 // {{{conference}}}. Association for Computing Machinery, 1998, 53–62 с. DOI:10.1145/276698.276712.
  6. ↑ а б Ambainis, A. Quantum search algorithms // ACM SIGACT News 35 (2). 2004-06-01. DOI:10.1145/992287.992296. с. 22–35.
  7. ↑ Jordan, Stephen. Quantum Algorithm Zoo // quantumalgorithmzoo.org. Посетен на 2021-04-21. (на английски)
  8. ↑ Cerf, Nicolas J. и др. Nested Quantum Search and NP-Hard Problems // Applicable Algebra in Engineering, Communication and Computing 10 (4). 2000-05-01. DOI:10.1007/s002000050134. с. 311–338.
  9. ↑ Ambainis, Andris. Quantum Walk Algorithm for Element Distinctness // SIAM Journal on Computing 37 (1). 2007-01-01. DOI:10.1137/S0097539705447311. с. 210–239.
  10. ↑ LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings // {{{conference}}}. Т. 1380. Springer, 1998, 163–169 с. DOI:10.1007/BFb0054319.
  11. ↑ Post-quantum cryptography. Berlin, Springer, 2009. ISBN 978-3-540-88702-7. OCLC 318545517.
  12. ↑ Bernstein, Daniel J. Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete? // Conference Proceedings for Special-purpose Hardware for Attacking Cryptographic Systems (SHARCS '09) 09. 2021-04-21. с. 105–117.
  13. ↑ 62–70 с. DOI:10.1109/mcse.2005.53.
  14. ↑ Sinitsyn N. A. и др. Topologically protected Grover's oracle for the partition problem // Physical Review A 108 (2). 2023. DOI:10.1103/PhysRevA.108.022412. с. 022412.
  Тази страница частично или изцяло представлява превод на страницата Grover's algorithm в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​

Взето от „https://bg.wikipedia.org/w/index.php?title=Алгоритъм_на_Гроувър&oldid=12434134“.