论文标题
可重新确定的量子计算及其与克隆和自适应后选择的等效性
Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
论文作者
论文摘要
我们定义了倒量子测量的倒带操作员。 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.我们的主要结果是$ {\ sf bpp}^{\ sf pp} \ subSeteq {\ sf rwbqp} = {\ sf cbqp} = {\ sf cbqp} = {\ sf adpostBqp} \ subSeteq {\ subSeteq {\ sf pspace} $。作为此结果的副产品，我们表明$ {\ sf postbqp} $中的任何问题都可以通过仅在多个概率接近一个事件的事件的情况下解决。在强烈认为的假设下，$ {\ sf bqp} \ nsupseteq {\ sf szk} $或最短的独立矢量问题无法有效地解决量子计算机，我们还表明，单个重新连接的操作员足以实现可在量子计算中可行的任务。最后，我们表明可恢复的Clifford电路在经典上仍然可以模拟，但是可重新定位的瞬时量子量子多项式时间电路可以解决$ {\ sf pp} $中的任何问题。
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 events that occur with probabilities 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. Finally, we show that rewindable Clifford circuits remain classically simulatable, but rewindable instantaneous quantum polynomial time circuits can solve any problem in ${\sf PP}$.
