A state-preparation procedure succeeds

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 state-preparation procedure AA succeeds, in the sense of amplitude amplification, with probability aa that is not known exactly, only that it lies somewhere in the range 0.01≤a≤0.040.01\le a\le0.04. The amplification operator QQ rotates the state through an angle θ\theta in the good/bad plane, with sin⁡(θ/2)=a\sin(\theta/2)=\sqrt a, so that after kk applications of QQ the success probability is Pk(a)=sin⁡2 ⁣((2k+1)θ2).P_k(a)=\sin^2\!\left(\frac{(2k+1)\theta}{2}\right). ((a)) Tabulate Pk(a)P_k(a) at the two ends of the range, a=0.01a=0.01 and a=0.04a=0.04, for k=0,1,…,7k=0,1,\ldots,7, and take the smaller of the two values in each row as that count's guaranteed (worst-case) success probability. Show that no single count kk reaches a worst-case probability of 0.90.9, and identify the count with the largest worst-case probability, together with its value. ((b)) A two-run strategy applies QQ for k1k_1 steps and checks the result with the oracle; if it is not good, the procedure is rerun from scratch with k2k_2 steps instead, so the overall success probability is Pk1,k2(a)=1−(1−Pk1(a))(1−Pk2(a)).P_{k_1,k_2}(a)=1-\bigl(1-P_{k_1}(a)\bigr)\bigl(1-P_{k_2}(a)\bigr). Working outward from the counts found in part (a), find integers k1≤k2≤9k_1\le k_2\le9 that make the worst case of Pk1,k2(a)P_{k_1,k_2}(a) over 0.01≤a≤0.040.01\le a\le0.04 as large as possible, and give that worst-case probability. ((c)) Explain in one sentence why the best pair found in part (b) has k1≠k2k_1\ne k_2.

Browse the problem library