Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1311.1074 · Quantum Information and Computation

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

Adam Paetznick, Krysta M. Svore

Published Nov 1, 2014• 155 citations
arXivHTMLPDF

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.

DOI
10.26421/qic14.15-16-2

Related papers

Efficient Synthesis of Universal Repeat-Until-Success Quantum Circuits

Alex Bocharov, Martin Roetteler, Krysta M. Svore

Recently it was shown that the resources required to implement unitary operations on a quantum computer can be reduced by using probabilistic quantum circuits called repeat-until-success (RUS) circuits. However, the previously best-known algorithm to synthesize a RUS circuit for a given target unitary requires exponential classical runtime. We present a probabilistically polynomial-time algorithm to synthesize a RUS circuit to approximate any given single-qubit unitary to precision ϵ over the Clifford+T basis. Surprisingly, the T count of the synthesized RUS circuit surpasses the theoretical lower bound of 3 log_{2}(1/ϵ) that holds for purely unitary single-qubit circuit decomposition. By taking advantage of measurement and an ancilla qubit, RUS circuits achieve an expected T count of 1.15 log_{2}(1/ϵ) for single-qubit z rotations. Our method leverages the fact that the set of unitaries implementable by RUS protocols has a higher density in the space of all unitaries compared to the density of purely unitary implementations.

arXiv:1404.5320•Physical Review Letters•Feb 27, 2015•177 citations

Direct U(2) approximation via repeat-until-success circuits

Vadym Kliuchnikov, Jendrik Brachter, Marcus P. da Silva

We show how to directly and efficiently approximate arbitrary one-qubit unitaries, bypassing the Euler decomposition and the magnitude approximation problem, at the cost of one ancillary qubit. Our technique also applies to approximating unitaries with multi-qubit gate sets such as Clifford and CS, or Clifford and CCZ, as well as to approximating orthogonal matrices using multi-qubit gate sets such as Real Clifford and CCZ. The key tools are repeat-until-success circuits, lattice-based exact synthesis algorithms, integer point enumeration in convex sets, and relative norm equations.

quant-pharXiv:2604.20033•Apr 23, 2026•0 citations

Efficient synthesis of probabilistic quantum circuits with fallback

Alex Bocharov, Martin Roetteler, Krysta M. Svore

Repeat-until-success (RUS) circuits can approximate a given single-qubit unitary with an expected number of $T$ gates of about $\frac{1}{3}$ of what is required by optimal, deterministic, ancilla-free decompositions over the Clifford + $T$ gate set. In this work, we introduce a more general and conceptually simpler circuit decomposition method that allows for synthesis into protocols that probabilistically implement quantum circuits over several universal gate sets including, but not restricted to, the Clifford + $T$ gate set. The protocol, which we call probabilistic quantum circuits with fallback (PQF), implements a walk on a discrete Markov chain in which the target unitary is an absorbing state and in which transitions are induced by multiqubit unitaries followed by measurements. In contrast to RUS protocols, the presented PQF protocols are guaranteed to terminate after a finite number of steps. Specifically, we apply our method to the Clifford + $T$, Clifford + $V$, and Clifford + $\ensuremath{\pi}/12$ gate sets to achieve decompositions with expected gate counts of ${log}_{b}(1/\ensuremath{\varepsilon})+O{ln[ln(1/\ensuremath{\varepsilon})]}$, where $b$ is a quantity related to the expansion property of the underlying universal gate set.

arXiv:1409.3552•Physical Review A•May 18, 2015•78 citations

Asymptotically Optimal Approximation of Single Qubit Unitaries by Clifford and T Circuits Using a Constant Number of Ancillary Qubits

Vadym Kliuchnikov, Dmitri A Maslov, Michele Mosca

