Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2004/iii/paper-53/4/1/solution

For independent attempts, measuring after each application of produces a success with probability . Recognize the answer with the verifier and restart on failure. The number of attempts has a geometric distribution, with . Summing the tail probabilities gives
This counts applications of ; it presumes and a fresh preparation for each attempt. If , neither repetition nor the amplification construction can create a good component from this input.

New to topics? Read the docs here!