Linear Nearest Neighbor Synthesis of Reversible Circuits by Graph Partitioning

Abstract

Linear Nearest Neighbor (LNN) synthesis in reversible circuits has emerged as an important issue in terms of technological implementation for quantum computation. The objective is to obtain a LNN architecture with minimum gate cost. As achieving optimal synthesis is a hard problem, heuristic methods have been proposed in recent literature. In this work we present a graph partitioning based approach for LNN synthesis with reduction in circuit cost. In particular, the number of SWAP gates required to convert a given gate-level quantum circuit to its equivalent LNN configuration is minimized. Our algorithm determines the reordering of indices of the qubit line(s) for both single control and multiple controlled gates. Experimental results for placing the target qubits of Multiple Controlled Toffoli (MCT) library of benchmark circuits show a significant reduction in gate count and quantum gate cost compared to those of related research works.

References in corpus (3)

• Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures
• Quantum Circuit Placement
• Synthesis of Reversible Functions Beyond Gate Count and Quantum Cost

Cited by in corpus (13)

• Time-Sliced Quantum Circuit Partitioning for Modular Architectures
• Optimized Surface Code Communication in Superconducting Quantum Computers
• Depth-Optimal Quantum Circuit Placement for Arbitrary Topologies
• Reducing the CNOT count for Clifford+T circuits on NISQ architectures
• Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers
• Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits
• QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis
• Using Spectral Graph Theory to Map Qubits onto Connectivity-Limited Devices
• Optimization of Quantum Circuit Mapping using Gate Transformation and Commutation
• MUQUT: Multi-Constraint Quantum Circuit Mapping on Noisy Intermediate-Scale Quantum Computers
• TILT: Achieving Higher Fidelity on a Trapped-Ion Linear-Tape Quantum Computing Architecture
• Context-Sensitive and Duration-Aware Qubit Mapping for Various NISQ Devices
• 2D Qubit Placement of Quantum Circuits using LONGPATH