BQP

BQP is the class of decision problems solvable by a uniform family of quantum circuits in polynomial time, with error probability bounded below one third on every input.

Quantum circuit: A computational model in which gates transform qubits and measurements produce classical outcomes. BQP formalizes the polynomial-time computations performed by uniform quantum circuits.
Quantum measurement: An interaction that produces a classical outcome from a quantum state according to probability rules. A BQP computation returns its decision by measuring a final quantum state.
P (complexity): The class of decision problems solvable by a deterministic algorithm in polynomial time. Whether BQP contains problems outside P remains unresolved.
Shor's algorithm: A quantum algorithm that factors integers and computes discrete logarithms in polynomial time. Its factoring procedure places integer factorization in BQP.
P versus BQP: The open question of whether quantum polynomial time solves problems outside deterministic polynomial time. No unconditional separation between P and BQP is known.
Qubit: A quantum information unit whose state can be a superposition of two basis states. Quantum circuits encode their computational states in qubits.
Quantum parallelism: The ability of a quantum state to encode amplitudes associated with many computational possibilities. BQP algorithms exploit superposition, though it does not directly reveal all encoded answers.
BPP: The class of decision problems solvable in randomized polynomial time with bounded error. BPP supplies classical randomness where BQP permits quantum computation.
Grover's algorithm: A quantum search algorithm that finds a marked item among N possibilities using O(√N) queries. It demonstrates a quadratic query advantage within BQP, not a known exponential one.
BQP versus NP: The unresolved relationship between bounded-error quantum computation and polynomially verifiable certificates. Known containments do not establish whether BQP contains NP or is contained in it.

Linked from 1 page

Polynomial timeCompared with: It tests whether quantum computation can solve problems beyond classical polynomial time.