Алгоритм Гровера - Grover's algorithm

В квантовых вычислениях , алгоритм Гровер , также известный как алгоритм квантового поиска , относится к квантовому алгоритму для неструктурированного поиска , который находит с высокой вероятностью уникальный на вход черного ящика функцию , которая производит конкретную выходную величину, используя только оценку функции, где это размер функции в области . Его изобрел Лов Гровер в 1996 году.

Аналогичная проблема в классических вычислениях не может быть решена за счет меньшего количества оценок (потому что в среднем нужно проверить половину области, чтобы получить 50% шанс найти правильный ввод). Примерно в то же время, когда Гровер опубликовал свой алгоритм, Чарльз Х. Беннет , Итан Бернштейн, Жиль Брассар и Умеш Вазирани доказали, что любое квантовое решение проблемы должно оценивать время функции , поэтому алгоритм Гровера является асимптотически оптимальным . Поскольку исследователи обычно считают, что NP-полные задачи сложны, потому что их пространства поиска по существу не имеют структуры, оптимальность алгоритма Гровера для неструктурированного поиска предполагает (но не доказывает), что квантовые компьютеры не могут решать NP-полные задачи за полиномиальное время .

В отличие от других квантовых алгоритмов, которые могут обеспечивать экспоненциальное ускорение по сравнению с их классическими аналогами, алгоритм Гровера обеспечивает только квадратичное ускорение. Однако даже квадратичное ускорение является значительным, когда оно велико, и алгоритм Гровера может применяться для ускорения широких классов алгоритмов. Алгоритм Гровера мог подобрать 128-битный симметричный криптографический ключ примерно за 2 64 итераций или 256-битный ключ примерно за 2 128 итераций. В результате иногда предлагается удвоить длину симметричного ключа для защиты от будущих квантовых атак.

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

Алгоритм Гровера, наряду с такими вариантами, как усиление амплитуды , можно использовать для ускорения широкого диапазона алгоритмов. В частности, алгоритмы для NP-полных задач обычно содержат исчерпывающий поиск как подпрограмму, которую можно ускорить с помощью алгоритма Гровера. Современный лучший алгоритм для 3SAT - один из таких примеров. Общие проблемы удовлетворения ограничений также видят квадратичное ускорение с помощью Гровера. Эти алгоритмы не требуют, чтобы ввод был дан в форме оракула, поскольку алгоритм Гровера применяется с явной функцией, например, функцией, проверяющей соответствие набора битов экземпляру 3SAT.

Алгоритм Гровера также может дать доказуемое ускорение для задач черного ящика в квантовой сложности запросов , включая различимость элементов и проблему коллизий (решаемая с помощью алгоритма Брассара – Хойера – Таппа ). В задачах такого типа можно рассматривать функцию оракула f как базу данных, и цель состоит в том, чтобы использовать квантовый запрос к этой функции как можно меньше раз.

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

Алгоритм Гровера по сути решает задачу обращения функций . Грубо говоря, если у нас есть функция, которую можно вычислить на квантовом компьютере, алгоритм Гровера позволяет нам вычислять, когда он задан . Следовательно, алгоритм Гровера дает широкое асимптотическое ускорение для многих видов атак грубой силы на криптографию с симметричным ключом , включая атаки с коллизией и атаки с предварительным изображением . Однако это не обязательно может быть наиболее эффективным алгоритмом, поскольку, например, параллельный алгоритм rho может находить коллизию в SHA2 более эффективно, чем алгоритм Гровера.

Ограничения

В оригинальной статье Гровера алгоритм описывался как алгоритм поиска в базе данных, и это описание до сих пор широко распространено. База данных в этой аналогии представляет собой таблицу всех выходных данных функции, индексированных соответствующим входом. Однако эта база данных не представлена ​​в явном виде. Вместо этого вызывается оракул для оценки элемента по его индексу. Чтение полного элемента базы данных за элементом и преобразование его в такое представление может занять намного больше времени, чем поиск Гровера. Чтобы учесть такие эффекты, алгоритм Гровера можно рассматривать как решение уравнения или удовлетворение ограничения . В таких приложениях оракул - это способ проверить ограничение и не связан с алгоритмом поиска. Такое разделение обычно предотвращает алгоритмическую оптимизацию, тогда как обычные алгоритмы поиска часто полагаются на такую ​​оптимизацию и избегают исчерпывающего поиска.

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

Описание проблемы

В качестве входных данных для алгоритма Гровера предположим, что у нас есть функция . В аналогии с «неструктурированной базой данных» домен представляет индексы для базы данных, и f ( x ) = 1 тогда и только тогда, когда данные x, на которые указывает, удовлетворяют критерию поиска. Мы дополнительно предполагаем, что только один индекс удовлетворяет условию f ( x ) = 1, и мы называем этот индекс ω . Наша цель - идентифицировать ω .

