Class Description

BQL: Bounded-Error Quantum Logspace

The class of decision problems solvable by a quantum Turing machine using O(log n) many qubits and polynomial time, with at most 1/3 probability of error.

Whether or not intermediate measurements are allowed does not change the resulting class [FR21].

Contained in DET [FR21].

Linked From

No class.