The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
arXiv:2311.12772 · doi:10.1145/3656397
Abstract
Numerous quantum algorithms require the use of quantum error correction to overcome the intrinsic unreliability of physical qubits. However, error correction imposes a unique performance bottleneck, known as T-complexity, that can make an implementation of an algorithm as a quantum program run more slowly than on idealized hardware. In this work, we identify that programming abstractions for control flow, such as the quantum if-statement, can introduce polynomial increases in the T-complexity of a program. If not mitigated, this slowdown can diminish the computational advantage of a quantum algorithm. To enable reasoning about the costs of control flow, we present a cost model that a developer can use to accurately analyze the T-complexity of a program and pinpoint the sources of slowdown. We also present a set of program-level optimizations, that a developer can use to rewrite a program to reduce its T-complexity, predict the T-complexity of the optimized program using the cost model, and then compile it to an efficient circuit via a straightforward strategy. We implement the program-level optimizations in Spire, an extension of the Tower quantum compiler. Using a set of 11 benchmark programs that use control flow, we show that the cost model is accurate, and that Spire's optimizations recover programs that are asymptotically efficient, meaning their runtime T-complexity under error correction is equal to their time complexity on idealized hardware. Our results show that optimizing a program before it is compiled to a circuit can yield better results than compiling the program to an inefficient circuit and then invoking a quantum circuit optimizer found in prior work. For our benchmarks, only 2 of 8 tested circuit optimizers recover circuits with asymptotically efficient T-complexity. Compared to these 2 optimizers, Spire uses 54x to 2400x less compile time.
22 pages, 17 figures. v2: camera-ready version of paper
References in corpus (42)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Machine Learning
- Elementary gates for quantum computation
- Quantum cryptography: Public key distribution and coin tossing
- Surface codes: Towards practical large-scale quantum computation
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- Quantum Amplitude Amplification and Estimation
- Suppressing quantum errors by scaling a surface code logical qubit
- A Theory of Fault-Tolerant Quantum Computation
- Elucidating Reaction Mechanisms on Quantum Computers
- Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
- Validating quantum computers using randomized model circuits
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- Toward the first quantum simulation with quantum speedup
- Restrictions on Transversal Encoded Quantum Gate Sets
- ProjectQ: An Open Source Software Framework for Quantum Computing
- tket : A Retargetable Compiler for NISQ Devices
- Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
- Even more efficient quantum computations of chemistry through tensor hypercontraction
- Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
- Quantum computational finance: Monte Carlo pricing of financial derivatives
- Quantum circuits of T-depth one
- Q#: Enabling scalable quantum computing and development with a high-level domain-specific language
- The Bitter Truth About Quantum Algorithms in the NISQ Era
- Automated optimization of large quantum circuits with continuous parameters
- Demonstration of weight-four parity measurements in the surface code architecture
- On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
- Focus beyond quadratic speedups for error-corrected quantum advantage
- Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
- A functional quantum programming language
- PyZX: Large Scale Automated Diagrammatic Reasoning
- A Verified Optimizer for Quantum Circuits
- Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
- The disjointness of stabilizer codes and limitations on fault-tolerant logical gates
- Comparing the Overhead of Topological and Concatenated Quantum Error Correction
- Synthesizing Quantum-Circuit Optimizers
- Tower: Data Structures in Quantum Superposition
- High Performance Quantum Modular Multipliers
- Enabling Dataflow Optimization for Quantum Programs
- Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer
- Quantum Expectation Transformers for Cost Analysis
- Defining Quantum Control Flow