Как реализован оракул в алгоритме поиска Гровера?

Алгоритм поиска Гровера обеспечивает доказуемое квадратичное ускорение поиска в несортированной базе данных. Алгоритм обычно выражается следующей квантовой схемой:

В большинстве представлений важнейшая часть протокола - «врата оракула» $U_\omega$ , который «волшебным образом» выполняет операцию $|x\rangle\mapsto(-1)^{f(x)}|x\rangle$ . Однако часто остается невысказанным, насколько трудно было бы реализовать такие ворота. В самом деле, может показаться, что использование «оракула» - это просто способ справиться с трудностями.

Как мы узнаем, осуществима ли такая оральная операция? И если да, то какова его сложность (например, с точки зрения сложности разложения ворот)?

Функция $f$ - это просто произвольная логическая функция строки битов: $f\colon \{0,1\}^n \to \{0,1\}$ . Для приложений для взлома криптографии, таких как [1] , [2] или [3] , это на самом деле не «поиск в базе данных», который потребует как-то хранить всю базу данных в виде квантовой схемы, а скорее такую ​​функцию, как

$$\begin{equation*} x \mapsto \begin{cases} 1, & \text{if $\operatorname{SHA-256}(x) = y$;} \\ 0, & \text{otherwise,} \end{cases} \end{equation*}$$

для фиксированного $y$ , который не имеет структуры, которую мы можем использовать для классического поиска, в отличие, скажем, от функции

$$\begin{equation*} x \mapsto \begin{cases} 1, & \text{if $2^x \equiv y \pmod{2^{2048} - 1942289}$}, \\ 0, & \text{otherwise}, \end{cases} \end{equation*}$$

которая имеет структуру, которая может быть использована для ее быстрого преобразования даже на классическом компьютере.

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

$f$

$$C\colon \left|a\right> \left|b\right> \to \left|a\right> \left|a \oplus b\right>$$ $\oplus$ $$F\colon \left|x\right> \left|a\right> \lvert\text{junk}\rangle \mapsto \left|x\right> \left|a \oplus f(x)\right> \lvert\text{junk}'\rangle$$ $C$$f$$\left|x\right>$$\left|-\right> = H\left|1\right> = (1/\sqrt{2})(\left|0\right> - \left|1\right>)$$H$

$$\begin{align*} F\left|x\right> \left|-\right> \lvert\text{junk}\rangle &= \frac{1}{\sqrt{2}}\bigl( F\left|x\right> \left|0\right> \lvert\text{junk}\rangle - F\left|x\right> \left|1\right> \lvert\text{junk}\rangle \bigr) \\ &= \frac{1}{\sqrt{2}}\bigl( \left|x\right> \left|f(x)\right> \lvert\text{junk}'\rangle - \left|x\right> \left|1 \oplus f(x)\right> \lvert\text{junk}'\rangle \bigr). \end{align*}$$

If $f(x) = 0$ then $1 \oplus f(x) = 1$, so by simplifying we obtain

$$F\left|x\right> \left|-\right> \lvert\text{junk}\rangle = \left|x\right> \left|-\right> \lvert\text{junk}'\rangle,$$ whereas if $f(x) = 1$ then $1 \oplus f(x) = 0$, so $$F\left|x\right> \left|-\right> \lvert\text{junk}\rangle = -\left|x\right> \left|-\right> \lvert\text{junk}'\rangle,$$ and thus in general $$F\left|x\right> \left|-\right> \lvert\text{junk}\rangle = (-1)^{f(x)} \left|x\right> \left|-\right> \lvert\text{junk}'\rangle.$$

Well, Grover's original paper, "Quantum mechanics helps in searching for a needle in a haystack" clearly states, it assumes that C(S) can be evaluated in a constant time. Grover's search is not concerned about the implementability, but the polynomial reduction in what's called a query complexity (how many times you consult the oracle, like a classical database)

In fact, the concept of oracle in computing was proposed by Alan Turing to describe constructs for which a description on a UTM might not be realizable (Wikipedia). It is in some sense magical.

But of course, coming back to your question, how do we then actually make the circuit for Grover search (or any oracular) algorithm? Do we need to know the answer in advance to search the result? Well, in some sense you need to. That is exactly what clever improvements on Grover search tries to work on, such that, we need not know the exact answer in advance, but some properties of it. Let me illustrate with an example.

For the pattern recognition problem using Grover's search, if I have 4 patterns on 2 qubits (00, 01, 10, 11) and I want to mark and amplify 11, the diagonal of my oracle unitary should be like (1,1,1,-1) to take care of the pi phase shift for the solution. So, for this simple implementation, for construction the unitary, you need to know the full answer in advance.

A clever improvement of pattern completion if given in the paper "Quantum pattern matching" by Mateas and Omar. In essence, it constructs as many fixed oracles as there are alphabets in the set. So for our binary string, there will be an oracle which marks out all 1s, and another that marks out all 0s. The oracles are invoked conditionally based on what I want to search. If I want to search 11, I call oracle 1 on the LSqubit, and oracle 1 again on the MSqubit. By the first oracle, I would amplify the states (01, 11), i.e. states with LSQ as 1, and in the 2nd call, it would amplify (10, 11). So as you see, 11 is the only state that gets amplified twice, ending in a higher measurement probability. Though the compiled quantum circuit would change based on what my input search pattern is, a high-level description of the quantum algorithm remains the same. You can think of the oracles as function calls based on a switch case of the alphabet set invoked for each character in the search string.