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.

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

References in corpus (48)

• Quantum Cryptography
• Elementary gates for quantum computation
• Quantum algorithm for solving linear systems of equations
• Strengths and Weaknesses of Quantum Computing
• Quantum Copying: Beyond the No-Cloning Theorem
• Fermionic quantum computation
• Prescription for experimental determination of the dynamics of a quantum black box
• Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
• Optimal Quantum Cloning Machines
• Complete Characterization of a Quantum Process: the Two-Bit Quantum Gate
• Quantum correlations with no causal order
• Quantum Darwinism
• Optimal Cloning of Pure States
• Quantum computations without definite causal structure
• Simulation of Electronic Structure Hamiltonians Using Quantum Computers
• Probabilistic cloning and identification of linearly independent quantum states
• Probabilistic theories with purification
• Programmable quantum gate arrays
• Quantum Metropolis Sampling
• Interacting Quantum Observables: Categorical Algebra and Diagrammatics
• Experimental Superposition of Orders of Quantum Gates
• Computational advantage from quantum-controlled ordering of gates
• Optimal universal quantum cloning and state estimation
• Experimental Verification of an Indefinite Causal Order
• Indefinite Causal Order in a Quantum Switch
• Optimal Cloning of Pure States, Judging Single Clones
• Quantum copying: A network
• Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms
• Quantum circuits cannot control unknown operations
• Quantum teleportation scheme by selecting one of multiple output ports
• Storing quantum dynamics in quantum states: stochastic programmable gate for U(1) operations
• Reversing Unknown Quantum Transformations: Universal Quantum Circuit for Inverting General Unitary Operations
• Quantum SDP-Solvers: Better upper and lower bounds
• Quantum Kolmogorov Complexity Based on Classical Descriptions
• Time-delocalized quantum subsystems and operations: on the existence of processes with indefinite causal structure in quantum mechanics
• Strategies and Networks for State-Dependent Quantum Cloning
• Quantum Computing with black-box Subroutines
• The space of logically consistent classical processes without causal order
• Optimal probabilistic storage and retrieval of unitary channels
• Quantum Tasks in Minkowski Space
• Probabilistic exact universal quantum circuits for transforming unitary operations
• Causal orders, quantum circuits and spacetime: distinguishing between definite and superposed causal orders
• Projected Least-Squares Quantum Process Tomography
• Optimal universal programming of unitary gates
• Approximate programmable quantum processors
• Complex conjugation supermap of unitary quantum maps and its universal implementation protocol
• 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