Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates

Abstract

In this paper, we show the equivalence of the set of unitaries computable by the circuits over the Clifford and T library and the set of unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$, in the single-qubit case. We report an efficient synthesis algorithm, with an exact optimality guarantee on the number of Hadamard and T gates used. We conjecture that the equivalence of the sets of unitaries implementable by circuits over the Clifford and T library and unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$ holds in the $n$-qubit case.

23 pages, 3 figures, added the proof of T-optimality of the circuits synthesized by Algorithm 1

References in corpus (6)

• Elementary gates for quantum computation
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Tackling Systematic Errors in Quantum Logic Gates with Composite Rotations
• A Depth-Optimal Canonical Form for Single-qubit Quantum Circuits
• Semidefinite programs for completely bounded norms
• Towards Large-Scale Quantum Computation

Cited by in corpus (17)

• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Quantum circuits of T-depth one
• Automated optimization of large quantum circuits with continuous parameters
• Witnessing eigenstates for quantum simulation of Hamiltonian spectra
• Emerging quantum computing algorithms for quantum chemistry
• Exact synthesis of multiqubit Clifford+T circuits
• Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits
• Concrete resource analysis of the quantum linear system algorithm used to compute the electromagnetic scattering cross section of a 2D target
• Arithmetic Circuits for Multilevel Qudits Based on Quantum Fourier Transform
• A Finite Presentation of CNOT-Dihedral Operators
• Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries
• Resource Optimized Quantum Architectures for Surface Code Implementations of Magic-State Distillation
• A framework for exact synthesis
• QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis
• Quantum Circuit Design of Integer Division Optimizing Ancillary Qubits and T-Count
• Generators and relations for the group $U_4(\mathbb{Z}[1/\sqrt{2},i])$
• The exact synthesis of 1- and 2-qubit Clifford+T circuits