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

$\endgroup$
  • $\begingroup$ Please refer to Chuang & Nielsen's book 'Quantum information and quantum computation', where you can find the answer. In fact we do not need to know 'which item' we are looking for, we only need to know 'how many items'. Then the algorithm can bring us the answer with a high enough probabiltiy. $\endgroup$ – XXDD Sep 28 '18 at 15:06

Your Answer

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

Browse other questions tagged or ask your own question.