  In laboratory and numerical experiments, physical quantities are known with a
finite precision and described by rational numbers. Based on this, we deduce
that quantum control problems both for open and closed systems are in general
not algorithmically solvable, i.e., there is no algorithm that can decide
whether dynamics of an arbitrary quantum system can be manipulated by
accessible external interactions (coherent or dissipative) such that a chosen
target reaches a desired value. This conclusion holds even for the relaxed
requirement of the target only approximately attaining the desired value. These
findings do not preclude an algorithmic solvability for a particular class of
quantum control problems. Moreover, any quantum control problem can be made
algorithmically solvable if the set of accessible interactions (i.e., controls)
is rich enough. To arrive at these results, we develop a technique based on
establishing the equivalence between quantum control problems and Diophantine
equations, which are polynomial equations with integer coefficients and integer
unknowns. In addition to proving uncomputability, this technique allows to
construct quantum control problems belonging to different complexity classes.
In particular, an example of the control problem involving a two-mode coherent
field is shown to be NP-hard, contradicting a widely held believe that two-body
problems are easy.
