Uncomputability and complexity of quantum control

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 exists no algorithm that can decide whether dynamics of an arbitrary quantum system can be manipulated by accessible external interactions (coherent and 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 does not preclude an algorithmic solvability for a particular class of quantum control problems. 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.