Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection

Ryo Hiromasa, Akihiro Mizutani, Yuki Takeuchi +1

We define rewinding operators that invert quantum measurements. Then, we define complexity classes $\mathsf{RwBQP}$, $\mathsf{CBQP}$, and $\mathsf{AdPostBQP}$ as sets of decision problems s…