Используется алгоритм Гровера, среди прочего, искать нужный пункт $\mathbf{y}$ в неупорядоченном списке элементов $[\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}]$ длины $n$ . Несмотря на то, что здесь есть много вопросов по этой теме, я все еще упускаю суть.

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

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

$$\mathrm{search}([\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}], \mathbf{y}) = i \in \mathbb{N} \quad \text{such that } \mathbf{x}_i = \mathbf{y}$$ Так что я даю список и требуемый элемент в качестве входных данных, и я получаю положение элемента в списке в качестве выходных данных. Кажетсяя понялчто информация о$\mathbf{y}$ встраивается в алгоритме через оракула ворот$O$ , такнаша функция становится $$\mathrm{search}_\mathbf{y}([\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n] ) = i \in \mathbb{N} \quad \text{such that } \mathbf{x}_i = \mathbf{y}$$ Давайте сделаем практический пример. Рассмотрим поиск туз пик$1\spadesuit$ в последовательности из 8 карт изстандартной колоды 52 карт:

Список длины $8$ : $[ \mathbf{x}_0 = J\clubsuit,$ $\mathbf{x}_1 = 10\diamondsuit,$ $\mathbf{x}_2 = 4\heartsuit,$ $\mathbf{x}_3 = Q\clubsuit,$ $\mathbf{x}_4 = 3\spadesuit,$ $\mathbf{x}_5 = 1\spadesuit,$ $\mathbf{x}_6 = 6\spadesuit,$ $\mathbf{x}_7 = 6\clubsuit]$ .

Требуемый элемент $\mathbf{x}_5$ . Я должен получить $\mathrm{search}_{\spadesuit}(cards) = 5$ . Каждая карта может быть закодирована с $\lceil{\log_2 52}\rceil = 6$ бит, список содержит $8$ элементов таким образом , мы должны $6\times 8 = 48$ бит для кодирования списка. В этом случае оракул $O$ будет реализовывать функцию:

$$f(\mathbf{x}) = \begin{cases} 1, & \mathbf{x} = 1\spadesuit \\ 0, & \text{otherwise} \end{cases}$$

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

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

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

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

Ввод $\mathrm{search}_{\spadesuit}(\cdot)$ теперь представляет собой $\lceil \log_2 8 \rceil = 3$ кубит-вектора $|\psi\rangle$ , которое должно быть суперпозицией всех элементов в пространстве поиска $S$ .

Мы знаем

• $|0_{3\text{qubits}}\rangle = |000\rangle$ соответствует$J\clubsuit$ ;
• $|1_{3\text{qubits}}\rangle = |001\rangle$ соответствует$10\diamondsuit$ ;
• $|2_{3\text{qubits}}\rangle = |010\rangle$ соответствует$4\heartsuit$ ;
• $|5_{3\text{qubits}}\rangle = |101\rangle$ соответствует к$1\spadesuit$ который является элементом разыскиваемый;
• и так далее...

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

$$\mathrm{search}_{\spadesuit}(|\psi\rangle) = |5_{3\text{qubits}}\rangle$$ Но в этом случае, наш оракул бы реализовать функцию $$f(|\psi\rangle) = \begin{cases} 1, & |\psi\rangle = |5_{3\text{qubits}}\rangle \\ 0, & \text{otherwise} \end{cases}$$

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

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

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

$$f(\mathbf{x}) = \begin{cases} 1, & \text{if x = 5, or binary '101'} \\ 0, & \text{otherwise} \end{cases}$$

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

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

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

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

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

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

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

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

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

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

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

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

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

$$f(x) = \begin{cases} 1, & x[0, \ldots, 3] + x[4, \ldots, 7] = 1010 \\ 0, & \text{otherwise} \end{cases}$$

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