BQP
Computational complexity class of problems / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about BQP?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
This article is about the computational complexity class. For other uses, see BQP (disambiguation).
In computational complexity theory, bounded-error quantum polynomial time (BQP) 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.[1] It is the quantum analogue to the complexity class BPP.
A decision problem is a member of BQP if there exists a quantum algorithm (an algorithm that runs on a quantum computer) that solves the decision problem with high probability and is guaranteed to run in polynomial time. A run of the algorithm will correctly solve the decision problem with a probability of at least 2/3.
More information AnswerproducedCorrectanswer, Yes ...
BQP algorithm (1 run) | ||
---|---|---|
Answer produced Correct answer |
Yes | No |
Yes | ≥ 2/3 | ≤ 1/3 |
No | ≤ 1/3 | ≥ 2/3 |
BQP algorithm (k runs) | ||
Answer producedCorrect answer |
Yes | No |
Yes | > 1 − 2−ck | < 2−ck |
No | < 2−ck | > 1 − 2−ck |
for some constant c > 0 |
Close