Efficient synthesis of universal Repeat-Until-Success circuits

Abstract

Recently, it was shown that Repeat-Until-Success (RUS) circuits can achieve a $2.5$ times reduction in expected $T$-count over ancilla-free techniques for single-qubit unitary decomposition. However, the previously best known algorithm to synthesize RUS circuits requires exponential classical runtime. In this paper we present an algorithm to synthesize an RUS circuit to approximate any given single-qubit unitary within precision $\epsilon$ in probabilistically polynomial classical runtime. Our synthesis approach uses the Clifford+$T$ basis, plus one ancilla qubit and measurement. We provide numerical evidence that our RUS circuits have an expected $T$-count on average $2.5$ times lower than the theoretical lower bound of $3{\log }_2(1/\epsilon )$ for ancilla-free single-qubit circuit decomposition.

15 pages, 10 figures; reformatted and minor edits; added Fig. 2 to visualize the density of z-rotations implementable via RUS protocols

References in corpus (6)

• Magic state distillation with low overhead
• 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
• Ancilla Driven Quantum Computation with arbitrary entangling strength

Cited by in corpus (5)

• Efficient synthesis of probabilistic quantum circuits with fallback
• Reducing the quantum computing overhead with complex gate distillation
• Synthesis of Arbitrary Quantum Circuits to Topological Assembly: Systematic, Online and Compact
• A framework for exact synthesis
• Resource comparison of two surface code implementations of small angle Z rotations