A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits

Abstract

We present an algorithm for computing depth-optimal decompositions of logical operations, leveraging a meet-in-the-middle technique to provide a significant speed-up over simple brute force algorithms. As an illustration of our method we implemented this algorithm and found factorizations of the commonly used quantum logical operations into elementary gates in the Clifford+T set. In particular, we report a decomposition of the Toffoli gate over the set of Clifford and T gates. Our decomposition achieves a total T-depth of 3, thereby providing a 40% reduction over the previously best known decomposition for the Toffoli gate. Due to the size of the search space the algorithm is only practical for small parameters, such as the number of qubits, and the number of gates in an optimal implementation.

23 pages, 15 figures, 1 table; To appear in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

References in corpus (7)

• Engineered 2D Ising interactions on a trapped-ion quantum simulator with hundreds of spins
• Exponential algorithmic speedup by quantum walk
• Superconducting qubit in waveguide cavity with coherence time approaching 0.1ms
• Complete universal quantum gate set approaching fault-tolerant thresholds with superconducting qubits
• Quantum accuracy threshold for concatenated distance-3 codes
• A Depth-Optimal Canonical Form for Single-qubit Quantum Circuits
• Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates

Cited by in corpus (159)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Roads towards fault-tolerant universal quantum computation
• Toward the first quantum simulation with quantum speedup
• Experimental Comparison of Two Quantum Computing Architectures
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Trading classical and quantum computational resources
• Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer
• Halving the cost of quantum addition
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• Quantum circuits of T-depth one
• Automated optimization of large quantum circuits with continuous parameters
• Novel constructions for the fault-tolerant Toffoli gate
• Mapping Quantum Circuits to IBM QX Architectures Using the Minimal Number of SWAP and H Operations
• Challenges and Opportunities of Near-Term Quantum Computing Systems
• Exact synthesis of multiqubit Clifford+T circuits
• Reducing T-count with the ZX-calculus
• Machine learning method for state preparation and gate synthesis on photonic quantum computers
• Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits
• Factoring with Qutrits: Shor's Algorithm on Ternary and Metaplectic Quantum Architectures
• Optimal Layout Synthesis for Quantum Computing
• Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
• Conformal field theories are magical
• A unified framework for magic state distillation and multi-qubit gate-synthesis with reduced resource cost
• Approximate Quantum Fourier Transform with $O(n\log (n))$ T gates
• Phase Gadget Synthesis for Shallow Circuits
• Requirements for fault-tolerant factoring on an atom-optics quantum computer
• There and back again: A circuit extraction tale
• Time-Space Complexity of Quantum Search Algorithms in Symmetric Cryptanalysis
• ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity
• Applying quantum algorithms to constraint satisfaction problems
• On the CNOT-complexity of CNOT-PHASE circuits
• Resources for bosonic quantum computational advantage
• Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations
• Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates
• Shorter gate sequences for quantum computing by mixing unitaries
• Unifying gate-synthesis and magic state distillation
• Experimental Demonstration of Non-local Controlled-Unitary Quantum Gates Using a Five-qubit Quantum Computer
• Qubit Mapping Based on Subgraph Isomorphism and Filtered Depth-Limited Search
• Grover on SIMON
• Verified compilation of space-efficient reversible circuits
• T-count optimization and Reed-Muller codes
• LEAP: Scaling Numerical Optimization Based Synthesis Using an Incremental Approach
• Compiler Optimization for Quantum Computing Using Reinforcement Learning
• On quantum circuits employing roots of the Pauli matrices
• Floating Point Representations in Quantum Circuit Synthesis
• Full-Stack, Real-System Quantum Computer Studies: Architectural Comparisons and Design Insights
• Efficient construction of three- and four-qubit quantum gates by global entangling gates
• T-count and T-depth of any multi-qubit unitary
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• SQUARE: Strategic Quantum Ancilla Reuse for Modular Quantum Programs via Cost-Effective Uncomputation
• Quantum optimal control using phase-modulated driving fields
• Optimization and experimental realization of the quantum permutation algorithm
• Exact gate decompositions for photonic quantum computing
• ZX-calculus for the working quantum computer scientist
• A polynomial time and space heuristic algorithm for T-count
• Quantum Circuit Design for Objective Function Maximization in Gate-Model Quantum Computers
• QFAST: Quantum Synthesis Using a Hierarchical Continuous Circuit Space
• Parallelizing quantum circuit synthesis
• Techniques to Reduce $\pi /4$-Parity-Phase Circuits, Motivated by the ZX Calculus
• Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits
• Phase polynomials synthesis algorithms for NISQ architectures and beyond
• New techniques for fault-tolerant decomposition of Multi-Controlled Toffoli gate
• Exact and approximate continuous-variable gate decompositions
• Enabling Dataflow Optimization for Quantum Programs
• Equivalence Checking of Parameterized Quantum Circuits: Verifying the Compilation of Variational Quantum Algorithms
• MQT Predictor: Automatic Device Selection with Device-Specific Circuit Compilation for Quantum Computing
• Efficient variational synthesis of quantum circuits with coherent multi-start optimization
• Holomorphic representation of quantum computations
• Constructions for Quantum Indistinguishability Obfuscation
• Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers
• Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging
• Magic State Distillation from Entangled States
• Logical Clifford Synthesis for Stabilizer Codes
• Quantum search on noisy intermediate-scale quantum devices
• Polylogarithmic-depth controlled-NOT gates without ancilla qubits
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits
• Quantum circuit synthesis using Householder transformations
• A Finite Presentation of CNOT-Dihedral Operators
• Heuristics for Quantum Compiling with a Continuous Gate Set
• Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries
• Logic Synthesis for Quantum Computing
• Enhancing Quantum Computation via Superposition of Quantum Gates
• As Accurate as Needed, as Efficient as Possible: Approximations in DD-based Quantum Circuit Simulation
• A Regular Representation of Quantum Circuits
• Logic Synthesis for Fault-Tolerant Quantum Computers
• Assertion-Based Optimization of Quantum Programs
• A Toffoli Gate Decomposition via Echoed Cross-Resonance Gates
• State Stabilization for Gate-Model Quantum Computers
• An algorithm for the T-count
• Automatic Depth-Optimized Quantum Circuit Synthesis for Diagonal Unitary Matrices with Asymptotically Optimal Gate Count
• Synthesis of Arbitrary Quantum Circuits to Topological Assembly: Systematic, Online and Compact
• A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz
• T-count Optimized Design of Quantum Integer Multiplication
• Distillation protocols for Fourier states in quantum computing
• Efficient Clifford+T approximation of single-qubit operators
• Enabling Accuracy-Aware Quantum Compilers using Symbolic Resource Estimation
• A Case for Synthesis of Recursive Quantum Unitary Programs
• QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis
• Robust and Resource-Efficient Quantum Circuit Approximation
• Unitary Synthesis of Clifford+T Circuits with Reinforcement Learning
• Synthesis of CNOT-Dihedral circuits with optimal number of two qubit gates
• Quantum Compiler Optimizations
• Everything You Always Wanted to Know About Quantum Circuits
• Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3
• End-to-end complexity for simulating the Schwinger model on quantum computers
• Block encoding bosons by signal processing
• T-count and Qubit Optimized Quantum Circuit Designs of Carry Lookahead Adder
• Characterization, synthesis, and optimization of quantum circuits over multiple-control $\text{Z}$-rotation gates: A systematic study
• Designs from magic-augmented Clifford circuits
• SlackQ : Approaching the Qubit Mapping Problem with A Slack-aware Swap Insertion Scheme
• Optimal and asymptotically optimal NCT reversible circuits by the gate types
• Variational quantum eigensolver with embedded entanglement using a tensor-network ansatz
• Robust Quantum Arithmetic Operations with Intermediate Qutrits in the NISQ-era
• Quantum Circuit Design of Integer Division Optimizing Ancillary Qubits and T-Count
• Generators and Relations for 2-Qubit Clifford+T Operators
• An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition
• Reducing the Compilation Time of Quantum Circuits Using Pre-Compilation on the Gate Level
• CNOT-count optimized quantum circuit of the Shor's algorithm
• Improved Quantum Ternary Arithmetics
• Resource optimization for fault-tolerant quantum computing
• Sketching the Best Approximate Quantum Compiling Problem
• Ancilla-free synthesis of large reversible functions using binary decision diagrams
• Lower T-count with faster algorithms
• Optimal compilation of parametrised quantum circuits
• T-count Optimized Quantum Circuits for Bilinear Interpolation
• Improving Figures of Merit for Quantum Circuit Compilation
• Optimizing T and CNOT Gates in Quantum Ripple-Carry Adders and Comparators
• Lowering the T-depth of Quantum Circuits By Reducing the Multiplicative Depth Of Logic Networks
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation
• Applying Grover's algorithm to AES: quantum resource estimates
• Efficient quantum circuits for binary elliptic curve arithmetic: reducing T-gate complexity
• Classical Coding Approaches to Quantum Applications
• Quantum Software Ecosystem Design
• Realizing Quantum Algorithms on Real Quantum Computing Devices
• Quantum Approximation of Normalized Schatten Norms and Applications to Learning
• Reversible Logic Circuit Complexity Analysis via Functional Decomposition
• Quantum advantage in temporally flat measurement-based quantum computation
• Asymptotically optimal synthesis of reversible circuits
• Space-time tradeoff in networked virtual distillation
• Quantum Theory from Principles, Quantum Software from Diagrams
• High-Precision Multi-Qubit Clifford+T Synthesis by Unitary Diagonalization
• qSAT: Design of an Efficient Quantum Satisfiability Solver for Hardware Equivalence Checking
• Design Automation and Design Space Exploration for Quantum Computers
• Quantum Key Recovery Attack on SIMON Block Cipher
• OrQstrator: An AI-Powered Framework for Advanced Quantum Circuit Optimization
• A T-depth two Toffoli gate for 2D square lattice architectures
• Measurement-Driven Adaptive Low-Overhead Implementation of Multi-Controlled Toffoli Gates
• Programming quantum computers using 3-D puzzles, coffee cups, and doughnuts
• Automatic synthesis of quantum circuits for point addition on ordinary binary elliptic curves
• Hybrid Reward-Driven Reinforcement Learning for Efficient Quantum Circuit Synthesis
• Quantum phase estimation with optimal confidence interval using three control qubits
• CNOT Minimal Circuit Synthesis: A Reinforcement Learning Approach
• ROS: Resource-constrained Oracle Synthesis for Quantum Computers
• Mapping of Topological Quantum Circuits to Physical Hardware
• Dual Toffoli and Peres-reversible gates
• Qrisp Implementation and Resource Analysis of a T-Count-Optimised Non-Restoring Quantum Square-Root Circuit
• Quantum Circuits in Additive Hilbert Space
• Optimized Aaronson-Gottesman stabilizer circuit simulation through quantum circuit transformations
• Nontrivial multi-product commutation relation toward reducing T-count in sequential Pauli-based computation