16
$\begingroup$

I'm fairly confused about how Grover's algorithm could be used in practice and I'd like to ask help on clarification through an example.

Let's assume an $N=8$ element database that contains colors Red, Orange, Yellow, Green, Cyan, Blue, Indigo and Violet, and not necessarily in this order. My goal is to find Red in the database.

The input for Grover's algorithm is $n = \log_2(N=8) = 3$ qubits, where the 3 qubits encode the indices of the dataset. My confusion comes here (might be confused about the premises so rather say confusion strikes here) that, as I understand, the oracle actually searches for one of the indices of the dataset (represented by the superposition of the 3 qubits), and furthermore, the oracle is "hardcoded" for which index it should look for.

My questions are:

  • What do I get wrong here?
  • If the oracle is really looking for one of the indices of the database, that would mean we know already which index we are looking for, so why searching?
  • Given the above conditions with the colors, could someone point it out if it is possible with Grover's to look for Red in an unstructured dataset?

There are implementations for Grover's algorithm with an oracle for $n=3$ searching for |111>, e.g. (or see an R implementation of the same oracle below): Oracle for 111 https://quantumcomputing.stackexchange.com/a/2205

Again, my confusion is, given I do not know the position of $N$ elements in a dataset, the algorithm requires me to search for a string that encodes the position of $N$ elements. How do I know which position I should look for when the dataset is unstructured?

R code:

 #START
 a = TensorProd(TensorProd(Hadamard(I2),Hadamard(I2)),Hadamard(I2))
 # 1st CNOT
 a1= CNOT3_12(a)
 # 2nd composite
 # I x I x T1Gate
 b = TensorProd(TensorProd(I2,I2),T1Gate(I2)) 
 b1 = DotProduct(b,a1)
 c = CNOT3_02(b1)
 # 3rd composite
 # I x I x TGate
 d = TensorProd(TensorProd(I2,I2),TGate(I2))
 d1 = DotProduct(d,c)
 e = CNOT3_12(d1)
 # 4th composite
 # I x I x T1Gate
 f = TensorProd(TensorProd(I2,I2),T1Gate(I2))
 f1 = DotProduct(f,e)
 g = CNOT3_02(f1)
 #5th composite
 # I x T x T
 h = TensorProd(TensorProd(I2,TGate(I2)),TGate(I2))
 h1 = DotProduct(h,g)
 i = CNOT3_01(h1)
 #6th composite
 j = TensorProd(TensorProd(I2,T1Gate(I2)),I2)
 j1 = DotProduct(j,i)
 k = CNOT3_01(j1)
 #7th composite
 l = TensorProd(TensorProd(TGate(I2),I2),I2)
 l1 = DotProduct(l,k)
 #8th composite
 n = TensorProd(TensorProd(Hadamard(I2),Hadamard(I2)),Hadamard(I2))
 n1 = DotProduct(n,l1)
 n2 = TensorProd(TensorProd(PauliX(I2),PauliX(I2)),PauliX(I2))
 a = DotProduct(n2,n1)
 #repeat the same from 2st not gate
 a1= CNOT3_12(a)
 # 2nd composite
 # I x I x T1Gate
 b = TensorProd(TensorProd(I2,I2),T1Gate(I2))
 b1 = DotProduct(b,a1)
 c = CNOT3_02(b1)
 # 3rd composite
 # I x I x TGate
 d = TensorProd(TensorProd(I2,I2),TGate(I2))
 d1 = DotProduct(d,c)
 e = CNOT3_12(d1)
 # 4th composite
 # I x I x T1Gate
 f = TensorProd(TensorProd(I2,I2),T1Gate(I2))
 f1 = DotProduct(f,e)
 g = CNOT3_02(f1)
 #5th composite
 # I x T x T
 h = TensorProd(TensorProd(I2,TGate(I2)),TGate(I2))
 h1 = DotProduct(h,g)
 i = CNOT3_01(h1)
 #6th composite
 j = TensorProd(TensorProd(I2,T1Gate(I2)),I2)
 j1 = DotProduct(j,i)
 k = CNOT3_01(j1)
 #7th composite
 l = TensorProd(TensorProd(TGate(I2),I2),I2)
 l1 = DotProduct(l,k)
 #8th composite
 n = TensorProd(TensorProd(PauliX(I2),PauliX(I2)),PauliX(I2))
 n1 = DotProduct(n,l1)
 n2 = TensorProd(TensorProd(Hadamard(I2),Hadamard(I2)),Hadamard(I2))
 n3 = DotProduct(n2,n1)
 result=measurement(n3)
 plotMeasurement(result)

Image2

Improve this question
$\endgroup$
2

3 Answers 3

Reset to default
7
$\begingroup$

This is already partially discussed in this related question, but I'll try here to address more specifically some of the issues you rise.

Generally speaking, Grover's algorithm rests upon the assumption that one is able to perform a querying operation of the form $$|i\rangle\mapsto(-1)^{f(x_i)}|i\rangle,$$ where $i$ is the index in the database, and $x_i$ whatever information the database attaches to $i$.

You can think of $f(x_i)$ as "asking a question about $x_i$". For example, "is $x_i$ a prime number?", or "does $x_i$ have property $P$?", where $P$ could mean "being red".

It is important to note that $f$ could be asking a question which does not fully characterize $x_i$. This means that after I run the algorithm and retrieve $i$, and thus $x_i$ with it, I also gain knowledge which was not used to build the oracle.

