В квантовых вычислениях , алгоритм Гровер , также известный как алгоритм квантового поиска , относится к квантовому алгоритму для поиска неструктурированного , который находит с высокой вероятностью уникальный на вход черного ящика функцию , которая производит особое значение выходного сигнала, используя только оценки функции, где является размер функции в области . Его изобрел Лов Гровер в 1996 году. [1]
Аналогичная проблема в классических вычислениях не может быть решена менее чем за оценки (потому что в среднем нужно проверить половину домена, чтобы получить 50% шанс найти правильный ввод). Примерно в то же время, когда Гровер опубликовал свой алгоритм, Чарльз Х. Беннет , Итан Бернштейн, Жиль Брассар и Умеш Вазирани доказали, что любое квантовое решение проблемы должно оценивать функциюраз, поэтому алгоритм Гровера асимптотически оптимален . [2] Поскольку исследователи обычно считают, что NP-полные задачи сложны, потому что их пространства поиска по существу не имеют структуры, оптимальность алгоритма Гровера для неструктурированного поиска предполагает (но не доказывает), что квантовые компьютеры не могут решать NP-полные задачи за полиномиальное время. . [3]
В отличие от других квантовых алгоритмов, которые могут обеспечивать экспоненциальное ускорение по сравнению с их классическими аналогами, алгоритм Гровера обеспечивает только квадратичное ускорение. Однако даже квадратичное ускорение значительно, когдаявляется большим, и алгоритм Гровера может применяться для ускорения широких классов алгоритмов. [3] Алгоритм Гровера мог подобрать 128-битный симметричный криптографический ключ примерно за 2 64 итераций или 256-битный ключ примерно за 2 128 итераций. В результате иногда предлагается [4] увеличить длину симметричного ключа вдвое для защиты от будущих квантовых атак.
Приложения и ограничения
Алгоритм Гровера, наряду с такими вариантами, как усиление амплитуды , может использоваться для ускорения широкого диапазона алгоритмов. [5] [6] [7] В частности, алгоритмы для NP-полных задач обычно содержат исчерпывающий поиск как подпрограмму, которая может быть ускорена с помощью алгоритма Гровера. [6] Лучший текущий алгоритм для 3SAT - один из таких примеров. Общие проблемы удовлетворения ограничений также видят квадратичное ускорение с помощью Гровера. [8] Эти алгоритмы не требуют, чтобы ввод был задан в форме оракула, поскольку алгоритм Гровера применяется с явной функцией, например, функцией, проверяющей соответствие набора битов экземпляру 3SAT.
Алгоритм Гровера также может дать доказуемое ускорение для задач черного ящика в квантовой сложности запросов , включая различимость элементов [9] и проблему коллизий [10] (решенную с помощью алгоритма Брассара – Хойера – Таппа ). В задачах такого типа можно рассматривать функцию оракула f как базу данных, и цель состоит в том, чтобы использовать квантовый запрос к этой функции как можно меньше раз.
Криптография
Алгоритм Гровера по сути решает задачу обращения функций . Грубо говоря, если у нас есть функция которые можно оценить на квантовом компьютере, алгоритм Гровера позволяет нам вычислить когда дано . Следовательно, алгоритм Гровера дает широкое асимптотическое ускорение для многих видов атак грубой силы на криптографию с симметричным ключом , включая атаки с коллизией и атаки с предварительным изображением . [11] Однако это не обязательно может быть наиболее эффективным алгоритмом, поскольку, например, параллельный алгоритм rho может находить коллизию в SHA2 более эффективно, чем алгоритм Гровера. [12]
Ограничения
В оригинальной статье Гровера алгоритм описывался как алгоритм поиска в базе данных, и это описание до сих пор широко распространено. База данных в этой аналогии представляет собой таблицу всех выходных данных функции, индексированных соответствующим входом. Однако эта база данных не представлена в явном виде. Вместо этого вызывается оракул для оценки элемента по его индексу. Чтение полного элемента базы данных за элементом и преобразование его в такое представление может занять намного больше времени, чем поиск Гровера. Чтобы учесть такие эффекты, алгоритм Гровера можно рассматривать как решение уравнения или удовлетворение ограничения . В таких приложениях оракул - это способ проверить ограничение и не связан с алгоритмом поиска. Такое разделение обычно предотвращает алгоритмическую оптимизацию, тогда как обычные алгоритмы поиска часто полагаются на такую оптимизацию и избегают исчерпывающего поиска. [13]
Основным препятствием для реализации ускорения алгоритма Гровера является то, что достигнутое квадратичное ускорение слишком скромно, чтобы преодолеть большие накладные расходы квантовых компьютеров в ближайшем будущем. [14] Однако более поздние поколения отказоустойчивых квантовых компьютеров с более высокой производительностью оборудования могут реализовать это ускорение для практических экземпляров данных.
Описание проблемы
В качестве входных данных для алгоритма Гровера предположим, что у нас есть функция . В аналогии с «неструктурированной базой данных» домен представляет индексы для базы данных, и f ( x ) = 1 тогда и только тогда, когда данные x, на которые указывает, удовлетворяют критерию поиска. Мы дополнительно предполагаем, что только один индекс удовлетворяет условию f ( x ) = 1, и мы называем этот индекс ω . Наша цель - идентифицировать ω .
Мы можем получить доступ к f с помощью подпрограммы (иногда называемой оракулом ) в форме унитарного оператора U ω, который действует следующим образом:
Это использует -мерное пространство состояний , который предоставляется регистром с кубиты . Это часто записывается как
Алгоритм Гровера выводит ω с вероятностью не менее 1/2, используяприложения U ω . Эту вероятность можно сделать сколь угодно малой, если выполнить алгоритм Гровера несколько раз. Если запустить алгоритм Гровера до тех пор, пока не будет найдено ω , ожидаемое количество приложений все равно останется, так как в среднем он будет запускаться только дважды.
Реализуя U ω
U ω отличается от стандартного квантового оракула для функции f . Этот стандартный оракул, обозначенный здесь как U f , использует вспомогательную систему кубитов (как в квантовой схеме, изображенной ниже). Затем операция представляет собой инверсию ( НЕ вентиль ), обусловленную значением f ( x ) в основной системе:
или вкратце,
Эти оракулы обычно реализуются без вычислений .
Если нам дан U f в качестве нашего оракула, то мы также можем реализовать U ω , поскольку U ω является U f, когда вспомогательный кубит находится в состоянии:
Итак, алгоритм Гровера можно запускать независимо от того, какой оракул задан. [3] Если задано U f , мы должны поддерживать дополнительный кубит в состояниии применяем U f вместо U ω .
Алгоритм
Шаги алгоритма Гровера представлены следующим образом:
- Инициализировать систему до однородной суперпозиции по всем состояниям
- Выполните следующую «итерацию Гровера» раз:
- Применить оператора .
- Примените оператор диффузии Гровера.
- Измерьте полученное квантовое состояние в вычислительной базе.
За правильно подобранное значение , вывод будет с вероятностью, приближающейся к 1 для N 1. Анализ показывает, что это конечное значение для удовлетворяет .
Реализация шагов для этого алгоритма может быть выполнена с использованием ряда вентилей, линейных по количеству кубитов. [3] Таким образом, сложность этого алгоритма равна, или же за итерацию.
Геометрическое доказательство правильности
Существует геометрическая интерпретация алгоритма Гровера, вытекающая из наблюдения, что квантовое состояние алгоритма Гровера остается в двумерном подпространстве после каждого шага. Рассмотрим плоскость, натянутую на а также ; эквивалентно, плоскость, натянутая наи перпендикулярный кет .
Алгоритм Гровера начинается с начального кет , лежащая в подпространстве. Оператор является отражением в гиперплоскости, ортогональной для векторов в плоскости, натянутой на а также , т. е. действует как отражение на . В этом можно убедиться, написавв виде отражения Хаусхолдера :
Оператор это отражение через . Оба оператора а также принимать состояния в плоскости, охватываемой а также к состояниям в самолете. Следовательно, алгоритм Гровера остается в этой плоскости на протяжении всего алгоритма.
Несложно проверить, что оператор каждого шага итерации Гровера поворачивает вектор состояния на угол . Итак, при достаточном количестве итераций можно повернуть из начального состояния в желаемое состояние выхода . Начальный кет близок к состоянию, ортогональному к:
Геометрически угол между а также дан кем-то
Нам нужно остановиться, когда вектор состояния пройдет близко к ; После этого, последующие итерации поворота вектора состояния в сторону от, снижая вероятность получения правильного ответа. Точная вероятность измерения правильного ответа равна
где r - (целое) число итераций Гровера. Таким образом, самое раннее время, когда мы получаем почти оптимальное измерение, является.
Алгебраическое доказательство правильности
Чтобы завершить алгебраический анализ, нам нужно выяснить, что происходит, когда мы неоднократно применяем . Естественный способ сделать это - анализ собственных значений матрицы. Обратите внимание, что в течение всего вычисления состояние алгоритма представляет собой линейную комбинацию а также . Мы можем написать действие а также в пространстве, охваченном в виде:
Итак, в основе (который не является ни ортогональным, ни базисом всего пространства) действие применения с последующим задается матрицей
Эта матрица имеет очень удобную жорданову форму . Если мы определим, это
- где
Отсюда следует, что r -я степень матрицы (соответствующая r итерациям) равна
Используя эту форму, мы можем использовать тригонометрические тождества для вычисления вероятности наблюдения ω после r итераций, упомянутых в предыдущем разделе,
В качестве альтернативы можно было бы разумно предположить, что почти оптимальное время для различения было бы, когда углы 2 rt и −2 rt находятся как можно дальше друг от друга, что соответствует, или же . Тогда система находится в состоянии
Краткий расчет теперь показывает, что наблюдение дает правильный ответ ω с ошибкой.
Расширения и варианты
Несколько совпадающих записей
Если вместо 1 совпадающей записи есть k совпадающих записей, работает тот же алгоритм, но количество итераций должно бытьвместо .
Есть несколько способов справиться с ситуацией, когда k неизвестно. [15] Простое решение работает оптимально с точностью до постоянного множителя: многократно запускайте алгоритм Гровера для все более малых значений k , например, принимая k = N, N / 2, N / 4, ... и т. Д., Принимаядля итерации t до тех пор, пока не будет найдена соответствующая запись.
С достаточно высокой вероятностью отмеченная запись будет найдена итерацией. для некоторой постоянной c . Таким образом, общее количество выполненных итераций не превосходит
Версия этого алгоритма используется для решения проблемы столкновения . [16] [17]
Квантовый частичный поиск
Модификация алгоритма Гровера, называемая квантовым частичным поиском, была описана Гровером и Радхакришнаном в 2004 году. [18] При частичном поиске никто не заинтересован в поиске точного адреса целевого элемента, а только первых нескольких цифр адреса. Точно так же мы можем подумать о «разбиении» области поиска на блоки, а затем спросить, «в каком блоке находится целевой элемент?». Во многих приложениях такой поиск дает достаточно информации, если целевой адрес содержит нужную информацию. Например, используя пример, приведенный Л.К. Гровером, если у кого-то есть список студентов, организованный по классам, нас может интересовать только то, находится ли студент в нижних 25%, 25–50%, 50–75% или 75–100% процентиль.
Чтобы описать частичный поиск, мы рассматриваем базу данных, разделенную на блоки, каждый размером . Проблема частичного поиска проще. Рассмотрим классический подход: мы выбираем один блок наугад, а затем выполняем обычный поиск по остальным блокам (на языке теории множеств, дополнение). Если мы не находим цель, значит, мы знаем, что она находится в блоке, который не искали. Среднее количество итераций падает с к .
Алгоритм Гровера требует итераций. Частичный поиск будет быстрее на числовой коэффициент, который зависит от количества блоков.. Частичный поиск использует глобальные итерации и локальные итерации. Назначен глобальный оператор Гровера и местный оператор Гровера назначен .
На блоки действует глобальный оператор Гровера. По сути, это дается следующим образом:
- Выполнять стандартные итерации Гровера для всей базы данных.
- Выполнять локальные итерации Гровера. Локальная итерация Гровера - это прямая сумма итераций Гровера по каждому блоку.
- Выполните одну стандартную итерацию Гровера.
Оптимальные значения а также обсуждаются в статье Гровера и Радхакришнана. Можно также задаться вопросом, что произойдет, если применить последовательные частичные поиски на разных уровнях «разрешения». Эта идея была подробно изучена Владимиром Корепиным и Сюй, которые назвали ее бинарным квантовым поиском. Они доказали, что на самом деле это не быстрее, чем выполнение одного частичного поиска.
Оптимальность
Алгоритм Гровера оптимален с точностью до субконстантных факторов. То есть любой алгоритм, который обращается к базе данных только с помощью оператора U ω, должен применять U ω не менеедроби столько раз, сколько алгоритм Гровера. [19] Расширение алгоритма Гровера на k совпадающих элементов, π ( N / k ) 1/2 / 4, также является оптимальным. [16] Этот результат важен для понимания ограничений квантовых вычислений.
Если бы задачу поиска Гровера можно было решить с помощью log c N приложений U ω , это означало бы, что NP содержится в BQP , путем преобразования проблем в NP в задачи поиска типа Гровера. Оптимальность алгоритма Гровера предполагает, что квантовые компьютеры не могут решать NP-Complete задачи за полиномиальное время, и, следовательно, NP не содержится в BQP.
Было показано, что класс нелокальных квантовых компьютеров со скрытыми переменными может реализовать поиск-item база данных не более шаги. Это быстрее, чемшаги, предпринятые алгоритмом Гровера. [20]
Смотрите также
- Усиление амплитуды
- Алгоритм Шора (для факторизации)
- Алгоритм Брассара – Хойера – Таппа (для решения проблемы столкновений )
Заметки
- ^ Гровер, 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 .
- ^ а б в г Нильсен, Майкл А. (2010). Квантовые вычисления и квантовая информация . Исаак Л. Чуанг. Кембридж: Издательство Кембриджского университета. С. 276–305. ISBN 978-1-107-00217-3. OCLC 665137861 .
- ^ Дэниел Дж. Бернштейн (2010-03-03). «Гровер против МакЭлиса» (PDF) . Цитировать журнал требует
|journal=
( помощь ) - ^ Гровер, Лов К. (1997). «Фреймворк для быстрых квантово-механических алгоритмов». arXiv : квант-ph / 9711043 .
- ^ а б Амбайнис, А. (2004-06-01). «Алгоритмы квантового поиска» . Новости ACM SIGACT . 35 (2): 22–35. DOI : 10.1145 / 992287.992296 . ISSN 0163-5700 .
- ^ Джордан, Стивен. "Зоопарк квантовых алгоритмов" . Quantumalgorithmzoo.org . Проверено 21 апреля 21 .
- ^ Cerf, Nicolas J .; Grover, Lov K .; Уильямс, Колин П. (2000-05-01). «Вложенный квантовый поиск и NP-трудные задачи» . Применимая алгебра в инженерии, коммуникации и вычислениях . 10 (4): 311–338. DOI : 10.1007 / s002000050134 . ISSN 1432-0622 .
- ^ Амбаинис, Андрис (01.01.2007). «Алгоритм квантового блуждания для определения различимости элементов» . 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: другие ( ссылка )
- ^ Бернштейн, Дэниел Дж. (21.04.2021). «Анализ затрат на хэш-коллизии: сделают ли квантовые компьютеры 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) .
- ^ а б Мишель Бойер; Жиль Брассар; Питер Хойер; Ален Тапп (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 .
- Крейг Гидни (2013-03-05). «Алгоритм квантового поиска Гровера» .
- Франсуа Шварцентрубер (18 мая 2013 г.). «Алгоритм Гровера» .
- Александр Прокопеня. "Квантовая схема, реализующая алгоритм поиска Гровера" . Вольфрам Альфа .
- "Квантовые вычисления, теория" , Математическая энциклопедия , EMS Press , 2001 [1994]
- Роберто Маэстре (2018-05-11). «Алгоритм Гровера, реализованный на языках R и C» .