PostBQP
In computational complexity theory, PostBQP is a complexity class consisting of all of the computational problems solvable in polynomial time on a quantum Turing machine with postselection and bounded error (in the sense that the algorithm is correct at least 2/3 of the time on all inputs). Postselection is not considered to be a feature that a realistic computer (even a quantum one) would possess, but nevertheless postselecting machines are interesting from a theoretical perspective. Removing either one of the two main features (quantumness, postselection) from PostBQP gives the following two complexity classes, both of which are subsets of  PostBQP: The addition of postselection seems to make quantum Turing machines much more powerful: Scott Aaronson proved PostBQP is equal to PP, a class which is believed to be relatively powerful, whereas BQP is not known even to contain the seemingly smaller class NP. Using similar techniques, Aaronson also proved that small changes to the laws of quantum computing would have significant effects. As specific examples, under either of the two following changes, the "new" version of BQP would equal PP: Basic properties. In order to describe some of the properties of PostBQP we fix a formal way of describing  quantum postselection. Define a quantum algorithm to be a family of quantum circuits (specifically, a uniform circuit family). We designate one qubit as the "postselection qubit P" and another as the "output qubit Q". Then PostBQP is defined by postselecting upon the event that the postselection qubit is formula_4. Explicitly, a language "L" is in PostBQP if there is a quantum algorithm "A" so that after running "A" on input "x" and measuring the two qubits "P" and "Q", One can show that allowing a single postselection step at the end of the algorithm (as described above) or allowing intermediate  postselection steps during the algorithm are equivalent. Here are three basic properties of PostBQP (which also hold for BQP via similar proofs): More generally, combinations of these ideas show that PostBQP is closed under union and BQP truth-table reductions. Scott Aaronson showed that the complexity classes (postselected bounded error quantum polynomial time) and PP (probabilistic polynomial time) are equal. The result was significant because this quantum computation reformulation of gave new insight and simpler proofs of properties of . The usual definition of a circuit family is one with two outbit qubits "P" (postselection) and "Q" (output) with a single  measurement of "P" and "Q" at the end such that the probability of measuring has nonzero probability, the conditional probability Pr["Q" = 1|"P" = 1] ≥ 2/3 if the input "x" is in the language, and Pr["Q" = 0|"P" = 1] ≥ 2/3 if the input "x" is not in the language. For technical reasons we tweak the definition of as follows: we require that for some constant "c" depending on the circuit family. Note this choice does not affect the basic properties of, and also it can be shown that any computation consisting of typical gates (e.g. Hadamard, Toffoli ) has this property whenever . Proving ⊆. Suppose we are given a family of circuits to decide a language "L". We assume without loss of generality (e.g. see the inessential properties of quantum computers) that all gates have transition matrices that are represented with real numbers, at the expense of adding one more qubit. Let denote the final quantum state of the circuit before the postselecting measurement is made. The overall goal of the proof is to construct a algorithm to decide "L". More specifically it suffices to have "L" correctly compare the squared amplitude of in the states with to  the squared amplitude of in the states with to determine which is bigger. The key insight is that the comparison of these amplitudes can be transformed into comparing the acceptance probability of a machine with 1/2. Matrix view of PostBQP algorithms. Let "n" denote the input size, denote the total number of qubits in the circuit (inputs, ancillary, output and postselection qubits), and denote the total number of gates. Represent the "i"th gate by its transition matrix "A" (a real unitary formula_7 matrix) and let the initial state be formula_1 (padded with zeroes). Then formula_9. Define "S" (resp. "S") to  be the set of basis states corresponding to (resp. ) and define the probabilities The definition of ensures that either formula_12 or formula_13 according to whether "x" is in "L" or not. Our machine will compare formula_14 and formula_15. In order to do this, we expand the definition of matrix multiplication: where the sum is taken over all lists of "G" basis vectors formula_17. Now formula_18 and formula_19 can be expressed as a sum of pairwise products of these terms. Intuitively, we want to design a machine whose acceptance probability is something like formula_20, since then formula_21 would imply that the  acceptance probability is formula_22, while formula_23 would imply that the acceptance probability is formula_24. Technicality: we may assume entries of the transition matrices are rationals with denominator for some polynomial "f"("n").. The definition of tells us that formula_25 if "x" is in "L", and that otherwise formula_26. Let us replace all entries of "A" by the nearest fraction with denominator formula_27 for a large polynomial that we presently describe. What will be used later is that the "new" values satisfy formula_28 if "x" is in "L", and formula_29 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 formula_30 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 formula_31 and define the shorthand notation then We define our machine to Then it is straightforward to compute that this machine accepts with probability formula_45 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  formula_46. 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 formula_49 is the number of rejected strings. It is straightforward to argue that without loss of generality, formula_50; 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 formula_51. 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 the last register (the last qubit) in the residual state Where "H" denotes the Hadamard gate, we compute the state Where formula_54 are positive real numbers to be chosen later with formula_55, we compute the state formula_56 and measure the second qubit, postselecting on its value being equal to 1, which leaves the first qubit in a residual state depending on formula_57 which we denote Visualizing the possible states of a qubit as a circle, we see that if formula_59, (i.e. if formula_21) then formula_61 lies in the open quadrant formula_62 while if formula_63 , (i.e. if formula_23) then formula_61 lies in the open quadrant formula_66. In fact for any fixed "x" (and its corresponding "s"), as we vary the ratio formula_57 in formula_68, note that the image of formula_69 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 formula_70, which is the center of formula_71, and let formula_72 be orthogonal to formula_73. Any qubit in formula_74, when measured in the basis formula_75, gives the value formula_73 less than 1/2 of the time. On the other hand , if formula_23 and we had picked formula_78 then measuring formula_79 in the basis formula_75 would give the value formula_73 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 formula_57 in hopes of getting one that is "near" "r*". Specifically, note formula_83 and let us successively set formula_57 to every value of the form formula_85 for formula_86. Then elementary calculations show that for one of these values of "i", the probability that the measurement of formula_87 in the basis formula_75  yields formula_73 is at least formula_90 Overall, the algorithm is as follows. Let "k" be any constant strictly between 1/2 and formula_91. We do the following experiment for each formula_86: construct and measure formula_87 in the basis formula_75 a total of formula_95 times where "C" is a constant. If the proportion of formula_73 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 formula_87 has postselection probability formula_98 and so the overall probability is formula_99.