Quantum circuits of T-depth one

Abstract

We give a Clifford+T representation of the Toffoli gate of T-depth 1, using four ancillas. More generally, we describe a class of circuits whose T-depth can be reduced to 1 by using sufficiently many ancillas. We show that the cost of adding an additional control to any controlled gate is at most 8 additional T-gates, and T-depth 2. We also show that the circuit THT does not possess a T-depth 1 representation with an arbitrary number of ancillas initialized to 0.

5 pages

References in corpus (2)

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

Cited by in corpus (85)

• Application of a resource theory for magic states to fault-tolerant quantum computing
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• Quantum attacks on Bitcoin, and how to protect against them
• Magic State Distillation: Not as Costly as You Think
• Novel constructions for the fault-tolerant Toffoli gate
• Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
• On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
• Quantum computation with realistic magic state factories
• Exact synthesis of multiqubit Clifford+T circuits
• Lower bounds on the non-Clifford resources for quantum computations
• Quantifying the magic of quantum channels
• A Threshold for Quantum Advantage in Derivative Pricing
• High-fidelity three-qubit iToffoli gate for fixed-frequency superconducting qubits
• Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules
• Conformal field theories are magical
• Topological Quantum Compiling with Reinforcement Learning
• 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
• Fault tolerant resource estimation of quantum random-access memories
• Applying quantum algorithms to constraint satisfaction problems
• On the CNOT-complexity of CNOT-PHASE circuits
• Optimized compiler for Distributed Quantum Computing
• Optimizing resource efficiencies for scalable full-stack quantum computers
• Grover on SIMON
• T-count optimization and Reed-Muller codes
• Transversal Clifford gates on folded surface codes
• On quantum circuits employing roots of the Pauli matrices
• Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states
• Floating Point Representations in Quantum Circuit Synthesis
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Learning quantum circuits of some $T$ gates
• Quantum state preparation protocol for encoding classical data into the amplitudes of a quantum information processing register's wave function
• ZX-calculus for the working quantum computer scientist
• A polynomial time and space heuristic algorithm for T-count
• Subdivided Phase Oracle for NISQ Search Algorithms
• Magic-State Functional Units: Mapping and Scheduling Multi-Level Distillation Circuits for Fault-Tolerant Quantum Architectures
• Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging
• A ZX-Calculus with Triangles for Toffoli-Hadamard, Clifford+T, and Beyond
• Derivative Pricing using Quantum Signal Processing
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits
• Logic Synthesis for Quantum Computing
• Logic Synthesis for Fault-Tolerant Quantum Computers
• Resource Optimized Quantum Architectures for Surface Code Implementations of Magic-State Distillation
• Finding solutions to the integer case constraint satisfiability problem using Grover's algorithm
• Hybrid quantum-classical circuit simplification with the ZX-calculus
• Distillation protocols for Fourier states in quantum computing
• The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
• The phase/state duality in reversible circuit design
• Solving reaction dynamics with quantum computing algorithms
• Everything You Always Wanted to Know About Quantum Circuits
• 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
• Y-Calculus: A Language for Real Matrices Derived from the ZX-Calculus
• Robust Quantum Arithmetic Operations with Intermediate Qutrits in the NISQ-era
• Delegating Quantum Computation in the Quantum Random Oracle Model
• Resource optimization for fault-tolerant quantum computing
• Resource Estimation of Quantum Multiplication Algorithms
• Lower T-count with faster algorithms
• A quantum random access memory (QRAM) using a polynomial encoding of binary strings
• Quantum-accelerated algorithms for generating random primitive polynomials over finite fields
• Ladder Operator Block-Encoding
• $T$-depth-optimized Quantum Search with Quantum Data-access Machine
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation
• Qubit Optimized Quantum Implementation of SLIM
• Space-time tradeoff in networked virtual distillation
• Weighted Quantum Channel Compiling through Proximal Policy Optimization
• Quantum Theory from Principles, Quantum Software from Diagrams
• Faster manipulation of large quantum circuits using wire label reference diagrams
• Classification and transformations of quantum circuit decompositions for permutation operations
• Quantum Key Recovery Attack on SIMON Block Cipher
• Unfolded distillation: very low-cost magic state preparation for biased-noise qubits
• Catalytic $z$-rotations in constant $T$-depth
• Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis
• Quantum Speedup of Monte Carlo Integration with respect to the Number of Dimensions and its Application to Finance
• Constructing all qutrit controlled Clifford+T gates in Clifford+T
• Proto-Quipper with Reversing and Control
• Partial Blind Quantum Computation: A Framework for Selective Circuit Protection
• Interpolation Methods for Binary and Multivalued Logical Quantum Gate Synthesis
• Transversal AND in Quantum Codes
• Measurement-Driven Adaptive Low-Overhead Implementation of Multi-Controlled Toffoli Gates
• A T-depth two Toffoli gate for 2D square lattice architectures
• QUANTIFY: A framework for resource analysis and design verification of quantum circuits
• Quantum Oracles in Constant Depth with Measurement-Based Quantum Computation