  The famous no-cloning principle has been shown recently to enable a number of
uncloneable functionalities. Here we address for the first time unkeyed quantum
uncloneablity, via the study of a complexity-theoretic tool that enables a
computation, but that is natively unkeyed: quantum advice. Remarkably, this is
an application of the no-cloning principle in a context where the quantum
states of interest are not chosen by a random process. We show the
unconditional existence of promise problems admitting uncloneable quantum
advice, and the existence of languages with uncloneable advice, assuming the
feasibility of quantum copy-protecting certain functions. Along the way, we
note that state complexity classes, introduced by Rosenthal and Yuen (ITCS
2022) - which concern the computational difficulty of synthesizing sequences of
quantum states - can be naturally generalized to obtain state cloning
complexity classes. We make initial observations on these classes, notably
obtaining a result analogous to the existence of undecidable problems.
  Our proof technique establishes the existence of ingenerable sequences of
finite bit strings - essentially meaning that they cannot be generated by any
uniform circuit family. We then prove a generic result showing that the
difficulty of accomplishing a computational task on uniformly random inputs
implies its difficulty on any fixed, ingenerable sequence. We use this result
to derandomize quantum cryptographic games that relate to cloning, and then
incorporate a result of Kundu and Tan (arXiv 2022) to obtain uncloneable
advice. Applying this two-step process to a monogamy-of-entanglement game
yields a promise problem with uncloneable advice, and applying it to the
quantum copy-protection of pseudorandom functions with super-logarithmic output
lengths yields a language with uncloneable advice.
