Orchestrated Trios: Compiling for Efficient Communication in Quantum Programs with 3-Qubit Gates

Abstract

Current quantum computers are especially error prone and require high levels of optimization to reduce operation counts and maximize the probability the compiled program will succeed. These computers only support operations decomposed into one- and two-qubit gates and only two-qubit gates between physically connected pairs of qubits. Typical compilers first decompose operations, then route data to connected qubits. We propose a new compiler structure, Orchestrated Trios, that first decomposes to the three-qubit Toffoli, routes the inputs of the higher-level Toffoli operations to groups of nearby qubits, then finishes decomposition to hardware-supported gates. This significantly reduces communication overhead by giving the routing pass access to the higher-level structure of the circuit instead of discarding it. A second benefit is the ability to now select an architecture-tuned Toffoli decomposition such as the 8-CNOT Toffoli for the specific hardware qubits now known after the routing pass. We perform real experiments on IBM Johannesburg showing an average 35% decrease in two-qubit gate count and 23% increase in success rate of a single Toffoli over Qiskit. We additionally compile many near-term benchmark algorithms showing an average 344% increase in (or 4.44x) simulated success rate on the Johannesburg architecture and compare with other architecture types.

In ASPLOS '21: 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, 12 pages, 12 figures

References in corpus (12)

• Quantum Computing in the NISQ era and beyond
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Elementary gates for quantum computation
• A Quantum Engineer's Guide to Superconducting Qubits
• Quantum Circuit Simplification and Level Compaction
• Software Mitigation of Crosstalk on Noisy Intermediate-Scale Quantum Computers
• Automated optimization of large quantum circuits with continuous parameters
• Quantum arithmetic with the Quantum Fourier Transform
• ScaffCC: Scalable Compilation and Analysis of Quantum Programs
• Time-Sliced Quantum Circuit Partitioning for Modular Architectures
• On the qubit routing problem
• Two-step approach to scheduling quantum circuits

Cited by in corpus (7)

• Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging
• A Toffoli Gate Decomposition via Echoed Cross-Resonance Gates
• Dancing the Quantum Waltz: Compiling Three-Qubit Gates on Four Level Architectures
• Hardware-Conscious Optimization of the Quantum Toffoli Gate
• QContext: Context-Aware Decomposition for Quantum Gates
• Mantra: Rewriting Quantum Programs to Minimize Trap-Movements for Zoned Rydberg Atom Arrays
• A T-depth two Toffoli gate for 2D square lattice architectures