Grover's iteration acts as a rotation in the two-dimensional real span of

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

Grover's iteration acts as a rotation in the two-dimensional real span of ∣α⟩|\alpha\rangle, the normalised uniform superposition of the N−MN-M unmarked computational basis states, and ∣β⟩|\beta\rangle, the normalised uniform superposition of the MM marked ones. Consider unstructured search with NN items, MM of them marked, and a phase oracle OfO_f that multiplies each marked basis state by −1-1 and leaves the rest alone. ((a)) Starting from the uniform state ∣s⟩=N−MN∣α⟩+MN∣β⟩|s\rangle=\sqrt{\frac{N-M}{N}}|\alpha\rangle+\sqrt{\frac{M}{N}}|\beta\rangle, show that OfO_f is a reflection about ∣α⟩|\alpha\rangle in this plane, that the diffusion operator D=2∣s⟩⟨s∣−ID=2|s\rangle\langle s|-I is a reflection about ∣s⟩|s\rangle, and that the Grover iteration G=DOfG=DO_f is a rotation through an angle θ\theta with sin⁡(θ/2)=M/N\sin(\theta/2)=\sqrt{M/N}. Give Gk∣s⟩G^k|s\rangle in terms of ∣α⟩|\alpha\rangle, ∣β⟩|\beta\rangle and θ\theta. ((b)) A register of n=5n=5 qubits (N=32N=32 memory addresses) is searched with a phase oracle that marks M=3M=3 faulty addresses. Find θ\theta in degrees and, using R=round(π2θ−12)R=\mathrm{round}\left(\frac{\pi}{2\theta}-\frac12\right), the optimal number of Grover iterations RR and the resulting success probability. ((c)) The diffusion operator's core is 2∣0⟩⟨0∣−I2|0\rangle\langle0|-I on the nn qubits, built up to a global sign from X⊗nX^{\otimes n} conjugating Cn−1(Z)C^{n-1}(Z) (a ZZ on the last qubit controlled by the other n−1n-1), which for nn qubits costs n−2n-2 ancillas, 2(n−2)2(n-2) Toffoli gates and one controlled-ZZ gate. State this cost for the n=5n=5 register of part (b).

Browse the problem library