A register of qubits ( ) is searched with Grover's algorithm for marked items

PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms

Quantum Information and Technology, Ch Grover search, amplitude amplification and counting

Problem

A register of n=10n=10 qubits (N=210=1024N=2^{10}=1024) is searched with Grover's algorithm for M=3M=3 marked items, using a phase oracle and a diffusion step implemented as array operations on the NN-component real amplitude vector (sign flip on the marked entries, then inversion about the mean). ((a)) Compute the rotation angle θ\theta, in degrees, from sin⁡(θ/2)=M/N\sin(\theta/2)=\sqrt{M/N}. ((b)) Using R=round(π2θ−12)R=\mathrm{round}\left(\frac{\pi}{2\theta}-\frac12\right), find the optimal number of Grover iterations RR. ((c)) Compute the success probability Pk=sin⁡2 ⁣((2k+1)θ2)P_k=\sin^2\!\left(\frac{(2k+1)\theta}{2}\right) for k=R−2, R−1, R, R+1, R+2k=R-2,\,R-1,\,R,\,R+1,\,R+2, and confirm that it peaks at k=Rk=R and falls symmetrically on either side, as an array simulation that records PkP_k at every kk would show. ((d)) Predict, without further calculation of intermediate steps, the success probability the same array simulation would show at k=2Rk=2R, and explain in one sentence why running the simulation for longer than RR iterations 'to be safe' is a mistake.

Browse the problem library