Алгоритм Гровера: где список?

15

Используется алгоритм Гровера, среди прочего, искать нужный пункт y в неупорядоченном списке элементов [x0,x1,...,xn1] длины n . Несмотря на то, что здесь есть много вопросов по этой теме, я все еще упускаю суть.

Поиск в списке, классический способ

Как правило, я бы разработать функцию поиска таким образом ,

search([x0,x1,...,xn1],y)=iNsuch that xi=y
Так что я даю список и требуемый элемент в качестве входных данных, и я получаю положение элемента в списке в качестве выходных данных. Кажетсяя понялчто информация оy встраивается в алгоритме через оракула воротO , такнаша функция становится
searchy([x1,x2,...,xn])=iNsuch that xi=y
Давайте сделаем практический пример. Рассмотрим поиск туз пик1 в последовательности из 8 карт изстандартной колоды 52 карт:

перетасованная колода

Список длины 8 : [x0=J, x1=10, x2=4, x3=Q, x4=3, x5=1, x6=6, x7=6] .

Требуемый элемент x5 . Я должен получить search(cards)=5 . Каждая карта может быть закодирована с log252=6 бит, список содержит 8 элементов таким образом , мы должны 6×8=48 бит для кодирования списка. В этом случае оракул O будет реализовывать функцию:

