Uncomputability and complexity of quantum control

Quantum control is actively developed nowadays due to various existing and prospective applications in quantum technologies. For example, in quantum computing it is used for high fidelity gate generation. We study computability of quantum control problems in the real experimental situation when the number of available controls is finite. For this situation we show that quantum control problems are in general not algorithmically solvable. There is no algorithm which could decide if a given quantum problem has optial solution or not. To prove this statement, we develop a technique based on establishing the equivalence between quantum control problems and Diophantine equations, 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.