Quantum circuit optimizations for NISQ architectures
Currently available quantum computing hardware platforms have limited 2-qubit
connectivity among their addressable qubits. In order to run a generic quantum
algorithm on such a platform, one has to transform the initial logical quantum
circuit describing the algorithm into an equivalent one that obeys the
connectivity restrictions.
  In this work we construct a circuit synthesis scheme that takes as input the
qubit connectivity graph and a quantum circuit over the gate set generated by
$\{\text{CNOT},R_{Z}\}$ and outputs a circuit that respects the connectivity of
the device. As a concrete application, we apply our techniques to Google's
Bristlecone 72-qubit quantum chip connectivity, IBM's Tokyo 20-qubit quantum
chip connectivity, and Rigetti's Acorn 19-qubit quantum chip connectivity. In
addition, we also compare the performance of our scheme as a function of
sparseness of randomly generated quantum circuits.
  Note: Recently, the authors of arXiv:1904.00633 independently presented a
similar optimization scheme. Our work is independent of arXiv:1904.00633, being
a longer version of the seminar presented by Beatrice Nash at the Dagstuhl
Seminar 18381: Quantum Programming Languages, pg. 120, September 2018,
Dagstuhl, Germany, slide deck available online at
https://materials.dagstuhl.de/files/18/18381/18381.BeatriceNash.Slides.pdf.
Beatrice Nash Vlad Gheorghiu Michele Mosca