Optimal ancilla-free Clifford+T approximation of z-rotations
arXiv:1403.2975
Abstract
We consider the problem of approximating arbitrary single-qubit z-rotations by ancilla-free Clifford+T circuits, up to given epsilon. We present a fast new probabilistic algorithm for solving this problem optimally, i.e., for finding the shortest possible circuit whatsoever for the given problem instance. The algorithm requires a factoring oracle (such as a quantum computer). Even in the absence of a factoring oracle, the algorithm is still near-optimal under a mild number-theoretic hypothesis. In this case, the algorithm finds a solution of T-count m + O(log(log(1/epsilon))), where m is the T-count of the second-to-optimal solution. In the typical case, this yields circuit approximations of T-count 3log_2(1/epsilon) + O(log(log(1/epsilon))). Our algorithm is efficient in practice, and provably efficient under the above-mentioned number-theoretic hypothesis, in the sense that its expected runtime is O(polylog(1/epsilon)).
40 pages. New in v3: added a section on worst-case behavior
Cited by in corpus (14)
- Elucidating Reaction Mechanisms on Quantum Computers
- Emerging quantum computing algorithms for quantum chemistry
- A Software Methodology for Compiling Quantum Programs
- Performing Quantum Computing Experiments in the Cloud
- Quantum error mitigation as a universal error-minimization technique: applications from NISQ to FTQC eras
- Quantum Algorithm for Spectral Measurement with Lower Gate Count
- Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
- 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
- Synthesis of Arbitrary Quantum Circuits to Topological Assembly
- Shorter quantum circuits via single-qubit gate approximation
- Resource Optimized Quantum Architectures for Surface Code Implementations of Magic-State Distillation
- Experimental pairwise entanglement estimation for an N-qubit system :A machine learning approach for programming quantum hardware
- Managing Classical Processing Requirements for Quantum Error Correction