| （英） |
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. |