BQP

In computational complexity theory BQP stands for Bounded error, Quantum, Polynomial time. It denotes 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. In other words, there is an algorithm for a quantum computer 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 p... more

In computational complexity theory BQP stands for Bounded error, Quantum, Polynomial time. It denotes 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. In other words, there is an algorithm for a quantum computer 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. This number of repeats increases if becomes closer to 1/2, but it does not depend on the input size. Detailed analysis can show more strongly that p can depend on the input size n anywhere in the range without... less