However, in many proof of principle implementations of Grover's algorithm, like the one you show, this is not the case. Indeed, in these demonstrations the question that is being asked is "trivial", in the sense that $x_i=i$, and the question is of the form "is $x_i$ equal to 3?".

In such a case, the algorithm is indeed not particularly useful in that the answer has to be hardcoded into the oracle, but this needs not be the case in general.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for your reply! Perhaps would it be possible to provide a real life example where the Grover's is "useful" applied on some real data given the presented oracle? E.g. how would it work with a 8 element database with primes and non primes? $\endgroup$
    – 01000001
    Commented Jun 18, 2018 at 8:12
  • 2
    $\begingroup$ @01000001 I believe this answer on a related question on cstheory.SE could qualify. It is a nice example of Grover being used for a nontrivial $f$. In his case, $f$ codifies whether a given boolean formula is satisfied by the input. The output of the algorithm is thus an $x$ satisfying a boolean formula $\endgroup$
    – glS ♦
    Commented Jun 18, 2018 at 13:34
  • $\begingroup$ One comment on this answer: ƒ could be an implementation that retrieves a value from a databse, but the entire retrieval function needs to be part of the same quantum wave equation. $\endgroup$
    – vy32
    Commented Apr 4, 2021 at 14:48
6
$\begingroup$

One main assumption to be efficient within a usage of a database is that you can load with a superposition of addresses data from a RAM, also called QRAM (see https://arxiv.org/abs/0708.1879). Then assume you have one state for the address, one state for the value, and a load operation, which loads the value of the corresponding address into the value register. So the load operation would do the step $$|x\rangle_{\text{address}}|0\rangle_{\text{value}} \rightarrow |x\rangle_{\text{address}}|\textrm{load}(x)\oplus 0\rangle_{\text{value}} = |x\rangle_{\text{address}}|\textrm{load}(x)\rangle_{\text{value}}.$$

In the first step you apply the Hadamard gates on the address register and then apply the load operation on both registers. Then you will have a superposition of all values in the database an the value register. $$H^{\otimes n}_{\text{address}} |0\rangle_{\text{address}}|\textrm0\rangle_{\text{value}}=\frac1{2^{n/2}}\sum_{x=0}^{2^n-1} |x\rangle_{\text{address}}|\textrm0\rangle_{\text{value}} $$ $$\text{apply load}\rightarrow \frac1{2^{n/2}}\sum_{x=0}^{2^n-1} |x\rangle_{\text{address}}|\textrm{load}(x)\rangle_{\text{value}}$$ Then you apply the Grover algorithm on the value register with any oracle you want like looking a for a prime or a specific value. We know after $O(\sqrt{N})$ iterations the correct answer will be measured with high probability. Thus, the correct solution together with the register address $x^*$ of the correct solution will be very probable measured $$|x^*\rangle_{\text{address}}|\textrm{load}(x^*)\rangle_{\text{value}}.$$

Maybe the main problem you have is with understanding the database not the Grover algorithm. You can see a more detailed explanation in chapter 6.5 Nielsen & Chuang for this.

I also think that the most useful application of the Grover algorithm is not the database application, but is its generalizations as amplitude amplification (see https://arxiv.org/abs/quant-ph/0005055) on any quantum algorithm.

EDIT: I thought of the problem glS answered already a bit: If we can built an oracle, isn't the problem already solved? Because to construct the oracle, we need to know how the correct solution looks like. And if you would have no background in computer science, this question would be hard to answer by yourself. However, under assumptions most scientists believe (NP$\neq$P), this is exactly the case for a subset of NP-complete problems (the ones which do not have good approximation methods) . We can construct an oracle, which can check if a solution is correct in polynomial time, but to construct an oracle, which finds the correct solution seems to be not efficiently computable.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don't think you need to invoke P$\neq$NP for this. For example, consider a case in which you have a high-dimensional qudit coupled with a qubit, so a state of the form $\sum_k |k\rangle\otimes|s_k\rangle$. This can encode something like "a phone book" (series of numbers), with a record (here binary) associated with each number. Your goal is to find the $k$ that is associated with $s_k=+1$. You can then apply Grover's algorithm, with the oracle acting only on the inner dof and leaving the index untouched. Building the oracle is easy: just build something that probes $s_k$. $\endgroup$
    – glS ♦
    Commented Jul 24, 2018 at 10:50
  • $\begingroup$ Yes this example is maybe easier to understand as first example. But I think to understand that the Grover algorithm is useful for an application on a wider class of important problems, the idea behind P$\neq$NP is important. $\endgroup$
    – Alex Go
    Commented Jul 26, 2018 at 14:46
1
$\begingroup$

I suggest you read this article, which discussed the quantum speedup for unsupervised learning like clustering. This paper gathered the progression of the quantum algorithms to accelerate unsupervised learning, and a lot of the algorithms depend on the Grover search.

Here comes an example.

Algo 1. find maximum distance

For n points, this algorithm searches the distances(up to n^2 different distances) and it can get the distance_maximum in O(n) expected time with high probability. For proof of this claim, see this article.

But there is one thing I myself is also quite confused about, which is how to construct the oracle to compute the distance(and the crucial point are how efficient it is and whether it is asymptotically optimal). I think the building of the oracle is the major problem of Grover search, not how to get more variant applications.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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