Мы можем получить доступ к f с помощью подпрограммы (иногда называемой оракулом ) в форме унитарного оператора U ω, который действует следующим образом:

При этом используется -мерное пространство состояний , которое обеспечивается регистром с кубитами . Это часто записывается как

Алгоритм Гровера выводит ω с вероятностью не менее 1/2, используя приложения U ω . Эту вероятность можно сделать сколь угодно малой, если выполнить алгоритм Гровера несколько раз. Если алгоритм Гровера запускается до тех пор, пока не будет найдено ω , ожидаемое количество приложений останется прежним , поскольку в среднем он будет выполняться только дважды.

Альтернативное определение оракула

В этом разделе сравнивается вышеупомянутый оракул с оракулом .

U ω отличается от стандартного квантового оракула для функции f . Этот стандартный оракул, обозначенный здесь как U f , использует вспомогательную систему кубитов . Затем операция представляет собой инверсию ( НЕ вентиль ), обусловленную значением f ( x ) в основной системе:

или вкратце,

Эти оракулы обычно реализуются без вычислений .

Если нам дан U f в качестве нашего оракула, то мы также можем реализовать U ω , поскольку U ω является U f, когда вспомогательный кубит находится в состоянии :

Итак, алгоритм Гровера можно запускать независимо от того, какой оракул задан. Если задано U f , мы должны поддерживать в этом состоянии дополнительный кубит и применять U f вместо U ω .

Алгоритм

Представление квантовой схемы алгоритма Гровера

Шаги алгоритма Гровера представлены следующим образом:

  1. Инициализировать систему до однородной суперпозиции по всем состояниям
  2. Выполните следующие «итерации Гровера» раз:
    1. Применяем оператора .
    2. Примените оператор диффузии Гровера .
  3. Измерьте полученное квантовое состояние в вычислительной базе.

Для правильно выбранного значения выход будет с вероятностью приближающейся к 1 для N 1. Анализ показывает, что это конечное значение для удовлетворяет .

Реализация шагов для этого алгоритма может быть выполнена с использованием ряда вентилей, линейных по количеству кубитов. Таким образом, сложность этого алгоритма равна или на итерацию.

Геометрическое доказательство правильности

Изображение, показывающее геометрическую интерпретацию первой итерации алгоритма Гровера. Вектор состояния поворачивается к целевому вектору, как показано.

Существует геометрическая интерпретация алгоритма Гровера, вытекающая из наблюдения, что квантовое состояние алгоритма Гровера остается в двумерном подпространстве после каждого шага. Рассмотрим плоскость, натянутую на и ; эквивалентно, плоскость натянута на перпендикуляр кет .

Алгоритм Гровера начинается с начального кета , лежащего в подпространстве. Оператор является отражением в гиперплоскости, ортогональной векторам в плоскости, натянутой на и , т. Е. Действует как отражение поперек . Это можно увидеть, написав в форме отражения Хаусхолдера :

Оператор - это отражение насквозь . Оба оператора и принимать состояния в плоскости , натянутой и состояния на плоскости. Следовательно, алгоритм Гровера остается в этой плоскости на протяжении всего алгоритма.

Несложно проверить, что оператор на каждой итерации Гровера поворачивает вектор состояния на угол . Таким образом, при достаточном количестве итераций можно перейти из начального состояния в желаемое выходное состояние . Начальный кет близок к состоянию, ортогональному :

С геометрической точки зрения угол между и определяется выражением

Нам нужно остановиться, когда вектор состояния пройдет близко к ; после этого последующие итерации поворачивают вектор состояния в сторону от , уменьшая вероятность получения правильного ответа. Точная вероятность измерения правильного ответа равна

где r - (целое) число итераций Гровера. Таким образом, самое раннее время, когда мы получаем почти оптимальное измерение, составляет .

Алгебраическое доказательство правильности

Чтобы завершить алгебраический анализ, нам нужно выяснить, что происходит, когда мы повторно подаем заявку . Естественный способ сделать это - анализ собственных значений матрицы. Обратите внимание, что в течение всего вычисления состояние алгоритма представляет собой линейную комбинацию и . Мы можем записать действие и в пространстве, охватываемом как:

Таким образом, в базисе (который не является ни ортогональным, ни базисом всего пространства) действие применения, за которым следует, задается матрицей

Эта матрица имеет очень удобную жорданову форму . Если мы определим , это

куда

Отсюда следует, что r -я степень матрицы (соответствующая r итерациям) равна

Используя эту форму, мы можем использовать тригонометрические тождества для вычисления вероятности наблюдения ω после r итераций, упомянутых в предыдущем разделе,

В качестве альтернативы можно было бы разумно предположить, что почти оптимальное время для различения было бы, когда углы 2 rt и -2 rt находятся как можно дальше друг от друга, что соответствует , или . Тогда система находится в состоянии

