  Nonlinear modifications to the laws of quantum mechanics have been proposed
as a possible way to consistently describe information processing in the
presence of closed timelike curves. These have recently generated controversy
due to possible exotic information-theoretic effects, including breaking
quantum cryptography and radically speeding up both classical and quantum
computers. The physical interpretation of such theories, however, is still
unclear. We consider a large class of operationally-defined theories that
contain "nonlinear boxes" and show that operational verifiability without
superluminal signaling implies a split in the equivalence classes of
preparation procedures. We conclude that any theory satisfying the above
requirements is (a) inconsistent unless it contains distinct representations
for the two different kinds of preparations and (b) incomplete unless it also
contains a rule for uniquely distinguishing them at the operational level. We
refer to this as the preparation problem for nonlinear theories. In addition to
its foundational implications, this work shows that, in the presence of
nonlinear quantum evolution, the security of quantum cryptography and the
existence of other exotic effects remain open questions.
