Reducing the CNOT count for Clifford+T circuits on NISQ architectures

Abstract

While mapping a quantum circuit to the physical layer one has to consider the numerous constraints imposed by the underlying hardware architecture. Connectivity of the physical qubits is one such constraint that restricts two-qubit operations, such as CNOT, to "connected" qubits. SWAP gates can be used to place the logical qubits on admissible physical qubits, but they entail a significant increase in CNOT-count. In this paper we consider the problem of reducing the CNOT-count in Clifford+T circuits on connectivity constrained architectures, like noisy intermediate-scale quantum (NISQ) computing devices. We "slice" the circuit at the position of Hadamard gates and "build" the intermediate {CNOT,T} sub-circuits using Steiner trees, significantly improving on previous methods. We compared the performance of our algorithms while mapping different benchmark and random circuits to some well-known architectures such as 9-qubit square grid, 16-qubit square grid, Rigetti 16-qubit Aspen, 16-qubit IBM QX5 and 20-qubit IBM Tokyo. Our methods give less CNOT-count compared to Qiskit and TKET transpiler as well as using SWAP gates. Assuming most of the errors in a NISQ circuit implementation are due to CNOT errors, then our method would allow circuits with few times more CNOT gates be reliably implemented than the previous methods would permit.

arXiv commentAccepted in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD). This is an extended version with more illustrations. Comparison with Qiskit and TKET added

References in corpus (23)

• Quantum Computing in the NISQ era and beyond
• Quantum Mechanics helps in searching for a needle in a haystack
• Engineered 2D Ising interactions on a trapped-ion quantum simulator with hundreds of spins
• High-fidelity quantum logic gates using trapped-ion hyperfine qubits
• High-fidelity two-qubit quantum logic gates using trapped calcium-43 ions
• High-Fidelity Universal Gate Set for ${}^9$Be${}^{+}$ Ion Qubits
• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• Demonstration of Universal Parametric Entangling Gates on a Multi-Qubit Lattice
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures
• Scalable quantum circuit and control for a superconducting surface code
• Mapping Quantum Circuits to IBM QX Architectures Using the Minimal Number of SWAP and H Operations
• T-junction ion trap array for two-dimensional ion shuttling, storage and manipulation
• Compiling quantum circuits to realistic hardware architectures using temporal planners
• Efficient Quantum Circuits for Diagonal Unitaries Without Ancillas
• Quantum circuit optimizations for NISQ architectures
• On the CNOT-complexity of CNOT-PHASE circuits
• Linear Nearest Neighbor Synthesis of Reversible Circuits by Graph Partitioning
• Formal Constraint-based Compilation for Noisy Intermediate-Scale Quantum Systems
• Quantum circuits and low-degree polynomials over F_2
• Efficient and Effective Quantum Compiling for Entanglement-based Machine Learning on IBM Q Devices
• Synthesis of Linear Nearest Neighbor Quantum Circuits
• Computing quopit Clifford circuit amplitudes by the sum-over-paths technique

Cited by in corpus (14)

• T-count and T-depth of any multi-qubit unitary
• The Impact of Imperfect Timekeeping on Quantum Control
• Synthesizing efficient circuits for Hamiltonian simulation
• Quantum-state texture and gate identification
• Calculating the energy profile of an enzymatic reaction on a quantum computer
• Dynamic Qubit Routing with CNOT Circuit Synthesis for Quantum Compilation
• Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian
• A quantum random access memory (QRAM) using a polynomial encoding of binary strings
• Wasserstein Complexity of Quantum Circuits
• On the role of coherence for quantum computational advantage
• Improving Qubit Routing by Using Entanglement Mediated Remote Gates
• Global Synthesis of CNOT Circuits with Holes
• Evolutionary-Based Circuit Optimization for Distributed Quantum Computing
• CNOT Minimal Circuit Synthesis: A Reinforcement Learning Approach