The realization of quantum algorithms relies on specific quantum compilations according to the underlying quantum processors. However, there are various ways to physically implement qubits and manipulate those qubits in different physical devices. These differences lead to different communication methods and connection topologies, with each vendor implementing its own set of primitive gates. Therefore, quantum circuits have to be rewritten or transformed in order to be transplanted from one platform to another. We propose a pattern matching based framework for rewriting quantum circuits, called QRewriting. It takes advantage of a new representation of quantum circuits using symbolic sequences. Unlike the traditional approach using directed acyclic graphs, the new representation allows us to easily identify the patterns that appear non-consecutively but are reducible. Then, we convert the problem of pattern matching into that of finding distinct subsequences and propose a polynomial-time dynamic programming based pattern matching and replacement algorithm. We develop a rule library for basic optimizations and rewrite the arithmetic and Toffoli circuits from a commonly used gate set to the gate set supported by the Surface-17 quantum processor. Compared with a state-of-the-art quantum circuit optimization framework PaF optimized on the BIGD benchmarks, QRewriting further reduces the depth and the gate count by an average of 26.5% and 17.4%, respectively.

The goal of qubit mapping is to map a logical circuit to a physical device by introducing additional gates as few as possible in an acceptable amount of time. We present an effective approach called Tabu Search Based Adjustment (TSA) algorithm to construct the mappings. It consists of two key steps: one is making use of a combined subgraph isomorphism and completion to initialize some candidate mappings, and the other is dynamically modifying the mappings by TSA. Our experiments show that, compared with state-of-the-art methods, TSA can generate mappings with a smaller number of additional gates and have better scalability for large-scale circuits.