Exact synthesis of multiqubit Clifford+T circuits

Abstract

We prove that a unitary matrix has an exact representation over the Clifford+T gate set with local ancillas if and only if its entries are in the ring Z[1/sqrt(2),i]. Moreover, we show that one ancilla always suffices. These facts were conjectured by Kliuchnikov, Maslov, and Mosca. We obtain an algorithm for synthesizing a exact Clifford+T circuit from any such n-qubit operator. We also characterize the Clifford+T operators that can be represented without ancillas.

7 pages

References in corpus (4)

• Elementary gates for quantum computation
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Quantum circuits of T-depth one
• Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates

Cited by in corpus (60)

• Quantum information processing with superconducting circuits: a review
• Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
• Efficient synthesis of universal Repeat-Until-Success circuits
• Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits
• Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• Concrete resource analysis of the quantum linear system algorithm used to compute the electromagnetic scattering cross section of a 2D target
• Efficient synthesis of probabilistic quantum circuits with fallback
• Solovay-Kitaev Decomposition Strategy for Single-Qubit Channels
• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
• No-go theorems for quantum resource purification II: new approach and channel theory
• LEAP: Scaling Numerical Optimization Based Synthesis Using an Incremental Approach
• Compiler Optimization for Quantum Computing Using Reinforcement Learning
• Lower bound for the T count via unitary stabilizer nullity
• Designing a Million-Qubit Quantum Computer Using Resource Performance Simulator
• Lattice Surgery Translation for Quantum Computation
• A polynomial time and space heuristic algorithm for T-count
• Parallelizing quantum circuit synthesis
• QFAST: Quantum Synthesis Using a Hierarchical Continuous Circuit Space
• Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits
• MQT Predictor: Automatic Device Selection with Device-Specific Circuit Compilation for Quantum Computing
• Remarks on Matsumoto and Amano's normal form for single-qubit Clifford+T operators
• Magic State Distillation and Gate Compilation in Quantum Algorithms for Quantum Chemistry
• Heuristics for Quantum Compiling with a Continuous Gate Set
• A Finite Presentation of CNOT-Dihedral Operators
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits
• Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries
• Completeness of the ZX-Calculus
• Synthesis of unitaries with Clifford+T circuits
• The Classification of Clifford Gates over Qubits
• QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis
• The phase/state duality in reversible circuit design
• Universal quantum computation and quantum error correction using discrete holonomies
• Multi-objective evolutionary algorithms for quantum circuit discovery
• FeynmanDD: Quantum Circuit Analysis with Classical Decision Diagrams
• Unitary Synthesis of Clifford+T Circuits with Reinforcement Learning
• A full dichotomy for Holant${}^c$, inspired by quantum computation
• With a Few Square Roots, Quantum Computing is as Easy as Π
• Exact Synthesis of Multiqutrit Clifford-Cyclotomic Circuits
• Speedy Contraction of ZX Diagrams with Triangles via Stabiliser Decompositions
• Building Qutrit Diagonal Gates from Phase Gadgets
• Synthesizing quantum circuits via numerical optimization
• Generators and Relations for Un(Z[1/2,i])
• Generators and Relations for 2-Qubit Clifford+T Operators
• Reducing the Compilation Time of Quantum Circuits Using Pre-Compilation on the Gate Level
• Generators and relations for the group $U_4(\mathbb{Z}[1/\sqrt{2},i])$
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Improving Figures of Merit for Quantum Circuit Compilation
• Generators and Relations for the Group On(Z[1/2])
• Resource optimization for fault-tolerant quantum computing
• Momentum switches
• The exact synthesis of 1- and 2-qubit Clifford+T circuits
• High-Precision Multi-Qubit Clifford+T Synthesis by Unitary Diagonalization
• Quantum systems simulatability through classical networks
• Constructing all qutrit controlled Clifford+T gates in Clifford+T
• Programming quantum computers using 3-D puzzles, coffee cups, and doughnuts
• Transversal AND in Quantum Codes
• CNOT Minimal Circuit Synthesis: A Reinforcement Learning Approach
• Contributions to the Theory of Clifford-Cyclotomic Circuits
• Equivalent quantum systems