Resource Quantification for the No-Programming Theorem

Abstract

The no-programming theorem prohibits the existence of a Universal Programmable Quantum Processor. This statement has several implications in relation to quantum computation, but also to other tasks of quantum information processing, making this construction a central notion in this context. Nonetheless, it is well known that even when the strict model is not implementable, it is possible to conceive of it in an approximate sense. Unfortunately, the minimal resources necessary for this aim are still not completely understood. Here, we investigate quantitative statements of the theorem, improving exponentially previous bounds on the resources required by such a hypothetical machine. The proofs exploit a new connection between quantum channels and embeddings between Banach spaces which allows us to use classical tools from geometric Banach space theory in a clean and simple way.

arXiv comment14 (6+8) pages, 1 table. Changes implemented in order to match the published version

References in corpus (30)

• Unconditionally secure quantum bit commitment is impossible
• Is Quantum Bit Commitment Really Possible?
• A new proof for the existence of mutually unbiased bases
• Programmable quantum gate arrays
• Locking classical correlation in quantum states
• Asymptotic teleportation scheme as a universal programmable quantum processor
• Optimal quantum learning of a unitary transformation
• Simplified instantaneous non-local quantum computation with applications to position-based cryptography
• Parameter estimation of quantum channels
• Quantum Tagging: Authenticating Location via Quantum Information and Relativistic Signalling Constraints
• Storing quantum dynamics in quantum states: stochastic programmable gate for U(1) operations
• Efficient universal blind computation
• Quantum multimeters: A programmable state discriminator
• Probabilistic implementation of universal quantum processors
• Limitations on information theoretically secure quantum homomorphic encryption
• Nonlocal variables with product states eigenstates
• Universal measurement apparatus controlled by quantum software
• Survey on Nonlocal Games and Operator Space Theory
• Overcoming efficiency constraints on blind quantum computation
• Efficient universal programmable quantum measurements
• Quantum Tagging for Tags Containing Secret Classical Data
• Unambiguous coherent state identification: Searching a quantum database
• Multi-copy programmable discrimination of general qubit states
• Unambiguous discrimination between two unknown qudit states
• Probabilistic programmable quantum processors with multiple copies of program state
• Optimality of programmable quantum measurements
• Programmable discrimination with an error margin
• Entanglement detection from channel parameter estimation problem
• Storing unitary operators in quantum states
• Entropy in Quantum Information Theory -- Communication and Cryptography

Cited by in corpus (19)

• Optimal probabilistic storage and retrieval of unitary channels
• Optimal universal programming of unitary gates
• Fundamental energy requirement of reversible quantum operations
• Asymptotic performance of port-based teleportation
• Geometry of Banach spaces: a new route towards Position Based Cryptography
• A comparative study of universal quantum computing models: towards a physical unification
• A prototype of quantum von Neumann architecture
• Programmability of covariant quantum channels
• Choi states, symmetry-based quantum gate teleportation, and stored-program quantum computing
• Communication Cost of Quantum Processes
• Probabilistic storage and retrieval of qubit phase gates
• Infinite-Dimensional Programmable Quantum Processors
• Port-Based State Preparation and Applications
• Constraints on physical computers in holographic spacetimes
• Representation matching for delegated quantum computing
• Quantum Advantage in Storage and Retrieval of Isometry Channels
• Robustness of optimal probabilistic storage and retrieval of unitary channels to noise
• Compression of quantum shallow-circuit states
• A resource theory of asynchronous quantum information processing