  We introduce a first-order quantum programming language, named FOQ, whose
terminating programs are reversible. We restrict FOQ to a strict and tractable
subset, named PFOQ, of terminating programs with bounded width, that provides a
first programming language-based characterization of the quantum complexity
class FBQP. Finally, we present a tractable semantics-preserving algorithm
compiling a PFOQ program to a quantum circuit of size polynomial in the number
of input qubits.