Decomposing unitaries into a sequence of elementary operations is at the core of quantum computing. Information theoretic arguments show that approximating a random unitary with precision $\ensuremath{\epsilon}$ requires $\ensuremath{\Omega}\mathbf{(}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ gates. Prior to our work, the state of the art in approximating a single qubit unitary included the Solovay-Kitaev algorithm that requires $O\mathbf{(}{log}^{3+\ensuremath{\delta}}(1/\ensuremath{\epsilon})\mathbf{)}$ gates and does not use ancillae and the phase kickback approach that requires $O\mathbf{(}{log}^{2}(1/\ensuremath{\epsilon})\mathrm{log}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ gates but uses $O\mathbf{(}{log}^{2}(1/\ensuremath{\epsilon})\mathbf{)}$ ancillae. Both algorithms feature upper bounds that are far from the information theoretic lower bound. In this Letter, we report an algorithm that saturates the lower bound, and as such it guarantees asymptotic optimality. In particular, we present an algorithm for building a circuit that approximates single qubit unitaries with precision $\ensuremath{\epsilon}$ using $O\mathbf{(}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ Clifford and $T$ gates and employing up to two ancillary qubits. We connect the unitary approximation problem to the problem of constructing solutions corresponding to Lagrange's four-square theorem, and thereby develop an algorithm for computing an approximating circuit using an average of $O\mathbf{(}{log}^{2}(1/\ensuremath{\epsilon})\mathrm{log}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ operations with integers.

arXiv:1212.0822•Physical Review Letters•May 8, 2013•146 citations

Approximate synthesis of general single-qubit unitaries over the Clifford+$\sqrt{T}$ gate set

Mathias Weiden, Jae Won Kim, Justin Kalloor +2 more

For the standard Clifford+$T$ gate set, deterministic, ancilla-free synthesis now attains the minimal $T$-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The $\sqrt{T}$ gate rotates by half the angle of $T$, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+$\sqrt{T}$ algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from $\varepsilon=10^{-3}$ to $10^{-8}$, the cost of Clifford+$\sqrt{T}$ circuits scales as $2.4\log_2(1/\varepsilon)$ compared to $3.0\log_2(1/\varepsilon)$ for $T$-count-optimal Clifford+$T$ circuits. Once a one-time catalyst state is amortized, the Clifford+$\sqrt{T}$ circuits are never costlier than their Clifford+$T$ counterparts.

quant-pharXiv:2609.16659•Sep 16, 2026•0 citations

Quantum arithmetic and numerical analysis using Repeat-Until-Success circuits

Nathan Wiebe, Martin Roetteler

We develop a method for approximate synthesis of single-qubit rotations of the form e−if(φ1,...,φk)X that is based on the Repeat-Until-Success (RUS) framework for quantum circuit synthesis. We demonstrate how smooth computable functions f can be synthesized from two basic primitives. This synthesis approach constitutes a manifestly quantum form of arithmetic that differs greatly from the approaches commonly used in quantum algorithms. The key advantage of our approach is that it requires far fewer qubits than existing approaches: as a case in point, we show that using as few as 3 ancilla qubits, one can obtain RUS circuits for approximate multiplication and reciprocals. We also analyze the costs of performing multiplication and inversion on a quantum computer using conventional approaches and find that they can require too many qubits to execute on a small quantum computer, unlike our approach.

arXiv:1406.2040•Quantum Information and Computation•Jan 1, 2016•70 citations
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 ZZZ-axis rotation to within distance ϵ\epsilonϵ, where the number of TTT gates scales as 1.26log⁡2(1/ϵ)−3.531.26\log_2(1/\epsilon) - 3.531.26log2​(1/ϵ)−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.4log⁡2(1/ϵ)−3.282.4\log_2(1/\epsilon) - 3.282.4log2​(1/ϵ)−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.
Recently it was shown that the resources required to implement unitary operations on a quantum computer can be reduced by using probabilistic quantum circuits called repeat-until-success (RUS) circuits. However, the previously best-known algorithm to synthesize a RUS circuit for a given target unitary requires exponential classical runtime. We present a probabilistically polynomial-time algorithm to synthesize a RUS circuit to approximate any given single-qubit unitary to precision ϵ over the Clifford+T basis. Surprisingly, the T count of the synthesized RUS circuit surpasses the theoretical lower bound of 3 log_{2}(1/ϵ) that holds for purely unitary single-qubit circuit decomposition. By taking advantage of measurement and an ancilla qubit, RUS circuits achieve an expected T count of 1.15 log_{2}(1/ϵ) for single-qubit z rotations. Our method leverages the fact that the set of unitaries implementable by RUS protocols has a higher density in the space of all unitaries compared to the density of purely unitary implementations.
We show how to directly and efficiently approximate arbitrary one-qubit unitaries, bypassing the Euler decomposition and the magnitude approximation problem, at the cost of one ancillary qubit. Our technique also applies to approximating unitaries with multi-qubit gate sets such as Clifford and CS, or Clifford and CCZ, as well as to approximating orthogonal matrices using multi-qubit gate sets such as Real Clifford and CCZ. The key tools are repeat-until-success circuits, lattice-based exact synthesis algorithms, integer point enumeration in convex sets, and relative norm equations.
Repeat-until-success (RUS) circuits can approximate a given single-qubit unitary with an expected number of TTT gates of about 13\frac{1}{3}31​ of what is required by optimal, deterministic, ancilla-free decompositions over the Clifford + TTT gate set. In this work, we introduce a more general and conceptually simpler circuit decomposition method that allows for synthesis into protocols that probabilistically implement quantum circuits over several universal gate sets including, but not restricted to, the Clifford + TTT gate set. The protocol, which we call probabilistic quantum circuits with fallback (PQF), implements a walk on a discrete Markov chain in which the target unitary is an absorbing state and in which transitions are induced by multiqubit unitaries followed by measurements. In contrast to RUS protocols, the presented PQF protocols are guaranteed to terminate after a finite number of steps. Specifically, we apply our method to the Clifford + TTT, Clifford + VVV, and Clifford + $\ensuremath{\pi}/12$ gate sets to achieve decompositions with expected gate counts of ${log}_{b}(1/\ensuremath{\varepsilon})+O{ln[ln(1/\ensuremath{\varepsilon})]}$, where bbb is a quantity related to the expansion property of the underlying universal gate set.
Decomposing unitaries into a sequence of elementary operations is at the core of quantum computing. Information theoretic arguments show that approximating a random unitary with precision $\ensuremath{\epsilon}$ requires $\ensuremath{\Omega}\mathbf{(}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ gates. Prior to our work, the state of the art in approximating a single qubit unitary included the Solovay-Kitaev algorithm that requires $O\mathbf{(}{log}^{3+\ensuremath{\delta}}(1/\ensuremath{\epsilon})\mathbf{)}$ gates and does not use ancillae and the phase kickback approach that requires $O\mathbf{(}{log}^{2}(1/\ensuremath{\epsilon})\mathrm{log}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ gates but uses $O\mathbf{(}{log}^{2}(1/\ensuremath{\epsilon})\mathbf{)}$ ancillae. Both algorithms feature upper bounds that are far from the information theoretic lower bound. In this Letter, we report an algorithm that saturates the lower bound, and as such it guarantees asymptotic optimality. In particular, we present an algorithm for building a circuit that approximates single qubit unitaries with precision $\ensuremath{\epsilon}$ using $O\mathbf{(}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ Clifford and TTT gates and employing up to two ancillary qubits. We connect the unitary approximation problem to the problem of constructing solutions corresponding to Lagrange's four-square theorem, and thereby develop an algorithm for computing an approximating circuit using an average of $O\mathbf{(}{log}^{2}(1/\ensuremath{\epsilon})\mathrm{log}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ operations with integers.
Approximate synthesis of general single-qubit unitaries over the Clifford+T\sqrt{T}T​ gate set
For the standard Clifford+TTT gate set, deterministic, ancilla-free synthesis now attains the minimal TTT-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The T\sqrt{T}T​ gate rotates by half the angle of TTT, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+T\sqrt{T}T​ algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from ε=10−3\varepsilon=10^{-3}ε=10−3 to 10−810^{-8}10−8, the cost of Clifford+T\sqrt{T}T​ circuits scales as 2.4log⁡2(1/ε)2.4\log_2(1/\varepsilon)2.4log2​(1/ε) compared to 3.0log⁡2(1/ε)3.0\log_2(1/\varepsilon)3.0log2​(1/ε) for TTT-count-optimal Clifford+TTT circuits. Once a one-time catalyst state is amortized, the Clifford+T\sqrt{T}T​ circuits are never costlier than their Clifford+TTT counterparts.
We develop a method for approximate synthesis of single-qubit rotations of the form e−if(φ1,...,φk)X that is based on the Repeat-Until-Success (RUS) framework for quantum circuit synthesis. We demonstrate how smooth computable functions f can be synthesized from two basic primitives. This synthesis approach constitutes a manifestly quantum form of arithmetic that differs greatly from the approaches commonly used in quantum algorithms. The key advantage of our approach is that it requires far fewer qubits than existing approaches: as a case in point, we show that using as few as 3 ancilla qubits, one can obtain RUS circuits for approximate multiplication and reciprocals. We also analyze the costs of performing multiplication and inversion on a quantum computer using conventional approaches and find that they can require too many qubits to execute on a small quantum computer, unlike our approach.