describe. What will be used later is that the new values satisfy if x is in L, and if x is not in L. Using the earlier technical assumption and by analyzing how the 1-norm of the computational state changes, this is seen to be satisfied if thus clearly there is a large enough f that is polynomial in n. Constructing the PP machine Now we provide the detailed implementation of our machine. Let denote the sequence and define the shorthand notation , then We define our machine to pick a basis state uniformly at random if then STOP and accept with probability 1/2, reject with probability 1/2 pick two sequences of G basis states uniformly at random compute (which is a fraction with denominator such that ) if then accept with probability and reject with probability (which takes at most coin flips) otherwise (then ) accept with probability and reject with probability (which again takes at most coin flips) Then it is straightforward to compute that this machine accepts with probability so this is a machine for the language L, as needed. Proving ⊆ Suppose we have a machine with time complexity on input x of length . Thus the machine flips a coin at most T times during the computation. We can thus view the machine as a deterministic function f (implemented, e.g. by a classical circuit) which takes two inputs (x, r) where r, a binary string of length T, represents the results of the random coin flips that are performed by the computation, and the output of f is 1 (accept) or 0 (reject). The definition of tells us that Thus, we want a algorithm that can determine whether the above statement is true. Define s to be the number of random strings which lead to acceptance, and so is the number of rejected strings. It is straightforward to argue that without loss of generality, ; for details, see a similar without loss of generality assumption in the proof that is closed under complementation. Aaronson's algorithm Aaronson's algorithm for solving this problem is as follows. For simplicity, we will write all quantum states as unnormalized. First, we prepare the state . Second, we apply Hadamard gates to the second register (each of the first T qubits), measure the second register and postselect on it being the all-zero string. It is easy to verify that this leaves