Grover Search :

Init

SetOptions[Graphics,Background->None];
SetOptions[BarChart,BaseStyle->{FontSize->14},Background->None,ChartStyle->Orange,Frame->True,FrameTicks->{None,Automatic},ChartLabels->{Placed[Table[i,{i,1,20}],Axis]},ImagePadding->{{50,10},{30,10}}];

Classical  search algorithm :

Let' s try to find the green square from a set of colored squares.

colors={Yellow,Green,Blue,Red,Gray,Brown,Pink,Magenta,Purple,Cyan};
hidden=Table[Black,{i,1,10}];
squares=
Graphics[{Dynamic[current[[1]]],Rectangle[{0,0}],Dynamic[current[[2]]],Rectangle[{1.1,0}],Dynamic[current[[3]]],Rectangle[{2.2,0}],Dynamic[current[[4]]],Rectangle[{3.3,0}],Dynamic[current[[5]]],Rectangle[{4.4,0}],
Dynamic[current[[6]]],Rectangle[{0,1.1}],Dynamic[current[[7]]],Rectangle[{1.1,1.1}],Dynamic[current[[8]]],Rectangle[{2.2,1.1}],Dynamic[current[[9]]],Rectangle[{3.3,1.1}],Dynamic[current[[10]]],Rectangle[{4.4,1.1}],
White,Sequence@@Table[Text[Style[Round[i]+1,FontSize->28],{i+0.5,0.5}],{i,0,4.4,1.1}],Sequence@@Table[Text[Style[Round[i]+6,FontSize->28],{i+0.5,1.6}],{i,0,4.4,1.1}]
},ImageSize->900,Background->None];
DetermineSquare[{x_,y_}]:=(Piecewise[{{1, (0<x<=1)&&(0<y<=1)}, {2, (1.1<x<=2.2)&&(0<y<=1)}, {3, (2.2<x<=3.3)&&(0<y<=1)}, {4, (3.3<x<=4.4)&&(0<y<=1)}, {5, (4.4<x<=5.5)&&(0<y<=1)}, {6, (0<x<=1)&&(1.1<y<2.1)}, {7, (1.1<x<=2.2)&&(1.1<y<2.1)}, {8, (2.2<x<=3.3)&&(1.1<y<2.1)}, {9, (3.3<x<=4.4)&&(1.1<y<2.1)}, {10, (4.4<x<=5.5)&&(1.1<y<2.1)}}])