f(x)={1,x=10,otherwise

Однако ввод алгоритма Гровера не является состоянием из 48 кубитов.

(NB: изображение перетасованной колоды взято отсюда )

Гровер и его оракул

(Например. Некоторые источники здесь - графический объяснить) говорят о том , что вход алгоритма отличается: вход состояние берется из пространства поиска S={0,1,2,...,N}={0,1,2,...,7} где N - количество элементов списка. Каждое число соответствует позиции элемента в списке.

Ввод search() теперь представляет собой log28=3 кубит-вектора |ψ , которое должно быть суперпозицией всех элементов в пространстве поиска S .

Мы знаем

  • |03qubits=|000 соответствуетJ ;
  • |13qubits=|001 соответствует10 ;
  • |23qubits=|010 соответствует4 ;
  • |53qubits=|101 соответствует к1 который является элементом разыскиваемый;
  • и так далее...

В этом случае мы имеем

search(|ψ)=|53qubits
Но в этом случае, наш оракул бы реализовать функцию
f(|ψ)={1,|ψ=|53qubits0,otherwise

Построение оракула требует , чтобы мы знали , что находится в положении 5. Какой смысл выполнить алгоритм , если мы уже искали элемент для того , чтобы построить оракул?

incud
источник
Мне также трудно понять преимущество алгоритма Гровера. Предположим, что у меня есть N пунктов в списке. При каждом обращении к Оракулу он оценивал все N возможностей? Даже если оценка очень быстрая, но если нам все еще нужно перебирать все конфигурации, сложность оценки Oracle составляет O (N). Таким образом, алгоритм Гровера, кажется, не быстрее, чем тупой поиск. Это верно?
Санпарит Марукатат
@SanparithMarukatat Это не правильно. Элементы вашего списка - это условия суперпозиции состояния, участвующего в поиске. Когда Oracle работает в этом состоянии, он считается одной операцией. Способность Оракула обозначать искомый термин вашей суперпозиции является фундаментальной частью понимания Гровера. Чтобы понять алгоритм Гровера, я рекомендую сначала понять, как происходит выделение нужного состояния. После этого обязательно поймите роль государства . |
Р. Шопен
Если вы это понимаете, то вам следует изучить оператора, способного увеличить амплитуду нужного члена в суперпозиции и в то же время уменьшить амплитуду нежелательных членов суперпозиции. Для меня самый простой способ приблизиться к Гроверу - это посмотреть на оператор обратного среднего. (Некоторые люди принимают геометрический вид, но я не нахожу его таким ясным.)
Р. Шопен

Ответы:

10

Если у вас есть 8 элементов в списке (как в примере с вашей картой), то ввод оракула составляет 3 (qu) бита. Количество карт в колоде (52) не имеет значения, вам нужно только 3 бита для кодирования 8 карт.

Вы можете думать, что 3 бита кодируют позицию в списке искомой карты; тогда вы не знаете положение, но оракул знает. Таким образом, если вы ищете туз пик, то оракул знает, что туз пик является 6-й картой (или 5-й отсчет от нуля) и реализует функцию

f(x)={1,if x = 5, or binary '101'0,otherwise

PS: Лучше думать об алгоритме Гровера по-другому: у вас есть оракул, реализующий булеву функцию, которая выводит для одной комбинации входных битов, иначе выдает ноль, и ваша задача - найти эту комбинацию. Проблема имеет ту же сложность, что и поиск в несортированном списке или базе данных, поэтому алгоритм Гровера обычно описывают как поиск в несортированной базе данных. Но применение алгоритма к реальному поиску в базе данных действительно поднимает вопросы, выходящие за рамки самого алгоритма. Алгоритм Гровера просто ищет то, что знает оракул.1

kludg
источник
Да, извините, что 6 было от предыдущего редактирования
incud
2
Спасибо за ваш ответ. Я исправил ошибку. Какой смысл выполнять алгоритм, если для построения оракула мне нужно знать положение искомого элемента?
incud
1
@incud Действительно, это не имеет смысла. Я обновил ответ.
Клудг
« Алгоритм Гровера просто ищет то, что знает оракул »: не обязательно. Оракул может проверять только какое-то конкретное свойство ввода, так что полученный в конце результат содержит больше информации, чем закодировано в оракуле. Типичный пример - поиск в телефонной книге. Оракул «просит» запись, прикрепленную к определенному имени, но как только найдена правильная запись, также можно получить дополнительную информацию о номере телефона, прикрепленном к этой записи, который вообще не был закодирован в оракуле
GLS
4

Хотя нам, пожалуй, проще всего думать о функции оракула как о том, что он уже вычислил все эти значения, но это не то, что он делает. В случае, который вы описали, оракул имеет 8 возможных входов (т.е. закодирован в 3 (qu) бита), и оракул выполняет все необходимые вычисления на лету . Итак, в момент, когда вы пытаетесь оценить оракула для некоторого значения , оракул ищет (в данном случае) карту, на которой значение xxxсоответствует, а затем проверяет, является ли эта карта помеченной картой. Идея в том, что каждый раз, когда вы называете оракула, он проходит этот процесс один раз. В целом, вы оцениваете функцию столько раз, сколько вы вызываете оракула. Цель любого алгоритма поиска - вызывать этого оракула как можно меньше раз.

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

Ключевые отличия в вашем примере по сравнению с более реалистичным сценарием использования:

  • Пространство поиска обычно огромно. Нет реальной перспективы предварительного расчета всех значений. Действительно, это именно то, чего мы пытаемся избежать.

  • Обычно мы не говорим «найди туз пик». Вместо этого есть который нетривиально оценить, чтобы проверить, является ли x отмеченным элементом или нет. Тот факт, что оракулу может потребоваться достаточно много времени для оценки, даже для одной записи, является причиной того, что оракул является дорогостоящей частью реализации (а все остальные ворота предоставляются бесплатно), и поэтому вам необходимо минимизировать количество вызовов ,е(Икс)Икс

Итак, действительно, классический поиск будет работать на вашу проблему: выберите случайно. Оцените y = f ( x ) . Если y = 1 , верните x , в противном случае повторите. В то время как чистым эффектом f ( x ) является «является входом x 0 , отмеченная запись?», Это не фактический расчет, который он выполняет.ИксYзнак равное(Икс)Yзнак равно1Иксе(Икс)Икс0

DaftWullie
источник
2

В конечном счете, возникает вопрос: «Какой смысл выполнять алгоритм, если мы уже искали элемент для построения оракула?»

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

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

Мы спрашиваем оракула: какой у него уже есть ответ на вопрос, который у него уже есть? Даже Матеус и Омар спрашивали бы «символ оракула для конкретного алфавита» во время выполнения, каковы позиции его символа в строке, которую он уже скомпилировал? Оракул даст ответ на наш запрос только после одной консультации, но в этой истории он, например, не может просто выписать ответ в виде двоичной строки и отправить его нам по классическому каналу связи. Он будет скрывать свой ответ в суперпозиции, чтобы мы могли его вытянуть.

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

Брендан М
источник
2

Учитывая предоставленный вами оракул, поиск действительно бессмыслен. Тем не менее, этот оракул пропускает смысл алгоритма Гровера, потому что поиск карты в колоде карт не является неструктурированным поиском, потому что, как вы сказали, вы уже знаете порядок. Ergo, ваш поиск структурирован. Причина, по которой этот оракул используется, заключается в том, что он демонстрирует, как можно применять Гровера без обсуждения оракула, который мог бы сделать Гровера полезным, поскольку такой оракул был бы более сложным, чем ценным. Поэтому лучшим оракулом для демонстрации полезности Гровера может быть что-то вроде:

е(Икс)знак равно{1,Икс[0,...,3]+Икс[4,...,7]знак равно10100,в противном случае

Этот оракул подразумевает, что у вас есть 8-кубитный поиск, в котором вы берете первые четыре кубита, добавляете их ко вторым четырем кубитам и переключаете M, если сложение составляет 10 (1010 в двоичном виде). Разница между этим оракулом и предоставленным вами заключается в том, что этот оракул проверяет шаблон (добавьте операнды к 10), а ваш - равенство (это индекс 5). Этот оракул гораздо сложнее построить, но он использует истинную силу Гровера, который, по сути, является перебором, где ваш оракул определяет пространство поиска.

Woody1193
источник