  The qubit routing problem, also known as the swap minimization problem, is a
(classical) combinatorial optimization problem that arises in the design of
compilers of quantum programs. We study the qubit routing problem from the
viewpoint of theoretical computer science, while most of the existing studies
investigated the practical aspects. We concentrate on the linear nearest
neighbor (LNN) architectures of quantum computers, in which the graph topology
is a path. Our results are three-fold. (1) We prove that the qubit routing
problem is NP-hard. (2) We give a fixed-parameter algorithm when the number of
two-qubit gates is a parameter. (3) We give a polynomial-time algorithm when
each qubit is involved in at most one two-qubit gate.
