|
In computational complexity theory, BQP (bounded error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue of the complexity class BPP. In other words, there is an algorithm for a quantum computer (a quantum algorithm) that solves the decision problem with ''high'' probability and is guaranteed to run in polynomial time. On any given run of the algorithm, it has a probability of at most 1/3 that it will give the wrong answer. Similarly to other "bounded error" probabilistic classes the choice of 1/3 in the definition is arbitrary. We can run the algorithm a constant number of times and take a majority vote to achieve any desired probability of correctness less than 1, using the Chernoff bound. Detailed analysis shows that the complexity class is unchanged by allowing error as high as 1/2 − ''n''−''c'' on the one hand, or requiring error as small as 2−''nc'' on the other hand, where ''c'' is any positive constant, and ''n'' is the length of input. ==Definition== BQP can also be viewed as a bounded-error uniform family of quantum circuits. A language ''L'' is in BQP if and only if there exists a polynomial-time uniform family of quantum circuits , such that * For all , ''Qn'' takes ''n'' qubits as input and outputs 1 bit * For all ''x'' in ''L'', * For all ''x'' not in ''L'', 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「BQP」の詳細全文を読む スポンサード リンク
|