Quantum Circuit Transformation Based on Simulated Annealing and Heuristic Search

Abstract

Quantum algorithm design usually assumes access to a perfect quantum computer with ideal properties like full connectivity, noise-freedom and arbitrarily long coherence time. In Noisy Intermediate-Scale Quantum (NISQ) devices, however, the number of qubits is highly limited and quantum operation error and qubit coherence are not negligible. Besides, the connectivity of physical qubits in a quantum processing unit (QPU) is also strictly constrained. Thereby, additional operations like SWAP gates have to be inserted to satisfy this constraint while preserving the functionality of the original circuit. This process is known as quantum circuit transformation. Adding additional gates will increase both the size and depth of a quantum circuit and therefore cause further decay of the performance of a quantum circuit. Thus it is crucial to minimize the number of added gates. In this paper, we propose an efficient method to solve this problem. We first choose by using simulated annealing an initial mapping which fits well with the input circuit and then, with the help of a heuristic cost function, stepwise apply the best selected SWAP gates until all quantum gates in the circuit can be executed. Our algorithm runs in time polynomial in all parameters including the size and the qubit number of the input circuit, and the qubit number in the QPU. Its space complexity is quadratic to the number of edges in the QPU. Experimental results on extensive realistic circuits confirm that the proposed method is efficient and can reduce by 57% on average the size of the output circuits when compared with the state-of-the-art algorithm on the most recent IBM quantum device viz. IBM Q20 (Tokyo).

in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

References in corpus (10)

• Quantum Computing in the NISQ era and beyond
• Elementary gates for quantum computation
• A Quantum Engineer's Guide to Superconducting Qubits
• Building logical qubits in a superconducting quantum computing system
• Mapping Quantum Circuits to IBM QX Architectures Using the Minimal Number of SWAP and H Operations
• A Software Methodology for Compiling Quantum Programs
• Circuit Transformations for Quantum Architectures
• Full-Stack, Real-System Quantum Computer Studies: Architectural Comparisons and Design Insights
• Qubit Allocation for Noisy Intermediate-Scale Quantum Computers
• SANQ: A Simulation Framework for Architecting Noisy Intermediate-Scale Quantum Computing System

Cited by in corpus (11)

• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era
• Qubit Mapping Based on Subgraph Isomorphism and Filtered Depth-Limited Search
• Quantum Circuit Compiler for a Shuttling-Based Trapped-Ion Quantum Computer
• Supervised Learning Enhanced Quantum Circuit Transformation
• Exploring ab initio machine synthesis of quantum circuits
• Quantum circuit compilation with quantum computers
• Qubit assignment using time reversal
• Quantum Circuit Transformation Based on Tabu Search
• Quantum Circuit Transformation: A Monte Carlo Tree Search Framework
• A Variation-Aware Quantum Circuit Mapping Approach Based on Multi-agent Cooperation