Graphics[{#,Rectangle[]},ImageSize->100]&/@colors

current=hidden;
(* Create a random distribution *)
open=RandomSample[colors,Length[colors]];
EventHandler[squares,{"MouseClicked":> (current=Evaluate[Join[Table[current[[i]],{i,1,DetermineSquare[MousePosition["Graphics"]]-1}],{open[[DetermineSquare[MousePosition["Graphics"]]]]},Table[current[[i]],{i,DetermineSquare[MousePosition["Graphics"]]+1,Length[current]}]]])}]

result={8,7,8,1,1,1,4,7,6}
Mean[result]//N

On average 5 draws are needed!

Quantum Grover Search

Each color is encoded as a state vector. The Grover algorithm picks the right state from a superposition of all states.

=(({{1}, {0}, {0}, {0}, {0}, {0}})),=(({{0}, {1}, {0}, {0}, {0}, {0}})),  =(({{0}, {0}, {1}, {0}, {0}, {0}})),=(({{0}, {0}, {0}, {1}, {0}, {0}})),= (({{0}, {0}, {0}, {0}, {1}, {0}})) , = (({{0}, {0}, {0}, {0}, {0}, {1}})),...

Prepare superposition state :

ψ=((({{1}, {0}, {0}, {0}, {0}, {0}, {0}, {0}, {0}, {0}}))+(({{0}, {1}, {0}, {0}, {0}, {0}, {0}, {0}, {0}, {0}}))+(({{0}, {0}, {1}, {0}, {0}, {0}, {0}, {0}, {0}, {0}}))+(({{0}, {0}, {0}, {1}, {0}, {0}, {0}, {0}, {0}, {0}}))+(({{0}, {0}, {0}, {0}, {1}, {0}, {0}, {0}, {0}, {0}}))+(({{0}, {0}, {0}, {0}, {0}, {1}, {0}, {0}, {0}, {0}}))+(({{0}, {0}, {0}, {0}, {0}, {0}, {1}, {0}, {0}, {0}}))+(({{0}, {0}, {0}, {0}, {0}, {0}, {0}, {1}, {0}, {0}}))+(({{0}, {0}, {0}, {0}, {0}, {0}, {0}, {0}, {1}, {0}}))+(({{0}, {0}, {0}, {0}, {0}, {0}, {0}, {0}, {0}, {1}})))/(Sqrt[10])

Implement Operators

The ' oracle' operator picks the correct by changing its sign :
  Oω | ω> = -|ω>
  Oω |x> = |x> for x≠ω
  
 Corresponds to the boolean search function which has value 1 if state is correct (f(ω)=1) and value 0 if the wrong state has been picked (f(x)=0).

Oracle for green:

ψgreen=(({{0}, {1}, {0}, {0}, {0}, {0}, {0}, {0}, {0}, {0}}));
ψother=(({{0}, {0}, {0}, {1}, {0}, {0}, {0}, {0}, {0}, {0}}))
Ogreen=IdentityMatrix[10]-2KroneckerProduct[ψgreen,ψgreen\[Transpose]];
Os=2KroneckerProduct[ψ,ψ\[Transpose]]-IdentityMatrix[10]; (* Grover Dispersion operator *)

Check whether the oracle works:

Ogreen.ψother//MatrixForm

Print["green:",Ogreen.ψgreen//MatrixForm,"; other: ",Ogreen.ψother//MatrixForm]
Ogreen.ψgreen==ψgreen
Ogreen.ψother==ψother

Search the database

Probability amplitudes - Initial state ψ=((Subscript[Σ, i])^N)(Subscript[c, i])|i> with (Subscript[c, i])=1/(Sqrt[N])= 0.316

BarChart[Flatten[((Abs[ψ])^2)],PlotRange->{0,1},FrameLabel->{"i","|(Subscript[c, i])((|)^2)"}]

1. iteration

ψ1oracle=(Ogreen.ψ)//N;
BarChart[Flatten[ψ1oracle],PlotRange->{-1,1},BaseStyle->{FontSize->14},FrameLabel->{"i","(Subscript[c, i])"}]

ψ1=(Os.Ogreen.ψ)//N;

BarChart[Flatten[ψ1],PlotRange->{-1,1},BaseStyle->{FontSize->14},FrameLabel->{"i","(Subscript[c, i])"}]

after 2nd iteration we are done

ψ2=(Os.Ogreen.ψ1)//N

BarChart[Flatten[ψ2],PlotRange->{-1,1},BaseStyle->{FontSize->14},FrameLabel->{"i","(Subscript[c, i])"}]

Implementation for higher dimensions

Higher Dimensions (N=100) :

dim=100;
ψh={Table[1.,{i,1,dim}]}\[Transpose]/(Sqrt[dim]);
(* we search for ψelem=(({{0}, {0}, {.}, {.}, {.}, {i}, {0}, {.}, {.}, {0}})) with i = 12 *)
ψelem={ReplacePart[Table[0,{i,1,dim}]/(Sqrt[dim]),12->1]}\[Transpose];
Oelem=IdentityMatrix[dim]-2KroneckerProduct[ψelem,ψelem\[Transpose]];
Osh=2KroneckerProduct[ψh,ψh\[Transpose]]-IdentityMatrix[dim];

State is picked in about 7 steps((π/4)(Sqrt[N]))

(*Probability to find system in state ψelem *)
((Abs[(ψelem\[Transpose].#)[[1]]])^2)&/@ NestList[Osh.Oelem.#&,ψh,7]//N
BarChart[Flatten@%,ChartLabels->ToString/@Range[1,9],FrameLabel->{"iteration","|(Subscript[c, i])((|)^2)"}]

Speedup

Plot[{x/2,(Sqrt[x])},{x,1,200},BaseStyle->{FontSize->12,FontFamily->"Arial"},FrameLabel->{"N","# of function calls"},Frame->True,PlotStyle->{Thick}]

Plot[{x/2,(Sqrt[x])},{x,1,10},BaseStyle->{FontSize->12,FontFamily->"Arial"},FrameLabel->{"N","# of function calls"},Frame->True,PlotStyle->{Thick}]