Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits
arXiv:1212.0822 · doi:10.1103/PhysRevLett.110.190502
Abstract
We present an algorithm for building a circuit that approximates single qubit unitaries with precision ε using O(log(1/ε)) Clifford and T gates and employing up to two ancillary qubits. The algorithm for computing our approximating circuit requires an average of O(log^2(1/ε)log log(1/ε)) operations. We prove that the number of gates in our circuit saturates the lower bound on the number of gates required in the scenario when a constant number of ancillae are supplied, and as such, our circuits are asymptotically optimal. This results in significant improvement over the current state of the art for finding an approximation of a unitary, including the Solovay-Kitaev algorithm that requires O(log^{3+δ}(1/ε)) gates and does not use ancillae and the phase kickback approach that requires O(log^2(1/ε)log log(1/ε)) gates, but uses O(log^2(1/ε)) ancillae.
References in corpus (4)
Cited by in corpus (72)
- Quantum Chemistry in the Age of Quantum Computing
- Quantum Error Mitigation
- A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
- Quantum-assisted quantum compiling
- Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer
- Quantum algorithm for simulating real time evolution of lattice Hamiltonians
- Quantum Algorithm for Spectral Measurement with Lower Gate Count
- Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
- Conformal field theories are magical
- Topological Quantum Compiling with Reinforcement Learning
- A unified framework for magic state distillation and multi-qubit gate-synthesis with reduced resource cost
- A randomized quantum algorithm for statistical phase estimation
- Requirements for fault-tolerant factoring on an atom-optics quantum computer
- Early fault-tolerant simulations of the Hubbard model
- Trading T gates for dirty qubits in state preparation and unitary synthesis
- Concrete resource analysis of the quantum linear system algorithm used to compute the electromagnetic scattering cross section of a 2D target
- Efficient Decomposition of Single-Qubit Gates into Basis Circuits
- Practical approximation of single-qubit unitaries by single-qubit quantum Clifford and T circuits
- Solovay-Kitaev Decomposition Strategy for Single-Qubit Channels
- Shorter gate sequences for quantum computing by mixing unitaries
- Unifying gate-synthesis and magic state distillation
- T-count optimization and Reed-Muller codes
- No-go theorems for quantum resource purification II: new approach and channel theory
- Variational quantum compiling with double Q-learning
- Reducing the quantum computing overhead with complex gate distillation
- Normal form for single-qutrit Clifford+T operators and synthesis of single-qutrit gates
- Floating Point Representations in Quantum Circuit Synthesis
- An efficient magic state approach to small angle rotations
- Super-Golden-Gates for PU(2)
- T-count and T-depth of any multi-qubit unitary
- Designing a Million-Qubit Quantum Computer Using Resource Performance Simulator
- Simulation of single-qubit open quantum systems
- Shorter quantum circuits via single-qubit gate approximation
- A polynomial time and space heuristic algorithm for T-count
- Quantum circuit design for accurate simulation of qudit channels
- Exact gate decompositions for photonic quantum computing
- Canonical forms for single-qutrit Clifford+T operators
- Parallelizing quantum circuit synthesis
- Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
- Nonlocal and controlled unitary operators of Schmidt rank three
- Exact and approximate continuous-variable gate decompositions
- Logical Clifford Synthesis for Stabilizer Codes
- 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
- A comparative study of universal quantum computing models: towards a physical unification
- Synthesis of unitaries with Clifford+T circuits
- Quantum compiling with diffusive sets of gates
- Theory of quasi-exact fault-tolerant quantum computing and valence-bond-solid codes
- Quantum Error Correction Implementation after Multiple Gates
- Quantum Error Correction During 50 Gates
- Fundamental limitations for measurements in quantum many-body systems
- Efficient Clifford+T approximation of single-qubit operators
- A framework for exact synthesis
- Cost-optimal single-qubit gate synthesis in the Clifford hierarchy
- Experimental pairwise entanglement estimation for an N-qubit system :A machine learning approach for programming quantum hardware
- Methods for Classically Simulating Noisy Networked Quantum Architectures
- Probabilistic unitary synthesis with optimal accuracy
- Single-qubit rotation algorithm with logarithmic Toffoli count and gate depth
- Lower T-count with faster algorithms
- Pseudo-Random Circuits from Clifford Plus T-Gates
- Resource optimization for fault-tolerant quantum computing
- Weighted Quantum Channel Compiling through Proximal Policy Optimization
- Classical Coding Approaches to Quantum Applications
- Compiling universal quantum circuits
- Composability of global phase invariant distance and its application to approximation error management
- Catalytic -rotations in constant -depth
- A Novel Single-Layer Quantum Neural Network for Approximate SRBB-Based Unitary Synthesis
- CNOT Minimal Circuit Synthesis: A Reinforcement Learning Approach
- Classical Control of Large-Scale Quantum Computers
- Symmetry boosts quantum computer performance
- Programming quantum computers using 3-D puzzles, coffee cups, and doughnuts
- Approximate quantum gates compiling with self-navigation algorithm