Topologically driven no-superposing theorem with a tight error bound

Abstract

To better understand quantum computation we can search for its limits or no-gos, especially if analogous limits do not appear in classical computation. Classical computation easily implements and extensively employs the addition of two bit strings, so here we study 'quantum addition': the superposition of two quantum states. We prove the impossibility of superposing two unknown states, no matter how many samples of each state are available. The proof uses topology; a quantum algorithm of any sample complexity corresponds to a continuous function, but the function required by the superposition task cannot be continuous by topological arguments. Our result for the first time quantifies the approximation error and the sample complexity $N$ of the superposition task, and it is tight. We present a trivial algorithm with a large approximation error and $N=1$, and the matching impossibility of any smaller approximation error for any $N$. Consequently, our results limit state tomography as a useful subroutine for the superposition. State tomography is useful only in a model that tolerates randomness in the superposed state. The optimal protocol in this random model remains open.

arXiv comment12 pages, 4 figures, + 6 pages appendices. Quantum journal version

References in corpus (21)

• Quantum cryptography: Public key distribution and coin tossing
• Noncommuting mixed states cannot be broadcast
• Quantum cloning
• Quantum Darwinism
• Probabilistic theories with purification
• Programmable quantum gate arrays
• Interacting Quantum Observables: Categorical Algebra and Diagrammatics
• Reliable Quantum State Tomography
• Linear growth of quantum circuit complexity
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Quantum Kolmogorov Complexity Based on Classical Descriptions
• Creation of superposition of unknown quantum states
• Quantum Tasks in Minkowski Space
• Precision-guaranteed quantum tomography
• Approximate Quantum Adders with Genetic Algorithms: An IBM Quantum Experience
• The Forbidden Quantum Adder
• Experimental creation of superposition of unknown photonic quantum states
• Experimentally superposing two pure states with partial prior knowledge
• State complexity and quantum computation
• Universal superposition of arbitrary orthogonal states
• Topological obstructions to quantum computation with unitary oracles