the last register (the last qubit) in the residual state Where H denotes the Hadamard gate, we compute the state . Where are positive real numbers to be chosen later with , we compute the state and measure the second qubit, postselecting on its value being equal to 1, which leaves the first qubit in a residual state depending on which we denote . Visualizing the possible states of a qubit as a circle, we see that if , (i.e. if ) then lies in the open quadrant while if , (i.e. if ) then lies in the open quadrant . In fact for any fixed x (and its corresponding s), as we vary the ratio in , note that the image of is precisely the corresponding open quadrant. In the rest of the proof, we make precise the idea that we can distinguish between these two quadrants. Analysis Let , which is the center of , and let be orthogonal to . Any qubit in , when measured in the basis , gives the value less than 1/2 of the time. On the other hand, if and we had picked then measuring in the basis would give the value all of the time. Since we don't know s we also don't know the precise value of r*, but we can try several (polynomially many) different values for in hopes of getting one that is "near" r*. Specifically, note and let us successively set to every value of the form for . Then elementary calculations show that for one of these values of i, the probability that the measurement of in the basis yields is at least Overall, the algorithm is as follows. Let k be any constant strictly between 1/2 and . We do the following experiment for each : construct and measure in the basis a total of times where C is a constant. If the proportion of measurements is greater than k, then reject. If we don't reject for any i, accept. Chernoff bounds then show that for a sufficiently large universal constant C, we correctly classify x with probability at least 2/3. Note that this algorithm satisfies the technical assumption that the overall postselection probability is not too small: each individual measurement of has postselection probability and so the overall probability is . Implications See Quantum computation reformulation of PP References Articles containing proofs Quantum complexity