25
$\begingroup$

Grover's search algorithm provides a provable quadratic speed-up for unsorted database search. The algorithm is usually expressed by the following quantum circuit:

In most representations, a crucial part of the protocol is the "oracle gate" $U_\omega$, which "magically" performs the operation $|x\rangle\mapsto(-1)^{f(x)}|x\rangle$. It is however often left unsaid how difficult realizing such a gate would actually be. Indeed, it could seem like this use of an "oracle" is just a way to sweep the difficulties under the carpet.

How do we know whether such an oracular operation is indeed realizable? And if so, what is its complexity (for example in terms of complexity of gate decomposition)?

$\endgroup$
  • 4
    $\begingroup$ That's something I wondered about, too. In this experiment for example they hard-wire the solution into the oracle, which tastes a bit like cheating to me... $\endgroup$ – M. Stern Mar 17 '18 at 2:48
  • $\begingroup$ Another great answer to this question is provided in this answer on CS Theory SE. $\endgroup$ – glS Jun 16 '18 at 12:51
18
$\begingroup$

The function $f$ is simply an arbitrary boolean function of a bit string: $f\colon \{0,1\}^n \to \{0,1\}$. For applications to breaking cryptography, such as [1], [2], or [3], this is not actually a ‘database lookup’, which would necessitate storing the entire database as a quantum circuit somehow, but rather a function such as

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

for fixed $y$, which has no structure we can exploit for a classical search, unlike, say, the function

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

which has $p = 2k\pm s$ with $s$ small less recommandable than others as a discrete log modulus?’, crypto.stackexchange.com, 2011-12-01.">structure that can be exploited to invert it faster even on a classical computer.

The question of the particular cost can't be answered in general because $f$ can be any circuit—it's just a matter of making a quantum circuit out of a classical circuit. But usually, as in the example above, the function $f$ is very cheap to evaluate on a classical computer, so it shouldn't pose a particularly onerous burden on a quantum computer for which everything else about Grover's algorithm is within your budget.

The only general cost on top of $f$ is an extra conditional NOT gate $$C\colon \left|a\right> \left|b\right> \to \left|a\right> \left|a \oplus b\right>$$ where $\oplus$ is xor, and an extra ancillary qubit for it. In particular, if we have a circuit $$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$$ built out of $C$ and the circuit for $f$, then if we apply it to $\left|x\right>$ together with an ancillary qubit initially in the state $\left|-\right> = H\left|1\right> = (1/\sqrt{2})(\left|0\right> - \left|1\right>)$ where $H$ is a Hadamard gate, then we get

\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.$$

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.