Efficient Decomposition of Single-Qubit Gates into $V$ Basis Circuits

Abstract

We develop the first constructive algorithms for compiling single-qubit unitary gates into circuits over the universal $V$ basis. The $V$ basis is an alternative universal basis to the more commonly studied $\{H,T\}$ basis. We propose two classical algorithms for quantum circuit compilation: the first algorithm has expected polynomial time (in precision $\log (1/\epsilon )$) and offers a depth/precision guarantee that improves upon state-of-the-art methods for compiling into the $\{H,T\}$ basis by factors ranging from 1.86 to ${\log }_2(5)$. The second algorithm is analogous to direct search and yields circuits a factor of 3 to 4 times shorter than our first algorithm, and requires time exponential in $\log (1/\epsilon )$; however, we show that in practice the runtime is reasonable for an important range of target precisions.

13 pages

References in corpus (4)

• Novel constructions for the fault-tolerant Toffoli gate
• Improved magic states distillation for quantum universality
• Scalability of Shor's algorithm with a limited set of rotation gates
• Distilling one-qubit magic states into Toffoli states

Cited by in corpus (32)

• 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
• Topological Quantum Compiling with Reinforcement Learning
• The Complexity Geometry of a Single Qubit
• 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
• Variational quantum compiling with double Q-learning
• Arithmetic Circuits for Multilevel Qudits Based on Quantum Fourier Transform
• Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets
• Floating Point Representations in Quantum Circuit Synthesis
• T-count and T-depth of any multi-qubit unitary
• Shorter quantum circuits via single-qubit gate approximation
• Criteria for universality of quantum gates
• Parallelizing quantum circuit synthesis
• Canonical forms for single-qutrit Clifford+T operators
• Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits
• Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries
• Logic Synthesis for Fault-Tolerant Quantum Computers
• Optimal Ancilla-free Pauli+V Circuits for Axial Rotations
• How to check universality of quantum gates?
• Distillation protocols for Fourier states in quantum computing
• A framework for exact synthesis
• Multi-objective evolutionary algorithms for quantum circuit discovery
• Calculable lower bounds on the efficiency of universal sets of quantum gates
• Small Codes for Magic State Distillation
• Resource optimization for fault-tolerant quantum computing
• Matrix concentration inequalities and efficiency of random universal sets of quantum gates
• Ancilla Approximable Quantum State Transformations
• Weighted Quantum Channel Compiling through Proximal Policy Optimization
• Resource comparison of two surface code implementations of small angle Z rotations
• Compiling universal quantum circuits
• Synthesis of Single Qutrit Circuits from Clifford+R