  One-time programs are modelled after a black box that allows a single
evaluation of a function, and then self-destructs. Because software can, in
principle, be copied, general one-time programs exists only in the hardware
token model: it has been shown that any function admits a one-time program as
long as we assume access to physical devices called one-time memories. Quantum
information, with its well-known property of no-cloning, would, at first
glance, prevent the basic copying attack for classical programs. We show that
this intuition is false: one-time programs for both classical and quantum maps,
based solely on quantum information, do not exist, even with computational
assumptions. We complement this strong impossibility proof by an equally strong
possibility result: assuming the same basic one-time memories as used for
classical one-time programs, we show that every quantum map has a quantum
one-time program that is secure in the universal composability framework. Our
construction relies on a new, simpler quantum authentication scheme and
corresponding mechanism for computing on authenticated data.
