3
$\begingroup$

I am new to this field and I have been baffled by the idea of Oracle for a long time.

I am aware of the procedure, but I am very confused about how we choose the oracle.

Let say we have 4 poker cards, the spade of Ace, the club of 7, the heart of 9, and the diamond of 7. I shuffled the four cards and now I want to know where is the spade of ace.

I would first encode the cards, say 00, 01, 10, and 11 respectively for the spade of Ace, the club of 7, the heart of 9, and the diamond of 7.

To solve the problem on a quantum computer, I will first initialize the system in the superposition of the four states, and I apply the oracle corresponding to $|00\rangle$ (see Qiskit), and evolve the state and everything, I will finally end up with the state $|00\rangle$.

My question is how does this result help me in any way? I wanted to know the position of the spade of Ace in the deck of cards but instead I got a state $|00\rangle$, which means spade of the Ace. Am I missing a step somewhere?

I would appreciate it if the answer could continue with the example, and show from beginning to end how one can find the position of the card.

$\endgroup$
3

1 Answer 1

1
$\begingroup$

In your card example, since you've created the encoding, you've kind of already made Grover's algorithm useless. That is, you already know that 00 is the spade of Ace, so you don't need to search. Grover's algorithm would only help find the spade of Ace if you didn't already know which bitstring encoded it.

As an example: Suppose you shuffle the cards and you want to know where the spade of Ace is. If you have an encoding from bitstrings to the cards themselves, then of course this can't help you because that encoding doesn't have any information about the ordering after the shuffle.

Instead, imagine that the encoding was: 00 returned the first card, 01 returned the second card, etc. Now your question is: which card is the spade of Ace?

Suppose your Grover oracle is able to take this bitstring as input, look at the card in that position, and flip the phase if that card is the space of Ace. Then Grover's algorithm will work. If the spade of Ace is the first card, then Grover's algorithm with return 00.

Of course this example is a bit too small to really make sense anyway, since you can just look at all the cards. If you had a full deck of 52 cards, it would make a bit more sense: Grover's algorithm could tell you the position of the spade of Ace after only "looking at" $\approx\frac{\pi}{2}\sqrt{52}\approx 11$ cards (although you would need some way to look at cards in a coherent superposition).

$\endgroup$
2
  • $\begingroup$ Thanks for the explanation, but how does the oracle that "take this bitstring as input, look at the card in that position, and flip the phase if that card is the space of Ace"? Namely what would the circuit look like? $\endgroup$
    – wooohooo
    May 8, 2020 at 19:37
  • $\begingroup$ In practice that would be impossible, since searching through a deck of cards isn't really a task a computer can do. $\endgroup$
    – Sam Jaques
    May 10, 2020 at 10:16

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