Storing Quantum Dynamics in Quantum States: A Stochastic Programmable Gate

We show how to encode quantum dynamics in the state of a quantum system, in such a way that the system can be used to stochastically perform, at a later time, the stored transformation on some other quantum system. The probability of failure decreases exponentially with the number of qubits that store the transformation. We discuss optimality of this scheme, whose applications include viability of a (stochastic) programmable quantum gate and the teleportation of quantum transformations using entanglement and unidirectional classical communication.