Topological obstructions to quantum computation with unitary oracles

Abstract

Algorithms with unitary oracles can be nested, which makes them extremely versatile. An example is the phase estimation algorithm used in many candidate algorithms for quantum speed-up. The search for new quantum algorithms benefits from understanding their limitations: Some tasks are impossible in quantum circuits, although their classical versions are easy, for example, cloning. An example with a unitary oracle $U$ is the if clause, the task to implement controlled $U$ (up to the phase on $U$). In classical computation the conditional statement is easy and essential. In quantum circuits the if clause was shown impossible from one query to $U$. Is it possible from polynomially many queries? Here we unify algorithms with a unitary oracle and develop a topological method to prove their limitations: No number of queries to $U$ and $U^{†}$ lets quantum circuits implement the if clause, even if admitting approximations, postselection and relaxed causality. We also show limitations of process tomography, oracle neutralization, and $\sqrt[\dim U]{U}$, $U^T$, and $U^{†}$ algorithms. Our results strengthen an advantage of linear optics, challenge the experiments on relaxed causality, and motivate new algorithms with many-outcome measurements.

14 pages, 8 figures, 2 tables + Appendix: 12 pages, 1 figure. Rewritten version, some results about unitary oracle tasks strengthened to approximations

References in corpus (9)

• Quantum algorithm for solving linear systems of equations
• Quantum Darwinism
• Experimental Verification of an Indefinite Causal Order
• Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms
• Quantum teleportation scheme by selecting one of multiple output ports
• Projected Least-Squares Quantum Process Tomography
• Optimal universal programming of unitary gates
• Approximating Fractional Time Quantum Evolution
• Holomorphic representation of quantum computations

Cited by in corpus (3)

• Learning the structure of any Hamiltonian from minimal assumptions
• Analytical Lower Bound on Query Complexity for Transformations of Unknown Unitary Operations
• Topologically driven no-superposing theorem with a tight error bound