Linear Depth QFT over IBM Heavy-hex Architecture

Compiling a given quantum algorithm into a target hardware architecture is a challenging optimization problem. The compiler must take into consideration the coupling graph of physical qubits and the gate operation dependencies. The existing noise in hardware architectures requires the compilation to use as few running cycles as possible. Existing approaches include using SAT solver or heuristics to complete the mapping but these may cause the issue of either long compilation time (e.g., timeout after hours) or suboptimal compilation results in terms of running cycles (e.g., exponentially increasing number of total cycles). In this paper, we propose an efficient mapping approach for Quantum Fourier Transformation (QFT) circuits over the existing IBM heavy-hex architecture. Such proposal first of all turns the architecture into a structure consisting of a straight line with dangling qubits, and then do the mapping over this generated structure recursively. The calculation shows that there is a linear depth upper bound for the time complexity of these structures and for a special case where there is 1 dangling qubit in every 5 qubits, the time complexity is 5N+O(1). All these results are better than state of the art methods.