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

Шаблон:Машинен превод Алгоритъмът на Гроувър, известен също като алгоритъм за квантово търсене в квантовите изчисления е алгоритъм за неструктурирано търсене, който намира с голяма вероятност уникалния вход на функция "черна кутия", която произвежда определена изходна стойност със сложност $O(\sqrt{N})$, където $N$ е размерът на областта на определение (домейна) на функцията. Той е създаден от Lov Grover през 1996 г.

Аналогичният проблем в областта на класическите изчисления не може да бъде решен от алгоритъм със сложност по-малка от $O(N)$ (тъй като средно човек трябва да провери половината от домейна, за да има 50% шанс да намери правилния вход). Чарлз Х. Бенет, Итън Бърнстейн, Жил Брасар и Умеш Вазирани доказват, че всяко квантово решение на проблема трябва да оцени функцията $\mathrm{\Omega }(\sqrt{N})$ пъти, така че алгоритъмът на Гроувър е асимптотично оптимален . Тъй като класическите алгоритми за NP-пълни проблеми изискват експоненциално много стъпки, а алгоритъмът на Гроувър осигурява най-много квадратично ускорение спрямо класическото решение, това предполага, че алгоритъмът на Гроувър сам по себе си няма да предостави решения за полиномиално време на NP проблеми ( тъй като квадратният корен на експоненциална функция е експоненциална, а не полиномиална функция).

Въпреки това, когато N е голям, квадратичното ускорение е значително и алгоритъмът на Гровър може да бъде приложен, за да ускори широк набор от алгоритми. Алгоритъмът може да форсира 128-битов симетричен криптографски ключ за приблизително 2 ⁶⁴ итерации или 256-битов ключ за приблизително 2 ¹²⁸ итерации. Възможно е обаче алгоритъмът на Гроувър да не представлява значително по-голям риск за криптирането в сравнение със съществуващите класически алгоритми.

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

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

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

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

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

Ограничения

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

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

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