Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries

Abstract

We present a decomposition technique that uses non-deterministic circuits to approximate an arbitrary single-qubit unitary to within distance $\epsilon$ and requires significantly fewer non-Clifford gates than existing techniques. We develop "Repeat-Until-Success" (RUS) circuits and characterize unitaries that can be exactly represented as an RUS circuit. Our RUS circuits operate by conditioning on a given measurement outcome and using only a small number of non-Clifford gates and ancilla qubits. We construct an algorithm based on RUS circuits that approximates an arbitrary single-qubit $Z$-axis rotation to within distance $\epsilon$, where the number of $T$ gates scales as $1.26{\log }_2(1/\epsilon )-3.53$, an improvement of roughly three-fold over state-of-the-art techniques. We then extend our algorithm and show that a scaling of $2.4{\log }_2(1/\epsilon )-3.28$ can be achieved for arbitrary unitaries and a small range of $\epsilon$, which is roughly twice as good as optimal deterministic decomposition methods.

26 pages, 12 figures. (v2): Slightly improved T scaling, improved achievable approximation accuracy with gearbox circuits, fixed several clerical errors

References in corpus (10)

• Topological fault-tolerance in cluster state quantum computation
• Novel constructions for the fault-tolerant Toffoli gate
• Exact synthesis of multiqubit Clifford+T circuits
• Simulating chemistry efficiently on fault-tolerant quantum computers
• A Depth-Optimal Canonical Form for Single-qubit Quantum Circuits
• Scalability of Shor's algorithm with a limited set of rotation gates
• Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates
• Logic Synthesis for Fault-Tolerant Quantum Computers
• An algorithm for the T-count
• Ancilla Driven Quantum Computation with arbitrary entangling strength

Cited by in corpus (11)

• An Experimental Microarchitecture for a Superconducting Quantum Processor
• Efficient synthesis of probabilistic quantum circuits with fallback
• LEAP: Scaling Numerical Optimization Based Synthesis Using an Incremental Approach
• The Efficient Preparation of Normal Distributions in Quantum Registers
• Lanczos recursion on a quantum computer for the Green's function and ground state
• Repeat-Until-Success circuits with fixed-point oblivious amplitude amplification
• On The Power Of Coherently Controlled Quantum Adiabatic Evolutions
• Direct Application of the Phase Estimation Algorithm to Find the Eigenvalues of the Hamiltonians
• A framework for exact synthesis
• Resource comparison of two surface code implementations of small angle Z rotations
• Minimal ancilla mediated quantum computation