Quantum Advantage in Reversing Unknown Unitary Evolutions

We introduce the Quantum Unitary Reversal Algorithm (QURA), a deterministic and exact approach to universally reverse arbitrary unknown unitary transformations using $\mathcal{O}(d^2)$ calls of the unitary, where $d$ is the system dimension. Our construction resolves a fundamental problem of time-reversal simulations for closed quantum systems by affirming the feasibility of reversing any unitary evolution without knowing the exact process. The algorithm also provides the construction of a key oracle for unitary inversion in quantum algorithm frameworks such as quantum singular value transformation. Notably, our work demonstrates that compared with classical methods relying on process tomography, reversing an unknown unitary on a quantum computer holds a quadratic quantum advantage in computation complexity. QURA ensures an exact unitary inversion while the classical counterpart can never achieve exact inversion using a finite number of unitary calls.
Comment: 17 pages including appendix