Efficient Discrete Approximations of Quantum Gates

Abstract

Quantum compiling addresses the problem of approximating an arbitrary quantum gate with a string of gates drawn from a particular finite set. It has been shown that this is possible for almost all choices of base sets and furthermore that the number of gates required for precision epsilon is only polynomial in log 1/epsilon. Here we prove that using certain sets of base gates quantum compiling requires a string length that is linear in log 1/epsilon, a result which matches the lower bound from counting volume up to constant factor.

7 pages, no figures, v3 revised to correct major error in previous versions

Cited by in corpus (52)

• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Quantum algorithms for algebraic problems
• Emerging quantum computing algorithms for quantum chemistry
• Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits
• When does reinforcement learning stand out in quantum control? A comparative study on state preparation
• Introduction to topological quantum computation with non-Abelian anyons
• Asymptotically Optimal Topological Quantum Compiling
• Random bosonic states for robust quantum metrology
• Limitations on information theoretically secure quantum homomorphic encryption
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Efficient Decomposition of Single-Qubit Gates into $V$ Basis Circuits
• Minimum construction of two-qubit quantum operations
• Concentration for random product formulas
• Quantum Singular Value Decomposer
• Scaling of variational quantum circuit depth for condensed matter systems
• A State Distillation Protocol to Implement Arbitrary Single-qubit Rotations
• No-go theorems for quantum resource purification II: new approach and channel theory
• Quantum Branching Programs and Space-Bounded Nonuniform Quantum Complexity
• Application-Motivated, Holistic Benchmarking of a Full Quantum Computing Stack
• Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets
• Floating Point Representations in Quantum Circuit Synthesis
• Energy-constrained discrimination of unitaries, quantum speed limits and a Gaussian Solovay-Kitaev theorem
• Universality of single qudit gates
• Shorter quantum circuits via single-qubit gate approximation
• Universal extensions of restricted classes of quantum operations
• A single $T$-gate makes distribution learning hard
• Optimising the Solovay-Kitaev algorithm
• Criteria for universality of quantum gates
• A Family of Quantum Codes with Exotic Transversal Gates
• Equivalence Checking of Sequential Quantum Circuits
• Stability of the Trotter-Suzuki decomposition
• Quantum geometry and quantum algorithms
• Optimal Ancilla-free Pauli+V Circuits for Axial Rotations
• Quantum compiling with diffusive sets of gates
• Sample-efficient verification of continuously-parameterized quantum gates for small quantum processors
• How to check universality of quantum gates?
• Unitary Synthesis of Clifford+T Circuits with Reinforcement Learning
• Calculable lower bounds on the efficiency of universal sets of quantum gates
• Saturation and recurrence of quantum complexity in random local quantum dynamics
• Hay from the haystack: explicit examples of exponential quantum circuit complexity
• Space Complexity of Streaming Algorithms on Universal Quantum Computers
• Single-qubit rotation algorithm with logarithmic Toffoli count and gate depth
• Probabilistic unitary synthesis with optimal accuracy
• Matrix concentration inequalities and efficiency of random universal sets of quantum gates
• Weighted Quantum Channel Compiling through Proximal Policy Optimization
• Quantum Compiling by Deep Reinforcement Learning
• How smooth is quantum complexity?
• Policy Gradient Approach to Compilation of Variational Quantum Circuits
• Fundamental solutions of heat equation on unitary groups establish an improved relation between $\epsilon$-nets and approximate unitary $t$-designs
• Error Crafting in Mixed Quantum Gate Synthesis
• Synthesis of Single Qutrit Circuits from Clifford+R
• Extremal jumps of circuit complexity of unitary evolutions generated by random Hamiltonians