|
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: * BQP is the same as PostBQP except without postselection * BPPpath is the same as PostBPP except that instead of quantum, the algorithm is a classical randomized algorithm (with postselection) The addition of postselection seems to make quantum Turing machines much more powerful: Scott Aaronson proved〔. Preprint available at ()〕 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: * if we broadened the definition of 'quantum gate' to include not just unitary operations but linear operations, or * if the probability of measuring a basis state was proportional to instead of for any even integer ''p > 2''. ==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 |1>. 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'', * ''P'' = 1 with nonzero probability * if the input ''x'' is in ''L'' then Pr() ≥ 2/3 * if the input ''x'' is not in ''L'' then Pr() ≥ 2/3. 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): 1. PostBQP is ''closed under complement''. Given a language ''L'' in PostBQP and a corresponding deciding circuit family, create a new circuit family by flipping the output qubit after measurement, then the new circuit family proves the complement of ''L'' is in PostBQP. 2. You can do ''probability amplification'' in PostBQP. The definition of PostBQP is not changed if we replace the 2/3 value in its definition by any other constant strictly between 1/2 and 1. As an example, given a PostBQP algorithm ''A'' with success probability 2/3, we can construct another algorithm which runs three independent copies of ''A'', outputs a postselection bit equal to the conjunction of the three "inner" ones, and outputs an output bit equal to the majority of the three "inner" ones; the new algorithm will be correct with conditional probability , greater than the original 2/3. 3. PostBQP is ''closed under intersection''. Suppose we have PostBQP circuit families for two languages ''L1'' and ''L2'', with respective postselection qubits and output qubits ''P1, P2, Q1, Q2''. We may assume by probability amplification that both circuit families have success probability at least 5/6. Then we create a composite algorithm where the circuits for ''L1'' and ''L2'' are run independently, and we set ''P'' to the conjunction of ''P1'' and ''P2'', and ''Q'' to the conjunction of ''Q1'' and ''Q2''. It is not hard to see by a union bound that this composite algorithm correctly decides membership in with (conditional) probability at least 2/3. More generally, combinations of these ideas show that PostBQP is closed under union and BQP truth-table reductions. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「PostBQP」の詳細全文を読む スポンサード リンク
|