Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning

Abstract

Most work in quantum circuit optimization has been performed in isolation from the results of quantum fault-tolerance. Here we present a polynomial-time algorithm for optimizing quantum circuits that takes the actual implementation of fault-tolerant logical gates into consideration. Our algorithm re-synthesizes quantum circuits composed of Clifford group and T gates, the latter being typically the most costly gate in fault-tolerant models, e.g., those based on the Steane or surface codes, with the purpose of minimizing both T-count and T-depth. A major feature of the algorithm is the ability to re-synthesize circuits with additional ancillae to reduce T-depth at effectively no cost. The tested benchmarks show up to 65.7% reduction in T-count and up to 87.6% reduction in T-depth without ancillae, or 99.7% reduction in T-depth using ancillae.

Version 2 contains substantial improvements and extensions to the previous version. We describe a new, more robust algorithm and achieve significantly improved experimental results

References in corpus (10)

• Superconducting qubit in waveguide cavity with coherence time approaching 0.1ms
• Complete universal quantum gate set approaching fault-tolerant thresholds with superconducting qubits
• A new quantum ripple-carry addition circuit
• Quantum Circuit Simplification and Level Compaction
• Quantum circuits of T-depth one
• Fast Quantum Modular Exponentiation
• Quantum accuracy threshold for concatenated distance-3 codes
• Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with no Auxiliary Qubits in Finite Neighbor Quantum Architectures
• Time-optimal quantum computation
• Optimization of Clifford Circuits

Cited by in corpus (101)

• Application of a resource theory for magic states to fault-tolerant quantum computing
• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer
• Automated optimization of large quantum circuits with continuous parameters
• On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
• Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus
• Challenges and Opportunities of Near-Term Quantum Computing Systems
• Reducing T-count with the ZX-calculus
• Quantifying the magic of quantum channels
• Towards Large-scale Functional Verification of Universal Quantum Circuits
• A Verified Optimizer for Quantum Circuits
• Automated distribution of quantum circuits via hypergraph partitioning
• Quantum circuit optimizations for NISQ architectures
• Conformal field theories are magical
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• A unified framework for magic state distillation and multi-qubit gate-synthesis with reduced resource cost
• Phase Gadget Synthesis for Shallow Circuits
• Fault tolerant resource estimation of quantum random-access memories
• There and back again: A circuit extraction tale
• Quantum circuit optimization with deep reinforcement learning
• ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity
• staq -- A full-stack quantum processing toolkit
• On the CNOT-complexity of CNOT-PHASE circuits
• Optimized compiler for Distributed Quantum Computing
• Unifying gate-synthesis and magic state distillation
• Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters
• T-count optimization and Reed-Muller codes
• Synthesizing Quantum-Circuit Optimizers
• The Impact of Hardware Specifications on Reaching Quantum Advantage in the Fault Tolerant Regime
• T-count and T-depth of any multi-qubit unitary
• Parallelising the Queries in Bucket Brigade Quantum RAM
• Constructing quantum circuits with global gates
• Variational circuit compiler for quantum error correction
• Reducing the Depth of Linear Reversible Quantum Circuits
• A polynomial time and space heuristic algorithm for T-count
• Quantum Circuits for Toom-Cook Multiplication
• ZX-calculus for the working quantum computer scientist
• Parallelizing quantum circuit synthesis
• Synthesis of and compilation with time-optimal multi-qubit gates
• Techniques to Reduce $\pi /4$-Parity-Phase Circuits, Motivated by the ZX Calculus
• Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits
• Reducing the CNOT count for Clifford+T circuits on NISQ architectures
• Systems Architecture for Quantum Random Access Memory
• Phase polynomials synthesis algorithms for NISQ architectures and beyond
• Enabling Dataflow Optimization for Quantum Programs
• Magic-State Functional Units: Mapping and Scheduling Multi-Level Distillation Circuits for Fault-Tolerant Quantum Architectures
• Reducing 2-QuBit Gate Count for ZX-Calculus based Quantum Circuit Optimization
• Constructions for Quantum Indistinguishability Obfuscation
• Architecture-Aware Synthesis of Phase Polynomials for NISQ Devices
• Synthesizing efficient circuits for Hamiltonian simulation
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits
• A Finite Presentation of CNOT-Dihedral Operators
• Logic Synthesis for Quantum Computing
• Gaussian Elimination versus Greedy Methods for the Synthesis of Linear Reversible Circuits
• Logic Synthesis for Fault-Tolerant Quantum Computers
• Quantum circuit compilation and hybrid computation using Pauli-based computation
• A Regular Representation of Quantum Circuits
• Resource Optimized Quantum Architectures for Surface Code Implementations of Magic-State Distillation
• Assertion-Based Optimization of Quantum Programs
• A Complete Equational Theory for Quantum Circuits
• Hybrid quantum-classical circuit simplification with the ZX-calculus
• A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz
• T-count Optimized Design of Quantum Integer Multiplication
• Complete Flow-Preserving Rewrite Rules for MBQC Patterns with Pauli Measurements
• Optimal Hadamard gate count for Clifford$+T$ synthesis of Pauli rotations sequences
• A Case for Synthesis of Recursive Quantum Unitary Programs
• The phase/state duality in reversible circuit design
• ZX-Calculus and Extended Wolfram Model Systems II: Fast Diagrammatic Reasoning with an Application to Quantum Circuit Simplification
• The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
• Randomized Benchmarking of Clifford Operators
• Linear and non-linear relational analyses for Quantum Program Optimization
• Decoding techniques applied to the compilation of CNOT circuits for NISQ architectures
• Formal Methods for Quantum Programs: A Survey
• Unitary Synthesis of Clifford+T Circuits with Reinforcement Learning
• Everything You Always Wanted to Know About Quantum Circuits
• Verified Optimization in a Quantum Intermediate Representation
• Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3
• T-count and Qubit Optimized Quantum Circuit Designs of Carry Lookahead Adder
• Dynamic Qubit Routing with CNOT Circuit Synthesis for Quantum Compilation
• Symbolic Synthesis of Clifford Circuits and Beyond
• Generators and Relations for 2-Qubit Clifford+T Operators
• Comparing planar quantum computing platforms at the quantum speed limit
• Lower T-count with faster algorithms
• On the role of coherence for quantum computational advantage
• Fast algorithms for classical specifications of stabiliser states and Clifford gates
• A recursively partitioned approach to architecture-aware ZX Polynomial synthesis and optimization
• $T$-depth-optimized Quantum Search with Quantum Data-access Machine
• Wasserstein Complexity of Quantum Circuits
• Composability of global phase invariant distance and its application to approximation error management
• Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis
• Quantum Theory from Principles, Quantum Software from Diagrams
• QUANTIFY: A framework for resource analysis and design verification of quantum circuits
• A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log^2 n)
• Quantum Circuit Optimization by Graph Coloring
• Hamiltonian simulation with explicit formulas for Digital-Analog Quantum Computing
• Quantum Speedup of Monte Carlo Integration with respect to the Number of Dimensions and its Application to Finance
• Quantum states supported by matroids
• Reducing depth and measurement weights in Pauli-based computation
• POPQC: Parallel Optimization for Quantum Circuits (Extended Version)
• Nontrivial multi-product commutation relation toward reducing T-count in sequential Pauli-based computation