Краткий расчет теперь показывает, что наблюдение дает правильный ответ ω с ошибкой .

Расширения и варианты

Несколько совпадающих записей

Если вместо 1 совпадающей записи есть k совпадающих записей, работает тот же алгоритм, но вместо этого должно быть количество итераций .

Есть несколько способов справиться со случаем, если k неизвестно. Простое решение работает оптимально с точностью до постоянного множителя: многократно запускайте алгоритм Гровера для все более малых значений k , например, принимая k = N, N / 2, N / 4, ... и так далее, принимая в качестве итерации t до тех пор, пока найдена соответствующая запись.

С достаточно высокой вероятностью отмеченная запись будет найдена итерацией для некоторой константы c . Таким образом, общее количество выполненных итераций не превосходит

Версия этого алгоритма используется для решения проблемы столкновения .

Квантовый частичный поиск

Модификация алгоритма Гровера, называемая квантовым частичным поиском, была описана Гровером и Радхакришнаном в 2004 году. При частичном поиске человек не заинтересован в поиске точного адреса целевого элемента, а только первых нескольких цифр адреса. Точно так же мы можем подумать о «разбиении» области поиска на блоки, а затем спросить, «в каком блоке находится целевой элемент?». Во многих приложениях такой поиск дает достаточно информации, если целевой адрес содержит нужную информацию. Например, используя пример, приведенный Л.К. Гровером, если у кого-то есть список студентов, организованный по классам, нас может интересовать только то, находится ли студент в нижних 25%, 25–50%, 50–75% или 75–100% процентиль.

Чтобы описать частичный поиск, мы рассматриваем базу данных, разделенную на блоки, каждый по размеру . Проблема частичного поиска проще. Рассмотрим классический подход: мы выбираем один блок наугад, а затем выполняем обычный поиск по остальным блокам (на языке теории множеств, дополнение). Если мы не находим цель, значит, мы знаем, что она находится в блоке, который мы не искали. Среднее количество итераций снижается с до .

Алгоритм Гровера требует итераций. Частичный поиск будет быстрее на числовой коэффициент, который зависит от количества блоков . Частичный поиск использует глобальные итерации и локальные итерации. Назначается глобальный оператор Гровера и назначается местный оператор Гровера .

На блоки действует глобальный оператор Гровера. По сути, это дается следующим образом:

  1. Выполните стандартные итерации Гровера для всей базы данных.
  2. Выполните локальные итерации Гровера. Локальная итерация Гровера - это прямая сумма итераций Гровера по каждому блоку.
  3. Выполните одну стандартную итерацию Гровера.

Оптимальные значения и обсуждаются в статье Гровера и Радхакришнана. Можно также задаться вопросом, что произойдет, если применить последовательные частичные поиски на разных уровнях «разрешения». Эта идея была подробно изучена Владимиром Корепиным и Сюй, которые назвали ее бинарным квантовым поиском. Они доказали, что на самом деле это не быстрее, чем выполнение одного частичного поиска.

Оптимальность

Алгоритм Гровера оптимален с точностью до субконстантных факторов. То есть любой алгоритм, который обращается к базе данных только с помощью оператора U ω, должен применять U ω по крайней мере в несколько раз больше, чем алгоритм Гровера. Расширение алгоритма Гровера на k совпадающих элементов, π ( N / k ) 1/2 / 4, также является оптимальным. Этот результат важен для понимания ограничений квантовых вычислений.

Если бы задачу поиска Гровера можно было решить с помощью log c N приложений U ω , это означало бы, что NP содержится в BQP , путем преобразования задач в NP в задачи поиска типа Гровера. Оптимальность алгоритма Гровера предполагает, что квантовые компьютеры не могут решать NP-Complete задачи за полиномиальное время, и поэтому NP не содержится в BQP.

Было показано, что класс нелокальных квантовых компьютеров со скрытыми переменными может реализовать поиск в базе данных -элементов не более чем за несколько этапов. Это быстрее, чем шаги, предпринимаемые алгоритмом Гровера.

Смотрите также

