Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection

Abstract

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 solvable by polynomial-size quantum circuits with a polynomial number of rewinding operators, cloning operators, and adaptive postselections, respectively. Our main result is that ${\mathsf{BPP}}^{\mathsf{PP}}\subseteq \mathsf{RwBQP}=\mathsf{CBQP}=\mathsf{AdPostBQP}\subseteq \mathsf{PSPACE}$. As a byproduct of this result, we show that any problem in $\mathsf{PostBQP}$ can be solved with only postselections of events that occur with probabilities polynomially close to one. Under the strongly believed assumption that $\mathsf{BQP}⊉\mathsf{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 $\mathsf{PP}$.

32 pages, 4 figures, v2: Added Result 3 and improved Result 4, v3: Revised Theorem 34, reflected TQC review comments, and added minor revisions, v4: close to published version in Theor. Comp. Sys

References in corpus (22)

• Characterizing Quantum Supremacy in Near-Term Devices
• Quantum Computational Supremacy
• Gaussian Boson Sampling
• Universal blind quantum computation
• Boson Sampling from Gaussian States
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
• Closed timelike curves via post-selection: theory and experimental demonstration
• On the hardness of classically simulating the one clean qubit model
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• Anticoncentration theorems for schemes showing a quantum speedup
• Quantum state cloning using Deutschian closed timelike curves
• QFactory: classically-instructed remote secret qubits preparation
• Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
• On the possibility of classical client blind quantum computing
• Non-Unitary Quantum Computation in the Ground Space of Local Hamiltonians
• Closed Timelike Curves Make Quantum and Classical Computing Equivalent
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
• Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy