  Due to little consideration in the hardware constraints, e.g., limited
connections between physical qubits to enable two-qubit gates, most quantum
algorithms cannot be directly executed on the Noisy Intermediate-Scale Quantum
(NISQ) devices. Dynamically remapping logical qubits to physical qubits in the
compiler is needed to enable the two-qubit gates in the algorithm, which
introduces additional operations and inevitably reduces the fidelity of the
algorithm. Previous solutions in finding such remapping suffer from high
complexity, poor initial mapping quality, and limited flexibility and
controllability.
  To address these drawbacks mentioned above, this paper proposes a SWAP-based
BidiREctional heuristic search algorithm SABRE, which is applicable to NISQ
devices with arbitrary connections between qubits. By optimizing every search
attempt,globally optimizing the initial mapping using a novel reverse traversal
technique, introducing the decay effect to enable the trade-off between the
depth and the number of gates of the entire algorithm, SABRE outperforms the
best known algorithm with exponential speedup and comparable or better results
on various benchmarks.

Emerging Technologies;Quantum Physics