Примечания

  1. ^ Гровер, Lov К. (1996-07-01). «Быстрый квантово-механический алгоритм поиска по базам данных» . Материалы двадцать восьмого ежегодного симпозиума ACM по теории вычислений . СТОК '96. Филадельфия, Пенсильвания, США: Ассоциация вычислительной техники: 212–219. DOI : 10.1145 / 237814.237866 . ISBN 978-0-89791-785-8.
  2. ^ Bennett CH; Бернштейн Э .; Brassard G .; Вазирани У. (1997). «Сильные и слабые стороны квантовых вычислений» . SIAM Journal on Computing . 26 (5): 1510–1523. arXiv : квант-ph / 9701001 . DOI : 10.1137 / s0097539796300933 . S2CID  13403194 .
  3. ^ a b c d Нильсен, Майкл А. (2010). Квантовые вычисления и квантовая информация . Исаак Л. Чуанг. Кембридж: Издательство Кембриджского университета. С. 276–305. ISBN 978-1-107-00217-3. OCLC  665137861 .
  4. ^ Дэниел Дж. Бернштейн (2010-03-03). «Гровер против МакЭлиса» (PDF) . Цитировать журнал требует |journal=( помощь )
  5. ^ Гровер, Lov К. (1997). «Фреймворк для быстрых квантово-механических алгоритмов». arXiv : квант-ph / 9711043 .
  6. ^ a b Амбаинис, А. (2004-06-01). «Алгоритмы квантового поиска» . Новости ACM SIGACT . 35 (2): 22–35. DOI : 10.1145 / 992287.992296 . ISSN  0163-5700 .
  7. ^ Джордан, Стивен. "Зоопарк квантовых алгоритмов" . Quantumalgorithmzoo.org . Проверено 21 апреля 2021 .
  8. ^ Серф, Николас Дж .; Grover, Lov K .; Уильямс, Колин П. (2000-05-01). «Вложенный квантовый поиск и NP-трудные задачи» . Применимая алгебра в инженерии, коммуникации и вычислениях . 10 (4): 311–338. DOI : 10.1007 / s002000050134 . ISSN  1432-0622 .
  9. ^ Ambainis, Andris (2007-01-01). «Алгоритм квантового блуждания для определения различимости элементов» . SIAM Journal on Computing . 37 (1): 210–239. DOI : 10,1137 / S0097539705447311 . ISSN  0097-5397 .
  10. ^ Брассар, Жиль; Хойер, Питер; Тэпп, Ален (1997). «Квантовый алгоритм для проблемы столкновения» . Конспект лекций по информатике : 163–169. arXiv : квант-ph / 9705002 . DOI : 10.1007 / BFb0054319 .
  11. ^ Постквантовая криптография . Даниэль Дж. Бернштейн, Йоханнес Бухманн, Эрик, дипломированный математик Дахмен. Берлин: Springer. 2009. ISBN. 978-3-540-88702-7. OCLC  318545517 .CS1 maint: другие ( ссылка )
  12. ^ Бернштейн, Дэниел Дж. (2021-04-21). «Анализ затрат на хэш-коллизии: сделают ли квантовые компьютеры SHARCS устаревшими?» (PDF) . Материалы конференции по специализированному оборудованию для атак на криптографические системы (SHARCS '09) . 09 : 105–117.
  13. ^ Viamontes GF; Марков ИЛ; Hayes JP (2005), "Практичен ли квантовый поиск?" (PDF) , Вычисления в науке и технике , 7 (3): 62–70, arXiv : Quant-ph / 0405001 , Bibcode : 2005CSE ..... 7c..62V , doi : 10.1109 / mcse.2005.53 , S2CID  8929938
  14. ^ Баббуш, Райан; McClean, Jarrod R .; Ньюман, Майкл; Гидни, Крейг; Бойшо, Серджио; Невен, Хартмут (29 марта 2021 г.). «Сосредоточьтесь не на квадратичном ускорении, а на квантовом преимуществе с исправлением ошибок» . PRX Quantum . 2 (1): 010103. DOI : 10,1103 / PRXQuantum.2.010103 .
  15. Ааронсон, Скотт (19 апреля 2021 г.). «Введение в конспект лекций по квантовой информатике» (PDF) .
  16. ^ a b Мишель Бойер; Жиль Брассар; Питер Хойер; Ален Тапп (1998), "Тесные границы квантового поиска", Fortsch. Phys. , 46 : 493–506, arXiv : Quant-ph / 9605034 , Bibcode : 1998ForPh..46..493B , doi : 10.1002 / 3527603093.ch10 , ISBN 9783527603091
  17. ^ Андрис Амбайнис (2004), «Алгоритмы квантового поиска», SIGACT News , 35 (2): 22–35, arXiv : Quant-ph / 0504012 , Bibcode : 2005quant.ph..4012A , doi : 10.1145 / 992287.992296 , S2CID  11326499
  18. ^ Л.К. Гровер; Дж. Радхакришнан (07.02.2005). «Разве частичный квантовый поиск в базе данных проще?». arXiv : Quant-ph / 0407122v4 .
  19. ^ Залки, Кристофа (1999-10-01). «Алгоритм квантового поиска Гровера оптимален» . Physical Review . 60 (4): 2746–2751. arXiv : квант-ph / 9711070 . DOI : 10.1103 / PhysRevA.60.2746 .
  20. ^ Ааронсон, Скотт. «Квантовые вычисления и скрытые переменные» (PDF) .

использованная литература

внешние ссылки