Алгоритм Гровера - 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 для 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% процентиль.
Чтобы описать частичный поиск, мы рассматриваем базу данных, разделенную на блоки, каждый по размеру . Проблема частичного поиска проще. Рассмотрим классический подход: мы выбираем один блок наугад, а затем выполняем обычный поиск по остальным блокам (на языке теории множеств, дополнение). Если мы не находим цель, значит, мы знаем, что она находится в блоке, который мы не искали. Среднее количество итераций снижается с до .
Алгоритм Гровера требует итераций. Частичный поиск будет быстрее на числовой коэффициент, который зависит от количества блоков . Частичный поиск использует глобальные итерации и локальные итерации. Назначается глобальный оператор Гровера и назначается местный оператор Гровера .
На блоки действует глобальный оператор Гровера. По сути, это дается следующим образом:
- Выполните стандартные итерации Гровера для всей базы данных.
- Выполните локальные итерации Гровера. Локальная итерация Гровера - это прямая сумма итераций Гровера по каждому блоку.
- Выполните одну стандартную итерацию Гровера.
Оптимальные значения и обсуждаются в статье Гровера и Радхакришнана. Можно также задаться вопросом, что произойдет, если применить последовательные частичные поиски на разных уровнях «разрешения». Эта идея была подробно изучена Владимиром Корепиным и Сюй, которые назвали ее бинарным квантовым поиском. Они доказали, что на самом деле это не быстрее, чем выполнение одного частичного поиска.
Оптимальность
Алгоритм Гровера оптимален с точностью до субконстантных факторов. То есть любой алгоритм, который обращается к базе данных только с помощью оператора U ω, должен применять U ω по крайней мере в несколько раз больше, чем алгоритм Гровера. Расширение алгоритма Гровера на k совпадающих элементов, π ( N / k ) 1/2 / 4, также является оптимальным. Этот результат важен для понимания ограничений квантовых вычислений.
Если бы задачу поиска Гровера можно было решить с помощью log c N приложений U ω , это означало бы, что NP содержится в BQP , путем преобразования задач в NP в задачи поиска типа Гровера. Оптимальность алгоритма Гровера предполагает, что квантовые компьютеры не могут решать NP-Complete задачи за полиномиальное время, и поэтому NP не содержится в BQP.
Было показано, что класс нелокальных квантовых компьютеров со скрытыми переменными может реализовать поиск в базе данных -элементов не более чем за несколько этапов. Это быстрее, чем шаги, предпринимаемые алгоритмом Гровера.
Смотрите также
- Усиление амплитуды
- Алгоритм Шора (для факторизации)
- Алгоритм Брассара – Хойера – Таппа (для решения проблемы столкновений )
Примечания
- ^ Гровер, Lov К. (1996-07-01). «Быстрый квантово-механический алгоритм поиска по базам данных» . Материалы двадцать восьмого ежегодного симпозиума ACM по теории вычислений . СТОК '96. Филадельфия, Пенсильвания, США: Ассоциация вычислительной техники: 212–219. DOI : 10.1145 / 237814.237866 . ISBN 978-0-89791-785-8.
- ^ Bennett CH; Бернштейн Э .; Brassard G .; Вазирани У. (1997). «Сильные и слабые стороны квантовых вычислений» . SIAM Journal on Computing . 26 (5): 1510–1523. arXiv : квант-ph / 9701001 . DOI : 10.1137 / s0097539796300933 . S2CID 13403194 .
- ^ a b c d Нильсен, Майкл А. (2010). Квантовые вычисления и квантовая информация . Исаак Л. Чуанг. Кембридж: Издательство Кембриджского университета. С. 276–305. ISBN 978-1-107-00217-3. OCLC 665137861 .
-
^ Дэниел Дж. Бернштейн (2010-03-03). «Гровер против МакЭлиса» (PDF) . Цитировать журнал требует
|journal=
( помощь ) - ^ Гровер, Lov К. (1997). «Фреймворк для быстрых квантово-механических алгоритмов». arXiv : квант-ph / 9711043 .
- ^ a b Амбаинис, А. (2004-06-01). «Алгоритмы квантового поиска» . Новости ACM SIGACT . 35 (2): 22–35. DOI : 10.1145 / 992287.992296 . ISSN 0163-5700 .
- ^ Джордан, Стивен. "Зоопарк квантовых алгоритмов" . Quantumalgorithmzoo.org . Проверено 21 апреля 2021 .
- ^ Серф, Николас Дж .; Grover, Lov K .; Уильямс, Колин П. (2000-05-01). «Вложенный квантовый поиск и NP-трудные задачи» . Применимая алгебра в инженерии, коммуникации и вычислениях . 10 (4): 311–338. DOI : 10.1007 / s002000050134 . ISSN 1432-0622 .
- ^ Ambainis, Andris (2007-01-01). «Алгоритм квантового блуждания для определения различимости элементов» . SIAM Journal on Computing . 37 (1): 210–239. DOI : 10,1137 / S0097539705447311 . ISSN 0097-5397 .
- ^ Брассар, Жиль; Хойер, Питер; Тэпп, Ален (1997). «Квантовый алгоритм для проблемы столкновения» . Конспект лекций по информатике : 163–169. arXiv : квант-ph / 9705002 . DOI : 10.1007 / BFb0054319 .
- ^ Постквантовая криптография . Даниэль Дж. Бернштейн, Йоханнес Бухманн, Эрик, дипломированный математик Дахмен. Берлин: Springer. 2009. ISBN. 978-3-540-88702-7. OCLC 318545517 .CS1 maint: другие ( ссылка )
- ^ Бернштейн, Дэниел Дж. (2021-04-21). «Анализ затрат на хэш-коллизии: сделают ли квантовые компьютеры SHARCS устаревшими?» (PDF) . Материалы конференции по специализированному оборудованию для атак на криптографические системы (SHARCS '09) . 09 : 105–117.
- ^ 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
- ^ Баббуш, Райан; McClean, Jarrod R .; Ньюман, Майкл; Гидни, Крейг; Бойшо, Серджио; Невен, Хартмут (29 марта 2021 г.). «Сосредоточьтесь не на квадратичном ускорении, а на квантовом преимуществе с исправлением ошибок» . PRX Quantum . 2 (1): 010103. DOI : 10,1103 / PRXQuantum.2.010103 .
- ↑ Ааронсон, Скотт (19 апреля 2021 г.). «Введение в конспект лекций по квантовой информатике» (PDF) .
- ^ a b Мишель Бойер; Жиль Брассар; Питер Хойер; Ален Тапп (1998), "Тесные границы квантового поиска", Fortsch. Phys. , 46 : 493–506, arXiv : Quant-ph / 9605034 , Bibcode : 1998ForPh..46..493B , doi : 10.1002 / 3527603093.ch10 , ISBN 9783527603091
- ^ Андрис Амбайнис (2004), «Алгоритмы квантового поиска», SIGACT News , 35 (2): 22–35, arXiv : Quant-ph / 0504012 , Bibcode : 2005quant.ph..4012A , doi : 10.1145 / 992287.992296 , S2CID 11326499
- ^ Л.К. Гровер; Дж. Радхакришнан (07.02.2005). «Разве частичный квантовый поиск в базе данных проще?». arXiv : Quant-ph / 0407122v4 .
- ^ Залки, Кристофа (1999-10-01). «Алгоритм квантового поиска Гровера оптимален» . Physical Review . 60 (4): 2746–2751. arXiv : квант-ph / 9711070 . DOI : 10.1103 / PhysRevA.60.2746 .
- ^ Ааронсон, Скотт. «Квантовые вычисления и скрытые переменные» (PDF) .
использованная литература
- Гровер Л.К.: Быстрый квантово-механический алгоритм поиска в базе данных , Труды, 28-й ежегодный симпозиум ACM по теории вычислений, (май 1996 г.) с. 212
- Гровер Л.К .: От уравнения Шредингера к алгоритму квантового поиска , Американский журнал физики, 69 (7): 769–777, 2001. Педагогический обзор алгоритма и его истории.
- Гровер Л.К .: КВАНТОВЫЕ ВЫЧИСЛЕНИЯ: Как странная логика субатомного мира может позволить машинам вычислять в миллионы раз быстрее, чем они делают сегодня The Sciences , июль / август 1999 г., стр. 24–30.
- Нильсен, М.А. и Чуанг, И.Л. Квантовые вычисления и квантовая информация . Cambridge University Press, 2000. Глава 6.
- Что такое квантовая телефонная книга? , Лов Гровер, Lucent Technologies
внешние ссылки
- Дэви Уибирал. «Симулятор квантовой схемы» . Архивировано из оригинала на 2017-01-16 . Проверено 13 января 2017 .
- Крейг Гидни (05.03.2013). «Алгоритм квантового поиска Гровера» .
- Франсуа Шварцентрубер (18 мая 2013 г.). «Алгоритм Гровера» .
- Александр Прокопеня. "Квантовая схема, реализующая алгоритм поиска Гровера" . Вольфрам Альфа .
- "Квантовые вычисления, теория" , Энциклопедия математики , EMS Press , 2001 [1994]
- Роберто Маэстре (2018-05-11). «Алгоритм Гровера, реализованный на языках R и C» .