  We define rewinding operators that invert quantum measurements. Then, we
define complexity classes ${\sf RwBQP}$, ${\sf CBQP}$, and ${\sf AdPostBQP}$ as
sets of decision problems solvable by polynomial-size quantum circuits with a
polynomial number of rewinding operators, cloning operators, and adaptive
postselections, respectively. Our main result is that ${\sf BPP}^{\sf
PP}\subseteq{\sf RwBQP}={\sf CBQP}={\sf AdPostBQP}\subseteq{\sf PSPACE}$. As a
byproduct of this result, we show that any problem in ${\sf PostBQP}$ can be
solved with only postselections of outputs whose probabilities are polynomially
close to one. Under the strongly believed assumption that ${\sf
BQP}\nsupseteq{\sf SZK}$, or the shortest independent vectors problem cannot be
efficiently solved with quantum computers, we also show that a single rewinding
operator is sufficient to achieve tasks that are intractable for quantum
computation. In addition, we consider rewindable Clifford and instantaneous
quantum polynomial time circuits.
