  We study the fundamental design automation problem of equivalence checking in
the NISQ (Noisy Intermediate-Scale Quantum) computing realm where quantum noise
is present inevitably. The notion of approximate equivalence of (possibly
noisy) quantum circuits is defined based on the Jamiolkowski fidelity which
measures the average distance between output states of two super-operators when
the input is chosen at random. By employing tensor network contraction, we
present two algorithms, aiming at different situations where the number of
noises varies, for computing the fidelity between an ideal quantum circuit and
its noisy implementation. The effectiveness of our algorithms is demonstrated
by experimenting on benchmarks of real NISQ circuits. When compared with the
state-of-the-art implementation incorporated in Qiskit, experimental results
show that the proposed algorithms outperform in both efficiency and
scalability.
