Improving the Fidelity of CNOT Circuits on NISQ Hardware
We introduce an improved CNOT synthesis algorithm that considers
nearest-neighbour interactions and CNOT gate error rates in noisy
intermediate-scale quantum (NISQ) hardware. Compared to IBM's Qiskit compiler,
it improves the fidelity of a synthesized CNOT circuit by about 2 times on
average (up to 9 times). It lowers the synthesized CNOT count by a factor of 13
on average (up to a factor of 162).
  Our contribution is twofold. First, we define a $\textsf{Cost}$ function by
approximating the average gate fidelity $F_{avg}$. According to the simulation
results, $\textsf{Cost}$ fits the error probability of a noisy CNOT circuit,
$\textsf{Prob} = 1 - F_{avg}$, much tighter than the commonly used cost
functions. On IBM's fake Nairobi backend, it matches $\textsf{Prob}$ to within
$10^{-3}$. On other backends, it fits $\textsf{Prob}$ to within $10^{-1}$.
$\textsf{Cost}$ accurately quantifies the dynamic error characteristics and
shows remarkable scalability. Second, we propose a noise-aware CNOT routing
algorithm, NAPermRowCol, by adapting the leading Steiner-tree-based
connectivity-aware CNOT synthesis algorithms. A weighted edge is used to encode
a CNOT gate error rate and $\textsf{Cost}$-instructed heuristics are applied to
each reduction step. NAPermRowCol does not use ancillary qubits and is not
restricted to certain initial qubit maps. Compared with algorithms that are
noise-agnostic, it improves the fidelity of a synthesized CNOT circuit across
varied NISQ hardware. Depending on the benchmark circuit and the IBM backend
selected, it lowers the synthesized CNOT count up to $56.95\%$ compared to
ROWCOL and up to $21.62\%$ compared to PermRowCol. It reduces the synthesis
$\textsf{Cost}$ up to $25.71\%$ compared to ROWCOL and up to $9.12\%$ compared
to PermRowCol. Our method can be extended to route a more general quantum
circuit, giving a powerful new tool for compiling on NISQ devices.
Dohun Kim Minyoung Kim Sarah Meng Li Michele Mosca