Какие приложения есть в алгоритме поиска Grover?

14

Об алгоритме поиска Гровера обычно говорят в терминах поиска помеченной записи в несортированной базе данных. Это естественный формализм, который позволяет применять его непосредственно к поиску решений проблем NP (где хорошее решение легко распознается).

Мне было интересно узнать о других приложениях поиска Гровера для поиска минимума, среднего значения и медианы набора чисел. Это заставляет меня задуматься о том, существуют ли какие-либо другие менее очевидные приложения поиска Гровера (или приложения его обобщений, такие как усиление амплитуды), которые уже известны? Любое краткое понимание о том, как это делается, будет оценено.

DaftWullie
источник

Ответы:

7

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

Введение :

Проблема столкновения чаще всего относится к версии 2 к 1, которая была описана Скоттом Ааронсоном в его диссертации. Учитывая , что четно и функция F : { 1 , . , , , П } { 1 , . , , , n } мы заранее знаем, что f равно 1-к-1 или 2-к-1. Нам разрешено только делать запросы о значении f ( i ) для любого i { 1 , 2 ,Nе:{1,,,,,N}{1,,,,,N}ее(я) . Затем проблема спрашивает, сколько запросов нам нужно сделать, чтобы с уверенностью определить,являетсяли f 1-к-1 или 2-к-1.i{1,2,...,n}f

Решение версии 2-к-1 детерминировано требует запросов, и, в общем, для отличия функций r-to-1 от функций 1-к-1 требуется n / r + 1 запросов.n/2+1n/r+1

Детерминированное классическое решение :

Это прямое применение принципа голубя: если функция r-to-1, то после запросов мы гарантированно обнаружим столкновение. Если функция 1-к-1, то столкновения не существует. Если нам не повезет, то n / r- запросы могут дать разные ответы. Так что n / r + 1 запросов необходимы.N/р+1N/рN/р+1

Рандомизированное классическое решение :

Если мы допустим случайность, проблема будет проще. По парадоксу дня рождения, если мы выбираем (различные) запросы случайным образом, то с большой вероятностью мы находим столкновение в любой фиксированной функции 2-в-1 после запросы.Θ(N)

Квантовое решение BHT :

Интуитивно, алгоритм объединяет ускорение квадратного корня из парадокса дня рождения с использованием (классической) случайности с ускорением квадратного корня из алгоритма Гровера (квантового).

Во- первых, входы F выбраны случайным образом и е опрашивается на всех из них. Если между этими входами есть коллизия, мы возвращаем пару входов. В противном случае все эти входные данные отображаются в различные значения на f . Затем алгоритм Гровера используется, чтобы найти новый вход для f, который сталкивается. Поскольку существует только п 2 / 3 такие входы в F , алгоритм Гровера может найти один (если она существует), сделав только O ( N1/3ееееN2/3езапросы ке.О(N2/3)знак равноО(N1/3)е

Источники:

  1. https://en.wikipedia.org/wiki/Collision_problem

  2. https://en.wikipedia.org/wiki/BHT_algorithm

  3. Квантовый алгоритм для решения проблемы столкновения - Жиль Брассар, Питер Хойер, Ален Тапп

Санчайан Датта
источник
Некоторые замечания по поводу решения BHT (я не нашел википедии статью очень поучительный): Во- первых, выберите входа в тест - е в случайном порядке. Предположим, они не сталкиваются. Сортируйте эти значения x в соответствии с f ( x ) . Теперь, если F ( х ) 2-к-1, существует п 1 / 3 значения х уже не проверено , которые сталкиваются с тем испытанием. Итак, определите функцию, которая проверяет «еще не проверено и сталкивается». Это определяет отмеченные записи. Столкновение легко проверить с помощью отсортированного списка значений f ( xN1/3еИксе(Икс)е(Икс)N1/3Икс . Зная точное количество помеченных записей (если 2 к 1), Гровер (почти) гарантирует решение. е(Икс)
DaftWullie
@DaftWullie Да, это действительно имеет смысл. Алгоритм Гровера не гарантирует решение, но имеет высокую вероятность предоставления правильного решения. Но разве это не очевидно из самого описания Википедии? Я не уверен, что понимаю смысл или возражение, которое вы высказываете. Я что-то пропустил?
Санчайан Датта
Все, что я могу сказать, это то, что это не было очевидно для меня . При первом чтении я понял (ложно), что для Гровера вместо того, чтобы готовить суперпозицию всех возможных состояний, он готовил суперпозицию только к тем, которые еще не были проверены. Но это казалось решающим для объяснения ускорения. Кроме того, я был изначально обеспокоен тем, как проверяются столкновения: какие пары проверяются на столкновения и насколько эффективно можно рассчитать столкновение?
DaftWullie
@DaftWullie Ах, хорошо. Я понимаю вашу точку зрения. Википедия не вдавалась в подробности алгоритма. Вы всегда можете обратиться к оригинальному документу ( arxiv.org/abs/quant-ph/9705002 ) для деталей (что, я думаю, вы уже сделали). Позже я постараюсь расширить этот ответ, чтобы включить все детали. Я все еще читаю газету.
Санчайан Датта
1
Если кубиты и квантовые ворота не окажутся невероятно дешевле битов и классических ворот, любое обсуждение BHT должно включать оговорку о том, что затраты превышают современный классический поиск столкновений с машиной Ван Ооршота – Винера. Подробности см. В cr.yp.to/papers.html#collisioncost или blog.cr.yp.to/20171017-collisions.html . (Последнее является ответом на предполагаемое улучшение BHT, которое утверждает, что оно более рентабельно, чем классический поиск столкновений.)
Squeamish Ossifrage
4

Алгоритм Гровера широко используется и в квантовой криптографии. Его можно использовать для решения таких проблем, как проблема трансцендентального логарифма, проблема поиска полиномиального корня и т. Д.

da281
источник
Не могли бы вы уточнить немного? Каковы эти проблемы? Где я могу прочитать больше о них?
DaftWullie
1
ieeexplore.ieee.org/document/7016940 Эта статья посвящена разработке квантового алгоритма для решения проблемы поиска корней полинома. Вы можете прочитать больше об этом там
da281
0

MM

Фактически, алгоритм Гровера является самым известным квантовым алгоритмом для многих сложных задач оптимизации (таких как NP-полные), которые не имеют большой структуры, поддающейся классическому алгоритму, более умному, чем поиск методом перебора: https: // link.springer.com/chapter/10.1007/978-3-540-78773-0_67 .

tparker
источник