  In the era of noisy intermediate-scale quantum (NISQ), executing quantum
algorithms on actual quantum devices faces unique challenges. One such
challenge is that quantum devices in this era have restricted connectivity:
quantum gates are allowed to act only on specific pairs of physical qubits. For
this reason, a quantum circuit needs to go through a compiling process called
qubit routing before it can be executed on a quantum computer. In this study,
we propose a CNOT synthesis method called the token reduction method to solve
this problem. The token reduction method works for all quantum computers whose
architecture is represented by connected graphs. A major difference between our
method and the existing ones is that our method synthesizes a circuit to an
output qubit mapping that might be different from the input qubit mapping. The
final mapping for the synthesis is determined dynamically during the synthesis
process. Results showed that our algorithm consistently outperforms the best
publicly accessible algorithm for all of the tested quantum architectures.
