SQUARE: Strategic Quantum Ancilla Reuse for Modular Quantum Programs via Cost-Effective Uncomputation

Abstract

Compiling high-level quantum programs to machines that are size constrained (i.e. limited number of quantum bits) and time constrained (i.e. limited number of quantum operations) is challenging. In this paper, we present SQUARE (Strategic QUantum Ancilla REuse), a compilation infrastructure that tackles allocation and reclamation of scratch qubits (called ancilla) in modular quantum programs. At its core, SQUARE strategically performs uncomputation to create opportunities for qubit reuse. Current Noisy Intermediate-Scale Quantum (NISQ) computers and forward-looking Fault-Tolerant (FT) quantum computers have fundamentally different constraints such as data locality, instruction parallelism, and communication overhead. Our heuristic-based ancilla-reuse algorithm balances these considerations and fits computations into resource-constrained NISQ or FT quantum machines, throttling parallelism when necessary. To precisely capture the workload of a program, we propose an improved metric, the "active quantum volume," and use this metric to evaluate the effectiveness of our algorithm. Our results show that SQUARE improves the average success rate of NISQ applications by 1.47X. Surprisingly, the additional gates for uncomputation create ancilla with better locality, and result in substantially fewer swap gates and less gate noise overall. SQUARE also achieves an average reduction of 1.5X (and up to 9.6X) in active quantum volume for FT machines.

14 pages, 10 figures

References in corpus (20)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Mixed State Entanglement and Quantum Error Correction
• Quantum algorithm for solving linear systems of equations
• Surface codes: Towards practical large-scale quantum computation
• Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
• Demonstration of a small programmable quantum computer with atomic qubits
• Surface code quantum computing by lattice surgery
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• ProjectQ: An Open Source Software Framework for Quantum Computing
• On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
• A unified framework for magic state distillation and multi-qubit gate-synthesis with reduced resource cost
• Lattice Surgery with a Twist: Simplifying Clifford Gates of Surface Codes
• Optimized Surface Code Communication in Superconducting Quantum Computers
• Verified compilation of space-efficient reversible circuits
• Magic-State Functional Units: Mapping and Scheduling Multi-Level Distillation Circuits for Fault-Tolerant Quantum Architectures
• Wire Recycling for Quantum Circuit Optimization
• Resource Optimized Quantum Architectures for Surface Code Implementations of Magic-State Distillation

Cited by in corpus (10)

• Quantum PUF for Security and Trust in Quantum Computing
• NetQASM -- A low-level instruction set architecture for hybrid quantum-classical programs in a quantum internet
• Tower: Data Structures in Quantum Superposition
• Systems Architecture for Quantum Random Access Memory
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• Reqomp: Space-constrained Uncomputation for Quantum Circuits
• QRCC: Evaluating Large Quantum Circuits on Small Quantum Computers through Integrated Qubit Reuse and Circuit Cutting
• Qurts: Automatic Quantum Uncomputation by Affine Types with Lifetime
• Partial Blind Quantum Computation: A Framework for Selective Circuit Protection
• RESCQ: Realtime Scheduling for Continuous Angle Quantum Error Correction Architectures